Come posso dividere il globo in piccole griglie in modo tale da permettermi di assegnare ogni lat/long location a una griglia?

Question

Per calcolare le posizioni più vicine che sono rappresentate da latitudine/longitudine, stavo considerando la divisione della mappa in piccole griglie, griglie di circa 100x100 metri. Essenzialmente ogni punto sarebbe assegnato a una griglia.

Capisco che potrei invece utilizzare anche indici spaziali con MySQL ecc., Ma sto progettando di utilizzare un database non relazionale come Cassandra dove sarebbe difficile fare l'indicizzazione su oggetti spaziali, e quindi una sorta di tecnica di approssimazione della griglia potrebbe essere pulito

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

Edit1: Potrebbe essere accettabile se le griglie non sono perfettamente uniformi, a maggior ragione 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 a globo completo richiede un approccio diverso.

Answer 2

Non è possibile creare una griglia rettangolare che mappa in modo uniforme un globo. Se la griglia deve essere uniforme, è necessario utilizzare i triangoli. Ma in generale, dubito che questo risolva il tuo problema. Quello che ti serve è un 2D octree (questo è un link di ricerca di Google; controlla le immagini per capire 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 è possibile eseguire un paio di selezioni che porteranno rapidamente al rettangolo più piccolo che contiene le coordinate esistenti. Ora puoi controllare la dimensione del rettangolo. Se è < 100m, allora hai trovato una soluzione. Altrimenti, avrai solo poche posizioni da controllare (di solito una).

Google per "database SQL octree" per le implementazioni.

Answer 3

senza conoscere le specifiche esigenze applicative Geohashing potrebbe essere una tecnica appropriata. http://en.wikipedia.org/wiki/Geohash

"È una struttura di dati spaziali gerarchica che suddivide lo spazio in secchi di griglia forma Geohashes offrono immobili come precisione arbitraria e la possibilità di rimuovendo gradualmente i caratteri dalla fine del codice per ridurne le dimensioni (e gradualmente perdere la precisione). "

Answer 4

La mappatura dalle coordinate spaziali bidimensionali al tuo indice spaziale/geohash è un problema interessante. Potresti guardare a this article on quadtrees, geohashes and Hilbert curves. Hilbert curve è una curva che riempie lo spazio che fornisce la 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 risponditori) è 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 bidimensionale a un indice 1-d influirà su tale obiettivo.