The Weiler–Atherton is a polygon-clipping algorithm. It is used in areas like computer graphics and games development where clipping of polygons is needed. It allows clipping of a subject or candidate polygon by an arbitrarily shaped clipping polygon/area/region.
It is generally applicable only in 2D. However, it can be used in 3D through visible surface determination and with improved efficiency through Z-ordering.[1]
thumb|upright=1.2|Subdivision with the Weiler-Atherton algorithmBefore being applied to a polygon, the algorithm requires several preconditions to be fulfilled:
Given polygon A as the clipping region and polygon B as the subject polygon to be clipped, the algorithm consists of the following steps:
If there are no intersections then one of three conditions must be true:
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 very close to the edge of the other polygon may be considered as both in and out until their status can be confirmed after all the intersections have been found and verified; however, this increases the complexity.
Various strategies can be used to improve the speed of this labeling, and to avoid needing to proceed further. Care will be needed where the polygons share an edge.