在任意多邊形中，如何檢測任何一邊相互交叉的自由？

Question

我正在繪製旅行推銷員問題的多邊形，並且想要測試任何路徑的非交叉點，作爲自適應地停止基因搜索的一種手段。我試圖簡單地檢查線段或交叉點，但有時我得到一個不正確的結果，即使仍然存在一個或多個交叉點，也會終止搜索。

Answer 1

此問題基本上等同於檢測任意一組線段中的交點。

例如，bentley-ottmann algorithm可以用來解決這個問題。當然，只要找到一個路口就可以終止。

一個天真的檢查將只需要檢查每一個邊緣與所有其他邊緣（是不是在多邊形相鄰，因爲那些不能相交），但因爲你只需要找到一個路口，輸出敏感算法（如賓利奧特曼）可以加速你的支票相當多。