我正在研究一种算法，该算法反复需要从某个给定查询点到第k个最近点的(欧几里得)距离，这些距离全部取自点 vector 。另外，我反复需要查找点的给定半径内的所有点。
我正在考虑使用nanoflann库中的k-d树。但是，knnSearch()函数返回所有k个最近的邻居，我不需要。 (不过radiusSearch()函数适合我)。
除了每次遍历所有k个最近的邻居之外，还有什么更有效的方法来获取我需要的东西？更好的数据结构还是更好的实现？ (我正在使用C++。)
最佳答案
2D或3D的绝佳选择。
k-d树是处理低维数据的好选择(我想您已经拥有了，因为nanoflann“大部分针对2D或3D点云进行了优化。”)。
您需要第k个最近邻(NN)，但是在kd树中搜索k个NN时，代价高昂的操作(就时间而言)是找到第一个NN(要求您从树的下方一直下降)根到叶子)。
找到第二，第三或其他索引的NN相对便宜，我高度怀疑这会损害性能(即从树返回的k个NN中获取第k个NN将成为瓶颈)。
因此，我强烈建议您不要为此担心。
我不这么认为。我没有使用nanoflann，但是CGAL用于这种查询，值得一试(但是CGAL需要安装(不是小菜一碟)，而nanoflann只是一个头文件)。
关于c++ - 点的第k个最近邻居的空间查询，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46013343/