WEILER-ATHERTON POLYGON CLIPPING

Weiler Atherton Polygon Clipping Algorithm is an algorithm used for clipping polygons.
But unlike Sutherland-Hodgeman polygon clipping algorithm , this algorithm is able to clip concave polygons without leaving any residue behind.

The clipping region is called as clip polygon and the polygon to be clipped is referred to as subject polygon.



Algorithm:

 1. First make a list of all intersection points namely i1, i2, i3, ...
 2. Classify those intersection points as entering or exiting.
 3. Now, make two lists, one for the clip polygon, and the other 
    for the subject polygon.
 4. Fill both the lists up in such a way that the intersection points 
    lie between the correct vertices of each of the polygon. That is 
    the clip polygon list is filled up with all the vertices of 
    the clip polygon along with the intersecting points lying 
    between the corresponding vertices.
 5. Now, start at the 'subject' polygon's list.
 6. Choose the first intersection point which has been labelled as 
    an entering point. Follow the points in the list (looping back to 
    the top of the list, in case the list ends) and keep on pushing 
    them into a vector or something similar of the sorts. Keep on following
    the list until an exiting intersection point is found.
 7. Now switch the list to the 'clip polygon' list, and find
    the exiting intersection point  that was previously encountered. Now keep
    on following the points in this list (similar to how we followed the
    previous list) until the entering intersection point is found (the 
    one that was found in the previous 'subject polygon's list).
 8. This vector now formed by pushing all the encountered points in the 
    two lists, is now the clipped polygon (one of the many clipped 
    polygons if any of the clipping polygons is concave).
 9. Repeat this clipping procedure (i.e. from step 5) until all the 
    entering intersection points have been visited once.

Limitations:
This polygon clipping algorithm does not work for self --intersecting polygons, although some methods have been proposed to be able to solve this issue also, and have successfully worked