首页 / 知识

关于算法：计算2个城市之间的距离

2023-04-12 23:15:00

Calculating Distance Between 2 Cities

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

如果您需要考虑地球的曲率，则大圆距就是您想要的。 Wikipedia上的文章可能比我在解释该公式的工作方式上做得更好，并且还有一个航空公式页面，其中涵盖了更多细节。

但是，公式只是难题的第一部分，如果您需要对任意城市进行这项工作，则需要一个位置数据库来获取经纬度。幸运的是，尽管有商业数据库可用(请问Google)，您可以从Geonames.org免费获得。因此，一般而言，查找所需的两个城市，获取经纬度坐标，然后将其插入公式中，如Wikipedia Worked Example中所述。

其他建议：

要获得完整的商业解决方案，
有使用的PC Miler
许多卡车公司
计算运费。
调用Google Maps(或其他)api。如果您每天需要执行许多请求，请考虑将结果缓存在服务器上。
同样重要的是，如果您认为需要对数据进行分组，则考虑为城市，郊区，城镇等建立等效数据库。但是，这真的很复杂，您可能找不到适合您的问题的"一刀切"的解决方案。

最后但并非最不重要的一点是，Joel不久前写了一篇有关此问题的文章，因此您可以开始：新功能：求职

您使用Haversine公式。

使用SQL Server 2008中的地理类型非常容易做到这一点。

1 2	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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#!/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

如果要说的是真实球形地球(例如地球)上两个真实城市之间的最短距离，则需要较大的圆周距离。

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

1
2
3
4

// 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()。

请注意，您可能可以在一行中执行此操作，并且编译器可能会将其减少为与上面的代码等效：

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

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

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

我用距离
如此简单干净

我同意，一旦获得信息，如果它不会改变，请以某种方式存储它。 @Marko Tinto感谢您的T-SQL示例。对于那些无法访问SQL Server或希望使用其他方法的用户：如果需要高精度，请查看Wikipedia在Vincenty算法上的条目以获取更多信息。我相信有一个js实现，可以(如果尚未实现)很容易地移植到其他语言。同样，在该页面的底部是geoLibrary的链接，它的准确性比Vincenty算法高1000倍(如果您的数据很好，那可能很重要)。

为什么要使用Vincenty方法？因为地球不是一个完美的球体，所以像这样的方法可以输入更准确的长轴和短轴来对地球进行建模。

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