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

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

Author: fread2281, 2013-04-01
Source

5 answers

Las respuestas a Fórmula de Haversine en Python (Rumbo y Distancia entre dos puntos GPS) proporcionan implementaciones de Python que responden a su pregunta.

Usando la implementación siguiente I realizó 100,000 iteraciones en menos de 1 segundo en una computadora portátil más antigua. Creo que para sus propósitos esto debería ser suficiente. Sin embargo, debe perfilar cualquier cosa antes de optimizar el rendimiento. {[0]}

Subestimar haversine(lat1, long1, lat2, long2) * 0.90 o cualquier factor que quieras. Yo no vea cómo introducir el error a su subestimación es útil.

 93
Author: Aaron D,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-10-18 23:40:06

Dado que la distancia es relativamente pequeña, puede usar la aproximación de 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 fórmula a continuación. Nota importante: necesita 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 )

Puesto que 'R' está en km, la distancia 'd' estará en km.

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

 31
Author: TreyA,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-04-01 11:06:20

Una idea para la velocidad es transformar las coordenadas long/lat en coordenadas 3D (x,y,z). Después de preprocesar los puntos, utilice la distancia euclidiana entre los puntos como una subestimación calculada rápidamente de la distancia real.

 7
Author: Raymond Hettinger,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-04-01 02:56:34

Para la velocidad máxima, se podría crear algo así como una tabla arco iris para las distancias de coordenadas. Parece que ya conoces el área con la que estás trabajando, por lo que parece que pre-computarlos podría ser factible. Entonces, podrías cargar la combinación más cercana y simplemente usar eso.

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

 3
Author: Aaron D,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-04-01 03:55:39

Utilice 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
 0
Author: uher,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-08-02 07:26:23