Weiler-Atherton clipping algorithm

Weiler-Atherton clipping algorithm used in computer graphics.It allows clipping of a "subject polygon" by an arbitrarily shaped "clip polygon". It is generally applicable only in 2D.

Description

The algorithm requires polygons to be clockwise and not reentrant (self intersecting). The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes. Merging of polygons can also be performed by a variant of the algorithm.

Two lists are created from the coordinates of each polygons A and B.

The list entries are labelled as either inside or outside the other polygon. Various strategies can be used to improve the speed of this labelling, and to avoid needing to proceed further.

All the polygon intersections are then found and are inserted into both lists, linking the lists at the intersections. Care will be needed where the polygons share an edge.

If there are no intersections then one of three situations exist:
# A is inside B - return A for clipping, B for merging.
# B is inside A - return B for clipping, A for merging.
# A and B do not overlap - return None for clipping or A & B for merging.

A list of inbound intersections is then generated. Each intersection in the list is then followed clockwise around the linked lists until the start position is found. One or more concave polygons may produce more than one intersecting polygon. Convex polygons will only have one intersecting polygon.

The same algorithm can be used for merging two polygons by starting at the outbound intersections rather than the inbound ones. However this can produce counter-clockwise holes.

Some polygon combinations may be difficult to resolve, especially when holes are allowed.

Points on the edge of the polygon may be considered as both in and out until their status can be confirmed after the intersections have been found and verified, however this increases the complexity.

ee also

*Sutherland-Hodgman clipping algorithm

References

* [http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf HIDDEN SURFACE REMOVAL USING POLYGON AREA SORTING - Kevin Weiler and Peter Atherton]