点的第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只是一个头）。