Come posso dividere il globo in piccole griglie in modo che mi consenta di assegnare ogni posizione lat / long a una griglia? [chiuso]

Question

Al fine di calcolare le posizioni più vicine rappresentate da latitudine / longitudine, stavo considerando di dividere la mappa in piccole griglie, circa 100x100 metri. In sostanza ogni punto verrebbe assegnato a una griglia.

Comprendo che potrei invece utilizzare anche indici spaziali con MySQL ecc., ma sto pianificando di utilizzare un database non relazionale come Cassandra in cui sarebbe difficile eseguire l'indicizzazione su oggetti spaziali e quindi un qualche tipo di tecnica di approssimazione della griglia potrebbe sii pulito.

Quale sarebbe il modo migliore per creare un tale sistema a griglia e mappare le posizioni spaziali 2D su di esso?

Modifica1: potrebbe andare bene se le griglie non sono perfettamente uniformi, tanto più attorno ai poli.

Answer 1

Le griglie rettangolari possono essere una stima ragionevole, ma solo su un'area relativamente piccola che non è troppo vicina ai poli. Una soluzione globale richiede un approccio diverso.

Answer 2

La mappatura dalle coordinate spaziali bidimensionali al tuo indice spaziale / geohash è un problema interessante. Puoi consultare questo articolo su quadrifogli, geohash e curve di Hilbert . La curva di Hilbert è una curva di riempimento dello spazio che fornisce località; per i tuoi scopi, ciò significa che gli oggetti vicini nell'indice spaziale unidimensionale saranno vicini nello spazio bidimensionale.

L'obiettivo (come descritto da altri responder) è di ridurre al minimo il numero di query necessarie per coprire lo spazio in questione senza richiedere tonnellate di dati non necessari dal server. Il modo in cui esegui la mappatura dallo spazio 2-d a un indice 1-d influirà su tale obiettivo.

Answer 3

Senza conoscere i requisiti esatti dell'applicazione, Geohashing potrebbe essere una tecnica appropriata: http: //en.wikipedia. org / wiki / Geohash

" È una struttura gerarchica di dati spaziali che suddivide lo spazio in secchi di forma griglia. I geohash offrono proprietà come la precisione arbitraria e la possibilità di rimuovere gradualmente i caratteri dalla fine del codice per ridurne le dimensioni (e perdere gradualmente la precisione). & Quot;

Answer 4

Non puoi creare una griglia rettangolare che mappa uniformemente un globo. Se la griglia deve essere uniforme, è necessario utilizzare triangoli. Ma in generale, dubito che questo risolverà il tuo problema. Ciò di cui hai bisogno è un octree in 2D (questo è un link di ricerca di Google; controlla le immagini per un facile indizio su come funziona) di qualche tipo: devi dividere le tue coordinate in gerarchie (ad esempio nord / sud / est / ovest dell'origine per il primo livello e poi tra 90 gradi, ecc.)

Quindi puoi fare un paio di selezioni che produrranno rapidamente il rettangolo più piccolo che contiene coordinate esistenti. Ora puoi controllare le dimensioni del rettangolo. Se è & Lt; 100m, allora hai trovato una soluzione. Altrimenti, avrai solo alcune posizioni da verificare (di solito una).

Google per " octree sql database " per implementazioni.