Non-Convex Polygon Clipping

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.

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.

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.

Thanks all for help.

Actually my idea doesn’t solve the problem when the line intersects a hole-segment :frowning: . 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
        }
    }
}

I can across this a while ago

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