問題タブ [kdtree]

kdtree の 2 次元 (x, y) の最小要素を取得したい。最小要素は、kdtree のすべての要素 (x ', y') に対して、x

要素 x を繰り返すことができるので、どちらかを返します。

wiki で kd ツリーの説明を読んだことがあります。wiki によると、kd ツリーはポイントを保持します。私は三角形のメッシュを持っており、円柱との効果的な計算の交差と点への距離のクエリのための構造が必要です。私が理解しているように、メッシュを平面で分割すると、多くの三角形がその平面と交差する可能性があります。それで、私は何をすべきですか？三角形のコピーを左右の子ボックスに入れるか、交差する三角形を分割しますか?

したがって、NetworkX では、n^2 時間でアルゴリズムを使用してランダムな幾何学的グラフを生成することは明らかです。彼らは、KD ツリーを使用することで、より高速なアルゴリズムが可能になると言っています。私の質問は、このアルゴリズムの KD ツリー バージョンを実装するにはどうすればよいでしょうか? 私はこのデータ構造に精通していませんし、自分自身を Python の専門家と呼ぶつもりもありません。これを理解しようとしているだけです。すべての助けに感謝します、ありがとう!

四分木または kd ツリーの分割とマンデルブロ集合について読んだことがありますが、最初の分割前の四角形とフレームがマンデルブロ集合にあるか、反復深度が同じで、アルゴリズムがタイリングから戻った場合はどうなりますか? 長方形が大きすぎる場合、長方形の塗りつぶしを強制的にスキップするにはどうすればよいですか?

したがって、KD ツリーのバランスをとるときは、中央値を見つけて、それよりも小さいすべての要素を左側のサブツリーに配置し、大きいものを右側に配置する必要があります。しかし、中央値と同じ値を持つ要素が複数ある場合はどうなるでしょうか? それらは左のサブツリーに入りますか、右のサブツリーに入りますか、それとも破棄しますか?

私は複数のことを試してみましたが、最近傍検索アルゴリズムの結果に影響を与え、ツリーの特定のセクションのすべての要素がすべてまったく同じ値を持つ場合があるため、質問しません。その場合にそれらを分割する方法を知っています。

先月、私はフォトモザイクのWebサイトに取り組んでいます。私はすべてをPHPで構築し、それをうまく機能させました。私が嫌いなのは実行時間だけです。線形比較検索のため、これは長すぎると思います。それで、私は検索時間を改善する方法について尋ねてきました、そしてほとんどの人は私をKDツリーの方向に向けました。それはk最近傍をはるかに速くします。

だから私はKDツリーを調べていて、そのようなツリーを手動で構築する方法を理解しています。もちろん、これをコーディングしたいのですが、C++とJavaのライブラリしか見つかりませんでした。私はPHPに精通しているだけなので、自分でPHPを作成しようとしていますが、これは思ったほど簡単ではありません。

•私が直面している問題は、すべてをどのように保存するかです。すべてのポイントを含む最初の配列を取得したら、それを3つに分割します。左ブランチ、ノード、右ブランチ。もちろん、分割できなくなるまで左のブランチでも同じことを行います。もちろん、軸（XYZ）を循環します。しかし、すべての正しいブランチをどのように格納しますか？それらを配列のままにしますか？または、使用する準備ができたら、もう一度計算しますか？

•私が疑問に思っていたもう1つのことは、PHPがこの仕事に適した言語ではないため、なぜPHPKDツリースクリプトがないのかということです。

これは私がこれまでに得たものです。

この関数は、残りをテストするために使用するランダムカラー（RGB）を計算します。

この関数は、特定のキーで多次元配列を並べ替えます（デフォルトはR）

このクラスは、配列を左ブランチ、ノード、および右ブランチに分割します。

Google には、C で記述された KD ツリー ライブラリがあります。

私が知る限り、ツリーの関数の 1 つを使用してツリーにメモを挿入し、ツリーに最近傍をクエリします。新しい配列へのポインターを返します（私が知る限り）。

これが私の目標です：

私は 3D 配列を持っており、特定のポイントの最近傍のインデックスを返す方法を見つけたいと思っています。私が言いたいのは：ここにポイントがあります：（12,23,14）、次に、最も近いポイントのインデックスを教えてください：「それはあなたの配列の5番目のアイテムです」. ただし、これを行う方法がわかりません。

私の質問、誰か:

A) 適切に文書化された、c の k 次元最近傍検索ライブラリを知っている、または:

B) Google のコードを取得して配列内の最近傍の位置を返す方法を知っている。

Scipyには、K 次元ツリーを含む優れた空間分析パックがあります。クエリ関数を使用しようとしていますが、次のエラーが返されます:

ValueError: x は長さ 6 のベクトルで構成されている必要がありますが、形状は (2,) です。

このエラーが何を指しているのか誰か知っていますか?

いくつかのグーグル検索から、私はそれがこの一般的な形式を持っていることを発見しました:

これがソースコードだと思います。

Kd ツリーを実装して、C++ で最近傍検索と近似最近傍検索を実行しようとしています。これまでのところ、最も基本的な Kd ツリーの 2 つのバージョンに遭遇しました。

1. ここのように、データがノードとリーフに格納されるもの
2. ここのように、データが葉にのみ保存されるもの

それらは基本的に同じように見え、同じ漸近特性を持っています。

私の質問は次のとおりです。どちらかを選択する理由はありますか?

これまでのところ、2つの理由を考えました。

1. ノードにデータを格納するツリーも 1 レベル浅くなっています。
2. delete data葉だけにデータを格納するツリーは機能を実装しやすい

どちらを作成するかを決定する前に、考慮すべき他の理由はありますか?