View Full Version : Non-Convex Polygon Clipping

Janika

05-22-2012, 10:40 AM

I've been looking for an algorithm that clips polygon in 2D by a line. I could not find any that handles non-convex polygons with holes. Is it possible? Is it something has been done before?

Help appreciated.

aqnuep

05-22-2012, 12:06 PM

While clipping for non-convex polygons without holes might not be that difficult, I think for polygons with holes you might need to do a convex decomposition and perform the clipping as normal. At least I'm not aware of any analytic clipping mechanism that can handle polygons with holes.

Ilian Dinev

05-22-2012, 01:24 PM

Just sketch it on paper, and imagine for output/result you're filling-in an STL vector or similar variable-sized array with vertices.

A slightly suboptimal version is:

vec2 tempbuf[numInputVerts * 2];

int numtemps=0;

vec2 resultbuf[numInputVerts * 2];

int numResultVerts=0;

insert pStart into tempbuf[] // pStart is the first vertex from the input poly

For each segment [p0,p1] of the input poly:

if it intersects the plane into pZ

insert pZ into tempbuf[]

if p1 != pStart

insert p1 into tempbuf[]

foreach pT in tempbuf

if signed_distance(pT, clipPlane) >= 0.0

insert pT into resultbuf[]

// done

P.S. if there are holes in the poly, you have to represent the holes as a part of the surface by connecting a vertex from the hole to a vertex from the hull by 2 segments (with different directions, one segment being p6-p8, the other p8-p6). Care must be taken that those 2 segments don't intersect other segments from the poly (it's always possible you just have to iterate a bit if there are collisions). Attached an image showing those segments in red.

Janika

05-22-2012, 01:52 PM

Thanks all for help.

Ilian Dinev

05-22-2012, 02:09 PM

Actually my idea doesn't solve the problem when the line intersects a hole-segment :( . I think a small fix could handle it:

when a point from tempbuf[] was inserted because of an intersection, find the nearest other point, created from the intersection.

Fixed code:

struct ipoint{

vec2 pos;

bool isNew;

};

ipoint tempbuf[numInputVerts * 2];

int numtemps=0;

vec2 resultbuf[numInputVerts * 2];

int numResultVerts=0;

insert pStart into tempbuf[], with "isNew=false" // pStart is the first vertex from the input poly

For each segment [p0,p1] of the input poly:

if it intersects the plane into pZ

insert pZ into tempbuf[], with isNew=true

if p1 != pStart

insert p1 into tempbuf[], with isNew=false

for(int i=0;i<numtemps;i++){

ipoint pT = tempbuf[i];

if(signed_distance(pT.pos, clipPlane) >= 0.0){

insert pT.pos into resultbuf[]

if(pT.isNew){

int j;

float nearestDistSq = 100000000.0;

int nearestNewPt;

for(j=i+1;j<numtemps;j++){

if(tempbuf[j].isNew){

float distSq = distance_squared(pT.pos, tempbuf[j].pos);

if(nearestDistSq > distSq){

nearestDistSq = distSq;

nearestNewPt = j;

}

}

}

insert tempbuf[nearestNewPos].pos into resultbuf[]

i = nearestNewPt; // start from next one

}

}

}

tonyo_au

05-23-2012, 01:58 AM

I can across this a while ago

Clipper - an open source freeware polygon clipping library. (http://www.angusj.com/delphi/clipper.php)

Powered by vBulletin® Version 4.2.3 Copyright © 2016 vBulletin Solutions, Inc. All rights reserved.