c++ - 获取任何多边形内的所有 x,y 点

Question

我试图在 C++ 中获取 任何 多边形形状内的所有 x,y

例如，我有一个具有以下坐标的矩形，

第 1 点:

X = 5
Y = 10

第 2 点:

X = 5
Y = 8

第 3 点:

X = 9
Y = 8

第 4 点:

X = 9
Y = 10

因此基于给定的 4 个点的多边形内的坐标将是

X = 6 Y = 9 
X = 7 Y = 9 
X = 8 Y = 9 

我从 http://alienryderflex.com/polygon/ 找到了这个

bool pointInPolygon() {
    int   i, j=polySides-1;
    bool  oddNodes=NO;

    for (i=0; i<polySides; i++) {
    if (polyY[i]<y && polyY[j]>=y
       ||  polyY[j]<y && polyY[i]>=y) {
         if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
             oddNodes=!oddNodes; }}
         j=i; 
    }
     return oddNodes; 
}

甚至这个http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) {
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
  if ( ((verty[i]>testy) != (verty[j]>testy)) &&
   (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
     c = !c;
  }
 return c;
}

事实上，我发现的大部分搜索结果都与代码(如上所示)类似。据我了解，如果点在多边形内并且不返回在多边形内找到的任何线，则代码(如上所示)只会返回真/假。

Answer 1

运行 flood fill在你的多边形上，并记录所有具有整数坐标的点。

这适用于一般多边形。