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]
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].