問題タブ [kdtree]

KdTree をゼロから実装しようとしています。add-、最近傍の検索、range メソッドでのノードの検索を正常に実装したので、ノードの削除に行き詰まっています。

ウィキペディアに記載されている方法はあいまいで、役に立たないものです。代わりに、これらのスライドを出発点として使用しています。しかし、スライド 13 の remove メソッドの説明は私を混乱させます。

とを置き換えt.leftても意味がありません。nullt.right with remove(t.right, ...)

これは正しいですか。また、この方法には他に何か問題がありますか? これらのスライドで説明した方法とは逆に、右側ではなく左側に等しいノードを配置していることに注意してください。メソッドはまだ有効ですか？

AとBの2つのセットがあります。これらのセットはN次元の点で構成され、順序付けられています（N <10）。BのAに​​最も近い部分を見つける必要があります。最も近い部分がB1であるとしましょう。B1のポイントの数はAと同じである必要があり、B1のすべてのポイントからAまでの距離の合計は最小である必要があります。

kdツリーを確認しました。セット内で最も近い点を見つけるのに役立つだけです。では、最も近い範囲をすばやく見つけるためのアルゴリズムはありますか？

ありがとう。

ポリゴンである一連のリージョン (ジオフェンス) があります。このデータ セットは固定されています。したがって、データの挿入と削除の必要はありません。クエリ ポイント (経度、緯度) が含まれる地域を検索するために使用できるデータ構造はどれですか?

注: ポイントのセットに対して KD ツリー (実際には 2D ツリー) を正常に実装しました。しかし、この問題にはうまくいきません。次に、R ツリーを実装しました。それは問題を解決しますが、遅いです（または私の実装はひどいです）。

ありがとうございました

注: R ツリーの実装に取り​​組んでおり、現在は正常に動作しています。

CGALのKdツリー実装とファジー球をクエリオブジェクトとして使用して、ポイントr_maxを中心とする半径の球で囲まれたポイントを取得しています。この最小限の作業例を次に示します。

CGALの例のSpatial_searchingフォルダーの下にあるinterior_neighbor_searching.cppファイルからコメント「Printpoints」の下の行を取得して適合させました（私のバージョンは3.9です）。

質問は次のとおりです。ポイントの座標を標準に出力する代わりに、ある種のコンテナで検索の結果として得られたポイントへのポインタ/イテレータ/ハンドルを格納する別のOutputIterator（ではなく）を設定する方法はありますか？出力？ありがとうございました。std::ostream_iterator

次のクラスは、g++ から次のエラーを返します。

tree.h:9: エラー: 'template' の前に unqualified-id が必要です

5 行目のコメントを外すと、5 行目でのみ同じエラーが発生します。

これをあまりにも長く見つめているため、ここで明らかな構文エラーを見逃していますか? または、テンプレート クラスを不適切に宣言していますか?

私はPythonでBlender用のこのパーティクルエンジンに取り組み始めています：http ：//www.youtube.com/watch？v = uoK4QV3jg58＆feature = channel_video_title

すべてのデータは私のスクリプトによって処理されます。Blenderはビジュアルのためだけにあります。今のところ、私の問題は、上のビデオで、すべてのパーティクルの各パーティクル間の距離を計算して、それらが互いに衝突しているかどうかを検出することです。

私はについて読み始めています：

• 八分木
• kdTree
• BVHTree
• AABBtree
• ...などなど

Kdtreeは、最も近いネイバーを検索するのに非常に効率的であるように見えますが、静的クラウドのみを検索します。私のパーティクルは常に移動するため、反復ごとにkdTreeを再生成する必要があり、多くのプロセスを消費すると思います。私は多くのゲームがAABBツリーを使用していることを読みました。少し迷ってしまいました…何を選べばいいのかわかりません。私が欲しいのは：

• 非常に大量の粒子（25万以上）間の衝突を検出します
• リアルタイムである必要はありません（とにかく250000個のパーティクルでは実際には不可能です）。200万個のパーティクルに対してフレームあたり20分は私にとって問題ではありません。
• 私の粒子は常に球です
• パーティクルとポリゴンオブジェクト間の衝突を検出します
• 必要な距離計算を減らすためのアルゴリズム（遠くにある場合でも、互いにすべてのパーティクルまたはポリゴンを計算するなどの回避）
• パーティクルは動的であり、ポリゴンオブジェクトは動的または静的にすることができます。

誰かが私に最良の推測が何であるか、そして私がPythonのドキュメントとその例をどこで見つけることができるかを教えてくれるなら。

1つの画像（A）のSURF記述子を他のいくつかの画像（B、C、D、..）の記述子と比較して、Aに最も類似した画像を見つけたいと思います。記述子には64の次元があります。

C＃とEmguを使用して、Aの記述子をB、次にC、次にDなどと比較することによって照合が行われます。画像数が10を超えると、無関係な記述子を多数検索する必要があるため、これは非常に遅くなります。

プロセスをスピードアップするために、（記事によると）正しい方法は、（B、C、D、..）の記述子用に1つのkdツリーを構築して、Aの記述子をすばやく一致させることです。kd -ツリーはレベルに応じて次元で分割されます。最初の分割は1次元で決定され、2番目の分割は2次元で決定されます。ただし、記述子の次元数が多い場合（64）、KDツリーを使用する利点は小さくなります。

だから私の質問は：1つの画像（A）から複数の画像（B、C、D ..）にSURF記述子を一致させるためにKDツリー/他の方法を使用することでどのような経験または知識がありますか？何がうまくいくのか、あまりうまくいかないのか、そしてあなたはこのようなことをしましたか？

FLANNはOpenCVで使用されているため、ここではオプションになりますが、C＃のバージョンが見つかりません。ほぼ最も近いNeightboorもkdツリーを高速化するオプションですが、それは一致する画像でうまく機能しますか？

よろしくモーテン

以下のコード セグメントが何をしているのか理解できません。これは、Henrik Wann Jensen 著『フォトン マッピングを使用したリアルな画像合成』という本から引用されています。それがやろうとしていること（またはコード内の場所を考えてやるべきだと思うこと）は、開始インデックスと終了インデックスの間の配列で中央値インデックスを計算することだと思います。

より詳細なコンテキストについては、コードは、3D ポイントのリストを指定して kd-tree データ構造を構築するセクションからのものです。kd ツリーを構築する再帰的な各ステップで、(ある次元に関して) 中間点が選択され、新しい kd ツリーのルートになります。

このコードは、開始インデックスと終了インデックスの間の中央値インデックスを計算することになっていると思いますが、正しければ、なぜこの中央値インデックスが奇妙な方法で計算されるのかわかりません。

どんな助けや洞察もいただければ幸いです、ありがとう！

編集: Vaughn Cato のおかげで、この方法で中央値インデックスを計算する必要があることがわかりました。もともと、(end - start)/2 + start を実行できない理由について、私は混乱していました。このコードの目的は、ポイントのリストを取得し、それをヒープのようなデータ構造 (配列内のバイナリ ツリー全体) に格納できる完全でバランスの取れた kd ツリーに変換することです。単純な方法で中央値インデックスを計算しても、配列にフラット化できるツリーが得られるとは限りません。

今、私は誰かがどうやってそれを思いついたのか混乱しています. 誰かが私を説明したり、派生の方向に向けたりすることはできますか?

ポイントの最も近い単一の近傍を求めて Kd ツリーをトラバースする関数の作成に成功しました。

ただし、この関数を切り替えて、単一の隣人ではなく K 最近隣人を見つけるようにしています。これは、私が最初に想像したよりもはるかに困難な作業であることが証明されており、助けが必要であることがわかりました...

kDツリーに関するウィキペディアの記事には、次のように書かれています。

このアルゴリズムは、単純な変更によっていくつかの方法で拡張できます。1 つだけではなく k 個の現在のベストを維持することにより、ポイントに k 最近傍を提供できます。ブランチは、k 個の現在のベストのいずれよりも近いポイントを持つことができない場合にのみ削除されます。

…が、初期の現在のベストを取得する方法については何も述べていません。最初の「ベスト」を見つけるのは簡単ですが、以前のベストを削除して最初からやり直すことなく、残りのk-currentベストを見つける方法がわかりません...これは基本的に、アルゴリズムが速いため、k 回 (私の場合は 17 回) 実行する必要があります。

17 の最初の「ベスト」のリストが入力されている場合、アルゴリズムは正しいポイントを見つけると思います。

これが曖昧な場合は申し訳ありません。コード サンプルが必要な場合は、喜んで提供します。この問題について簡単な説明があれば、おそらく投稿する必要はないので、最初は投稿しません。

前もって感謝します！

長方形に収まるすべてのセグメントを見つけるためのデータ構造が必要です (C# では、それが主な問題でなくても)。

たとえば、セグメント [(0,0) , (10,10)] は、(5,5) から始まるサイズ (1,1) の長方形内になければなりません。

私は kdtree を試しましたが、彼の点の 1 つが長方形の中にある場合にのみセグメントを返します。セグメントを実線として認識しません。

この検索を効率的に行うには、どのようなデータ構造が必要ですか?
非常に標準的なように見えますが、検索しましたが、このケースについては何も見つかりませんでした!

問題の寸法: 6000 のセグメント、平均 20 の線セグメントが長方形内にある

重複の並べ替え:

• 行を kd ツリーに最適に格納する方法
• 高速ラインクエリのデータ構造?