data-structures - 線分のデータベースの場合、長方形と交差するすべての線分を見つけます

Question

線分が大量にある場合、長方形と交差するすべての線分を効率的に見つけるにはどうすればよいでしょうか? 典型的なアプリケーションは、現在の視野内にあるすべての道路を検索する GIS データベースです。ポイントの場合、これはポイントを KD ツリーに格納することで効率的に行うことができますが、線分に対応するデータ構造は何ですか?

アルゴリズムが線幅を考慮している場合はボーナスですが、幅ゼロのアルゴリズムは完全に問題ありません。

Answer 1

CGALに存在するようなセグメント ツリーを使用できます: dD Range および Segment Trees。このデータ構造は、次元 2 を含むすべての次元で使用できます。

Answer 2

別の可能なデータ構造はR-treeです。特に優先度の高い R ツリーを使用すると、実行時間の上限が保証されますが、実際にはヒューリスティックなバリアントの方が高速になる場合があります。