¿Cómo puedo estimar rápidamente la distancia entre dos puntos (latitud, longitud)?

Quiero poder obtener una estimación de la distancia entre dos puntos (latitud, longitud). Quiero un poco de profundidad, ya que esto será para la búsqueda de gráficos A * y quiero que sea rápido . Los puntos estarán a lo sumo a 800 km de distancia.

Las respuestas a Haversine Formula en Python (orientación y distancia entre dos puntos GPS) proporcionan implementaciones de Python que responden a su pregunta.

Usando la implementación a continuación, realicé 100,000 iteraciones en menos de 1 segundo en una computadora portátil más antigua. Creo que para tus propósitos esto debería ser suficiente. Sin embargo, debe hacer un perfil de cualquier cosa antes de optimizar el rendimiento.

 from math import radians, cos, sin, asin, sqrt def haversine(lon1, lat1, lon2, lat2): """ Calculate the great circle distance between two points on the earth (specified in decimal degrees) """ # convert decimal degrees to radians lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2]) # haversine formula dlon = lon2 - lon1 dlat = lat2 - lat1 a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 c = 2 * asin(sqrt(a)) # Radius of earth in kilometers is 6371 km = 6371* c return km 

Para subestimar la haversine(lat1, long1, lat2, long2) * 0.90 o cualquier factor que desee. No veo por qué es útil introducir el error en su subestimación.

Como la distancia es relativamente pequeña, puede usar la aproximación de la distancia equirectangular. Esta aproximación es más rápida que usar la fórmula de Haversine. Por lo tanto, para obtener la distancia desde su punto de referencia (lat1 / lon1) hasta el punto que está probando (lat2 / lon2), use la siguiente fórmula. Nota importante: debe convertir todos los puntos lat / lon a radianes:

 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 ) 

Como ‘R’ está en km, la distancia ‘d’ estará en km.

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

Una idea para la velocidad es transformar el largo / lat coordinado en coordenadas 3D (x, y, z). Después de preprocesar los puntos, use la distancia euclidiana entre los puntos como un subimpulso calculado rápidamente de la distancia real.

Para una velocidad máxima, puedes crear algo así como una tabla de arco iris para distancias de coordenadas. Parece que ya conoce el área en la que está trabajando, por lo que parece que el cálculo previo puede ser factible. Entonces, podrías cargar la combinación más cercana y simplemente usarla.

Por ejemplo, en los Estados Unidos continentales, la longitud es un intervalo de 55 grados y la latitud es 20, lo que sería 1100 puntos de números enteros. La distancia entre todas las combinaciones posibles es un problema de apretón de manos que se responde con (n-1) (n) / 2 o con combinaciones de aproximadamente 600k. Eso parece bastante factible para almacenar y recuperar. Si proporciona más información sobre sus requisitos, podría ser más específico.

Si la distancia entre los puntos es relativamente pequeña (de metros a pocos km), uno de los enfoques rápidos podría ser

 from math import cos, sqrt def qick_distance(Lat1, Long1, Lat2, Long2): x = Lat2 - Lat1 y = (Long2 - Long1) * cos((Lat2 + Lat1)*0.00872664626) return 111.138 * sqrt(x*x + y*y) 

Lat, Long están en radianes, distancia en km.

La desviación de la distancia de Haversine es del orden del 1%, mientras que la ganancia de velocidad es más de ~ 10x.

0.00872664626 = 0.5 * pi / 180,

111.138: es la distancia que corresponde a 1 grado en Ecuador, puede reemplazarlo con su valor mediano como aquí https://www.cartographyunchained.com/cgsta1/ o reemplazarlo con una tabla de búsqueda simple.

Por favor use el siguiente código.

 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 

Para calcular una distancia entre dos puntos u simplemente puede usar la biblioteca mpu.haversine_distance () , como esto:

 >>> import mpu >>> munich = (48.1372, 11.5756) >>> berlin = (52.5186, 13.4083) >>> round(mpu.haversine_distance(munich, berlin), 1) >>> 504.2