13

3D ポイントクラウドがあり、任意のポイント p から距離 d 内にあるすべてのポイントを効率的にクエリしたい (保存されたポイントクラウドの一部であるとは限らない)

クエリは次のようになります

Pointcloud getAllPoints(Point p, float d);

これに適した加速構造は何ですか？範囲ツリーは、球のボリュームではなく、長方形のボリュームのクエリにのみ適しているようです (もちろん、球のバウンディング ボックスをクエリして、距離が d より大きいすべての頂点を並べ替えることができますが、もっと良い方法があるかもしれません)これ？？）

ありがとう！

ノベロクラッツの提案に従って、構造の望ましい機能を定義しようとしています。

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance)
SearchStructure Remove(Point p)
SearchStructure Insert(Point p)
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points

通常、n回のクエリの後、ポイントが移動し、いくつかの（多くはありません！）挿入と削除が行われます。オフセット ベクトルは、すべてのポイントのバウンディング ボックスに比べて非常に小さい

4

6 に答える 6

6

必要なのは、特定の領域を効率的に見つけることができるように空間を分解する構造です。適切に分解されたoctreeまたはkD-treepを使用すると、ポイントを含むツリーのセクションを「開く」だけで近くのポイントを探すことができるため、これをうまく行うことができます。これにより、距離を比較するために必要な余分なポイントの数に、かなり低い漸近限界を設定できるはずです (ある分解レベル以下では、すべてのポイントが十分に近いことがわかっています)。残念ながら、私はこの分野の文献を十分に知りません。これらとの出会いは、Barnes-Hut n-Body シミュレーション アルゴリズムによるものです。

これに密接に関連する別の質問があります。そしてもう一つ。そして3 つ目は、これまで聞いたことのないデータ構造 (Hilbert R-Trees) について言及しています。

于 2009-08-23T13:57:46.127 に答える
2

VTKは以下を助けることができます：

void vtkAbstractPointLocator :: FindPointsWithinRadius（
double R、double x、double y、double z、vtkIdList * result
）

vtkAbstractPointLocatorのサブクラスには、検索アクセラレーション用のさまざまなデータ構造（通常のバケット、kdツリー、およびoctree）が含まれています。

于 2009-09-10T13:00:23.673 に答える
1

最近傍問題のテンプレート（DDJのLarry Andrews）をご覧ください。その唯一の2Dであり、検索の複雑さはO（log n）ですが、3Dにも採用される可能性があります。

于 2009-09-10T13:08:39.260 に答える
1

私はあなたのAPIを理解していません。任意の球内にあるPointCloud内のすべてのポイントを切り上げることができますが、ポイントクラウドが保存されているとも言いますか? その場合、指定された球の内側にある PointCloud のリストを取得するべきではありません。

API を事前に定義しようとするのではなく、必要なときに定義します。絶対に呼び出されない関数を最適化することは言うまでもなく、決して使用されないものを実装する必要はありません (もちろん楽しみのためでない限り:))。

最初の実装として、境界ボックスのカリングを実装してから、より詳細な球体検索を実装する必要があると思います。おそらく、それはあなたが考えるほどのボトルネックではなく、おそらくもっと深刻なボトルネックを考慮する必要があるでしょう。すべてが計画どおりに機能していることを実際に確認したら、後で最適化することはいつでも可能です。

于 2009-08-23T15:08:48.887 に答える
0

キーが距離に等しく、値がポイント自体であるマップを使用すると、特定の距離または特定の範囲内にあるすべてのポイントを照会できます。

于 2009-08-23T13:52:02.733 に答える
0

まあ、それはデータ構造に必要な他の用途に依存します。

ポイント p から他のポイントまでの距離を距離順に並べたリストを作成し、これらのリストをハッシュマップを使用してポイントにマッピングできます。

map:
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}]
p2 -> ...
...

マップ内のポイントを検索し、距離が必要以上になるまでリストを繰り返すことができます。

于 2009-08-23T13:52:37.677 に答える