c# - KD ツリーに四角形/円/三角形を格納する

Question

Kd-tree を調べていたところ、このアルゴリズムの実装がいくつか見つかりました。これらはすべてポイントを格納していました (ほとんどの場合 2d)。私が達成しようとしているのは、長方形、三角形などのさまざまな形状を格納することです。kd-trees で形状を格納することは可能ですか? 四分木用のコードがいくつかあります。その中に形が保存されていました。

Answer 1

これは、クワッド ツリーで使用される方法とそれほど違いはありません。

形状ごとに、以下を計算できるはずです。

• その重心。

• その封筒。

中央値を計算するときは、重心を使用します。シェイプのエンベロープはクワッドに収まる必要があります。四角形に形状を挿入するときは、そのエンベロープが超平面を横切るかどうかを確認してください。true の場合、形状をクワッドに保存します。false の場合、このシェイプを左または右のクワッド コンストラクション コールのシェイプの適切なリストに入れます。

乾杯

Answer 2

これは KD ツリーの自然な拡張です。

ツリーにポイントしかない場合:

• ツリーのノードは空間の領域に対応します
• 親ノード P と子ノード C1、C2、...、CN が与えられた場合、子ノード Ci は互いに素であり、P を分割します。
• 各点 x は、ツリーのちょうど 1 つのリーフ ノードに存在します。

ツリーにボリュームがある場合:

• ツリーのノードは空間の領域に対応します
• 親ノード P と子ノード C1、C2、...、CN が与えられた場合、子ノード Ci は互いに素であり、P を分割します。
• 各ボリューム v は、ツリーの少なくとも 1 つのリーフ ノードに存在します (それが交差する任意のリーフ ノードの「内」にあります)。