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

Question

我试图找到一种有效的方法，可能O（log（n））在给定地理坐标的情况下查找给定数量的最靠近查询位置的位置（ lat，lon）。

查询点未预先知道，但我可以提前组织其他位置以优化查询。

有没有这样的方法，还是必须订购和裁剪所有同行的列表？

Answer 1

如果您的表面满足三角形不等式，即是一个euklidian空间，那么对空间索引重新排序的最佳算法是空间填充曲线或怪物曲线。它将二维问题简化为一维问题，并离散化并解决空间的适应问题。类似位置的查找类似于O（log（n））。你可以在尼克空间索引希尔伯特曲线四叉树博客中找到一篇好文章。我也建议看看n元单调的灰色代码。我写了一个php实现，包括4个方向的希尔伯特曲线和摩尔曲线。