Re: Point Inside Polygon - Ray Method

In article <4447F62D.A6CF7A29@xxxxxxxx>,
James Waldby <j-waldby@xxxxxxxx> wrote:

Larry Hammick wrote:

Keith A. Lewis wrote:

There is an alternative method called "winding". It counts the number of
times the polygon goes around the point.
...
If the final winding count is 0, the point is outside. If it's 1, the
polygon went counterclockwise around the point.

Note, winding numbers may exceed 1 if the polygon isn't simple.

Three rays are enough; any three distinct ones will do.
Related, but fancier, is this suped-up version of Sperner's lemma:
http://planetmath.org/encyclopedia/SpernersLemma.html

Perhaps strict convexity would be a sufficient condition for three
rays to be enough; it seems to me it ought to be, but the link below
says point inclusion can be tested in O(log n) time for convex polygons.

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
compares crossing-number and winding-number point-is-in-polygon
algorithms, and says that at the moment winding number calculations
can be done slightly faster (although of same asymptotic efficiency).

-jiw

If the boundary of a plane region is a simple closed curve, then one ray
from any point not on the boundary is enough to determine whether that
point is inside or outside the region. The point is inside or outside
according to whether the parity of the number of intersections of the
ray with the boundary is odd or even (with points of multiple contact of
the ray with the boundary counted with their multiplicities, though a
slight dispacement of the ray will usually eliminate all such multiple
points).
.

Relevant Pages

  • Re: Polygon filling? Winding rule?
    ... The idea is to count the number of edges a ray crosses. ... (as the polygon is drawn). ... the edge crosses the ray right-to-left. ... OUTPUT: Returns winding value. ...
    (comp.graphics.algorithms)
  • Re: Polygon filling? Winding rule?
    ... The idea is to count the number of edges a ray crosses. ... (as the polygon is drawn). ... the edge crosses the ray right-to-left. ... OUTPUT: Returns winding value. ...
    (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. ... Perhaps strict convexity would be a sufficient condition for three ...
    (sci.math)
  • Re: Determining if a point on a 2D polygon is hidden
    ... > and the ray before the ray reaches your point. ... This is an Oalgorithm, which is reasonable for a small number ... of polygon vertices, ... The topic of "visibility graphs" is covered in Joseph O'Rourke's book ...
    (comp.graphics.algorithms)
  • Re: Determining if a point on a 2D polygon is hidden
    ... is to shot a ray from the external point to the other one and see whether there is an intersection between the polygon and the ray before the ray reaches your point. ... This is an Oalgorithm, which is reasonable for a small number ... An output-sensitive algorithm for computing visibility graphs, ...
    (comp.graphics.algorithms)