如何檢測多邊形是否具有自相交？

Question

想象一下，你有一個2D多邊形（更精確的2D closed polygonal chain）。你如何檢查它是否包含自交？它可以是凸面或凹面，順時針或逆時針方向。

現在，我可以運行一個標準的O(N log N)算法來檢查是否有任何兩個段交叉。但我相信因爲我們有一些額外的結構 - 段的順序和每兩個連續段在端點相遇的事實 - 可以設計更簡單和更快的（也許是O(N)？）算法。

任何想法？

Answer 1

您是否需要檢查自交叉，或查找所有交叉點？後者比O(N log N)更難，因爲你可以有O(n^2)與n段的交點。

如果您只需要瞭解自相交是否存在或找到少量，則看看here。本文似乎聲稱你需要什麼，特別是在多邊形平面化部分。我懷疑實現那裏描述的算法會很簡單，或者對於任何合理大小的問題都值得。但是這樣的算法確實存在。免責聲明：我沒有嘗試通讀論文並理解它。