c++ - 空间查询点的第 k 个最近邻点

Question

我正在研究一种算法，该算法反复需要从某个给定查询点到第 k 个最近点的(欧几里德)距离，所有这些都取自点 vector 。此外，我反复需要找到一个点的给定半径内的所有点。

我正在考虑使用 nanoflann 中的 k-d TreeMap 书馆。但是，knnSearch() 函数返回我不需要的所有 k 个最近的邻居。 (不过，radiusSearch() 函数非常适合我)。

除了每次都通过所有 k 个最近的邻居之外，是否有更有效的方法来获得我需要的东西？更好的数据结构还是更好的实现？ (我正在使用 C++。)

Answer 1

I'm thinking of using k-d trees

2D 或 3D 的绝佳选择。

k-d 树是低维数据的一个很好的选择(我假设你有，因为 nanoflann “主要针对 2D 或 3D 点云进行了优化。”)。

Is there a more efficient way to get what I need, other than slogging through all the k nearest neighbors every time?

您需要第 k 个最近邻 (NN)，但是当在 k-d 树中搜索 k 个 NN 时，代价高昂的操作(就时间而言)是找到第一个 NN(这需要您沿着树向下，所有从根到叶子的方式)。

找到第二个、第三个或另一个索引 NN 相对便宜，我非常怀疑它会损害性能(即从树返回的 k 个 NN 中获取第 k 个 NN 将成为瓶颈)。

因此，我强烈建议您不要担心这一步。

A better data structure or a better implementation?

我不这么认为。我没有用过 nanoflann，但是 CGAL对于这种查询，值得一试(但是 CGAL 需要安装(不是小菜一碟)，而 nanoflann 只是一个 header 包含)。