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

Question

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

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

如果可以，则为ε近似值。

Answer 1

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

几年前，我在一个项目中使用过一次GEOS，这是一个‘几何引擎，开源’，我非常满意。

Answer 2

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

希望这能有所帮助！