Guttman の元の論文に基づいて R ツリーの実装を書いています。マウスで移動/サイズ変更できる画面上の多くの長方形を含む、私が書いているプログラムにRツリーを使用することを考えていました。
特定の四角形にある四角形のみを効率的に選択して描画したい (100 以上のアイテムを反復して境界が交差するかどうかを確認する代わりに)。Guttman の論文を数回読んだ後に私が見つけた問題は、2D オブジェクトの z オーダーを維持できないことです。
たとえば、オブジェクトを移動すると、削除されてから再挿入されます。再挿入すると、挿入先のノードは適切な順序を追跡できなくなります。私が見た R ツリーのほとんどの実装では、配列を使用し、空の位置を見つけるだけです。再挿入すると、基本的に z オーダーの配置が破棄されます。
したがって、長方形と交差するすべての長方形を描画しようとすると、それらが返される順序は必ずしも正しいとは限りません。
この仮定は間違っていますか？配列を使用する代わりに、AVL または Red-Black ツリーを使用し、Comparerz-index で比較する a を使用してツリーに挿入できると考えていました。このように、z オーダーは常に維持されます (これが最も重要な要素です)。
返却時に仕分けも考えていたのですが、こちらの方が高くつくのではないかと思っています。