多边形内的点（不包括边界）

我目前在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.兰多夫富兰克林的pnpoly（http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html），但它也考虑到构成“形状内部”形状的坐标。

请注意，上面的形状只是一个例子。坐标可以在任何地方。

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

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

来源

2013-05-07 Todd

如果这实际上是您想要测试的形状，那么与两个矩形进行交点可能更容易。 – 2013-05-07 14:59:24

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

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

来源

2013-05-07 15:47:20

只有所有的边都是轴对齐的，'收缩'才会起作用，但是海报已经声明“坐标可以在任何地方”。 – 2013-05-07 22:00:22

由于您有测试点是否位于给定多边形内的代码，因此您只需要排除多边形上的那些点。 注意：如果您使用整数坐标（不是浮点数），则此测试仅可靠。

struct Point { 
    int X; 
    int Y; 
}; 

bool PointOnLineSegment(const Point pt, const Point linePt1, const Point linePt2) 
{ 
    return ((pt.X == linePt1.X) && (pt.Y == linePt1.Y)) || 
    ((pt.X == linePt2.X) && (pt.Y == linePt2.Y)) || 
    (((pt.X > linePt1.X) == (pt.X < linePt2.X)) && 
    ((pt.Y > linePt1.Y) == (pt.Y < linePt2.Y)) && 
    ((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) == 
     (linePt2.X - linePt1.X) * (pt.Y - linePt1.Y))); 
} 

bool PointOnPolygonEdge(const Point pt, Point *poly, int vertexCnt) 
{ 
    if (vertexCnt < 2) return false; 
    vertexCnt--; 
    for (int i = 0; i < vertexCnt; ++i) 
    if (PointOnLineSegment(pt, poly[i], poly[i+1])) 
     return true; 
    if (PointOnLineSegment(pt, poly[vertexCnt], poly[0])) return true; 
    return false; 
}

来源

2013-05-07 16:42:34

多边形内的点（不包括边界）

回答

相关问题