Weiler–Atherton clipping algorithm

It is used in areas like computer graphics and games development where clipping of polygons is needed.

However, it can be used in 3D through visible surface determination and with improved efficiency through Z-ordering.

The same algorithm can be used for merging two polygons by starting at the outbound intersections rather than the inbound ones.

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.