刪除多邊形中的孔

Question

我有一個由點陣列確定的多邊形。

這個多邊形正在交叉自己在多邊形本身上做一些洞。

我的問題是：我怎樣才能省略這個孔，只是得到多邊形的外部點？

或者什麼會是相同的，可能更容易：我應該使用哪種算法檢查點是否在多邊形內部，以檢測多邊形孔中的點作爲內點？

由於提前，

/羅傑

Answer 1

首先，找到邊緣的所有交叉點，這些交叉點添加到頂點列表，並在這些交叉點邊緣分裂。然後，從一個顯然是外部頂點（例如「最右邊的」）的頂點開始，並追蹤輪廓，將邊和頂點添加到結果集中。追蹤輪廓僅僅沿着邊緣以最小角度到最後邊緣。

Answer 2

您可能想要找到多邊形中所有點的凸包。

這樣做的一種算法是複雜度爲O（nlgn）的Graham-Scan。來自Cormen：

Let Q be the set of all points in your polygon 
Graham-Scan(Q) 

1 let p0 be the point in q with the minimum y-coordinate or the leftmost in case of tie 
2 let (p1, p2,...,pm) be the remaining points in Q, sorted by polar angle around p0 
     if more than one point shares the same polar angle, keep the farthest point 

3 let S be an empty stack 
4 PUSH(p0, S) 
5 PUSH(p1, S) 
6 PUSH(p2, S) 
7 for i = 3 to m 
8 while the angle formed by points NEXT_TO_TOP(S), TOP(S), and pi makes a non-left turn 
9  POP(S) 
10 PUSH(pi, S) 
11 return S 

S現在包含您的多邊形的所有外部點。你必須做一些極座標數學，但這很簡單。按極座標排序按照您最底部的點排列其餘切點上的所有點。我忘記了檢查右轉的代碼，但是如果你只是從格雷厄姆掃描中搜索，它就在互聯網上。希望這可以幫助！