algorithm - 计算 2 个城市之间的距离

Question

如何计算两个城市之间的距离？

score 33 · Accepted Answer

如果您需要考虑地球的曲率，大圆距离就是您要寻找的。维基百科的文章可能比我更好地解释了公式的工作原理，还有这个航空公式页面涵盖了更详细的内容。

公式只是难题的第一部分，如果您需要对任意城市进行这项工作，您将需要一个位置数据库来获取纬度/经度。幸运的是，您可以从Geonames.org免费获得它，尽管有可用的商业数据库（询问 google）。因此，一般而言，查找您想要的两个城市，获取纬度/经度坐标并将它们插入公式中，如Wikipedia Worked Example中所示。

其他建议：

对于完整的商业解决方案，许多货运公司使用PC Miler来计算运费。
调用 Google Maps（或其他）api。如果您每天需要执行许多请求，请考虑将结果缓存在服务器上。
如果您认为您需要对数据进行分组，那么考虑为城市、郊区、城镇等建立一个等价数据库也是非常重要的。但是，这变得非常复杂，您可能找不到针对您的问题的万能解决方案。

最后但并非最不重要的一点是，Joel 不久前写了一篇关于这个问题的文章，所以你去吧：新功能：求职

score 9 · Accepted Answer

9

您使用Haversine 公式。

于 2008-08-22T21:42:08.260 回答

score 2 · Accepted Answer

在 SQL Server 2008 中使用地理类型很容易做到这一点。

SELECT geography::Point(lat1, lon1, 4326).STDistance(geography::Point(lat2, lon2, 4326))
-- computes distance in meters using eliptical model, accurate to the mm

4326 是 WGS84 椭球地球模型的 SRID

score 1 · Accepted Answer

您可以使用A*算法找到这两个城市之间的最短路径，这样您就可以获得距离。

score 1 · Accepted Answer

如果您在飞机上工作并且想要“乌鸦飞翔”的欧几里得距离：

// Cities are points x0,y0 and x1,y1 in kilometers or miles or Smoots[1]
dx = x1 - x0;
dy = y1 - y0;
dist = sqrt(dx*dx + dy*y);

不需要三角函数！只是勾股定理和平方总是正的事实，所以你不需要 dx = abs(x1 - x0) 等来获得一个正数来传递给 sqrt()。

请注意，您可能可以在一行中执行此操作，并且编译器可能会将其简化为上述等效代码：

dist = sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));

[1] http://en.wikipedia.org/wiki/Smoot

score 1 · Accepted Answer

如果您谈论的是真实球形行星（如地球）上两个真实城市之间的最短距离，您需要大圆距离。

score 1 · Accepted Answer

您可以从 google map api 获取两个城市之间的距离。这是它在 Python 中的实现

#!/usr/bin/python
import requests
from sys import argv 
def get_distance(origin,destination):
    gmap='http://maps.googleapis.com/maps/api/distancematrix/json'
    payload={"origins":origin,"destinations":destination,"sensor":'false' }
    try:
        a=requests.get(gmap,params=payload)
        data = a.json()
        origin = str(data['origin_addresses'][0])
        destination= str(data['destination_addresses'][0])
        distance = data['rows'][0]['elements'][0]['distance']['text']
        return distance,origin,destination
    except Exception,e:
        print "The %s or %destination does not exists :(" %(origin,destination)
        exit()

if __name__=="__main__":
    if len(argv)<3:
        print "sorry Check the format"
    else:
        origin=argv[1]
        destination=argv[2]
        distance,origin,destination=get_distance(origin,destination)
        print "%s ---> %s    :   %s" %(origin,destination,distance)

示例链接：https ://gist.github.com/sarathsp06/cf063e47bcc515b51c84

score 0 · Accepted Answer

0

您找到城市的纬度/经度，然后对纬度/经度坐标使用距离估计算法。

于 2008-08-22T21:41:18.153 回答

score 0 · Accepted Answer

如果你需要一个代码示例，我想我有一个我可以在家里挖出来，但是像以前的许多答案一样，你需要一个 long / lat db 来进行计算

score 0 · Accepted Answer

最好使用查找表来获得两个城市之间的距离。

这是有道理的，因为 * 计算距离 a 的公式计算量很大。 * 城市之间的距离不太可能改变。

因此，除非您的需求非常具体（例如来自卫星或某些地形算法或其他东西的地形图），否则您实际上应该将城市列表和它们之间的距离保存到表格中并根据需要进行查找。

score 0 · Accepted Answer

我最近一直在做很多工作。我发现 SQL2008 的新特性确实让这一切变得简单。我可以在不到一秒的时间内找到 100k 记录表中 Xkm 的所有点......不太破旧。

与 vincenty 公式（椭球假设，地球是什么）相比，我测试中的大圆（球形假设）方法大约相差 2.5 英里。

真正的诀窍是获得经纬度..为此我正在使用谷歌。

score 0 · Accepted Answer

@Jared - 对您的代码示例的小修正。第一个代码示例的最后一行应为：

dist = sqrt(dx*dx + dy*dy);

score 0 · Accepted Answer

我同意，一旦你有了信息，如果它不会改变，以某种方式存储它。@Marko Tinto 感谢 T-SQL 示例。对于那些无法访问 SQL Server 或更喜欢其他方法的人：如果您需要高精度，请查看Wikipedia 关于 Vincenty 算法的条目以获取更多信息。我相信有一个 js 实现，它（如果还没有的话）很容易移植到其他语言。此外，在该页面的底部是一个到 geolib 的链接，它声称比 Vincenty 算法精确 1000 倍（如果你有这么好的数据，这可能很重要）。

你为什么要使用像文森蒂方法这样的东西？因为地球不是一个完美的球体，这样的方法允许输入更准确的主轴和次轴来模拟地球。

score 0 · Accepted Answer

0

我用距离如此简单和干净

于 2012-06-04T22:48:46.820 回答

algorithm - 计算 2 个城市之间的距离

14 回答 14

Related

Reference