How inside test are performed using odd-parity rules or winding number methods ?

• Inside-outside test states, “How can we determine whether or not a point is inside of a polygon”.

• Following are the two methods to identify this :

  • Odd-parity methods :

    • Following is a simple idea to check whether a point is inside or outside.

      • Draw a horizontal line to the right of each point and extend it to infinity.

      • Count the number of times the line intersects with polygon edges.

      • A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.

    • If the point of intersection is also the vertex where two sides met then to handle this case we must look at the other endpoints of the two segments which meet at this vertex.

    • If these points lie on the same side of the constructed line, then the point in question counts as an even number of intersection.

    • If they lie opposite side of the constructed line, then the point is counted as a single intersection.

  • Winding number method :

    • In this method every point has a winding number, and the interior points of a two dimensional object are defined to be those that have a nonzero value for the winding number :
• Initializing the winding number to 0.
• Imagine a line drawn from any position P to a distant point beyond the coordinate extents of the object.
• Count the number of edges that cross the line in each direction.
• We add 1 to the winding number every time we intersect a polygon edge that crosses the line from right to left, and we subtract 1 every time we intersect an edge that crosses from left to right.
• If the winding number is non-zero then point P is inside otherwise P is outside the polygon.