Determining if a point lies on the interior of a polygon

Written by Paul Bourke  November 1987

Solution 1 (2D)

The folloget='_blank'>wing is a simple solution to the problem often encountered in computer graphics, determining whether or not a point (x,y) lies inside or outside a 2D polygonally bounded plane. This is necessary for example in applications such as polygon filling on raster devices, hatching in drafting software, and determining the intersection of multiple polygons.

Consider a polygon made up of N vertices (x_i,y_i) where i ranges from 0 to N-1. The last vertex (x_N,y_N) is assumed to be the same as the first vertex (x₀,y₀), that is, the polygon is closed. To determine the status of a point (x_p,y_p) consider a horizontal ray emanating from (x_p,y_p) and to the right. If the number of times this ray intersects the line segments making up the polygon is even then the point is outside the polygon. Whereas if the number of intersections is odd then the point (x_p,y_p) lies inside the polygon. The following shows the ray for some sample points and should make the technique clear.

Note: for the purposes of this discussion 0 will be considered even, the test for even or odd will be based on modulus 2, that is, if the number of intersections modulus 2 is 0 then the number is even, if it is 1 then it is odd.

The only trick is what happens in the special cases when an edge or vertex of the polygon lies on the ray from (x_p,y_p). The possible situations are illustrated below.

The thick lines above are not considered as valid intersections, the thin lines do count as intersections. Ignoring the case of an edge lying along the ray or an edge ending on the ray ensures that the endpoints are only counted once.

Note that this algorithm also works for polygons with holes as illustrated below

The following C function returns INSIDE or OUTSIDE indicating the status of a point P with respect to a polygon with N points.

#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)#define INSIDE 0#define OUTSIDE 1typedef struct {  double x,y;} Point;int InsidePolygon(Point *polygon,int N,Point p){ int counter = 0; int i; double xinters; Point p1,p2; p1 = polygon[0]; for (i=1;i<=N;i++) {  p2 = polygon[i % N];  if (p.y > MIN(p1.y,p2.y)) {   if (p.y <= MAX(p1.y,p2.y)) {    if (p.x <= MAX(p1.x,p2.x)) {     if (p1.y != p2.y) {      xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;      if (p1.x == p2.x || p.x <= xinters)       counter++;     }    }   }  }  p1 = p2; } if (counter % 2 == 0)  return(OUTSIDE); else  return(INSIDE);}

The following code is by Randolph Franklin, it returns 1 for interior points and 0 for exterior points.

  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;  }

Contribution by Alexander Motrichuk: 

//SOLUTION #1 (2D) - Redesigned#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)#define INSIDE  1#define OUTSIDE  0struct Point{  Point() : x(.0), y(.0) {};  Point(double x1, double y1) : x(x1), y(y1) {};  bool operator==(const Point& _right)  {    return x == _right.x && y == _right.y;  };  double x, y;};//horizintal left cross over direction algorithm//-----------------------------------------------// bound  |  value that will be returned only if (p) lies on the bound or vertexint InsidePolygon(Point* polygon, int N, Point p, int bound){  //cross points count of x  int __count = 0;  //neighbour bound vertices  Point p1, p2;  //left vertex  p1 = polygon[0];  //check all rays  for(int i = 1; i <= N; ++i)  {    //point is an vertex    if(p == p1) return bound;    //right vertex    p2 = polygon[i % N];    //ray is outside of our interests    if(p.y < MIN(p1.y, p2.y) || p.y > MAX(p1.y, p2.y))    {      //next ray left point      p1 = p2; continue;    }    //ray is crossing over by the algorithm (common part of)    if(p.y > MIN(p1.y, p2.y) && p.y < MAX(p1.y, p2.y))    {      //x is before of ray      if(p.x <= MAX(p1.x, p2.x))      {        //overlies on a horizontal ray        if(p1.y == p2.y && p.x >= MIN(p1.x, p2.x)) return bound;        //ray is vertical        if(p1.x == p2.x)        {          //overlies on a ray          if(p1.x == p.x) return bound;          //before ray          else ++__count;        }        //cross point on the left side        else        {          //cross point of x          double xinters = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;          //overlies on a ray          if(fabs(p.x - xinters) < __DBL_EPSILON__) return bound;          //before ray          if(p.x < xinters) ++__count;        }      }    }    //special case when ray is crossing through the vertex    else    {      //p crossing over p2      if(p.y == p2.y && p.x <= p2.x)      {        //next vertex        const Point& p3 = polygon[(i+1) % N];        //p.y lies between p1.y & p3.y        if(p.y >= MIN(p1.y, p3.y) && p.y <= MAX(p1.y, p3.y))        {          ++__count;        }        else        {          __count += 2;        }      }    }    //next ray left point    p1 = p2;  }  //EVEN  if(__count % 2 == 0) return(OUTSIDE);  //ODD  else return(INSIDE);}

原标题：Determining if a point lies on the interior of a polygon

关键词：ie