La forma más rápida de encontrar la distancia entre dos puntos Lat / Long

227

Actualmente tengo poco menos de un millón de ubicaciones en una base de datos mysql, todas con información de longitud y latitud.

Estoy tratando de encontrar la distancia entre un punto y muchos otros puntos a través de una consulta. No es tan rápido como quiero que sea, especialmente con más de 100 golpes por segundo.

¿Hay una consulta más rápida o posiblemente un sistema más rápido que no sea mysql para esto? Estoy usando esta consulta:

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

Nota: La distancia proporcionada es en millas . Si necesita kilómetros , use en 6371lugar de 3959.

Ryan Detzel
fuente
31
La fórmula que da parece tener muchos elementos que son constantes. ¿Es posible calcular previamente los datos y almacenar esos valores también en su base de datos? Por ejemplo, 3959 * acos (cos (radianes (42.290763)) es una constante pero tiene 4 cálculos principales. En su lugar, ¿podría simplemente almacenar 6696.7837?
Peter M
1
¿O al menos pre-calcular constantes fuera de la consulta? Eso reducirá el trabajo que debe hacerse.
Peter M
2
@ Peter M Parece probable que cualquier base de datos SQL decente se optimice, por lo que se calculó solo una vez.
mhenry1384
25
Para aquellos que se preguntan, 42.290763 es la latitud y -71.35368 es la longitud del punto desde el cual calcular las distancias.
user276648
14
Solo para información, la distancia calculada por esta fórmula es en millas, no en kilómetros. Reemplace 3959 por 6371 para obtener resultados en kilómetros
Sahil

Respuestas:

115
  • Cree sus puntos utilizando Pointvalores de Geometrytipos de datos en la MyISAMtabla. A partir de Mysql 5.7.5, las InnoDBtablas ahora también admiten SPATIALíndices.

  • Crea un SPATIALíndice sobre estos puntos

  • Use MBRContains()para encontrar los valores:

    SELECT  *
    FROM    table
    WHERE   MBRContains(LineFromText(CONCAT(
            '('
            , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
            , ' '
            , @lat + 10 / 111.1
            , ','
            , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
            , ' '
            , @lat - 10 / 111.1 
            , ')' )
            ,mypoint)

, o, en MySQL 5.1y arriba:

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

Esto seleccionará todos los puntos aproximadamente dentro del cuadro (@lat +/- 10 km, @lon +/- 10km).

Esto en realidad no es una caja, sino un rectángulo esférico: segmento de la esfera unido a la latitud y la longitud. Esto puede diferir de un rectángulo simple en Franz Joseph Land , pero bastante cerca de él en la mayoría de los lugares habitados.

  • Aplique filtros adicionales para seleccionar todo dentro del círculo (no el cuadrado)

  • Posiblemente aplique un filtrado fino adicional para tener en cuenta la distancia del círculo grande (para distancias grandes)

Quassnoi
fuente
15
@Quassnoi: un par de correcciones: probablemente querrás cambiar el orden de las coordenadas a lat, long. Además, las distancias longitudinales son proporcionales al coseno de la latitud , no a la longitud. Y querrás cambiarlo de multiplicación a división, para que tu primera coordenada se corrija como @lon - 10 / ( 111.1 / cos(@lat))(y sea la segunda en el par una vez que todo esté correcto.)
M. Dave Auayan
8
ADVERTENCIA : El cuerpo de la respuesta NO ha sido editado de acuerdo con el comentario muy válido hecho por @M. Dave Auayan. Notas adicionales: Este método tiene forma de pera si el círculo de interés (a) incluye un poste o (b) se intersecta con el meridiano de longitud de +/- 180 grados. El uso también cos(lon)es preciso solo para distancias pequeñas. Ver janmatuschek.de/LatitudeLongitudeBoundingCoordinates
John Machin
3
¿Hay alguna manera de que podamos obtener una idea de lo que representan las constantes (10, 111.11, @lat, @lon, mypoint)? Supongo que el 10 es para kilómetros de distancia, @lat y @lon representan la longitud y la longitud proporcionadas, pero ¿qué representan 111.11 y mypoint en el ejemplo?
ashays
44
@ashays: hay aproximadamente 111.(1)km en un grado de latitud. mypointes el campo en la tabla que almacena las coordenadas.
Quassnoi
1
Otra corrección de error: le falta un cierre) en la penúltima línea
en
100

No es una respuesta específica de MySql, pero mejorará el rendimiento de su declaración sql.

Lo que efectivamente está haciendo es calcular la distancia a cada punto de la tabla, para ver si está dentro de las 10 unidades de un punto dado.

Lo que puede hacer antes de ejecutar este sql es crear cuatro puntos que dibujen un cuadro de 20 unidades a un lado, con su punto en el centro, es decir. (x1, y1). . . (x4, y4), donde (x1, y1) es (dado largo + 10 unidades, dado Lat + 10 unidades). . . (givenLong - 10units, givenLat -10 unidades). En realidad, solo necesitas dos puntos, arriba a la izquierda y abajo a la derecha, llámalos (X1, Y1) y (X2, Y2)

Ahora su declaración SQL usa estos puntos para excluir filas que definitivamente están a más de 10u de su punto dado, puede usar índices en las latitudes y longitudes, por lo que serán órdenes de magnitud más rápidos que los que tiene actualmente.

p.ej

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

El enfoque de cuadro puede devolver falsos positivos (puede recoger puntos en las esquinas del cuadro que están> 10u desde el punto dado), por lo que aún necesita calcular la distancia de cada punto. Sin embargo, esto nuevamente será mucho más rápido porque ha limitado drásticamente el número de puntos para probar a los puntos dentro del cuadro.

Yo llamo a esta técnica "Pensar dentro de la caja" :)

EDITAR: ¿Se puede poner esto en una declaración SQL?

No tengo idea de lo que mySql o Php es capaz, lo siento. No sé dónde es el mejor lugar para construir los cuatro puntos, o cómo podrían pasarse a una consulta mySql en Php. Sin embargo, una vez que tenga los cuatro puntos, no hay nada que le impida combinar su propia declaración SQL con la mía.

select name, 
       ( 3959 * acos( cos( radians(42.290763) ) 
              * cos( radians( locations.lat ) ) 
              * cos( radians( locations.lng ) - radians(-71.35368) ) 
              + sin( radians(42.290763) ) 
              * sin( radians( locations.lat ) ) ) ) AS distance 
from locations 
where active = 1 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

Sé que con MS SQL puedo construir una declaración SQL que declara cuatro flotantes (X1, Y1, X2, Y2) y los calcula antes de la declaración de selección "principal", como dije, no tengo idea si esto se puede hacer con MySql. Sin embargo, todavía estaría inclinado a construir los cuatro puntos en C # y pasarlos como parámetros a la consulta SQL.

Lo siento, no puedo ser más ayuda, si alguien puede responder las partes específicas de MySQL y Php de esto, no dude en editar esta respuesta para hacerlo.

Binario Worrier
fuente
44
Puede encontrar un procedimiento mysql para este enfoque en esta presentación: scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
Lucia
37
Para buscar por kilómetros en lugar de millas, reemplace 3959 con 6371.
ErichBSchulz
44
+1, gran opción; agregar el cuadro redujo mi consulta de 4s a 0.03s promedio.
jvenema
1
Aunque parezca tan lógico, ¡se reserva un premio por esta solución! En una base de datos de registro de 2 millones, la consulta pasó de 16 segundos a 0.06 segundos. Nota: ¡ Es aún más rápido (para tablas grandes) si corta el cálculo de distancia de la consulta y hace el cálculo de la distancia en su código de programa!
NLAnaconda
2
@Binary Worrier: Entonces, X1, X2 e Y1, Y2 serán Longitude Min y Max y Latitude Min y Max según el ejemplo aquí: blog.fedecarg.com/2009/02/08/… por favor avise.
Prabhat
14

La siguiente función MySQL se publicó en esta publicación de blog . No lo he probado mucho, pero por lo que obtuve de la publicación, si sus campos de latitud y longitud están indexados , esto puede funcionar bien para usted:

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(
  geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), 
  geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) 
    + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) 
    * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) 
    * 60 * 1.1515);
END $$

DELIMITER ;

Uso de la muestra:

Suponiendo una tabla llamada placescon campos latitudey longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;
Brad Parks
fuente
He intentado esto y funciona perfectamente, pero de alguna manera no me permite poner una instrucción WHERE basada en distance_from_input. ¿Alguna idea de por qué no?
Chris Visser
puede hacerlo como una subselección: seleccione * de (...) como t donde distance_from_input> 5;
Brad Parks el
2
o simplemente siga recto con: seleccione * de los lugares donde get_distance_in_miles_between_geo_locations (-34.017330, 22.809500, latitud, longitud)> 5000;
Brad Parks el
2
Metros de retorno:SELECT ROUND(((ACOS(SIN(lat1 * PI() / 180) * SIN(lat2 * PI() / 180) + COS(lat1 * PI() / 180) * COS(lat2 * PI() / 180) * COS((lnt1 - lnt2) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) * 1.609344 * 1000) AS distance
Mohammad
13

Necesitaba resolver un problema similar (filtrando filas por distancia desde un solo punto) y combinando la pregunta original con respuestas y comentarios, se me ocurrió una solución que funciona perfectamente para mí tanto en MySQL 5.6 como en 5.7.

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinateses un campo con tipo POINTy tiene un SPATIALíndice
6371es para calcular la distancia en kilómetros
56.946285es la latitud para el punto central
24.105078es la longitud para el punto central
15es la distancia máxima en kilómetros

En mis pruebas, MySQL usa el índice SPATIAL en el coordinatescampo para seleccionar rápidamente todas las filas que están dentro del rectángulo y luego calcula la distancia real para todos los lugares filtrados para excluir lugares de las esquinas de los rectángulos y dejar solo lugares dentro del círculo.

Esta es la visualización de mi resultado:

mapa

Las estrellas grises visualizan todos los puntos en el mapa, las amarillas son las que devuelve MySQL query. Las estrellas grises dentro de las esquinas del rectángulo (pero fuera del círculo) fueron seleccionadas por MBRContains()y luego deseleccionadas por la HAVINGcláusula.

Māris Kiseļovs
fuente
No puedo votar esto lo suficiente. Al buscar en una tabla con aproximadamente 5 millones de registros y un índice espacial con este método, el tiempo de búsqueda es de 0.005 segundos en un procesador A8 antiguo. Sé que 6371 se puede reemplazar con 3959 para obtener resultados en millas, pero ¿es necesario ajustar los valores de 111.133 y 111.320 o son universalmente constantes?
Wranorn el
Gran solución
SeaBiscuit
Cómo crear Point es POINT (lat, lng) o POINT (lng, lat)
user606669
2
@ user606669 Es POINT (lng, lat)
Māris Kiseļovs
Las funciones X () e Y () deberían ser ST_Y y ST_X hoy en día.
Andreas
11

si está utilizando MySQL 5.7. *, puede usar st_distance_sphere (POINT, POINT) .

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance
alriyami
fuente
1
Esta es una alternativa muy buena y fácil de leer. tenga en cuenta que el orden de los parámetros a POINT () es (lng, lat); de lo contrario, podría terminar con "cerrar" pero aún así resultados muy diferentes a los otros métodos aquí. ver: stackoverflow.com/questions/35939853/…
Andy P
9
SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

Esta es la consulta de cálculo de distancia entre puntos en MySQL, la he usado en una base de datos larga, ¡funciona perfectamente! Nota: realice los cambios (nombre de la base de datos, nombre de la tabla, columna, etc.) según sus requisitos.

Sanni Poriya
fuente
¿Qué representa el valor 1.1515? He visto una fórmula similar antes, pero usó 1.75 en lugar de 1.1515.
TryHarder
1
En respuesta a mi propia pregunta, creo que la respuesta podría estar aquí stackoverflow.com/a/389251/691053
TryHarder el
8
set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

fuente

Abhigyan
fuente
11
Por favor, cita tus fuentes. Esto es de: blog.fedecarg.com/2009/02/08/…
redburn
¿Qué es 69 en este caso? ¿Cómo hacer en caso de que tengamos el radio de la tierra?
CodeRunner
2
El kilómetro en 1 Latittude es de 111 KM. Milla en 1 Latittude es de 69 millas. y 69 millas = 111 km. Es por eso que hemos usado los parámetros en las conversiones.
CodeRunner
Había estado buscando esto por siempre. No sabía que puede ser así de simple. Muchas gracias.
Vikas
¿No sería incorrecto ya que lng_min / lng_max necesitaría usar lat_min y lat_max en las matemáticas de radio?
Ben
6
   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;
usuario3113927
fuente
5

Una función MySQL que devuelve el número de metros entre las dos coordenadas:

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

Para devolver el valor en un formato diferente, reemplace el 6371000en la función con el radio de la Tierra en su unidad de elección. Por ejemplo, kilómetros serían 6371y millas serían3959 .

Para usar la función, simplemente llámela como lo haría con cualquier otra función en MySQL. Por ejemplo, si tuviera una mesa city, podría encontrar la distancia entre cada ciudad y todas las demás ciudades:

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`
Robert
fuente
4

El código completo con detalles sobre cómo instalar como complemento MySQL está aquí: https://github.com/lucasepe/lib_mysqludf_haversine

Publiqué esto el año pasado como comentario. Como amablemente @TylerCollier me sugirió publicar como respuesta, aquí está.

Otra forma es escribir una función UDF personalizada que devuelva la distancia de Haversine desde dos puntos. Esta función puede tomar en entrada:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

Entonces podemos escribir algo como esto:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

para obtener todos los registros con una distancia inferior a 40 kilómetros. O:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

para buscar todos los registros con una distancia inferior a 25 pies.

La función principal es:

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}
Luca Sepe
fuente
3

Se puede hacer una aproximación rápida, simple y precisa (para distancias más pequeñas) con una proyección esférica . Al menos en mi algoritmo de enrutamiento obtengo un aumento del 20% en comparación con el cálculo correcto. En el código Java se ve así:

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

No estoy seguro acerca de MySQL (¡lo siento!).

Asegúrese de conocer la limitación (el tercer parámetro de afirmar Equilibrios significa la precisión en kilómetros):

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);
Karussell
fuente
3

Aquí hay una descripción muy detallada de Geo Distance Search con MySQL, una solución basada en la implementación de Haversine Formula en mysql. La descripción completa de la solución con teoría, implementación y una mayor optimización del rendimiento. Aunque la parte de optimización espacial no funcionó correctamente en mi caso. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Konstantin Voronov
fuente
3

Eche un vistazo a Geo Distance Search con MySQL , una solución basada en la implementación de Haversine Formula en MySQL. Esta es una descripción completa de la solución con teoría, implementación y una mayor optimización del rendimiento. Aunque la parte de optimización espacial no funcionó correctamente en mi caso.

Noté dos errores en esto:

  1. el uso de absen la declaración select en p8. Simplemente lo omití absy funcionó.

  2. la función de distancia de búsqueda espacial en p27 no se convierte a radianes ni multiplica la longitud por cos(latitude), a menos que sus datos espaciales estén cargados con esto en consideración (no se puede distinguir por el contexto del artículo), pero su ejemplo en p26 indica que sus datos espaciales POINTno están cargados con radianes o grados.

Richard Sandoz
fuente
0
$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";
Neeraj Sharma
fuente
0

Usando mysql

SET @orig_lon = 1.027125;
SET @dest_lon = 1.027125;

SET @orig_lat = 2.398441;
SET @dest_lat = 2.398441;

SET @kmormiles = 6371;-- for distance in miles set to : 3956

SELECT @kmormiles * ACOS(LEAST(COS(RADIANS(@orig_lat)) * 
 COS(RADIANS(@dest_lat)) * COS(RADIANS(@orig_lon - @dest_lon)) + 
 SIN(RADIANS(@orig_lat)) * SIN(RADIANS(@dest_lat)),1.0)) as distance;

Ver: https://andrew.hedges.name/experiments/haversine/

Ver: https://stackoverflow.com/a/24372831/5155484

Ver: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

NOTA: LEASTse utiliza para evitar valores nulos como un comentario sugerido en https://stackoverflow.com/a/24372831/5155484

William Desportes
fuente