測試多邊形是簡單還是複雜

對於定義爲（x，y）點序列的多邊形，如何檢測它是否複雜？一個複雜的多邊形具有交叉點與自身，如圖所示：測試多邊形是簡單還是複雜

example complex polygon image

是否有比檢查每對這將具有O（N 2 ）的時間複雜度的更好的解決方案？

那麼，如果多邊形是由用戶使用gmaps輸入的，那麼你不可能有超過100個頂點。在這種情況下，我會先用簡單的解決方案，看看是否足夠。 – 2010-10-23 00:00:35

@Nikita，這個問題在這方面可能是誤導。用戶還可以編輯具有數千個頂點的現有多邊形。無論如何，我仍然有興趣瞭解最佳方法。 – 2010-10-23 00:03:28

有掃描方法可以比暴力方法快得多。另外，它們可以用來將一個非簡單的多邊形分解爲多個簡單的多邊形。

有關詳細信息，請參閱this article，特別是此code to test for a simple polygon。

2010-10-23 00:15:53

代碼鏈接是http://geomalgorithms.com/a09-_intersect-3.html#simple_Polygon（）markdown中的自動轉義版本不起作用。 – 2013-06-26 14:01:27

參見Bentley Ottmann Algorithm用於基於掃描的O（（N + I）logN）方法。其中N是線段的數量，I是交點的數量。

2010-10-23 04:01:58

實際上，這可以用線性時間來完成Chazelle的三角剖分算法。它要麼對多邊形進行三角化，要麼發現多邊形並不簡單。

2015-01-17 09:28:12

除了由於其實施的複雜性而導致Chazelle的實際實現的寶貴數量很少。 – 2016-02-17 16:42:18

回答