c++ - 到最近邻居的平均距离的近似值？

Question

我正在寻找另一种算法：到最近邻问题的平均距离的免费 C/C++ 实现。

所以基本上我有一个 3D 点云，我想要所有点与其各自最近邻点之间距离的平均值。所以最简单的方法是为每个点找到最近的邻居，计算该邻居到该点的距离，然后将这些距离的总和除以点的数量。但是，还有更好的算法，因为它有很多冗余并且近似值运行得更快。我正在寻找那些更好算法的免费 C/C++ 实现。

一个 ε-Approximate 如果没问题。

Answer 1

C++ 库FLANN允许您进行“快速近似最近邻搜索”。它是用 C++ 编写的，并声称是此类搜索中最快的实现之一。

希望这可以帮助！

Answer 2

您可以尝试四叉树，如本问题所述。在其他 3D/2D 图形库中也有许多针对您的问题的实现。

几年前，我曾在一个项目中使用过GEOS，即“开源几何引擎”，并且非常满意。