This algorithm is used for clipping concave polygons. Here V1, V2, V3, V4, V5 are the vertices of the polygon. C4, C2, C3, C4 are the vertices of the clip polygon and I1, I2, I3, I4 are the intersection points of polygon and clip polygon.

In this algorithm we take a starting vertex like I1 and traverse the polygon like I1, V3, I2. At occurrence of leaving intersection the algorithm follows the clip polygon vertex list from leaving vertex in downward direction. At occurrence of entering intersection the algorithm follows subject polygon vertex list from the entering intersection vertex. This process is repeated till we get starting vertex. This process has to be repeated for all remaining entering intersections which are not included in the previous traversing of vertex list. Since I3 was not included in first traverse, hence, we start the second traversal from I3. Therefore, first traversal gives polygon as: I1, V3, I2, I1 and second traversal gives polygon as: I3, V5, I4, I3.

## Leave a Reply