c++ - 最も近い隣人までの平均距離の概算は?

Question

そして、私が探している別のアルゴリズム: 最近隣問題までの平均距離の無料の C/C++ 実装。

したがって、基本的に私は 3D の点群を持っており、すべての点とそれぞれの最も近い点の間の距離の平均が必要です。これを行う最も簡単な方法は、すべてのポイントの最近傍を見つけ、その近傍からポイントまでの距離を計算し、それらの距離の合計をポイントの数で割ることです。ただし、これには多くの冗長性があり、近似がさらに高速に実行されるため、はるかに優れたアルゴリズムがあります。これらのより優れたアルゴリズムの無料の C/C++ 実装を探しています。

うまくいけばε近似。

Answer 1

C ++ライブラリFLANNを使用すると、「高速近似最近傍検索」を実行できます。これはC++で記述されており、この種の検索の利用可能な最速の実装の1つであると主張しています。

お役に立てれば！

Answer 2

この質問 で説明されているように、Quadtree を試すことができます。他の 3D/2D グラフィック ライブラリにも、問題に対する多くの実装があります。

数年前にあるプロジェクトで「Geometry Engine, Open Source」であるGEOSを使用しましたが、非常に満足していました。