Weiler-Atherton Polygon Clipping Algorithm

By | March 13, 2022

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 :

  1. Direction of polygon processing i.e. clockwise or counterclockwise.
  2. 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 :

  1. If a pair of polygon vertices having out-in orientation then the polygon boundary follow.
  2. If a pair of polygon vertices having in-out orientation then clipping window boundary followed in a clockwise direction.

Example:

Let us consider a polygon P1, P2, P3, P4, P5, P6 with edges P1P2, P2P3, P3P4, P4P5, P5P6 and P6P1.

Example of Weiler-Atherton Polygon Clipping Algorithm

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.

Example of Weiler-Atherton Polygon Clipping Algorithm

Here two separate polygon areas generated without any extra line connecting two polygons.

Output of Weiler-Atherton Polygon Clipping Algorithm

Related posts:-