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

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.

• 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)

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.

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;

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:

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.

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 * 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

   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;

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`

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

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

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

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.

$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";

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