距離最近鄰居的平均距離的近似值？

Question

另一種算法，我正在尋找：一個免費的C/C + +實現平均距離最近鄰居問題。

所以基本上我有三維點的雲，我想要在所有點和它們各自最近的鄰居之間的距離的平均值。因此，最簡單的方法是找到每個點的最近鄰居，計算該鄰居到該點的距離，並將這些距離的總和除以點數。但是，有更好的算法，因爲這有很多冗餘，並且運行速度更快。我正在尋找這些更好算法的免費C/C++實現。

一個ε-近似如果罰款。

Answer 1

您可以嘗試四叉樹，如in this question所述。在其他3D/2D圖形庫中，您的問題也有許多實現。

我幾年前曾在一個項目中使用過'幾何引擎，開源'GEOS，並且非常滿意。

Answer 2

C++庫FLANN允許您執行「快速近似最近鄰居搜索」。它用C++編寫，並聲稱是這種可用搜索的最快實現之一。

希望這會有所幫助！