Come faccio a cercare in modo efficiente tutti i punti di riferimento entro un intervallo di un determinato punto di riferimento?

Da SQL Server 2008, c'è un geografia tipo di dati che memorizza le posizioni (coppie lat / lon) e semplifica la scrittura di query relative alla posizione.

Esiste una risposta StackOverflow esistente che ne discute in profondità.

Una query di base per trovare i 7 elementi più vicini :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Una query di base per trovare tutto all'interno 100 m (seconda risposta alla domanda)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100

Utilizza un database con supporto per le domande GIS (sistemi di informazioni geografiche) . La maggior parte dei database supporta questa soluzione o ha estensioni, ma i dettagli saranno specifici del database (in la loro risposta , Flater mostra la sintassi per SQL server).

Se è necessario implementare tali query all'interno dell'applicazione, è possibile implementare una struttura dati che consenta query spaziali, ad es. un albero k-d . Questo è come un albero di ricerca binario, eccetto che ogni livello delle partizioni dell'albero su una diversa dimensione di coordinate. Ciò consente di limitare la ricerca a un insieme più piccolo di candidati fattibili. In pratica, traduci la ricerca "raggio di 10 km" in limiti per ciascuna dimensione di coordinate e stringi i limiti mentre ricorri nell'albero.

Sì, c'è un modo migliore. Devi utilizzare un indice spaziale . Questi indici organizzano metadati sulle geometrie per filtrare molto rapidamente le geometrie molto lontane, risparmiando un sacco di cicli della CPU evitando i calcoli che descrivi. Non dovresti preoccuparti di implementarne uno tu stesso, poiché tutti i principali database relazionali forniscono un tipo di geometria spaziale e indici da utilizzare con essi.

• PostGIS (l'estensione GIS per PostgreSQL) utilizza R-Trees: link (tipo GiST)
• SQL Server utilizza gli indici di griglia: link
• Oracle utilizza R-Trees: link
• MySQL utilizza R-Trees: link

Quello che vuoi esaminare sono le query "a distanza" (query per le geometrie entro una certa distanza da qualche altra geometria). Si tratta di problemi molto standard e molto risolti e sono possibili in tutti i database di cui sopra (e integrati in diversi):

• PostGIS: ST_DWithin
• SQL Server: STDistance ( Non è chiaro che l'uso dell'indice sulla versione di geografia 3D di questa funzione sia supportato)
• Oracle: SDO_WITHIN_DISTANCE (Questo non dice esplicitamente che attiverà l'uso dell'indice. Vorrei controllare il piano di query. Potrebbe essere necessario applicare un SDO_FILTER per ottenere l'uso dell'indice.)
• MySQL: continua a capirlo.

Soluzione temporanea per l'attivazione dell'indice di utilizzo

Nel caso peggiore in cui si riscontrano problemi nel far sì che il sistema utilizzi l'indice spaziale con queste query, è possibile aggiungere un filtro aggiuntivo. Dovresti creare un riquadro di delimitazione quadrato con lati di lunghezza 2 * (distanza di ricerca) centrati nel punto di ricerca e confrontare i riquadri di delimitazione delle geometrie della tabella con che prima di controllare la distanza effettiva. Questo è ciò che PostGIS ' ST_DWithin sopra fa internamente comunque.

Distanza in GIS

Mentre gli indici spaziali sono fantastici e assolutamente la soluzione giusta per il tuo problema, il calcolo della distanza può diventare logicamente complicato. In particolare, devi preoccuparti di quale proiezione (fondamentalmente tutti i parametri per il sistema di coordinate) i tuoi dati sono memorizzati. La maggior parte delle proiezioni 2D (cose diverse dai sistemi di coordinate angolari come le varie proiezioni lat / long ) distorcono significativamente la lunghezza. Ad esempio, la proiezione Web Mercator (quella utilizzata da Google, Bing e ogni altro fornitore di mappe di base principali) espande le aree e le distanze sempre di più man mano che la posizione si allontana dall'equatore . Potrei sbagliarmi dato che non sono formalmente istruito in GIS, ma il meglio che ho visto per le proiezioni 2D sono alcuni specifici che promettono le distanze corrette da un singolo, punto costante nel mondo intero. (No, non è pratico utilizzare una proiezione diversa per ogni query, il che renderebbe inutilizzabili gli indici.)

La linea di fondo è che è necessario assicurarsi che la matematica sia accurata. Il modo più semplice per farlo in una prospettiva di sviluppo è utilizzare le proiezioni angolari (spesso definite "geografiche") e le funzioni che supportano il calcolo matematico utilizzando un modello sferoidale, ma questi calcoli sono leggermente più costosi rispetto alle controparti 2D. e alcuni DB potrebbero non supportare l'indicizzazione. Se riesci a ottenere una prestazione accettabile usando questi, però, questa è probabilmente la strada da percorrere. Un'altra opzione comune è rappresentata dalle proiezioni regionali (come le zone UTM) che consentono di correggere sia le distanze che le aree se i dati sono limitati a una particolare parte del mondo. Ciò che è meglio per la tua app dipenderà dalle tue esigenze specifiche, ma tieni presente che devi pensarci e magari imparare un po 'a riguardo.

Questo vale anche se non si utilizzano indici spaziali incorporati. I tuoi dati hanno qualche proiezione a prescindere dalla tecnologia o dalla tecnica che stai attualmente utilizzando o che utilizzerai in futuro, e al momento sta già influenzando tutte le query e i calcoli che stai facendo.

Sarei d'accordo sul fatto che, se possibile, utilizzare un supporto specifico in un database sia il modo più ragionevole per farlo.

Tuttavia, se dovessi farlo su un database senza supporto specifico, inizierei interrogando per un quadrato che racchiude il circolo ad es. (y > (y1 - rad)) AND (y < (y1 + rad)) AND (x > (x1 - rad)) AND (x < (x1 + rad)). Supponendo che i tuoi punti abbiano una distribuzione approssimativa pari a quella di un quadrato, otterrai le tue partite vere più il 30% in più di false corrispondenze. Puoi quindi estrarre le false corrispondenze.