查找相鄰多邊形的輪廓

我正在尋找一種方法來查找兩個相鄰多邊形的輪廓。查找相鄰多邊形的輪廓

多邊形由按多邊形中出現次序排列的點列表定義。在我的用例中，沒有重疊的多邊形，多邊形之間沒有間隙，也沒有帶有「孔」的多邊形。

我想計算沒有任何「洞」的兩個多邊形的輪廓。這些pictures顯示預期結果。

enter image description here

我知道有很多關於裁剪多邊形庫，但對於大多數人，因爲他們對於任何一種多邊形的工作（有孔，重疊的多邊形等）的表現不是很好。在我的用例中，該算法必須實時處理大量多邊形（> 20.000）。我怎樣才能最有效地計算輪廓？

2014-09-29 heinzwilli

嘗試...... http://stackoverflow.com/questions/83593/is-there -an-efficient-algorithm-to-generate-a-2d-concave-hull – 2014-09-29 16:05:51

將有助於1）避免重複頂點; 2）建立「這個頂點屬於這個/這些輪廓」的逆關係。從那裏，你可以找到共享一個頂點並且可以被合併的輪廓線，並且處理將減少到在邏輯上組合兩個頂點列表。 – 2014-09-29 17:27:35

對Yves Daoust：遵循您的建議，我可以確定哪些頂點屬於這兩個多邊形。但如何繼續？案例一在圖片中很容易。我只需要按照正確的順序在屬於兩個多邊形的多邊形1的兩個頂點之間插入多邊形2的頂點。情況2從圖片是我的事情更困難。如果我刪除多邊形之間的輪廓，則會留下「孔」。我怎樣才能確定哪些輪廓屬於「洞」？ – heinzwilli 2014-09-30 07:13:22

鑑於

沒有重疊的多邊形，還有多邊形之間沒有空隙，也沒有與多邊形的「洞」

以下算法應該做的伎倆。

丟棄重複的線段。
計算剩餘爲doubly connected edge list的自然組合嵌入。每個段產生兩個節點（半邊，彼此相反，段的一個端點是頭部（分別是尾部），另一個端點是尾部（分別是頭部）），並且每個半邊鏈接到逆時針順序的相同頭部的下一半邊緣。
提取面部。在組合嵌入中的一個面是最小的非空半邊集合，使得對於每個半邊e，來自e的下一個半邊的反向在該集合中。這組面是半邊的一個分區。請參閱下面的ASCII藝術圖。
```
U----V----W 
| | | 
| | | 
Z----Y----X 
```
無限的臉是{U->Z, Z->Y, Y->X, X->W, W->V, V->U}。 W->V的下一個半邊是U->V。從W->V開始的下一個半邊的倒數是V->U。其他面孔是{U->V, V->Y, Y->Z, Z->U}和{V->W, W->X, X->Y, Y->V}。

通過將帶符號的逆時針角度相加並測試符號來僅保留無限面。一個有限的臉像{U->V, V->Y, Y->Z, Z->U}具有負和

/_UVY - 180 + /_VYZ - 180 + /_YZU - 180 + /_ZUV - 180 
    = 4 * (90 - 180) = -360.

無限面具有正和

/_UZY - 180 + /_ZYX - 180 + /_YXW - 180 + /_XWV - 180 + /_WVU - 180 + /_VUZ - 180 
    = 4 * (270 - 180) + 2 * (180 - 180) = 360.

來源

2014-10-04 04:34:36

查找相鄰多邊形的輪廓

回答

相關問題