問題タブ [kdtree]

n最も近い点を見つけるために、pbrt ソース コードを使用して kdtree を実装しようとしています。3 次元空間に分布する点の配列があり、基準点から特定の距離内にある点の数を計算する必要があります。それで、誰かが私がどのように進むべきかについて私を導くことができますか? 基本的に、integrators/photonmap.cpp に記載されているものと同じルックアップ プロセス (PhotonProcess) を使用しています。しかし、どういうわけか私は奇妙な結果を得ることになります。ここに私が使用しているコードの小さな部分があります。

searchdist の期待値が得られません。ヒントのアイデアや提案は大歓迎です。

この質問の詳細ですが、より多くの制約があります。

考え方は同じで、2 ユークリッド次元の k 最近傍点の単純で高速なアルゴリズムを見つけます。データを適切に分割するグリッド サイズを見つけることができれば、バケット グリッドはうまく機能するようです。ただし、データが均一に分散されておらず、密度が非常に高い地域と非常に低い地域 (たとえば、米国の人口) があり、固定されたグリッド サイズでは十分な近隣と効率の両方を保証できない場合はどうなるでしょうか? この方法はまだ救済できますか？

そうでない場合は、他の提案が役に立ちますが、kd-trees などに移動するよりも簡単な答えを期待しています.

高次元データを処理すると思われる FLANN の kd-tree を実装する vlfeat の kdtree を使用しています。ただし、現在、128x15000 のデータセットから構築された kdtree があり、kd ツリーのクエリは、1 回のクエリで 8 秒まで遅くなりました。これはkd-treesの限界ですか？FLANNは、より高速に最適化されたkdtreeでもあるはずでした...

他にどのようなオプションがありますか?

私はデータ構造について独学しようとしており、Python で kd ツリーを実装しています。kd ツリー クラスの 1 つのポイントの特定の半径内でツリー内のポイントを検索するメソッドがあります。

それは機能しますが、返されるリストはかなりファンキーで、再帰呼び出しからの値が重複していますresult。ツリー再帰から返された値をリストに「蓄積」する良い方法は何ですか? しばらく考えているのですが、よくわかりません。

Pythonプログラミング言語で実装されたkd-treeのアルゴリズムビルドは次のとおりです（http://en.wikipedia.org/wiki/K-d_treeから）：

ソートはすべてのステップで実行されます。ソートの量を減らす方法は？

緯度、経度、およびタイム ゾーンのトリプレットの非常に長い半ソート リストがあります。このリストをすばやく検索して、特定の緯度と経度に最も近いタイム ゾーンを見つけられるようにしたいので、このリストを KD ツリーにしたいと考えています。

最初にファイル全体をある種のデータ構造に読み込む必要があると考えています(どのデータ構造ですか?おそらくArrayList<Triplet<Double, Double, String>>?)。次に、その構造の中央値要素を取得してルートにし、左と右のリストを残します。次に、各リストの中央値要素を取得し、それを左または右の子として追加し続けます。

これを最初に試みたときは、時間がかかり、効率が悪いように思えました... しかし、私はそれが間違っていたように感じます。私がやろうとしていることのアルゴリズムまたは疑似コードを教えてもらえますか?

の空間インデックスデータ構造の王様を実装したいと思いMKAnnotationsます。現在、距離基準に基づいてそれらをフィルタリングしようとすると、ひどく遅くなります（3〜4kの場所、現在は単純なダブルで非常に遅いfor...）。

MKAnnotationsのクラスターを作成して、別のクラスターに近いかどうかを判断したいと思います。また、これらの場所はある程度（作成）の順序であり、「前」/「次」の機能が「ジャンプ」するために必要になります（これは必須ではありません）。kd-treeと構造について読んだことがr-treeあり、どちらもフィルタリング/クラスタリングの高速距離/隣接取得オプションを満たしているようですが、どちらが私に最適か、または他のオプションもあるかどうかはわかりません。どのアルゴリズム/データ構造を使用する必要がありますか？

更新：これらの場所をCore Dataデータベースに保存します。これらは、パスを表します。マップを開くと、それらは配列にフェッチされ、距離の計算と注釈の作成にその配列を使用します。ユーザーがマップを移動/ズームするとき、私はそれらをループして、マップ上で何を変更する必要があるかを決定するので、全体が少し静的です。私が理解したように、私が木を使用している場合、そこに場所を保存することができ、ズーム/移動が発生したときに、それを検索して新しい領域の場所を取得するだけです。これは本当ですか ？

動的な場合でも、この配列に新しい場所を追加できる場合、それは1回の挿入であり、ほとんど発生しません。

2 つの画像 A と B があります。それらからキーポイント (a[i] と b[i]) を抽出します。
a[i] と b[j] の一致を効率的に判断するにはどうすればよいでしょうか。

明白な方法は、A の各ポイントを B の各ポイントと比較することですが、大規模な画像データベースでは時間がかかります。ポイントa[i]とb[k]だけを比較するにはどうすればよいですか

kd-treeが良い選択かもしれないと聞きましたね。kd-treeに関する良い例はありますか?

他の提案はありますか？

私は2次元配列を持っています:

最初の 2 つの要素MyArray[0]とMyArray[1]は、点のX座標とY座標です。

配列内のすべての要素について、半径X単位で最も近い 1 つの要素を返す最も簡単な方法を見つけたいと思います。これは 2D 空間にあると仮定しています。

この例で言いましょうX = 6。

すべての要素を他のすべての要素と比較することで問題を解決しましたが、リストが 22k ポイントの長さの場合、これには 15 分ほどかかります。最終的には、約 3000 万ポイントのリストでこれを実行したいと考えています。

Kd ツリーについて読んで、基本的な概念は理解しましたが、それらをスクリプト化する方法を理解するのに苦労しました。

html5 キャンバスに描画される長方形の大きなセットがあります。

マウス トラッキングを使用してこの画像を操作できるようにしたいと考えています (10 ～ 100k の四角形にスケーリングされないため、SVG は使用できません)。マウスのx、y座標が与えられた場合、マウスがどのボックスの上にあったかを(長方形の計算された位置を使用して)知ることができるデータ構造/アルゴリズムはありますか? kd ツリーのようなものを考えていましたが、確信が持てませんでした。