Weiler-Atherton Algorithm:-

The clipping algorithms studied require a convex polygon in context of many applications. e.g. hidden surface removal, the ability to clip to concave polygon is required. A powerful but somewhat more complex clipping algorithm developed by weiler and Atherton meets this requirement. This algorithm defines the Polygon to be clipped as a subject Polygon and the clipping region is the clip Polygon.

The algorithm describes both the subject and the clip polygon by a circular list of vertices. The boundaries of the subject polygon and the clip polygon may or may not intersect. If they intersect, then the intersections occur in pairs. One of the intersections occurs when a subject polygon edge enters the inside of the clip Polygon and one when it leaves. As shown in the figure (n),

there are four intersection vertices I1, I2 ,I3 and I4. In these intersections I1 and 13 are entering intersections, and I2 and I3 are leaving intersections. The clip polygon vertices are marked as C1, C2, C3 and C4.

In this algorithm two separate vertices lists are made one for clip polygon and one for subject polygon including intersection points. The Table 2 shows these two lists for polygons shown in figure (n).

The algorithm starts at an entering intersection (I1) and follows the subject polygon vertex list in the downward direction (i.e. I1, V3, V4, I1). At the occurrence of leaving intersection the algorithm follows the clip polygon vertex list from the leaving intersection vertex in the downward direction (i.e. I2, I1). At the occurrence of the entering intersection the algorithm follows the subject polygon vertex list from the entering intersection vertex.

This process is repeated until we get the starting vertex. This Process we have to repeat for all remaining entering intersections which are not included in the previous traversing of vertex list. In our example, entering vertex I3 was not included in the first traversing of vertex list, Therefore, we have to go for another vertex traversal from vertex I3.

The above two vertex traversal gives two clipped inside polygons. There are: - I1, V3, V4, I2, I1 and I3, V6, I4, I3