geometry - kd ツリーから長方形のセットを取得するにはどうすればよいですか?

Question

kd treesのウィキペディアのエントリを見ると、2D 空間を長方形に分割する点と平面のこの図が表示されます。

私の質問は、結果の長方形のセットを取得するにはどうすればよいですか? リーフノードへの各「パス」が境界を与える可能性があると考えました。任意の深さの N ポイントに対してこれを行う一般的な方法はありますか?

私が求めていないのは、超長方形構造の kd ツリーであることに注意してください。ここで、指定された入力は、範囲検索などのために照会できる長方形のセットです。私の入力はランダムな点のセットであり、出力したいデカルト空間を完全に「テッセレート」または細分割する長方形のセット。

Answer 1

多くの kD ツリーは、実際には各サブツリー/リーフの境界ハイパーレクトを格納するため、KNN 検索でより適切なプルーニングを実行できます。これらはすべてのスペースをカバーする長方形ではなく、ポイントがない葉の間に隙間を残すことに注意してください。個人的にはそちらの方がかっこいいと思います;-)

Answer 2

eh9さん、編集ありがとうございます。入力が一連のランダムな点から構築された kd ツリーであることを明確にするために、出力は結果として得られる四角形のセットです。

そして、「些細な」解決策を提供してくれたJerdakに感謝します。実際、ルートノードから始めてツリーをたどり、各軸の深さで長方形を分割し続けます。唯一の追加情報は、元の長方形の外側の境界です。すべてのノードにアクセスしたら、完全なセットを返すことができます。