從具有共線邊的多邊形中提取多邊形

Question

如何從包含共線邊的多邊形中提取簡單多邊形？ 對於以下非常簡單的情況，邊緣2-3和6-0是共線的。我想分開這個0,1,2和3,4,5,6。

我可以比較每條邊的共線性對其他邊，但這是一個緩慢的O（n^2）方法。有更快的方法嗎？

Answer 1

查找外接圓。計算邊界圓與每條邊所在的直線之間的上/右交點。這是O（n）。現在按照它的角度元組和它與邊界圓相交的角度位置對每個邊進行排序。這是O（nlogn），並將共線排列在您的排序列表中。

如果你不可能有很多平行但非共線的邊緣，那麼你可以跳過邊界圓的東西，只是按角度排序。如果有很多平行的非共線角度，那麼只是使用角度仍然「有效」，它只是不會爲您提高效率。

Answer 2

你能找到1-2和6-0的交點嗎？如果是這樣，您可以生成邊和頂點的圖形。然後，找到所有不重疊的多邊形很簡單。