Moyen le plus rapide de trouver la distance entre deux points lat / long

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

  •  06-07-2019
  •  | 
  •  

Question

J'ai actuellement un peu moins d'un million d'emplacements dans une base de données mysql, tous avec des informations de longitude et de latitude.

J'essaie de trouver la distance entre un point et de nombreux autres points via une requête. Ce n'est pas aussi rapide que je le souhaite, surtout avec plus de 100 coups par seconde.

Existe-t-il une requête plus rapide ou éventuellement un système plus rapide que mysql? J'utilise cette requête: 

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;

Remarque: la distance fournie est en Milles . Si vous avez besoin de kilomètres , utilisez 6371 au lieu de 3959 .

Était-ce utile?

La solution

  • Créez vos points en utilisant les valeurs Point des types de données Géométrie de la table MyISAM . Depuis Mysql 5.7.5, les tables InnoDB prennent également en charge les index SPATIAL .

  • Créez un index SPATIAL sur ces points

  • Utilisez MBRContains () pour rechercher les valeurs: 

    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)

, ou, dans MySQL 5.1 et supérieur: 

    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
                    )

Ceci sélectionnera tous les points approximativement dans la case (@ lat +/- 10 km, @lon +/- 10 km) .

Ce n’est en réalité pas une boîte, mais un rectangle sphérique: segment lié à la latitude et la longitude de la sphère. Cela peut différer d’un rectangle simple sur le Franz Joseph Land , mais assez proche de celui-ci dans la plupart des lieux habités.

  • Appliquez un filtrage supplémentaire pour tout sélectionner à l'intérieur du cercle (et non du carré)

  • Appliquez éventuellement un filtrage fin supplémentaire pour tenir compte de la distance du grand cercle (pour les grandes distances)

Autres conseils

Ce n'est pas une réponse spécifique à MySql, mais cela améliorera les performances de votre requête SQL.

Ce que vous êtes en train de faire, c'est calculer la distance par rapport à chaque point du tableau pour voir si elle se trouve à moins de 10 unités d'un point donné.

Ce que vous pouvez faire avant d’exécuter ce sql, est de créer quatre points qui dessinent une boîte de 20 unités d’un côté, avec votre point au centre c’est-à-dire .. (x1, y1). . . (x4, y4), où (x1, y1) est (étant donné long + 10 unités, donnéLat + 10 unités). . . (donnéLong - 10 unités, donnéLat -10 unités). En fait, vous n'avez besoin que de deux points: en haut à gauche et en bas à droite, appelez-les (X1, Y1) et (X2, Y2)

Désormais, votre instruction SQL utilise ces points pour exclure les lignes dont la taille est supérieure à 10u de votre point donné. Elle peut également utiliser des index sur les latitudes. longitudes, les ordres de grandeur seront donc plus rapides que ce que vous avez actuellement.

par exemple 

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

L'approche case peut renvoyer des faux positifs (vous pouvez récupérer des points situés dans les coins de la case qui sont> 10u à partir du point donné). Vous devez donc encore calculer la distance de chaque point. Cependant, cela sera à nouveau beaucoup plus rapide car vous avez considérablement limité le nombre de points à tester aux points situés dans la zone.

J’appelle cette technique "Penser à l’intérieur de la boîte" :)

MODIFIER: cela peut-il être inséré dans une instruction SQL?

Je n'ai aucune idée de ce que mySql ou Php est capable de faire, désolé. Je ne sais pas où le meilleur endroit est de construire les quatre points, ou comment ils pourraient être passés à une requête mySql en Php. Cependant, une fois que vous avez les quatre points, rien ne vous empêche de combiner votre propre instruction SQL avec la mienne. 

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;

Je sais avec MS SQL que je peux créer une instruction SQL qui déclare quatre flottants (X1, Y1, X2, Y2) et les calcule avant le "principal". comme je l'ai dit, je n'ai aucune idée si cela peut être fait avec MySql. Cependant, je serais toujours enclin à construire les quatre points en C # et à les transmettre en tant que paramètres à la requête SQL.

Désolé, je ne peux pas vous aider davantage si quelqu'un peut répondre à MySQL & amp; Des parties spécifiques à cela, n'hésitez pas à modifier cette réponse pour le faire.

Vérifiez cette présentation pour une bonne réponse. Fondamentalement, il montre les deux approches différentes montrées dans les commentaires, avec une explication détaillée sur pourquoi / quand vous devriez utiliser l’une ou l’autre et pourquoi le "dans la boîte" le calcul peut être très intéressant.

Recherche géolocalisée avec MySQL

sur cet article de blog , la fonction MySql suivante a été publiée. Je ne l'ai pas beaucoup testé, mais d'après ce que j'ai tiré de l'article, si vos champs de latitude et de longitude sont indexés , cela pourrait bien fonctionner pour vous: 

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 ;

Exemple d'utilisation: En supposant une table appelée Lieux avec des champs latitude & amp; longitude:

  

sélectionnez get_distance_in_miles_between_geo_locations (-34.017330,   22.809500, latitude, longitude) en tant que distance_de_passe depuis des lieux;

all accroché à ce message 

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

C’est la requête de calcul de distance entre les points de MySQL, je l’ai utilisée dans une longue base de données, ça marche parfaitement! Remarque: effectuez les modifications (nom de la base de données, nom de la table, colonne, etc.) selon vos besoins. 

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

source

si vous utilisez MySQL 5.7. *, vous pouvez utiliser 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;

Le code complet contenant des informations détaillées sur l'installation d'un plug-in MySQL est disponible à l'adresse suivante: https://github.com/lucasepe / lib_mysqludf_haversine

J'ai posté cette dernière année en tant que commentaire. Depuis la gentillesse de @TylerCollier m'a suggéré de poster comme réponse, la voici.

Une autre méthode consiste à écrire une fonction UDF personnalisée qui renvoie la distance haversine entre deux points. Cette fonction peut prendre en entrée: 

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

Nous pouvons donc écrire quelque chose comme ceci: 

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

chercher tous les enregistrements avec une distance inférieure à 40 kilomètres. Ou: 

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

pour récupérer tous les enregistrements dont la distance est inférieure à 25 pieds.

La fonction principale est: 

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

Une approximation rapide, simple et précise (pour de plus petites distances) peut être réalisée avec une projection sphérique . Au moins dans mon algorithme de routage, j'obtiens une augmentation de 20% par rapport au calcul correct. En code Java, cela ressemble à: 

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

Pas sûr de MySQL (désolé!).

Assurez-vous de connaître la limitation (le troisième paramètre d’assertEquals signifie l’exactitude en kilomètres): 

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

Voici une description très détaillée de Geo Distance Search avec MySQL, une solution basée sur la mise en œuvre de Haversine Formula dans mysql. La description complète de la solution avec théorie, implémentation et optimisation des performances. Bien que la partie optimisation spatiale ne fonctionne pas correctement dans mon cas. http://www.scribd.com/doc/2569355/Geo -Distance-Recherche-avec-MySQL

Prenez connaissance de la recherche de géolocalisation avec MySQL , une solution basé sur la mise en œuvre de Haversine Formula to MySQL. C'est une solution complète description avec théorie, mise en œuvre et optimisation ultérieure des performances. Bien que la partie optimisation spatiale ne fonctionne pas correctement dans mon cas.

J'ai remarqué deux erreurs dans ceci:

  1. l'utilisation de abs dans l'instruction select sur p8. J'ai juste omis abs et cela a fonctionné.

  2. la fonction de distance de recherche spatiale sur p27 ne convertit pas en radians ni ne multiplie la longitude par cos (latitude) , à moins que ses données spatiales ne soient chargées avec cela en considération (impossible à déterminer à partir du contexte de article), mais son exemple sur p26 indique que ses données spatiales POINT ne sont pas chargées en radians ou en degrés.

Une fonction MySQL qui renvoie le nombre de mètres entre les deux coordonnées: 

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

Pour renvoyer la valeur dans un format différent, remplacez 6371000 dans la fonction par le rayon de la Terre dans votre choix d'unité. Par exemple, les kilomètres seraient 6371 et les miles, 3959 .

Pour utiliser cette fonction, appelez-la comme toute autre fonction de MySQL. Par exemple, si vous avez une table ville , vous pouvez trouver la distance entre chaque ville et toutes les villes: 

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`

Je devais résoudre un problème similaire (filtrer les lignes en fonction de la distance d'un point) et en combinant une question originale avec des réponses et des commentaires, je trouvais une solution parfaitement adaptée à MySQL 5.6 et 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
Les

coordonnées sont des champs de type POINT et ont un index SPATIAL

6371 sert à calculer la distance en kilomètres
56.946285 est la latitude du point central
24.105078 est la longitude du point central
10 est la distance maximale en kilomètres

Dans mes tests, MySQL utilise SPATIAL index sur le champ coordonnées pour sélectionner rapidement toutes les lignes situées dans un rectangle, puis calcule la distance réelle de tous les emplacements filtrés afin d'exclure des emplacements des coins de rectangles et de ne laisser que des emplacements à l'intérieur. cercle.

Ceci est la visualisation de mon résultat:

map

Les étoiles grises visualisent tous les points de la carte, les étoiles jaunes sont celles renvoyées par la requête MySQL. Les étoiles grises situées à l'intérieur des coins du rectangle (mais hors du cercle) ont été sélectionnées par MBRContains () , puis désélectionnées par la clause HAVING .

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

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

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

Voir: http://www.plumislandmedia.net/mysql/ haversine-mysql-most-loc /

REMARQUE: LEAST est utilisé pour éviter les valeurs null en tant que commentaire suggéré dans 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";
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top