algorithm - 線交差横断

Question

ランダムな線分がいくつかあります。2つの線分の間に交差があるかどうかを確認する必要があります。回線が接続されている場合と接続されていない場合があります。この問題の良いアルゴリズムは何でしょうか？

Answer 1

ここで線分について話していると仮定します（そうでない場合は、線の傾きを比較します。傾きが等しくない場合は、交差します）。

[単一の]交差が2つ以上の線分のセットに存在するかどうかを確認するには、Shamos-Hoeyアルゴリズムを使用できます。

2つ以上の線分のセットですべての交差点を見つけるには、Bentley-Ottmannアルゴリズムを使用できます。

2つの実装、およびその他の「スイープライン」ベースのアルゴリズムは、インターネット上で豊富に利用できます。