Non-Convex Polygon Clipping

[Janika]

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]

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]

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]

Thanks all for help.

[Ilian Dinev]

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]

I can across this a while ago

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