c++ - 多边形内的点(不包括边界)

我目前正在找到具有12个顶点的特定形状内的坐标。

          (3,7)  (5,7)
            #######
            #     #
            #  X  #
       (3,5)#     #(5,5)
 (1,5)#######  X  #######(7,5)
      #                 #
      #  X  X  X  X  X  #
      #                 #
 (1,3)#######  X  #######(7,3)
       (3,3)#     #(5,3)
            #  X  #
            #     #
            #######
          (3,1)  (5,1)

我想找出形状内部的坐标(标记为“X”)，但不包括构成该形状的坐标。

我已经尝试了W. Randolph Franklin(http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html)进行的pnpoly，但是它也认为构成该形状的坐标为“该形状内部”。

请注意，以上形状仅是示例。坐标可以在任何地方。

如何修改代码，使其不允许包含形状的边界？

int pnpoly(int vertx[], int verty[], int testx, int testy) {
    int nvert = 12;
    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;
}

最佳答案

通过要排除的边框缩小形状，然后使用现有算法。

顺便说一句:不要使用int vertx[]，这是一个危险的谎言。等效的显而易见的代码是int* vertx，这很明显它缺少const。

关于c++ - 多边形内的点(不包括边界)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16422101/