我怎样才能快速估计两个(纬度,经度)点之间的距离?

我希望能够估计两个(纬度,经度)点之间的距离。 我想低调,因为这将是A *图search,我希望它是快速的 。 这些点将相距最多800公里。

Haversine公式在Python中的答案(两个GPS点之间的方位和距离)提供了可以回答你的问题的Python实现。

使用下面的实现,我旧笔记本电脑上进行了不到1秒的100,000次迭代 。 我认为你的目的应该是足够的。 但是,在优化性能之前,您应该分析任何内容。

 从math导入弧度,cos,sin,asin,sqrt
高半胱氨酸(lon1,lat1,lon2,lat2):
     “””
    计算两点之间的大圆距离 
    在地球上(以十进制度数表示)
     “””
     #将十进制度转换为弧度 
     lon1,lat1,lon2,lat2 =地图(弧度,[lon1,lat1,lon2,lat2])
     #haversine公式 
     dlon = lon2  -  lon1 
     dlat = lat2  -  lat1 
     a = sin(dlat / 2)** 2 + cos(lat1)* cos(lat2)* sin(dlon / 2)** 2
     c = 2 * asin(sqrt(a)) 
     #以公里为单位的地球半径为6371
     km = 6371 * c
    返回公里 

要低估haversine(lat1, long1, lat2, long2) * 0.90或任何你想要的因素。 我不明白如何将错误引入低估是有用的。

由于距离相对较小,可以使用等距离近似。 这个近似比使用Haversine公式更快。 因此,要获得从参考点(lat1 / lon1)到您正在testing的点(lat2 / lon2)的距离,请使用下面的公式。 重要提示:您需要将所有经纬度点转换为弧度:

 R = 6371 // radius of the earth in km x = (lon2 - lon1) * cos( 0.5*(lat2+lat1) ) y = lat2 - lat1 d = R * sqrt( x*x + y*y ) 

由于“R”以公里计,距离“d”将以公里为单位。

参考: http : //www.movable-type.co.uk/scripts/latlong.html

速度的一个想法是将长/纬度坐标转换成3D(x,y,z)坐标。 在预处理点之后,使用点之间的欧几里得距离作为实际距离的快速计算下冲。

为了获得最大的速度,你可以创build一个类似彩虹表的坐标距离。 这听起来像你已经知道你正在使用的领域,所以它似乎预先计算它们可能是可行的。 然后,你可以加载最近的组合,并使用它。

例如在美国大陆,经度为55度,纬度为20度,总数为1100点。 所有可能的组合之间的距离是握手问题 ,由(n-1)(n)/ 2或大约600k组合来回答。 这似乎是非常可行的存储和检索。 如果您提供更多有关您的要求的信息,我可以更具体一些。

请使用下面的代码。

 def distance(lat1, lng1, lat2, lng2): #return distance as meter if you want km distance, remove "* 1000" radius = 6371 * 1000 dLat = (lat2-lat1) * math.pi / 180 dLng = (lng2-lng1) * math.pi / 180 lat1 = lat1 * math.pi / 180 lat2 = lat2 * math.pi / 180 val = sin(dLat/2) * sin(dLat/2) + sin(dLng/2) * sin(dLng/2) * cos(lat1) * cos(lat2) ang = 2 * atan2(sqrt(val), sqrt(1-val)) return radius * ang