嚴格簡單的多邊形測試（允許有孔）？

Question

我正在尋找一種算法來測試多邊形是否「嚴格」簡單。通常該測試涉及檢查任何多邊形段之間的交集。但在這裏，因爲我想檢查並不總是處於邊緣交叉點的情況，所以我不太確定要查找什麼。

在上圖中，B C和D不是簡單的多邊形，但只有D會使相交測試失敗。我的術語（絕對簡單）也許稍微不合適，但我認爲這幅圖解釋了我的意思。

Answer 1

說兩線相交做，如果他們至少有一個共同點。

取一條邊並計算與任何其他邊的交點。如果它有

• 2個十字路口，那麼它有一個邊緣和一個邊緣的權利，一切都很好。如果超過2個交點，則它在終點（情況B）開始有兩個以上的邊，中間的一個邊的終點（情形C）或與另一行（情形D）的交點。
在我看來

所以，你的擔心是毫無根據的：

但在這裏，因爲我要檢查不總是落在下邊緣的邊緣相交的情況下[...]

這種方法也適用於此。

Answer 2

這三類無效多邊形必須單獨檢查。

案例B：

檢查，以確保沒有在您的多邊形沒有重複的頂點。

案例C：

檢查以確保沒有頂點落在任何邊緣上。假設你使用浮點數，這可能會變得棘手，因爲浮點數必須估計爲完全相等。這可以通過說他們不能在對方的某個EPS之內來繞過，但是這可能使其他一些幾乎無效的多邊形失效。我自己親自使用EPS，除非我真的需要最高精度（在這一點上，我不知道我會做什麼）。

案例d：

正如你所說，這可以通過檢查任何邊相交找到。

案例E： 兩條邊重疊（相交於無限多個點）並且它們的頂點不重合。

我不確定這是否需要一個單獨的案例，但這種情況可能不會被檢查案例D（我認爲你最終除以零）所捕獲。因此，您還需要檢查兩條邊是否完全對應於同一條線。

我想不出任何其他情況下暫時