next up previous contents
Next: Implementation Up: Polygon Clipping Previous: Polygon Clipping

Weiler-Atherton Algorithm

The Weiler-Atherton algorithm is capable of clipping a concave polygon with interior holes to the boundaries of another concave polygon, also with interior holes. The polygon to be clipped is called the subject polygon (SP) and the clipping region is called the clip polygon (CP). The new boundaries created by clipping the SP against the CP are identical to portions of the CP. No new edges are created. Hence, the number of resulting polygons is minimized.

The algorithm describes both the SP and the CP by a circular list of vertices. The exterior boundaries of the polygons are described clockwise, and the interior boundaries or holes are described counter-clockwise. When traversing the vertex list, this convention ensures that the inside of the polygon is always to the right. The boundaries of the SP and the CP may or may not intersect. If they intersect, the intersections occur in pairs. One of the intersections occurs when the SP edge enters the inside of the CP and one when it leaves. Fundamentally, the algorithm starts at an entering intersection and follows the exterior boundary of the SP clockwise until an intersection with a CP is found. At the intersection a right turn is made, and the exterior of the CP is followed clockwise until an intersection with the SP is found. Again, at the intersection, a right turn is made, with the SP now being followed. The process is continued until the starting point is reached. Interior boundaries of the SP are followed counter-clockwise.

A more formal statement of the algorithm is [3]


next up previous contents
Next: Implementation Up: Polygon Clipping Previous: Polygon Clipping
Anirudh Modi
4/15/1998