Re: Point Inside Polygon - Ray Method

"Narek Saribekyan" <narek.saribekyan@xxxxxxxxx> writes in article <1145458218.876150.94550@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> dated 19 Apr 2006 07:50:18 -0700:
There are some special cases.
1. Ray r intersects a segment in one of it's vertices.
2. Ray r is collinear to one of p's segments.
3. Point q is lying on one of p's segments.

I need a good method to avoid this special cases and/or other method to
solve this problem.

There is an alternative method called "winding". It counts the number of
times the polygon goes around the point.

Define the quadrants in the usual manner, except use q for the origin.
Traverse the polygon. When you "increment" the quadrant number (mod 4, so
IV-->I is an increment), add 1/4 to the winding count. When the quadrant
number (mod 4) decreases, subtract 1/4. If the difference is 2 quadrants,
you need to figure out which side of the point the line went.

If the final winding count is 0, the point is outside. If it's 1, the
polygon went counterclockwise around the point.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
.

Relevant Pages

  • Re: Point Inside Polygon - Ray Method
    ... Define the quadrants in the usual manner, except use q for the origin. ... Traverse the polygon. ... But for computing the winding number of a polygon around a curve, ... law gives a formula for the angle AOB, ...
    (sci.math)
  • Re: Companion question to polygon winding rule
    ... Bint wrote: ... > do with the outline of a complex polygon. ... > If I fill a polygon that intersects itself so that the holes are ... record the winding count on each side of it); ...
    (comp.graphics.algorithms)
  • Re: Point Inside Polygon - Ray Method
    ... polygon went counterclockwise around the point. ... winding numbers may exceed 1 if the polygon isn't simple. ... If the boundary of a plane region is a simple closed curve, then one ray ...
    (sci.math)
  • Re: Clipping does not work properly with ATI specific card.
    ... behavior (backface, winding etc). ... If polygon mode is GL_LINE, ... Clipping is performed before the polygon mode takes place, ...
    (comp.graphics.api.opengl)
  • Re: Point Inside Polygon - Ray Method
    ... polygon went counterclockwise around the point. ... winding numbers may exceed 1 if the polygon isn't simple. ... Perhaps strict convexity would be a sufficient condition for three ...
    (sci.math)