多邊形內的點（不包括邊界）

我目前在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

多邊形內的點（不包括邊界）

回答

相關問題