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]

• Determine the intersections of the subject and clip polygons - Add each intersection to the SP and CP vertex lists. Tag each intersection vertex and establish a bidirectional link between the SP and CP lists for each intersection vertex.
• Process nonintersecting polygon borders - Establish two holding lists: one for boundaries which lie inside the CP and one for boundaries which lie outside. Ignore CP boundaries which are outside the SP. CP boundaries inside the SP form holes in the SP. Consequently. a copy of the CP boundary goes on both the inside and the outside holding list. Place the boundaries on the appropriate holding list.
• Create two intersection vertex lists - One, the entering list, contains only the intersections for the SP edge entering the inside of the CP. The other, the leaving list, contains only the intersections for the SP edge leaving the inside of the CP. The intersection type will alternate along the boundary. Thus, only one determination is required for each pair of intersections.
• Perform the actual clipping -
  Polygons inside the CP are found using the following procedure.
  • Remove an intersection vertex from the entering list. If the list is empty, the process is complete.
  • Follow the SP vertex list until an intersection is found. Copy the SP list upto this point to the inside holding list.
  • Using the link, jump to the CP vertex list.
  • Follow the CP vertex list until an intersection is found. Copy the CP vertex list upto this point to the inside holding list.
  • Jump back to the SP vertex list.
  • Repeat until the starting point is again reached. At this point, the new inside polygon has been closed.

  Polygons outside the CP are found using the same procedure, except that the initial intersection vertex is obtained from the leaving list and the CP vertex list is followed in the reverse direction. The polygon lists are copied to the outside holding list.

  A suitably detailed description of the algorithm can be found in [3] and [6].