performance - 2次元空間で長方形を見つける

Question

2D空間にさまざまなサイズの長方形のセットがあります。長方形の数は10から100000に動的に変更でき、それらの位置とサイズは頻繁に更新されます。

与えられた点（x、y）で長方形を見つけるためにどの空間構造をお勧めしますか？検索操作も非常に頻繁に実行されたと仮定します（たとえば、マウスの移動）。さまざまな空間インデックスアルゴリズムの比較への参照を提供したり、ここでそれらの検索/ビルド/更新のパフォーマンスを比較したりできれば、それは素晴らしいことです。

Answer 1

R-Treeをお勧めします。これは主に長方形（またはN次元軸に整列された立方体）用に設計されています。

Answer 2

クアッドツリー（http://en.wikipedia.org/wiki/Quadtree）を使用します。

長方形が開始および終了する可能性のあるすべてのX値とY値を決定します。次に、これらの値に基づいて四分木を構築します。四分木の各葉に、どの長方形が葉の座標範囲と重なるかを保存します。どの長方形が重なっているのかを見つけるには、座標を含む葉を見つけるだけです。