PDA

View Full Version : Non-Convex Polygon Clipping

Janika
05-22-2012, 09: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, 11:06 AM
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, 12: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, 12:52 PM
Thanks all for help.

Ilian Dinev
05-22-2012, 01: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, 12:58 AM
I can across this a while ago

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