點的第k個最近鄰居的空間查詢

Question

我正在研究一個算法，該算法需要從某個給定查詢點的第k個最近點重複（歐幾里得）距離，所有查詢點都取自一個點向量。另外，我反覆需要找到某個點的給定半徑內的所有點。

我正在考慮使用nanoflann庫中的k-d樹。但是，knnSearch（）函數返回所有k個最近的鄰居，我不需要。 （雖然radiusSearch（）函數很適合我）。

有沒有更有效的方式來獲得我需要的東西，除了每次都通過所有k個最近的鄰居？更好的數據結構還是更好的實現？ （我使用C++。）

Answer 1

我想使用的k d樹木

爲2D或3D

最佳選擇的。

k-d樹是低維數據的理想選擇（我認爲你自從nanoflann「主要針對2D或3D點雲進行了優化」）。

有沒有更有效的方式來獲得我所需要的東西，除了每次都通過所有k個最近鄰居？

您需要第k個最近鄰（NN），但是當爲k個NN搜索kd樹時，耗時的操作（就時間而言）是找到第一個NN（它要求您下降到第樹，從根到葉）。尋找第二個，第三個或另一個索引化的NN相對便宜，我非常懷疑它會損害性能（即從樹返回的k個NN中獲得第k個NN將成爲瓶頸）。

所以，我強烈建議你不要擔心這一步。

更好的數據結構還是更好的實現？

我不這麼認爲。我沒有使用nanoflann，但這種查詢的CGAL，它值得嘗試（但CGAL需要安裝（而不是一塊蛋糕），而nanoflann只是一個頭）。