algorithm - すべての線分の交点を見つける

Question

線分のリストが与えられた場合、交点を見つける最も簡単な方法は、線分のリストをループして、それらが交差しているかどうかを確認し、交差している場合は交点を記録することです。

しかし、このメソッドの実行時間はO(n^2)であり、非常に非効率的です。このプロセスを高速化できる他のアルゴリズムはありますか?

Answer 1

Bentley-Ottmann アルゴリズムは、探しているものかもしれません。