Weiler-Atherton Polygon Clipping Algorithm
The problem encountered in clipping concave polygons in Sutherland-Hodgeman algorithm solved by Weiler-Atherton Polygon Clipping Algorithm. The basic idea in this algorithm is that instead of always proceeding around the polygon edges; as vertices processed, we may sometimes follow the window boundary.
Whether to follow polygon boundary (edges) or clipping window boundary, depends upon two factors :
- Direction of polygon processing i.e. clockwise or counterclockwise.
- Pair of polygon vertices process i.e. whether it is out-in pair or in-out pair.
For clockwise processing of polygon vertices, the following rules are used :
- If a pair of polygon vertices having out-in orientation then the polygon boundary follow.
- If a pair of polygon vertices having in-out orientation then clipping window boundary followed in a clockwise direction.
Let us consider a polygon P1, P2, P3, P4, P5, P6 with edges P1P2, P2P3, P3P4, P4P5, P5P6 and P6P1.
To apply this algorithm, we see if the edge is in-out or out-in. If the edge is out-in, then we follow side of polygon. If the edge is in-in, then we save intersecting point on window boundary.
- P1P2 is out-in edge, following side of polygon.
- P2P3 is in-in edge, we skip this and include this edge.
- P3P4 is in-out edge, saving intersecting point on window boundary i.e. P3′.
- P4P5 is out-in edge, following side of polygon.
- P5P6 is in-out edge, saving intersecting point on window boundary i.e. P5′.
- P6P1 is out-out edge, we skip this and exclude this edge.
Here two separate polygon areas generated without any extra line connecting two polygons.