geometry - 任意のポリゴンで、任意の辺が別の辺と交差しないことをどのように検出しますか？

Question

巡回セールスマン問題のポリゴンを描画しています。遺伝子検索を適応的に停止する手段として、パスが交差していないかどうかをテストしたいと思います。線分や交差点を確認してみましたが、交差点が1つ以上残っていても、間違った結果が出て検索が終了することがあります。

Answer 1

この問題は、基本的に、任意の線分の集合で交点を検出することと同じです。

たとえば、ベントレー オットマン アルゴリズムを使用して、この問題を解決できます。もちろん、交差点を1つ見つけたらすぐに終了できます。

単純なチェックでは、すべてのエッジと他のすべてのエッジ (交差できないため、ポリゴン内で隣接していないエッジ) をチェックするだけですが、交差点を1 つ見つけるだけでよいため、出力に依存するアルゴリズム (bentley-ottmann など) を使用すると高速化できます。あなたの小切手をかなり上げてください。