Confronto tra coordinate latitudine e longitudine

https://stackoverflow.com/questions/35870

09-06-2019
|

Domanda

Ho un elenco di oltre 15mila coordinate di latitudine e longitudine.Date le coordinate X,Y, qual è il modo più veloce per trovare le coordinate più vicine nell'elenco?

Soluzione

Dovrai utilizzare una costruzione geometrica chiamata a Diagramma di Voronoi.Questo divide l'aereo in un numero di aree, una per ogni punto, che comprendono tutti i punti più vicini a ciascuno dei punti indicati.

Il codice per gli algoritmi esatti per creare il diagramma di Voronoi e organizzare le ricerche della struttura dei dati è troppo grande per adattarsi a questa piccola casella di modifica.:)

@Linor:Questo è essenzialmente ciò che faresti dopo aver creato un diagramma di Voronoi.Ma invece di creare una griglia rettangolare, puoi scegliere linee di divisione che corrispondano strettamente alle linee del diagramma di Voronoi (in questo modo otterrai meno aree che attraversano le linee di divisione).Se dividi ricorsivamente il tuo diagramma di Voronoi a metà lungo la migliore linea di divisione per ciascun sottodiagramma, puoi quindi eseguire una ricerca ad albero per ogni punto che desideri cercare.Ciò richiede un po' di lavoro iniziale ma fa risparmiare tempo in seguito.Ogni ricerca sarebbe nell'ordine del log N dove N è il numero di punti.16 confronti sono molto meglio di 15.000!

Altri suggerimenti

L'ho fatto una volta per un sito web.Cioè.trova il rivenditore entro 50 miglia dal tuo codice postale.Ho usato il calcolo del circolo massimo per trovare le coordinate che erano 50 miglia a nord, 50 miglia a est, 50 miglia a sud e 50 miglia a ovest.Questo mi ha dato un lat minimo e massimo e un lungo minimo e massimo.Da lì poi ho eseguito una query sul database:

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

Poiché alcuni di questi risultati saranno ancora a più di 50 miglia di distanza, ho utilizzato il file formula del cerchio massimo ancora una volta su quella piccola lista di coordinate.Poi ho stampato l'elenco insieme alla distanza dal bersaglio.

Naturalmente, se si desidera cercare punti vicini alla linea del cambio data internazionale o ai poli, ciò non funzionerà.Ma funziona benissimo per le ricerche all'interno del Nord America!

Il concetto generale che stai descrivendo è ricerca del vicino più vicino, ed esistono tutta una serie di tecniche che si occupano di risolvere questo tipo di query, esattamente o approssimativamente.L'idea di base è utilizzare una tecnica di partizionamento spaziale per ridurre la complessità da O(n) per query a (approssimativamente) O(log n) per query.

I KD-Tree e le loro varianti sembrano funzionare molto bene, ma funzioneranno anche i quad-tree.La qualità di queste ricerche dipende dal fatto che il tuo set di 15.000 punti dati sia statico (non stai aggiungendo molti punti dati al set di riferimento).Il lavoro di Mount e Arya su Vicino più vicino approssimativo La libreria è facile da usare e da capire, anche senza una buona conoscenza di matematica.Ti dà anche una certa flessibilità nei tipi e nelle tolleranze delle tue query.

Dipende piuttosto da quante volte vuoi farlo e da quali risorse sono disponibili: se stai eseguendo il test una volta, le tecniche O (log N) sono buone.Se lo fai mille volte su un server, costruire una tabella di ricerca bitmap sarebbe più veloce, fornendo il risultato direttamente o come prima fase.2 GB di bitmap possono mappare l'intero mondo lat-lon con un valore di 32 bit a 0,011 gradi pixel (1,2 km all'equatore) e dovrebbero essere sufficienti in memoria.Se stai visualizzando solo un singolo paese o puoi escludere i poli, puoi avere una mappa più piccola o una risoluzione più elevata.Per 15.000 punti probabilmente hai una mappa molto più piccola: l'ho prima dimensionata come primo passo per eseguire ricerche da lat-lon a codice postale, che richiede una risoluzione più elevata.A seconda dei requisiti, utilizzi il valore mappato per puntare direttamente al risultato o a un breve elenco di candidati (il che consentirebbe una mappa più piccola, ma richiede una maggiore elaborazione successiva: non sei più nel territorio di ricerca O(1) ).

Non hai specificato cosa intendi per più veloce.Se vuoi ottenere rapidamente la risposta senza scrivere alcun codice, darei il file filtro raggio gpsbabel fa.

Sulla base dei tuoi chiarimenti, utilizzerei una struttura di dati geometrica come un albero KD o un albero R.MySQL ha un tipo di dati SPATIAL che fa questo.Altri linguaggi/framework/database dispongono di librerie per supportarlo.Fondamentalmente, una struttura di dati di questo tipo incorpora i punti in un albero di rettangoli e ricerca l'albero utilizzando un raggio.Dovrebbe essere abbastanza veloce e credo che sia più semplice che costruire un diagramma di Voronoi.Immagino che ci sia una soglia al di sopra della quale preferiresti le prestazioni aggiuntive di un diagramma di Voronoi, quindi sarai pronto a pagare la complessità aggiuntiva.

Questo può essere risolto in diversi modi.Per prima cosa affronterei questo problema generando un file Delaunay rete che collega i punti più vicini tra loro.Ciò può essere ottenuto con il comando v.delaunay nell'applicazione GIS open source ERBA.Potresti completare il problema in GRASS usando uno dei tanti moduli di analisi di rete nell'ERBA.In alternativa, è possibile utilizzare l'RDBMS spaziale gratuito PostGIS per fare le domande a distanza.Le query spaziali PostGIS sono considerevolmente più potenti di quelle in MySQL, poiché non sono vincolate alle operazioni BBOX.Per esempio:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

Poiché stai utilizzando Longitudine e Latitudine, probabilmente vorrai utilizzare il file Funzioni della distanza sferoidale.Con un indice spaziale, PostGIS si adatta molto bene a set di dati di grandi dimensioni.

Anche se crei un diagramma di Voronoi, ciò significa comunque che devi confrontare le tue coordinate x, y con tutte le 15mila aree create.Per renderlo più semplice, la prima cosa che mi è venuta in mente è stata quella di creare una sorta di griglia sui possibili valori, in modo da poter facilmente posizionare e coordinare x/y in una delle caselle di una griglia, se lo stesso è Fatto ciò per l'elenco delle aree, dovresti ridurre rapidamente i possibili candidati per il confronto (poiché la griglia sarebbe più rettangolare, è possibile che un'area si trovi in più posizioni della griglia).

L’ottimizzazione prematura è la radice di tutti i mali.

Le coordinate 15K non sono poi così tante.Perché non ripetere le coordinate 15K e vedere se si tratta davvero di un problema di prestazioni?Potresti risparmiare molto lavoro e forse non diventa mai troppo lento per accorgertene.

Quanto è grande l'area su cui sono distribuite queste coordinate?A che latitudine sono?Quanta precisione hai bisogno?Se sono abbastanza vicini tra loro, probabilmente puoi ignorare il fatto che la Terra è rotonda e trattarla semplicemente come un piano cartesiano invece di scherzare con la geometria sferica e le distanze ortodromiche.Naturalmente, man mano che ci si allontana dall'equatore, i gradi di longitudine diventano più piccoli rispetto ai gradi di latitudine, quindi una sorta di fattore di scala potrebbe essere appropriato.

Inizia con una formula di distanza abbastanza semplice e una ricerca con forza bruta e vedi quanto tempo ci vorrà e se i risultati sono sufficientemente accurati prima di diventare fantasioso.

Grazie a tutti per le risposte

@Tom, @Chris Upchurch:Le coordinate sono abbastanza vicine tra loro e si trovano in un'area relativamente piccola di circa 800 kmq.Immagino di poter supporre che la superficie sia piatta.Devo elaborare le richieste più e più volte e la risposta dovrebbe essere abbastanza veloce per una maggiore esperienza web.

Una griglia è molto semplice e molto veloce.Fondamentalmente è solo una serie di elenchi 2D.Ciascuna voce dell'array rappresenta i punti che rientrano in una cella della griglia.Molto semplice impostare la griglia:

for each point p
  get cell that contains p
  add point to that cell's list

ed è molto facile cercare le cose:

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

Alejo

Giusto per essere controcorrente, intendi vicino alla distanza o al tempo (di guida)?In un'area urbana guiderei volentieri 5 miglia (5 minuti) in autostrada piuttosto che 4 miglia (20 minuti stop and go) in un'altra direzione.

Pertanto, se si tratta di una metrica "più vicina" di cui hai bisogno, esaminerei i database GIS con le metriche del tempo di viaggio.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow