Subject 2.03: How do I find if a point lies within a polygon?
The definitive reference is "Point in Polygon Strategies" by
Eric Haines [Gems IV] pp. 24-46. Now also at
http://www.erichaines.com/ptinpoly.
The code in the Sedgewick book Algorithms (2nd Edition, p.354) fails
under certain circumstances. See
http://condor.informatik.Uni-Oldenburg. ... index.html
for a discussion.
The essence of the ray-crossing method is as follows.
Think of standing inside a field with a fence representing the polygon.
Then walk north. If you have to jump the fence you know you are now
outside the poly. If you have to cross again you know you are now
inside again; i.e., if you were inside the field to start with, the total
number of fence jumps you would make will be odd, whereas if you were
ouside the jumps will be even.
The code below is from Wm. Randolph Franklin <
wrf@ecse.rpi.edu>
(see URL below) with some minor modifications for speed. It returns
1 for strictly interior points, 0 for strictly exterior, and 0 or 1
for points on the boundary. The boundary behavior is complex but
determined; in particular, for a partition of a region into polygons,
each point is "in" exactly one polygon.
(See p.243 of [O'Rourke (C)] for a discussion of boundary behavior.)
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp
<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp))) &&
(x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp))
c = !c;
}
return c;
}
The code may be further accelerated, at some loss in clarity, by
avoiding the central computation when the inequality can be deduced,
and by replacing the division by a multiplication for those processors
with slow divides. For code that distinguishes strictly interior
points from those on the boundary, see [O'Rourke (C)] pp. 239-245.
For a method based on winding number, see Dan Sunday,
"Fast Winding Number Test for Point Inclusion in a Polygon,"
http://softsurfer.com/algorithms.htm, March 2001.
References:
Franklin's code:
http://www.ecse.rpi.edu/Homepages/wrf/r ... npoly.html
[Gems IV] pp. 24-46
[O'Rourke (C)] Sec. 7.4.
[Glassner:RayTracing]
Read more: http://www.faqs.org/faqs/graphics/algor ... z0bxFxaaJA
Visste att nån borde ha filurat på samma problem. 
