ポイントセットから最も離れた場所を見つけて、クエリポイントから遠く離れた位置に配置することについて多くの質問に答える必要があります。私が今までに見つけたすべてのアプローチは、このケースではうまくいきません(たとえば、k-dツリーにはクエリごとにO(N)があるかもしれません)、またはVoronoiダイアグラムを使用する必要があります。
このようなタスクのために設計された既知のアルゴリズムはありますか?3Dクエリポイントの最近傍点が点集合から遠く離れている
1
A
答えて
0
ここでの問題は距離です。クエリがあなたのデータセットから遠い場合、kd-treeは多くの点をチェックしなければならないので、クエリ時間が遅くなります。
あなたが直面しているシナリオは、Nearest Neighbor Structures(一般的なケースではありません)には難しいですが、私があなただったらBalanced Box-Decomposition treesというショットを付けました。データ構造。
0
いくつかの多次元インデックスには、特にk == 1の場合に、必要に応じて簡単に適応できるkNNクエリがあります。kNNアルゴリズムは、通常、最初に近似近似距離を推定する必要があり、次に、この距離を使用して範囲クエリを実行します。 Rツリーまたはクオッドツリーでは、この推定は、検索ポイントに最も近いノードを見つけることによって効率的に実行できます。次に、最も近いノードから1点を取り出し、探索点までの距離を計算し、この距離に基づいて範囲クエリを実行します。通常、k> 1であるため、いくつかの乗数が使用されます。 これは、検索ポイントが遠く離れていても合理的に効率的でなければなりません。
1点のみを検索している場合(k = 1)、このアルゴリズムを使用して、見つかった最も近い点に正確に基づく範囲クエリを使用できます。
Javaを使用している場合は、オープンソースの実装hereを使用できます。 PH-Tree(クアッドツリーの一種ですが、より効率的で読み込みが高速です)があり、同じkNNアプローチを使用しています。
関連する問題
- 1. Direct3Dスプライトの最近傍点補間?
- 2. 3Dの円の最も近い点。何が欠けている?
- 3. 二次元の点の集合から最も遠い点を「n」に選択する最適な方法
- 4. R - ラスタライズされたUSAマップ上の点の集合から最も遠い点を見つけよう
- 5. 交差点の重心パラメータを与えられた点に最も近い3D三角形の頂点
- 6. kNN - 計算された距離に基づいてトレーニング行列の最近傍点を見つける方法
- 7. Rstudioの別の点へのベクトルのK最近傍点を見つける
- 8. リスト内のn個の最近傍点を見つける
- 9. 2D-3D対応点の集合からのカメラ較正
- 10. 特定の2D点から2D点のリストまでの最も近い点Python
- 11. 点集合からの近似矩形の検索
- 12. 最も近い3D点を見つける
- 13. 各点の最も遠い点を計算する
- 14. 緯度と経度に基づいて最近傍点を計算するアルゴリズム
- 15. ポイントフィーチャから最近傍ポリゴンまでの距離R
- 16. 矩形の最も遠い点
- 17. 3D点から線分までの距離を求める
- 18. データフレーム内のすべての点で最近傍点クエリを実行するためにLSHを使用する
- 19. edittextからTextviewsが遠く離れている
- 20. 範囲の中の接触点までの点の集合から最も近い点を効率的に見つける方法はありますか?
- 21. 直線から最も遠い点を見つける
- 22. PostGis最近傍問合せ
- 23. プログラムによるスクリーンショット最近傍点を間違って表現する
- 24. 最後の点を除いて最も近い点を見つけるLibGDX Java
- 25. 他の点から最も近い点を効率的に見つける
- 26. 点集合から四角形の頂点を見つける
- 27. 浮動小数点型の最近傍の浮動小数点数に無効な文字があります
- 28. 他の点に最も近い点を見つける
- 29. 空間内の点の集合から最も近い/最も近い平面を見つける最良のアルゴリズム/論文は何ですか?
- 30. 下限を持つ最近傍点を見つける...しかし、データはソートされていません
あなたがk-NN問題を解こうとしていて、 'k 'を大きすぎると設定していることを意味しますか?または、クエリはポイントセットから遠く離れたmuuuuchですか? – gsamaras
私は、互いに比較的近いポイントの雲があることを意味します。しかし、このクラウドから遠いところにある私のクエリポイントは、すべてのクラウドポイントが(0; 0; 0)とエッジサイズ1でキューブ内にあり、クエリポイントが(2; 0; 0)、(4; 1; 3)など)。 K-dツリーや他の典型的なツリーは、この場合、クエリに答えるのに時間がかかりすぎるとうまくいきません。 – Inspiration
k << nのk個の井戸分布点のサブセットのみでボロノイ図を作成する方法はありますか?クエリでは、log(k)にVoronoiセルを配置してから、この領域の点でkd-tree検索を行います(そのような点のO(n/k)付近にあるはずです)。 – geoalgo