niente di meglio di delimitazione scatole?

Question

Ho un piano d'azione, dove ho x milione di punti di longitudine di latitudine.

Quando si aggiunge un nuovo punto di latitudine / longitudine Voglio sapere in modo efficiente che altri punti sono all'interno di un parametro di distanza configurato dall'utente, modo che io possa aggiungere a una lista.

Hai qualcosa di meglio che di delimitazione scatole?

Mi piacerebbe vedere gli algoritmi, riferimenti e alcune implementazioni;) Grazie di cuore

Answer 1

Ci sono alcune opzioni che sono meglio, per lo più a base intorno spazio partizionamento .

Una scelta comune, e spesso molto buono (che non è troppo difficile da implementare) è quello di utilizzare un KD-Tree . quadtree sono più facili da implementare, ma più lento per la ricerca. A seconda della distribuzione dei vostri dati e le vostre esigenze, altri algoritmi spazio di partizionamento possono svolgere meglio, hanno più bassi requisiti di memoria o altri problemi che sono correlati.

Answer 2

Un collega mi ha detto che ha avuto una buona esperienza con l'utilizzo di Morton-codice come un indice spaziale su dati GIS, forse questo è qualcosa che vale la pena indagare.

Answer 3

Questo approccio quick-and-dirty può risparmiare qualche dolore: Dividere la superficie della terra in 1 scatole di laurea. Si avrà quindi un elemento di matrice 180x360 e si avrà solo bisogno di cercare un piccolo numero di caselle, compresa la scatola che contiene il nuovo punto e tutte le caselle immediatamente attorno ad esso per i quali uno degli angoli è entro la distanza specificata dall'utente. Troverete che ci sono alcuni trucchi che si possono utilizzare per capire rapidamente cosa scatole da utilizzare senza considerare tutti. Basta non dimenticare di latitudine e longitudine avvolgente.

Se il "solo" hanno milioni di punti, e non sono raggruppati in hot-spot, che potrebbe ottenere attraverso.

Un modo teoricamente superiore: Si potrebbe mappare ogni punto in uno spazio tridimensionale e poi memorizzarli in un octree , che avrebbe permesso di trovare rapidamente luoghi entro una distanza arbitraria. Naturalmente, la distanza nello spazio tridimensionale sarà leggermente diversa rispetto alla distanza grande cerchio sul globo, in modo da avere per calcolare un fattore di conversione. Questo dovrebbe essere semplice, però. Non si parla di un linguaggio di implementazione, ma non v'è quasi certamente andando ad essere un'implementazione octree ben collaudato per qualsiasi lingua si sta lavorando. Se non ti dispiace l'inserimento del codice di terze parti, questa soluzione è il modo per andare.