Past exam question: 2082 Kartik (Back), Q2(b)
Open in the Padhaiko appExplain Weiler Atherton polygon clipping polygon clipping in with an example.
Solution
Overview and Advantage of Weiler-Atherton Algorithm: The Sutherland-Hodgman polygon clipping algorithm works reliably only for convex clipping windows and often creates extraneous connecting lines when clipping concave polygons. The Weiler-Atherton algorithm solves this limitation:
- It clips arbitrary concave polygons against arbitrary concave clipping windows (including windows or polygons with holes).
- When a polygon is fragmented into multiple disconnected regions by the clipping boundary, it produces separate, correctly bounded output polygon vertex lists.
Classification of Intersections: Both the subject polygon and the clipping window are represented as circularly linked lists of vertices traversed in a consistent direction (clockwise).
- Calculate all intersection points between the edges of the subject polygon and the edges of the clipping window.
- Insert each intersection point as an explicit vertex into both the subject polygon vertex list and the clipping window vertex list.
- Classify each intersection vertex as:
- Entering Intersection: An edge of the subject polygon enters the interior of the clipping window.
- Leaving (Exiting) Intersection: An edge of the subject polygon exits the interior of the clipping window to the outside.
Traversal Rules for Clipping: To extract the clipped polygon boundaries:
- Start at an unvisited entering intersection.
- Follow the subject polygon vertex list in the clockwise direction until an exiting intersection is encountered.
- At the exiting intersection, switch to the clipping window vertex list and follow its vertices in the clockwise direction until an entering intersection is reached.
- Switch back to the subject polygon list.
- Repeat steps 2–4 until returning to the starting entering intersection. Save this closed loop as one clipped polygon component.
- If there are remaining unvisited entering intersections, repeat the process from each one to extract additional disconnected polygon components.
Illustrative Example: Consider a concave U-shaped polygon clipped against a rectangular window :
- Let clipping window have clockwise vertices: .
- Let subject polygon be a horizontal bar .
- Intersections:
- Subject edge is outside. Edge enters across at (entering) and exits across at (leaving).
- Subject edge enters across at (entering) and exits across at (leaving).
- Traversal:
- Start at entering intersection .
- Follow subject polygon: (leaving intersection).
- Switch to window list at : follow clockwise window boundary down to (entering intersection).
- Switch to subject polygon at : follow subject polygon to (leaving intersection).
- Switch to window list at : follow clockwise window boundary up to (starting point).
- The resulting closed polygon vertices are , exactly representing the interior rectangular region.
The Weiler-Atherton algorithm clips arbitrary polygons by inserting intersections into both polygon and window vertex lists, classifying them as entering or exiting, and tracing paths clockwise: along the subject polygon from entering to exiting intersections, and along the window boundary from exiting to entering intersections until closed loops form.
All past exam questions for Computer Graphics and Visualization