Algorithme pour trouver toutes les positions de Longitude de Latitude à une certaine distance d'un emplacement lat Lng
étant donné une base de données d'endroits avec Latitude + Longitude emplacements, tels que 40.8120390, -73.4889650, Comment pourrais-je trouver tous les emplacements à une distance donnée d'un endroit spécifique?
il ne semble pas très efficace de sélectionner tous les emplacements à partir de la base de données et puis de passer par eux un par un, en obtenant la distance de l'emplacement de départ pour voir si elles sont à l'intérieur de la distance spécifiée. Y a-t-il un bon moyen de réduire les emplacements initialement sélectionnés à partir de DB? Une fois que j'ai (ou ne l'est pas?) une rétréci vers le bas emplacements, dois-je quand même passer par un par un pour vérifier la distance, ou est-il un meilleur moyen?
la langue dans laquelle je fais ceci n'a pas vraiment d'importance. Merci!
11 réponses
commencez par Comparer la distance entre les latitudes. Chaque degré de latitude est à environ 69 milles (111 kilomètres) l'un de l'autre. La portée varie (en raison de la forme légèrement ellipsoïde de la terre) de 68.703 miles (110.567 km) à l'Équateur à 69.407 (111.699 km) aux pôles. La distance entre deux emplacements sera égale ou plus grande que la distance entre leurs latitudes.
notez que ce n'est pas vrai pour les longueurs - 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 calculer une limite minimale et maximale pour les longitudinales aussi bien.
Continuer une faible précision, rapide calcul de la distance que suppose sphérique de la terre:
la distance D du grand cercle 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))
A formule mathématiquement équivalente, qui est moins sujette à l'erreur d'arrondissement pour les distances courtes est:
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 )
cette méthode les exigences en matière de calcul sont minimales. Cependant le résultat est très précis pour de petites distances.
alors, si elle est dans un plus ou moins à distance, utilisez une méthode plus précise.
GeographicLib est l'implémentation la plus précise que je connaisse, bien que Vincenty inverse formula puisse aussi être utilisé.
si vous utilisez un RDBMS, définissez la latitude comme clé primaire et la longitude comme clé secondaire. Requête pour une gamme de latitude, ou pour une gamme de latitude / longitude, comme décrit ci-dessus, puis calculer les distances exactes pour l'ensemble de résultats.
notez que les versions modernes de toutes les principales RDBMSs prennent en charge les types de données géographiques et les requêtes nativement.
basé sur la latitude de l'utilisateur actuel, la longitude et la distance que vous voulez trouver,la requête sql est donné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
PostgreSQL GIS extensions pourrait être utile - comme dans, Il peut déjà mettre en œuvre une grande partie de la fonctionnalité que vous envisagez de mettre en œuvre.
Essayez ceci pour la bonne solution: Géolocalisation de Recherche
Tanks Yogihosting
j'ai dans ma base de données un goups de tables de Open Streep Maps et j'ai testé avec succès.
travaux de Distance amende 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;
comme biziclop l'a mentionné, une sorte d'arbre spatial métrique serait probablement votre meilleure option. J'ai l'expérience de l'utilisation de KD-trees et quad trees pour faire ce genre de requêtes de portée et ils sont étonnamment rapides; ils ne sont pas non plus si difficile à écrire. Je suggère d'examiner l'une de ces structures, car elles vous permettent également de répondre à d'autres questions intéressantes comme "Quel est le point le plus proche de cet autre point dans mon ensemble de données?"
ce qu'il vous faut, c'est une recherche spatiale. Vous pouvez utiliser Solr de la recherche Spatiale . Il a également Lat / long Type de données intégré dans, vérifier ici .
vous pouvez convertir latitude-longitude au format UTM qui est le format métrique qui peut vous aider à calculer les distances. Ensuite, vous pouvez facilement décider si point tombe dans un endroit 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 voulez utiliser WGS datum, vous devez définir $spheroid à 'SPHEROID["WGS 84",6378137,298.257223563]'
en supposant que vous avez indexé places par la colonne geom , cela devrait être raisonnablement efficace.
, vous pouvez vérifier cette équation je pense que ça va aider
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;