Algoritmo per trovare tutte le posizioni di latitudine della latitudine entro una certa distanza da una determinata posizione di lat lng

Dato un database di luoghi con posizioni Latitude + Longitude, ad esempio 40.8120390, -73.4889650, come trovo tutte le posizioni all’interno di una determinata distanza di una posizione specifica?

Non sembra molto efficiente selezionare tutte le posizioni dal DB e quindi esaminarle una alla volta, ottenendo la distanza dalla posizione iniziale per vedere se si trovano entro la distanza specificata. C’è un buon modo per restringere i luoghi inizialmente selezionati dal DB? Una volta che ho (o non?) Un insieme ristretto di locazioni, le passo ancora una per una per controllare la distanza, o c’è un modo migliore?

Il linguaggio in cui lo faccio non ha molta importanza. Grazie!

Inizia confrontando la distanza tra le latitudini. Ogni grado di latitudine è di circa 69 miglia (111 chilometri) di distanza. La gamma varia (a causa della forma leggermente ellissoidale della terra) da 68.703 miglia (110.567 km) all’equatore a 69.407 (111.699 km) ai poli. La distanza tra due posizioni sarà uguale o superiore alla distanza tra le loro latitudini.

Si noti che questo non è vero per le longitudini – la lunghezza di ciascun grado di longitudine dipende dalla latitudine. Tuttavia, se i dati sono limitati ad un’area (ad esempio un singolo paese), è ansible calcolare anche i limiti minimi e massimi per le longitudini.


Continua eseguirà calcoli a bassa precisione e distanza veloce che presuppongono la terra sferica:

La grande distanza del cerchio d tra due punti con coordinate {lat1, lon1} e {lat2, lon2} è data da:

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

Una formula matematicamente equivalente, che è meno soggetta a errori di arrotondamento per brevi distanze è:

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

d è la distanza in radianti

 distance_km ≈ radius_km * distance_radians ≈ 6371 * d 

(6371 km è il raggio medio della terra )

I requisiti computazionali di questo metodo sono mimici. Tuttavia, il risultato è molto preciso per le piccole distanze.


Quindi, se è in una determinata distanza, più o meno, utilizzare un metodo più accurato.

GeographicLib è l’implementazione più accurata che conosca, anche se può essere usata anche la formula inversa di Vincenty .


Se si utilizza un RDBMS, impostare la latitudine come chiave primaria e la longitudine come chiave secondaria. Query per un intervallo di latitudine o per un intervallo di latitudine / longitudine, come descritto sopra, quindi calcolare le distanze esatte per il set di risultati.

Si noti che le versioni moderne di tutti i principali RDBMS supportano i tipi di dati geografici e le query in modo nativo.

In base alla latitudine, longitudine dell’utente corrente e alla distanza che si desidera trovare, la query sql viene fornita di seguito.

 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 e @longitude sono la latitudine e la longitudine del punto. Latitudine e longitudine sono le colonne della tabella delle distanze. Il valore di pi è 22/7

Le estensioni GIS di PostgreSQL potrebbero essere utili, poiché potrebbe già implementare gran parte delle funzionalità che stai pensando di implementare.

Prova questo per una buona soluzione: ricerca di geolocalizzazione

Tank’s Yogihosting

Ho nel mio database un gruppo di tabelle di Open Streep Maps e ho avuto successo.

La distanza funziona bene in metri.

 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; 

Potresti trovare queste domande utili:

  • Formule per calcolare la geo prossimità
  • Lunghezza massima di un grado decimale di latitudine / longitudine?

Come menzionato da biziclop, una sorta di albero dello spazio metrico sarebbe probabilmente la scelta migliore. Ho esperienza nell’usare alberi kd e quad per eseguire questo tipo di query e sono sorprendentemente veloci; anche loro non sono così difficili da scrivere. Ti suggerisco di esaminare una di queste strutture, in quanto ti consentono anche di rispondere ad altre domande interessanti come “qual è il punto più vicino nel mio set di dati a quest’altro punto?”

Ciò di cui hai bisogno è la ricerca spaziale. È ansible utilizzare la ricerca spaziale Solr . Ha anche ottenuto il datatype lat / long, controlla qui .

È ansible convertire la latitudine-longitudine in formato UTM che è il formato metrico che può aiutare a calcolare le distanze. Quindi puoi facilmente decidere se il punto cade in una posizione specifica.

Dal momento che dici che qualsiasi lingua è accettabile, la scelta naturale è PostGIS:

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

Se si desidera utilizzare il datum WGS, è necessario impostare $spheroid su 'SPHEROID["WGS 84",6378137,298.257223563]'

Supponendo di aver indicizzato i places base alla colonna geom , ciò dovrebbe essere ragionevolmente efficiente.

puoi controllare questa equazione penso che ti sarà d’aiuto

 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;