ポリゴンに自己交差があるかどうかを検出する方法は？

Question

2Dポリゴン（より正確には2D closed polygonal chain）があるとします。自己交差が含まれているかどうかをどのように確認しますか？それは、凸状または凹状であり、時計回りまたは反時計回りに向けることができる。

これで、標準のO(N log N)アルゴリズムを実行して、2つのセグメントが交差するかどうかを確認できました。しかし、私たちは、セグメントの順序と各2つの連続したセグメントがエンドポイントで会うという事実により、より簡単で高速な（おそらくO(N)？）アルゴリズムを考案することができると考えています。

アイデア？

Answer 1

自己交差をチェックするか、すべてを見つける必要はありますか？後者はO(N log N)より硬く、O(n^2)交差点にnセグメントがあるため、

自己交差が存在するかどうかを調べるか、少量しか見つからない場合は、hereと表示されます。このペーパーは、特にポリゴン平坦化セクションで、必要なものだけを主張するようです。私はそこに記載されているアルゴリズムを実装することは、合理的なサイズの問題に対しては単純か、価値があるとは思えません。しかし、そのようなアルゴリズムは存在する。免責事項：私は紙を介して作業し、それを理解しようとしていない。