Weiler-Atherton polygon clipping

The Weiler-Atherton algorithm clips any polygon (convex or concave) against any polygon window, and gives the correct output even when the result is several separate polygons. It works by following the boundary of the subject polygon and switching to the window boundary at the intersection points.

Terms

• Entering intersection: the subject polygon edge goes from outside to inside the window.
• Leaving intersection: the edge goes from inside to outside.

Algorithm (subject polygon vertices in clockwise order)

1. Find all intersection points of the subject polygon with the window,
   and mark each as entering or leaving. Insert them into both vertex lists.
2. Start at an unvisited entering intersection.
3. Follow the subject polygon edges (inside the window), adding each vertex
   to the output, until a leaving intersection is reached.
4. At the leaving intersection, turn and follow the window boundary
   (clockwise) until the next intersection with the subject polygon.
5. Continue from that intersection along the subject polygon (step 3).
6. When back at the start point, close the output polygon.
7. Repeat from step 2 for any entering intersection not yet processed.

Example

Window: square (0,0)-(10,10). Subject triangle with vertices in clockwise order A(5,5), C(3,14), B(14,3).

 y
14 C
   .
10 ---L1-----E1-----+  (10,10)
   |   .        .   |
   |      A       . |
 7 |                L2
   |                |
3.9|              E2--- B(14,3)
 0 +----------------+---- x
   0               10

Intersections: A→C leaves the window at L1 (3.89, 10); C→B enters at E1 (7, 10) and leaves at L2 (10, 7); B→A enters at E2 (10, 3.89).

1. Start at the entering point E1(7,10). Follow the subject edge C→B inside the window to the leaving point L2(10,7).
2. At L2, turn onto the window boundary and go clockwise (down the right edge) to the next intersection, E2(10,3.89).
3. At E2, return to the subject polygon: E2 → A(5,5) → leaving point L1(3.89,10).
4. At L1, follow the window boundary clockwise (along the top edge) to E1, the start point, and close the polygon.

Output polygon: (7,10), (10,7), (10,3.89), (5,5), (3.89,10).

Advantages: it handles concave polygons and correctly produces multiple output polygons (Sutherland-Hodgman can instead show extra connecting edges for concave polygons). Disadvantage: it is more complex to implement than Sutherland-Hodgman.