多邊形多邊形相交的特殊情況

Question

失敗，我已經實現了Bentley-Ottmann-algorithm檢測多邊形多邊形交集。這通常效果很好：由於多邊形不是自相交的，因此兩個多邊形的線段聯合中的任何線段交點都指示兩個多邊形都相交。

但是如果我看看這個案例：

不存在段相交。但顯然這兩個多邊形相交。

如何可以檢測這種情況下不使用幼稚算法來檢查點在多邊形中的其他多邊形的每個多邊形的每個點，並因此運行在O（m * n個）。

Answer 1

提示：

的特殊情況下的處理如上邊緣上的頂點或兩個重疊的邊緣是一個不安主題作爲配置是多種多樣的，箱子可伸縮（認爲幾個共線邊緣的重疊） 。

我最好的建議是通過分配每個頂點的內部或外部狀態（WRT其他多邊形）執行相干性。然後，當與另一個多邊形相交時，交點數的奇偶性必須與端點狀態（相同狀態=>交點數）的變化相匹配。

我不是用什麼方式分配的狀態指定，這將取決於特定的算法（在實踐中狀態分配，當您去）。重要的是，當一個國家進行測試時，你可能不會再改變它。

如果出現異常（交叉點數量不匹配狀態變化的奇偶校驗），則必須通過犧牲交叉點或通過複製一個交點（或您認爲合適的任何其他規則）來修復該問題。

實施例：

在此示例的情況下，綠色的點表示考慮外部的藍色多邊形頂點，並且數字表示可接受的分配給對應的邊緣交點的數目。

下面的黑色輪廓代表工會多邊形。因此分配狀態。