找到最接近给定点的最快方法是什么？

Question

找到数据数组中给定点的最近点的最快方法是什么？

例如,假设我有一个A3D点阵列(像往常一样坐标x,y和z)和点(x_p,y_p,z_p).如何找到A(x_p,y_p,z_p)中的最近点？

据我所知,最慢的方法是使用线性搜索.还有更好的解决方案吗？

可以添加任何辅助数据结构.

Answer 1

您可以在八月份组织您的积分.然后你只需要搜索一个小子集.

八叉树是一个相当简单的数据结构,您可以自己实现(这将是一个宝贵的学习经验),或者您可能会找到一些有用的库来帮助您前进.

Answer 2

如果您正在进行一次性最近邻居查询,那么线性搜索确实是您可以获得的最佳选择.这当然是假设数据没有预先构建.

但是,如果您要进行大量查询,则会有一些空间分区数据结构.这些结构需要一些预处理才能形成结构,但是可以非常快速地回答最近邻查询.

由于您正在处理3D空间,我建议您查看八叉树或kd树.Kd树更通用(它们适用于任意维度)并且如果您实现合适的平衡算法(例如,中位数效果很好),则可以比八叉树更有效,但是八叉树更容易实现.

ANN是一个使用这些数据结构的很棒的库,但也允许近似最近邻查询,这些查询明显更快,但误差很小,因为它们只是近似值.如果无法获取任何错误,请将错误绑定为0.

Answer 3

我建议 KD-tree 可以正常工作。也适用于最近邻搜索。