特定のポイントで動作するkdツリーの実装があります。たとえば、ツリーにポイントを追加してから、指定された x、y 座標に最も近いポイントを見つけることができます。これはすばらしいことです。
これを長方形で動作するように拡張したいと考えています。たとえば、ユーザーが x 座標と y 座標、幅と高さを指定した場合、この構造で範囲クエリと最近傍検索を実行できるようにしたいと考えています。長方形のデータを扱うために必要だった現在のツリーを拡張するにはどうすればよいでしょうか?
Kd ツリーは、低次元の点データに最適です。複数の点 (線、長方形など) で構成されるものについては、R ツリーを使用することをお勧めします。
長方形を処理するためのkdツリーの優れた拡張を知っています。これはBox Sortアルゴリズムと呼ばれ、ここでBox sortを見つけることができます。考え方は kd ツリーとほとんど同じです。このペーパーには Pascal での実装もありますが、Java への変換は簡単です。