La forma más rápida de encontrar la distancia entre dos puntos de latitud y longitud

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 mediante una consulta. No es tan rápido como quiero, especialmente con más de 100 golpes por segundo.

¿Existe 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 está en Millas . Si necesita Kilómetros , utilice 6371en lugar de 3959.

Jun 17 '09 19:06 Ryan Detzel

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

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

Lo que puede hacer antes de ejecutar este SQL es crear cuatro puntos que dibujen un cuadro de 20 unidades de lado, con su punto en el centro, es decir. (x1,y1). . . (x4, y4), donde (x1,y1) es (dadolong + 10 unidades, dadoLat + 10unidades). . . (dadoLong - 10 unidades, dadoLat -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 latitudes y longitudes, por lo que serán órdenes de magnitud más rápidos que lo que tiene actualmente.

p.ej

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

El método del cuadro puede arrojar falsos positivos (puede seleccionar puntos en las esquinas del cuadro que están a > 10u del 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 la cantidad de puntos para probar a los puntos dentro del cuadro.

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

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

No tengo idea de lo que es capaz mySql o Php, lo siento. No sé cuál es el mejor lugar para construir los cuatro puntos, ni cómo se podrían pasar a una consulta mySql en Php. Sin embargo, una vez que tengas los cuatro puntos, no hay nada que te impida combinar tu 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 crear 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 me inclinaría por crear los cuatro puntos en C# y pasarlos como parámetros a la consulta SQL.

Lo siento, no puedo ser de 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.

Jun 17 '2009 12:06 Binary Worrier

Necesitaba resolver un problema similar (filtrar filas por distancia desde un solo punto) y al combinar 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 SPATIALíndice
6371es para calcular la distancia en kilómetros
56.946285es la latitud del punto central
24.105078es la longitud del punto central
15es la distancia máxima en kilómetros

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

Esta es la visualización de mi resultado:

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

Aug 20 '2018 14:08 Māris Kiseļovs

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

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 muestra:

Suponiendo una tabla llamada placescon campos latitude& longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;

Jun 11 '2012 17:06 Brad Parks

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

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance

Nov 07 '2017 14:11 alriyami