Str*_*ide 5 algorithm geocoding latitude-longitude
注意还有其他类似的问题,但1)我不想依赖在线服务,2)我正在寻找一个干净的算法解决方案.
我有一个城市及其纬度/经度的数据库.我正在寻找一种方法,给定一个随意的纬度/经度,找到最近的城市.
到目前为止我能想到的解决方案:
当然,明显的蛮力解决方案是使用大圆距离公式计算所有可能的距离.这也需要很长时间并且是O(n).
对KD-Tree算法的修改可能有效,但我不知道如何修改此算法以在非笛卡尔坐标中工作,就像lat/lon的情况一样.如果这有帮助,我们可以假设墨卡托投影.
使用地理数据库,如PostgreSQL.这对我来说不适用.
任何见解？
关于2：从范围开始[-90..90, -180, 180]。
唯一的细微差别是，当您将上面的整个范围分成四个较小的矩形并计算从当前点到每个矩形的距离时，您需要考虑“溢出”的可能性。（该点(0, -179)比(0, 179)从经度看来更接近）
我还假设您没有靠近南极/北极的城市。