如何检查点（x，y）是否在笛卡尔坐标系中的多边形内？

小编典典

如何检查点（x，y）是否在笛卡尔坐标系中的多边形内？

algorithm

给定在笛卡尔坐标系中用N个线方程式表示的随机多边形，是否存在用于检查点（x，y）的隶属关系的标准公式？

一种简单的解决方案是获取所有线的公式，并检查X点是否在该线以下，该线上方以及另一条线的右侧，依此类推。但这可能很乏味。

我应该注意，多边形可以是具有任意多个边的任何形状，并且可以凹入或凸出。

为了方便起见，我已经添加了以下实用程序功能：

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 - p.y)/m + p.x;
    return CGPointMake(x,y);
}

CGPoint pointOnLineWithX(CGPoint p, float m, float x)
{
    float y = m*(x - p.x) + p.y;
    return CGPointMake(x, y);
}

阅读 225

2020-07-28

共1个答案

小编典典

如果有顶点，则可以计算测试点与构成多边形的每对点之间形成的角度之和。如果它是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<n;i++) {
      p1.h = polygon[i].h - p.h;
      p1.v = polygon[i].v - p.v;
      p2.h = polygon[(i+1)%n].h - p.h;
      p2.v = polygon[(i+1)%n].v - p.v;
      angle += Angle2D(p1.h,p1.v,p2.h,p2.v);
   }

   if (ABS(angle) < PI)
      return(FALSE);
   else
      return(TRUE);
}

/*
   Return the angle between two vectors on a plane
   The angle is from vector 1 to vector 2, positive anticlockwise
   The result is between -pi -> 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/多边形中点：_Jordan_Curve_Theorem

2020-07-28