获取任意多边形内的所有x，y点

Question

我正在尝试在C++中获取任何多边形形状内的所有x，y。

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

点1：

X = 5
Y = 10

点2：

X = 5
Y = 8

第三点：

X = 9
Y = 8

点4：

X = 9
Y = 10

因此，基于给定的四个点，多边形内部的坐标将是：

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

事实上，我发现大部分搜索结果都会类似于上面的代码。据我所知，上述代码只会返回一个真/假值，指示点是否在多边形内，并不会返回任何在多边形内找到的坐标。

- user2935569

---

任何形状，都包括自相交的多边形吗？ - paddy

Answer 1

在您的多边形上运行洪水填充，并记录所有整数坐标点。

这适用于一般多边形。

- John

Answer 2

如果你有一个函数 bool pointInPolygon(polygon *pol, int point_x, int point_y)，你可以这样做：

int x_min, x_max; // determines x min and max of your polygon
int y_min, y_max; // determines y min and max of your polygon
int i, j;

...

for(i = x_min; i < x_max; i++) {
  for(j = y_min; j < y_max; j++) {
     if(pointInPolygon(pol, i, j)) {
        // add the point (i, j) in an array
     }
  }
}

当你使用 2D 时，它的表现很好。

- Pierre Emmanuel Lallemant