歐幾里德三維數據查詢的良好數據結構？

Question

存儲點雲數據的好方法是什麼，以便對於執行這兩個查詢之一的應用程序來說它是最佳選擇？

1. 最近（即最低歐幾里德距離）的數據點以（X，Y，Z）
2. 獲取與周圍的點的半徑R（X，Y，Z）

一個球內的所有點

該結構將只填充一次，但多次閱讀。由於我可能正在處理大於700萬點的數據集，所以內存容量不足會很好，但速度應該是首要關注的問題。一個圖書館會很好，但如果在該領域有限的專業知識是可行的，我不會介意自己實施它。

在此先感謝！

Answer 1

A Kd-Tree你得到O（日誌（n））最近的鄰居，通常範圍查詢會很快。

這裏有一堆庫引用。我沒有使用過任何一個。

您可能還會看到CGAL。我已經使用CGAL來處理其他事情，它速度很快，非常全面，但是文檔會讓你喝酒。

Answer 2

數據結構中決定的一大部分將取決於數據的空間組織。例如，高度集羣的數據在kd樹中往往具有不同於均勻分佈的數據的性能特徵。

KD-Trees對於這兩個查詢都非常有用。

Octree在許多情況下也是很好的選擇，並且可能更容易實施。

有許多圖書館這樣做，使用各種算法。搜索k-nearest neighbor searching將顯示許多有用的庫。例如，過去我曾與ANN運氣相當好。