空间查询点的第 k 个最近邻点
Spatial querying for k-th closest neighbour of a point
我正在研究一种算法，该算法反复需要从某个给定查询点到第 k 个最近点的（欧几里得）距离，所有查询点都取自点向量。另外，我反复需要找到一个点的给定半径内的所有点。
我正在考虑使用 nanoflann 库中的 k-d 树。但是，knnSearch() 函数 returns 所有 k 最近的邻居，我不需要。 （不过 radiusSearch() 函数很适合我）。
除了每次都通过所有 k 个最近的邻居之外，是否有更有效的方法来获得我需要的东西？更好的数据结构还是更好的实现？ （我正在使用 C++。）
I'm thinking of using k-d trees
2D 或 3D 的绝佳选择。
k-d 树是低维数据的不错选择（我假设你有，因为 nanoflann 是 "mostly optimized for 2D or 3D point clouds."）。
Is there a more efficient way to get what I need, other than slogging through all the k nearest neighbors every time?
您需要 k-th 最近邻 (NN)，但是在 k-d 树中搜索 k 个 NN 时，代价高昂的操作（就时间而言）是找到第一个 NN（这需要你从树上下来，从根到叶）。
找到第二个、第三个或另一个索引 NN 相对便宜，我非常怀疑它会损害性能（即从树返回的 k 个 NN 中得到 k-th NN 将是瓶颈）。
所以，我强烈建议你不要担心这一步。
A better data structure or a better implementation?
我不这么认为。我没有使用过 nanoflann，但是 CGAL 用于此类查询，值得一试（但是 CGAL 需要安装（不是小菜一碟），而 nanoflann 只是一个 header 包含） .
我正在研究一种算法，该算法反复需要从某个给定查询点到第 k 个最近点的（欧几里得）距离，所有查询点都取自点向量。另外，我反复需要找到一个点的给定半径内的所有点。
我正在考虑使用 nanoflann 库中的 k-d 树。但是，knnSearch() 函数 returns 所有 k 最近的邻居，我不需要。 （不过 radiusSearch() 函数很适合我）。
除了每次都通过所有 k 个最近的邻居之外，是否有更有效的方法来获得我需要的东西？更好的数据结构还是更好的实现？ （我正在使用 C++。）
I'm thinking of using k-d trees
2D 或 3D 的绝佳选择。
k-d 树是低维数据的不错选择（我假设你有，因为 nanoflann 是 "mostly optimized for 2D or 3D point clouds."）。
Is there a more efficient way to get what I need, other than slogging through all the k nearest neighbors every time?
您需要 k-th 最近邻 (NN)，但是在 k-d 树中搜索 k 个 NN 时，代价高昂的操作（就时间而言）是找到第一个 NN（这需要你从树上下来，从根到叶）。
找到第二个、第三个或另一个索引 NN 相对便宜，我非常怀疑它会损害性能（即从树返回的 k 个 NN 中得到 k-th NN 将是瓶颈）。
所以，我强烈建议你不要担心这一步。
A better data structure or a better implementation?
我不这么认为。我没有使用过 nanoflann，但是 CGAL 用于此类查询，值得一试（但是 CGAL 需要安装（不是小菜一碟），而 nanoflann 只是一个 header 包含） .