如何检查点(x,y)是否在笛卡尔坐标系中的多边形内?
这个问题在这里已有答案:
指向Polygon aka命中测试
C#指向多边形
给定在笛卡尔坐标系中用N线方程组成的随机多边形,是否有任何标准公式用于检查点(x,y)的隶属度?
简单的解决方案是获取所有线公式,并检查点X是否在该线下方,在该线上方以及在另一条线的右侧,等等。但这可能是单调乏味的。
我应该注意,多边形可以是任何形状,具有任意数量的边,并且可以是凹的或凸的。
为方便起见,我已经添加了这些实用function:
float slope(CGPoint p1, CGPoint p2) { return (p2.y - p1.y) / (p2.x - p1.x); } CGPoint pointOnLineWithY(CGPoint p, float m, float y) { float x = (y - py)/m + px; return CGPointMake(x,y); } CGPoint pointOnLineWithX(CGPoint p, float m, float x) { float y = m*(x - px) + py; return CGPointMake(x, y); }
如果有顶点,则可以计算测试点与构成多边形的每对点之间的角度之和。 如果它是2 * pi,那么它是一个内部点。 如果它是0,那么它是一个外部点。
一些代码:
typedef struct { int h,v; } Point; int InsidePolygon(Point *polygon,int n,Point p) { int i; double angle=0; Point p1,p2; for (i=0;i pi */ double Angle2D(double x1, double y1, double x2, double y2) { double dtheta,theta1,theta2; theta1 = atan2(y1,x1); theta2 = atan2(y2,x2); dtheta = theta2 - theta1; while (dtheta > PI) dtheta -= TWOPI; while (dtheta < -PI) dtheta += TWOPI; return(dtheta); }
资料来源: http : //paulbourke.net/geometry/insidepoly/
您可以查看其他地方: http : //alienryderflex.com/polygon/
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
http://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem