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

Question

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

所以基本上我有三维点的云，我想要在所有点和它们各自最近的邻居之间的距离的平均值。因此，最简单的方法是找到每个点的最近邻居，计算该邻居到该点的距离，并将这些距离的总和除以点数。但是，有更好的算法，因为这有很多冗余，并且运行速度更快。我正在寻找这些更好算法的免费C/C++实现。

一个ε-近似如果罚款。

Answer 1

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

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

Answer 2

C++库FLANN允许您执行“快速近似最近邻居搜索”。它用C++编写，并声称是这种可用搜索的最快实现之一。

希望这会有所帮助！