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

StackOverflow https://stackoverflow.com/questions/1006654

  •  06-07-2019
  •  | 
  •  

Pregunta

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

¿Fue útil?

Solución

  • Cree sus puntos utilizando los valores de Point de los tipos de datos Geometry en la tabla MyISAM . A partir de Mysql 5.7.5, las tablas InnoDB ahora también admiten índices SPATIAL .

  • Cree un índice SPATIAL en 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.1 y superior: 

    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 un cuadro, 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)

Otros consejos

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

Lo que está haciendo efectivamente 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 en 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 instrucció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 & amp; longitudes, por lo que serán órdenes de magnitud más rápido de lo que tiene actualmente.

por ejemplo 

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 será mucho más rápido porque ha limitado drásticamente la cantidad de puntos a probar en 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 declare cuatro flotantes (X1, Y1, X2, Y2) y los calcule antes del " main " seleccione la declaración, 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 el MySQL & amp; Porciones específicas de PHP de esto, siéntase libre de editar esta respuesta para hacerlo.

Verifique esta presentación para obtener una buena respuesta. Básicamente, muestra los dos enfoques diferentes que se muestran en los comentarios, con una explicación detallada de por qué / cuándo debe usar uno u otro y por qué el " en el cuadro " el cálculo puede ser muy interesante.

Búsqueda de distancia geográfica con MySQL

en esta publicación de blog , se publicó la siguiente función MySql. 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 ;

Ejemplo de uso: Suponiendo una tabla llamada Lugares con campos latitud & amp; longitud:

  

seleccione get_distance_in_miles_between_geo_locations (-34.017330,   22.809500, latitud, longitud) como la distancia desde la entrada desde los lugares;

all enganchado a esta publicación 

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. 

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

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

   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;

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 incluir entradas: 

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 buscar 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;
}

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 Equivalentes 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);

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

Lea Búsqueda de distancia geográfica con MySQL , una solución basado en la implementación de Haversine Formula en MySQL. Esta es una solución completa Descripción con teoría, implementación y posterior 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 abs en la instrucción select en p8. Acabo de omitir abs y funcionó.

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

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 6371000 en la función con el radio de la Tierra en la unidad que elija. Por ejemplo, los kilómetros serían 6371 y las millas serían 3959 .

Para usar la función, simplemente llámela como lo haría con cualquier otra función en MySQL. Por ejemplo, si tuviera una tabla 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`

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í en MySQL 5.6 y 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

coordenadas es un campo con el tipo POINT y tiene un índice SPATIAL
6371 es para calcular la distancia en kilómetros
56.946285 es la latitud para el punto central
24.105078 es la longitud del punto central
10 es la distancia máxima en kilómetros

En mis pruebas, MySQL usa el índice SPATIAL en el campo coordenadas 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 círculo.

Esta es la visualización de mi resultado:

mapa

Las estrellas grises visualizan todos los puntos en el mapa, las estrellas 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 cláusula HAVING .

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 -arest-loc /

NOTA: LEAST se usa para evitar valores nulos como comentario sugerido en https: // stackoverflow. com / a / 24372831/5155484 

$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";
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top