Determining if a point lies on the interior of a polygonWritten by Paul Bourke November 1987Solution 1 (2D)The following is a simple solu ...
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 (xi,yi) where i ranges from 0 to N-1. The last vertex (xN,yN) is assumed to be the same as the first vertex (x0,y0), that is, the polygon is closed. To determine the status of a point (xp,yp) consider a horizontal ray emanating from (xp,yp) 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 (xp,yp) 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 (xp,yp). 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
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。