Point in polygon

From CGAFaq

The definitive reference to techniques for testing whether a point is inside a polygon is the chapter "Point in Polygon Strategies" by Eric Haines [Gems IV] pp. 24-46. Now also at

http://www.erichaines.com/ptinpoly.

Note that the code in the Sedgewick book "Algorithms" (2nd Edition, p. 354) fails under certain circumstances. See

http://condor.informatik.Uni-Oldenburg.DE/~stueker/graphic/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 (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[i]<=y) && (y<yp[j])) ||
         ((yp[j]<=y) && (y<yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      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,"