Rectangles のインデックスを提供するデータ構造を探しています。四角形が画面上を移動するため、挿入アルゴリズムをできるだけ高速にする必要があります (マウスで四角形を新しい位置にドラッグすることを考えてください)。
R-Tree、R+Tree、kD-Tree、Quad-Tree、B-Tree を調べましたが、私の理解では挿入は通常遅いです。リストされたデータ構造のいずれかについて誰かが私が間違っていることを証明できるように、サブリニア時間の複雑さで挿入することを好みます。
ポイント(x、y)にある長方形、または長方形(x、y、幅、高さ)と交差する長方形について、データ構造を照会できるはずです。
編集: 挿入を非常に速くしたい理由は、画面上で四角形を移動することを考えると、それらを削除してから再挿入する必要があるためです。
ありがとう！
私は、マルチスケール グリッド アプローチを使用します (何らかの形で四分木に相当します)。
整数座標 (つまりピクセル) を使用していて、すべてのピクセルを保持する十分なスペースがあると仮定しています。
各ピクセルに 1 つずつ、長方形のリストの配列があります。次に、2 つずつビンに入れ、もう一度実行します。すべてをカバーする 1 つのピクセルができるまで、何度も何度も何度も繰り返します。
ここで重要なのは、四角形のサイズにぴったりのレベルで四角形を挿入することです。これは (ピクセル サイズ) ~= min(高さ,幅)/2 のようなものになります。これで、各長方形に対して、リストに挿入する必要があるのはほんの一握りです (たとえば、4 から 16 ピクセルの間のものを選択するなど、定数で上にバインドできます)。
x、y ですべての長方形を探したい場合は、最小のピクセルのリストを調べてから、それを含む 2x2 ビニングされたピクセルのリストを調べ、次に 4x4 などを調べます。調べるには log2(ピクセル数) のステップが必要です。(ピクセルが大きい場合は、(x,y) が実際に四角形内にあるかどうかを確認する必要があります。それらの約半分が境界線で成功し、すべてが四角形内で成功すると予想されるため、ピクセルを直接調べた場合よりも 2 倍以上の作業になります。)
では、インサートはどうでしょうか。それは非常に安価です--リストの先頭に自分を固執するのにO(1)。
削除はどうですか？それはより高価です。入力したピクセルごとに各リストを調べて修復する必要があります。これは、空間内のその位置で重なり合う長方形の数が約 O(n) であり、ほぼ同じサイズです。非常に多数の長方形がある場合は、他のデータ構造を使用してそれらを保持する必要があります (ハッシュ セット、RB ツリーなど)。
(最小の四角形がピクセルよりも大きくなければならない場合、実際にマルチスケール構造をピクセル レベルまで完全に形成する必要はないことに注意してください。最小の四角形がビニングされたピクセル内で絶望的に失われないようになるまで、下に移動してください。 .)
これはおそらく、回答ではなく拡張コメントです。
あなたが本当に何を望んでいるのか、私は少し困惑しています。「長方形の ID を指定して、現在の座標を返す」などの質問に対する迅速な回答をサポートするデータ構造が必要であると推測できます。そうですか？
または、「(x,y) の位置にある四角形は何ですか」と答えたいですか? その場合、ディスプレイの高さと幅に一致する寸法の配列で十分であり、配列の各要素はそのピクセルの長方形の (おそらく短い) リストです。
しかし、常に移動する長方形に対処するために、挿入アルゴリズムをできるだけ高速にする必要があると述べています。たとえば、画面上に 10 個の四角形しかない場合、各四角形の座標を含む 10 要素の配列を単純に持つことができます。それらの位置を更新しても、データ構造への挿入は必要ありません。
長方形はいくつ？それらはどのくらいの速さで作成されますか? 破壊された？オーバーラップにどのように対処しますか? 長方形は単なる境界ですか、それとも内部を含みますか?
あなたが言及したデータ構造は非常に複雑です。特に、Bツリーは高速である必要があります（挿入するコストは、存在するアイテムの数の対数に応じて増加します）が、交差クエリを高速化することはありません.
それを無視して、最善を期待して、空間データ構造は 2 つの部分に分かれています。最初の部分では、データからツリー構造を構築する方法について説明します。2 番目の部分では、各ノードで、そのノードの下に格納されているアイテムを説明する情報を追跡する方法と、それを使用してクエリを高速化する方法について説明します。
通常、ツリーを正確に構築する方法についての (高価な) アイデアを使用せずに、各ノードで情報を追跡することについてのアイデアをつまむことができます。たとえば、各長方形のポイントの座標をビット インターリーブしてキーを作成し、完全に通常のツリー構造 (B ツリー、AVL ツリー、Red-Black ツリーなど) を使用して格納することができます。各ノードで情報を保持しながら。これにより、実際にはクエリが十分に高速化される可能性がありますが、実装して実際のデータでテストするまではわかりません。ほとんどのスキームにおけるツリー構築命令の目的は、パフォーマンスの保証を提供することです。
2 つの追記:
1) 私はこれについてパトリシア ツリーが好きです。実装がかなり簡単で、エントリを追加または削除してもツリー構造があまり乱されないため、ノードに格納されている情報を更新するための作業があまり必要ありません。
2) 前回ウィンドウ システムを見たとき、この巧妙な機能についてはまったく気にしませんでした。項目の線形リストを保持し、必要に応じてすべてを検索するだけでした。それは十分に高速でした。