2009-05-14 13 views
7

Desidero creare un grande database di coordinate GPS che può essere interrogato dicendo "Restituire tutte le coordinate che si trovano entro 'n' metri di [questa coordinata]".Memorizzazione e interrogazione delle coordinate GPS in modo efficace

Ho bisogno che sia il più efficiente possibile, quindi il looping di tutte le coordinate nel database e il calcolo di una coordinata entro 'n' metri non sarebbe una soluzione desiderata.

Esiste una soluzione più semplice?

Grazie

risposta

2

V'è il supporto a SQL Server 2008 per la memorizzazione spatial data. Non ho mai lavorato con me stesso, ma so che è possibile creare query del tipo desiderato.

0

Se è possibile avere la vostra scelta di DB, mi sento di raccomandare lo stesso di rwwilden e utilizzare SQL 2008 con le sue capacità di dati spaziali. Se non è possibile utilizzare quella soluzione o quella che include l'interrogazione spaziale, è possibile dare un'occhiata al documento di Microsoft su Hierarchical Triangular Mesh e implementare tali elementi. L'SDK per MSSQL '05 è stato fornito con un'intera soluzione per HTM out-of-the-box, quindi è possibile prenderlo e convertirlo in qualsiasi piattaforma si stia utilizzando.

EDIT:

Ecco più in dettaglio document spiegare HTM e di attuazione. Ovviamente puoi convertire nel tuo DB di scelta. È possibile trovare il codice sorgente in un'implementazione HTM completa nell'SDK per il 2005.

0

I database GIS (MS PostgreSQL ecc.) Implementano effettivamente alcune strutture dati per le ricerche di regione bidimensionali o tridimensionali (spatial indices). La più semplice struttura è l'indice della griglia, quindi i diversi alberi di ricerca (kd-tree, quad-tree) con R-tree come il più frequentemente utilizzato (un B-tree generalizzato per più dimensioni). Questi metodi sembrano adeguati.

Un indice di griglia di base (partizionare lo spazio in celle di griglia e cercare solo nelle celle vicine) può essere implementato facilmente e può ridurre il tempo di ricerca logaritmico. Gli alberi di ricerca sono un po 'più difficili da implementare, ma ci sono molte implementazioni open-source per molti linguaggi di programmazione. Tuttavia, nella maggior parte dei casi l'indicizzazione della griglia è sufficientemente efficiente.

6

Solitamente eseguo questo tipo di query utilizzando lat/lon. Usando la geometria sferica, puoi mettere un riquadro di delimitazione attorno a un punto specifico. Ad esempio, supponiamo di avere un punto (X, Y) che desideri tutte le coordinate entro 1 miglio (conversione in metri che lascerò come esercizio per il lettore). È possibile determinare un riquadro di delimitazione di (X-1, Y-1), (X + 1, Y + 1). Quindi interrogare il database dei punti utilizzando l'operatore BETWEEN (SELEZIONA foo FROM bar DOVE LAT TRA X-1 E X + 1 E LON TRA Y-1 E Y + 1). Quindi esegui il calcolo della distanza di dettaglio per "arrotondare gli angoli" del riquadro di delimitazione.

L'avvertenza è che le linee di longitudine sono più vicine nella parte superiore della sfera, in modo da ottenere risultati distorti il ​​più lontano possibile dall'equatore. Ma serve comunque a filtrare rapidamente i set di risultati.

Google "Great Circle Distance" per i calcoli.

MODIFICA: Ci sono 0,167469 gradi di longitudine per miglio (in realtà varia da 0,167469 a 0,014564) e 0,014483 gradi di latitudine per miglio. Quindi il riquadro di selezione è (lat - (miles * 0.014483), lon - (miles * 0.167469)), (lat + (miles * 0.014483), lon + (miles * 0.167469))

0

Seguito su Erich - se hai la tua scelta usa PostGIS (postgresql) è gratuito e open source, le domande che stai descrivendo molto rapidamente, girano su quasi tutte le piattaforme, e ho fatto menzionare che è gratuito?

0

Se si vuole evitare un'estensione GIS, ho adattato le funzioni da this post a Postgres SQL:

create or replace function change_in_lat(miles numeric) 
returns double precision as $$ 
with v as (select 
    3960.0 as earth_radius, 
    180/pi() as radians_to_degrees 
) select (miles/earth_radius) * radians_to_degrees from v; 
$$ language sql 
returns null on null input; 

create or replace function change_in_long(lat numeric, miles numeric) 
returns double precision as $$ 
with v as (select 
    3960.0 as earth_radius, 
    pi()/180 as degrees_to_radians, 
    180/pi() as radians_to_degrees 
) select (
    miles/(earth_radius * cos(lat * degrees_to_radians)) 
    ) * radians_to_degrees from v; 
$$ language sql 
returns null on null input; 

utilizzando quelli che si possono fare alcune circostanti quadrati query:

--find all "a"s within 25 miles of any "b" 
select * from a join b on (
a.gpslat between 
    b.gpslat - change_in_lat(25) and b.gpslat + change_in_lat(25) 
and a.gpslong between 
    b.gpslong - change_in_long(b.gpslat::numeric, 25) 
    and b.gpslong + change_in_long(b.gpslat::numeric, 25) 
); 

se si usato frequentemente abbastanza sono sicuro che trasformare le dichiarazioni tra una singola funzione sarebbe facile. Con questo però non ho mai fatto nessuna domanda "entro raggio".

Per qualcosa di più complicato, probabilmente vorrai un'estensione GIS come hanno detto altre risposte. PostGIS è buono, ma ho trovato che molte delle funzioni specifiche di gis possono essere difficili da ottenere e, a meno che non si utilizzino indici bounding-box, le query spaziali potrebbero richiedere un giorno se il set di dati è sufficientemente grande. Ma il compromesso della complessità è sicuramente valsa la pena per tutte le cose fantasiose, come l'output dei dati in formato geojson, ecc.