come ordinare i dati geografici per la ricerca rapida

Question

Ho alcuni oggetti che sono geo-localizzati (ho per ogni oggetto la latitudine + longitudine). La mia app deve visualizzare gli oggetti che si trovano a 3 chilometri attorno alla posizione GPS del dispositivo mobile. Ho diverse migliaia di oggetti e sono localizzati in un'ampia area (ad esempio, diversi stati degli Stati Uniti, diversi paesi piccoli), nel mio elenco di oggetti ne posso avere uno situato a New York e un altro a Miami, ma posso avere anche oggetti che sono molto vicini (pochi metri).

Attualmente, la mia app esegue una ricerca iterativa. Per ogni oggetto computo la distanza con la posizione GPS e se la distanza è < = 3KM, allora tengo l'oggetto che ignoro. Questo algoritmo non è molto efficiente e sto cercando un algoritmo che fornisca prestazioni migliori.

Suppongo che ci sia un modo per ordinare i miei oggetti usando il geo coord e accanto per trovare più velocemente gli oggetti che si trovano attorno alla posizione GPS.

La mia idea attuale è solo per calcolare il rettangolo con i "punti estremi", Nord/Sud/Est/Ovest (da 3 km della posizione GPS) per limitare la zona di ricerca. Quindi calcolerò la distanza solo per gli oggetti all'interno di questa casella. Penso qualcosa di meglio poteva essere fatto, ma non ho l'idea ...

Ogni proposta sarà apprezzato ;-) Grazie,

SEB.

Answer 1

sembra una nearest neighbor search, ma non con un massimo numero di vicini (come in kNN), ma con una distanza soglia massima.

Un approccio comune consiste nel mettere gli oggetti in una struttura dati speciale per consentire di escludere rapidamente ampie parti dello spazio di ricerca. Tuttavia, questi sono di solito realizzati con gli spazi euclidei in mente, e non per il piano sferico (lat/lon-) (problemi di avvolgimento). Pertanto, si sarebbe probabilmente bisogno di convertire le vostre coordinate di coordinate 3D in un sistema cartesiano rispetto al centro della sfera prima di applicare uno dei seguenti strutture di dati per la ricerca in modo efficiente per gli oggetti:

• Octree
• kd-tree

Answer 2

le altre risposte che citano indici spaziali sono corretti, ma non necessariamente la soluzione più semplice per voi.

Vorrei prendere in considerazione qualcosa di più semplice: Raggruppa gli articoli per paese, poi per stato, regione, città e infine - con alcuni punti di riferimento in città fitte (dove hai un sacco di oggetti).

Quindi è necessario eseguire solo alcune query (verificare quale Paese sono, in quale stato, regione, ecc.) Per limitarsi a un insieme molto piccolo di oggetti, senza implementare strutture dati avanzate nell'app mobile .

Answer 3

Un modo per eseguire questa operazione senza una datastructure specializzata sembra essere l'ordinamento di due copie dei dati: una volta per longitudine, una volta per latitudine. Qualunque cosa che le ricerche binarie in basso si chiudono su lat e long, è vicina.

Analogamente, è possibile utilizzare il solito albero di traccie (veloce) o rosso-nero (bassa variabilità).

Ma ci sono probabilmente dei vantaggi nell'utilizzo di un albero r o di un albero kd. Quello che ho descritto è probabilmente solo per evitare di prendere nuove dipendenze o evitare di codificare una nuova infrastruttura da zero.