Weiler–Atherton clipping algorithm
The Weiler–Atherton is a polygon clipping algorithm. It is used in the areas like computer graphics, games development and others where clipping of polygon 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]
Prelude
Before applying to any polygon, the algorithm requires several preconditions to be fulfilled.
- Candidate polygons need to be oriented clockwise.
- Candidate polygons should not be self intersecting (i.e. re-entrant).
- The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes. Then, merging of polygons can be performed by a variant of the algorithm.
The Algorithm
Suppose, A is the clipping polygon/region/area, and, B is the candidate polygon/subject polygon/polygon to be clipped.
First, two lists are created where one list contains the vertices of the clipping polygon A and the another list contains the vertices of the subject polygon B.
The list entries are labelled as either inside or outside the other polygon.
All the polygon intersections are then found and are inserted into both lists, linking the lists at the intersections.
Then a list of inbound intersections is generated.
Then each intersection in the list is followed clockwise around the linked lists until the start position is found.
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.
Conclusion
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.
See also
References
- ^ Foley, James, Andries van Dam, Steven Feiner, and John Hughes. "Computer Graphics: Principle and Practice". Addison-Wesley Publishing Company. Reading, Massachusetts: 1987. pages 689-693
- Weiler, Kevin and Atherton, Peter. "Hidden Surface Removal using Polygon Area Sorting", Computer Graphics, 11(2):214-222, 1977.
 | This computer graphics–related article is a stub. You can help Wikipedia by expanding it. |