Algorithme pour trouver tous les emplacements Latitude Longitude à une certaine distance d’un emplacement Lat Lng donné

Étant donné une firebase database de lieux avec des emplacements Latitude + Longitude, tels que 40.8120390, -73.4889650, comment trouver tous les emplacements à une distance donnée d’un emplacement spécifique?

Il ne semble pas très efficace de sélectionner tous les emplacements dans la firebase database et de les parcourir un par un, en obtenant la distance par rapport à l’emplacement de départ pour voir s’ils se trouvent à la distance spécifiée. Existe-t-il un bon moyen de réduire les emplacements initialement sélectionnés à partir de la firebase database? Une fois que j’ai (ou non?) Un ensemble de lieux restreint, est-ce que je les passe toujours un par un pour vérifier la distance ou y a-t-il une meilleure façon?

Le langage dans lequel je fais cela n’a pas vraiment d’importance. Merci!

Commencez par comparer la distance entre les latitudes. Chaque degré de latitude est à environ 69 miles (111 kilomètres). L’aire de répartition varie (en raison de la forme légèrement ellipsoïdale de la Terre) de 68,703 milles (110,567 km) à l’équateur à 69,407 (111,699 km) aux pôles. La distance entre deux endroits sera égale ou supérieure à la distance entre leurs latitudes.

Notez que ce n’est pas vrai pour les longitudes – la longueur de chaque degré de longitude dépend de la latitude. Cependant, si vos données sont limitées à une zone (un seul pays par exemple), vous pouvez également calculer des limites minimales et maximales pour les longitudes.


Continuez avec un calcul de distance rapide et de faible précision qui suppose une terre sphérique:

La grande distance de cercle d entre deux points de coordonnées {lat1, lon1} et {lat2, lon2} est donnée par:

d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2)) 

Une formule mathématiquement équivalente, qui est moins sujette à l’erreur d’arrondissement pour les courtes distances, est la suivante:

 d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 + cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2)) 

d est la distance en radians

 distance_km ≈ radius_km * distance_radians ≈ 6371 * d 

(6371 km est le rayon moyen de la terre )

Les exigences de calcul de cette méthode sont mimimales. Cependant, le résultat est très précis pour les petites distances.


Ensuite, si la distance est plus ou moins longue, utilisez une méthode plus précise.

GeographicLib est l’implémentation la plus précise que je connaisse, bien que la formule inverse de Vincenty puisse également être utilisée.


Si vous utilisez un SGBDR, définissez la latitude comme clé primaire et la longitude comme clé secondaire. Recherchez une plage de latitude ou une plage de latitude / longitude, comme décrit ci-dessus, puis calculez les distances exactes pour le jeu de résultats.

Notez que les versions modernes de tous les principaux SGBDR prennent en charge les types de données géographiques et les requêtes en mode natif.

Basé sur la latitude, la longitude et la distance que vous souhaitez trouver, la requête sql est indiquée ci-dessous.

 SELECT * FROM( SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t WHERE distance <= @distance 

@latitude et @longitude sont la latitude et la longitude du point. La latitude et la longitude sont les colonnes du tableau des distances. Valeur de pi est 22/7

Les extensions SIG PostgreSQL peuvent être utiles – comme dans, il peut déjà implémenter une grande partie des fonctionnalités que vous envisagez d’implémenter.

Essayez ceci pour une bonne solution: la recherche de géolocalisation

Tank Yogihosting

J’ai dans ma firebase database un groupe de tables d’Open Streep Maps et j’ai testé avec succès.

La distance fonctionne bien en mètres.

 SET @orig_lat=-8.116137; SET @orig_lon=-34.897488; SET @dist=1000; SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100; 

Vous pouvez trouver ces questions utiles:

  • Formules pour calculer la proximité géographique
  • Longueur maximale d’un degré de latitude / longitude décimal?

Comme mentionné biziclop, une sorte d’arborescence mésortingque serait probablement votre meilleure option. J’ai l’habitude d’utiliser des arbres kd et des arbres quadruples pour effectuer ces sortes d’interrogations à distance et ils sont incroyablement rapides. ils ne sont pas si difficiles à écrire. Je suggérerais de regarder l’une de ces structures, car elles vous permettent également de répondre à d’autres questions intéressantes telles que «quel est le point le plus proche de mes données par rapport à cet autre point?

Ce dont vous avez besoin est la recherche spatiale. Vous pouvez utiliser la recherche Solr Spatial . Il a également intégré un type de données lat / long, cochez ici .

Vous pouvez convertir la latitude-longitude au format UTM, qui est le format mésortingque qui peut vous aider à calculer les distances. Ensuite, vous pouvez facilement décider si le point tombe dans un emplacement spécifique.

Puisque vous dites que n’importe quelle langue est acceptable, le choix naturel est PostGIS:

 SELECT * FROM places WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres; 

Si vous souhaitez utiliser le datum WGS, vous devez définir $spheroid sur 'SPHEROID["WGS 84",6378137,298.257223563]'

En supposant que vous avez indexé des places par la colonne geom , cela devrait être raisonnablement efficace.

vous pouvez vérifier cette équation je pense que cela aidera

 SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;