我正在尝试找到一种方法,它可以高效地(可能是 O(log(n)))找到给定数量的最接近查询位置的给定地理坐标(纬度、经度)的位置。
查询点事先不知道,但我可以提前整理其他位置,以便优化查询。
是否有这样的方法,或者我是否必须订购并裁剪所有同行的列表?
最佳答案
如果您的曲面满足三角不等式,即是欧氏空间,则重新排序空间索引的最佳算法是空间填充曲线或怪物曲线。它将二维问题简化为一维问题并离散化并求解空间的寻址。类似位置的查找类似于 O(log(n))。您可以在 nick spatial index hilbert curve quadtree blog 找到一篇不错的文章。我建议也看看 n 元单调格雷码。我自己写了一个 php 实现,包括 4 个方向的希尔伯特曲线和摩尔曲线。
关于algorithm - 根据与查询点的地理距离有效地对位置进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8537306/