10

ポイントのいくつかの半径検索、kd-treeまたはoctreeを実行するのに適した構造を見つけようとしていますか? この質問ですでに言及されていましたが、答えはありませんでした。オクトリーはリーフのサイズが固定されているため、アクセスする必要があるブランチをすでに計算できますが、kd-tree の場合は、半径がカバーされるまで繰り返しブランチにアクセスする必要があります。

4

3 に答える 3

2

私のプロジェクトでは、範囲検索に Octree を使用しています。これは効率的に機能し、実装が簡単です。ただし、KD-Tree と比較したことはありません。私の知る限り、この操作の kd ツリーでの最悪の場合の時間の複雑さは、3 次元データの場合 O(n^(2/3)) ですが、Octree は O(n) しか保証できません。したがって、最悪の時間の複雑さを気にする場合は、KD ツリーを選択してください。（データセットでこれが決して起こらないことがわかっている場合、最悪の時間の複雑さは気にしません。）

于 2013-12-04T14:01:11.923 に答える