Non-Zero Winding Number Rule
Other methods exist for determining whether a point lies within a polygon. References to some of these may be found in the additional resources page. The one to be discussed here is the non-zero winding number rule. This method is easy to understand and is more versatile than odd parity, yet it is difficult to implement in raster graphics and may produce different fills for complex polygons from those of scan-line conversion.
The method of the non-zero winding number rule is to count the number of times edges wind around a point P in a counter-clockwise direction.
-
Initialize the winding number to zero.
-
Draw a line from P to the exterior of the polygon without passing through a vertex.
-
Add 1 to the winding number for every edge that crosses the line from P in one direction (clockwise or counter-clockwise) and subtract 1 from the winding number for every crossing edge in the opposite direction.
-
If the winding number is not equal to zero, the point P is within the polygon.
For example:
| << Previous Page | Next Page >> |