如何高效提取新的多邊形構成的多邊形存在

Question

多邊形圖像

多邊形的所有隻是，也有他們沒有漏洞。 板多邊形（P0到P7）

紅色多邊形（R0至R6）

綠色多邊形（G0 G1 P2 G3）

黃色多邊形（Y0至Y3）

我想有新的四個多邊形標記爲1到4，多邊形1的座標是（J7 J10 R5 R4）。 當我使用多邊形裁剪算法時，我可以得到容易的結果，板差異（紅色聯盟綠色聯盟黃色）。但是當我有超過10,000個多邊形時，我需要很長時間才能獲得結果。我的多邊形是簡單的，我的結果多邊形也是簡單的，結果多邊形中也沒有漏洞。

你知道我可以用眼睛找出四個多邊形容易形成圖像，但是如何使用算法找到它們。 謝謝。

Answer 1

如果計算得到的黑色多邊形的所有頂點的頂點上沒有超過2個邊相交，則可能比更一般的工具更快。由於多邊形的數量大約爲10000，因此首先嚐試計算所有多邊形對的交點，並希望交點的數量足夠小（如1000萬或更少）。然後，對於每個交點測試，看它是否包含在另一個多邊形的內部（如果有多個多邊形共同重疊）。測試一個點是否包含在多邊形內部可以快速完成，您可以閱讀如何在線。然後，所有不包含在另一個多邊形中的交點（該筆記還包含未包含在多邊形內部的所有原始多邊形頂點），這些是您要計算的「黑色」多邊形的頂點。這些點應與二級結構一起存儲，對於每個多邊形邊，它將按照排序順序存儲沿着該邊的所有存儲交點。同樣，對於每個存儲的頂點和交點，您應該存儲在該點相交的邊，以及上一個結構中交點的位置。因此，然後選擇任何存儲在黑色多邊形中尚未使用的交點，並選擇一個定義交點的邊。然後移動到沿着邊緣的相鄰交叉點，該交點具有兩個交點之間的邊緣部分不通過多邊形的屬性。然後繼續沿着定義相鄰交點的另一條邊移動。繼續，直到你到達你開始的頂點;這定義了一個黑色多邊形。然後你可以選擇一個新的未使用的存儲交叉點並重復。由於您的多邊形沒有孔，因此會找到所有黑色多邊形。