算法劃分自相交多邊形

Question

首先我知道有類似的問題已經問過，但它使用不同的結構，並在C（Divide self intersecting polygon (C Code)），我的問題是有點不同。

我有點自相交多邊形，它的邊緣，我也可以找到它使用Bentley-Ottmann算法相交的點。

我計劃通過編輯交叉點周圍的邊來構建非自相交多邊形，但問題是當您有兩條相交的邊時，您不知道四條邊中哪兩條是內部的，哪些位於多邊形。

我可以使用射線穿越算法來解決這個問題，但它太慢了。它的時間複雜度是O（n），並且每個交點至少有兩次這樣做。所以它會非常緩慢，約200k點的多邊形。

所以我問的是，有沒有更快的方法將自相交多邊形劃分爲非自相交多邊形。

我需要這個，因爲我正在做多邊形三角測量。我已經完成了掃描線三角測量算法，用於對具有孔的非自相交多邊形進行三角測量。所以我只需要將這些多邊形的數組作爲輸入。

Answer 1

作爲預處理步驟，您可以計算每個邊的邊緣的哪一邊決定了多邊形的外部。這比每個交點的O（n）時間便宜得多。然後當兩條邊相交時，您可以確定哪兩條線在外面，哪兩條在內。