有效地排序位置的地理距离从查询点

Question

我试图找到一种有效的方法，可能是O(log(n))，找到给定数量的最接近查询位置的位置给定其地理坐标(lat, lon)。

查询点是事先不知道的，但我可以提前组织其他位置，以便优化查询。

是否有这样一种方法，或者我必须排序并裁剪所有节点的列表?

Answer 1

如果你的曲面满足三角形不等式，即是一个欧几里得空间，那么重新排序空间索引的最佳算法是空间填充曲线或怪物曲线。它将二维问题简化为一维问题，并将其离散化，解决了空间的寻址问题。查找类似位置的时间大概是O(log(n))你可以在nick空间索引hilbert曲线四叉树博客上找到一篇很好的文章。我建议也看看n元单调灰色编码。我自己写了一个php实现，包括四个方向的希尔伯特曲线和摩尔曲线。