- In area filling and other graphics operation often required to find particular point is inside or outside the polygon.
- For finding which region is inside or which region is outside most graphics package use either odd-even rule or the nonzero winding number rule.
- It also called the odd parity rule or even odd rule.
- By conceptually drawing a line from any position to a distant point outside the coordinate extents of the object and counting the number of edges crossing by this line is odd, then is an interior point. Otherwise is the exterior point.
- To obtain accurate edge count we must sure that line selected it does not pass from any vertices.
Nonzero Winding Number Rule for Inside-Outside Tests
This Inside-Outside Tests method counts the number of times the polygon edges wind around a particular point in the counterclockwise direction. This count is called the winding number. And the interior points of a two-dimensional object are defined to those that have a nonzero value for the winding number.
We apply this rule for Inside-Outside Tests by initializing winding number with. And then draw a line for any point to distant point beyond the coordinate extents of the object.
The line we choose must not pass through vertices.
Then we move along that line we find a number of intersecting edge. And we add 1 to the winding number. If edge crosses our line from right to left. And subtract 1 from winding number if edges cross from left to right.
The final value of a winding number is nonzero then the point is interior. And if winding number is zero the point is exterior.
This shown in figure 2.21(b).
One way to determine directional edge crossing is to take the vector cross product of a vector along the line from to distant point with the edge vector for each edge that crosses the line.
If the component of the cross product𝑈 × 𝐸 for a particular edge is positive that edge crossing from right to left. And we add 1 to winding number otherwise the edge crossing from left to right and we subtract 1 from winding number.