Che tipo di algoritmo / layout di dati devo usare per una ricerca bidimensionale veloce?

Supponendo che stai abbinando la posizione attuale a una serie di punti noti, la memorizzazione di punti in un QuadTree dovrebbe ridurre la ricerca tempo per O (log n).

Essendo intelligente con suddivisioni e memorizzando 5-10 elementi nelle foglie, dovrebbe essere efficiente anche in termini di spazio di memoria.

Una curva Z-Order potrebbe essere una rappresentazione utile di un quad-tree nella tua memoria bassa, situazione a basso rendimento.

Fondamentalmente, calcola un ordinamento monodimensionale dei tuoi punti, che preserva la località. Una volta che sai da dove iniziare, cerchi linearmente in memoria, saltando le voci non nel rettangolo di ricerca. Wikipedia ha una descrizione di come farlo .

Questo potrebbe aiutarti a mantenere un quad-tree.

Un k -d albero sembra essere adatto a questo problema . In particolare, la ricerca del vicino più vicino sembra relativamente semplice:

The nearest neighbour search (NN) algorithm aims to find the point in the tree that is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space.

Searching for a nearest neighbour in a k-d tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is lesser than or greater than the current node in the split dimension).

2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"

3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:

   1. If the current node is closer than the current best, then it becomes the current best.

   2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the distance between the splitting coordinate of the search point and current node is lesser than the distance (overall coordinates) from the search point to the current best.

      1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.

      2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.

4. When the algorithm finishes this process for the root node, then the search is complete.

La creazione di un formato di file flat adeguatamente ricercabile per memorizzare detto albero k -d è lasciato come esercizio per il lettore.

Ho implementato questo tipo di ricerca per un database comune senza funzioni speciali di indicizzazione geografica. Il trucco è dividere le aree possibili in tessere a livelli di zoom sempre più elevati. Ad esempio, a livello di zoom 0, hai il riquadro 0. A livello di zoom 1, hai le tessere 1,2,3,4. A livello di zoom 2, hai le tessere 5,6,7,8, 9,10,11,12, 13,14,15,16, 17,18,19,20. Quindi, ogni tessera nel livello di zoom N è suddivisa in quattro tessere più piccole nel livello di zoom N + 1.

Quindi per ogni riga hai le colonne tile0, tile1, tile2, tile3, ..., tile19 (assumendo 20 livelli di zoom totali). O in realtà, puoi omettere tile0 poiché è sempre 0. Ciascuna di queste colonne N colonne è indicizzata da un indice B standard.

Quindi hai bisogno dell'algoritmo per decidere rapidamente quale sia la tessera corrispondente a una coordinata arbitraria (x, y) al livello di zoom N. Non ricordo ora come ho implementato questo algoritmo, ma ricordo che era un po 'complicato ma l'algoritmo si è rivelato estremamente veloce.

Nel caso in cui la coordinata (x, y) si trovi vicino al bordo della tessera, la tessera vicina potrebbe contenere una soluzione che è migliore della migliore soluzione nella tessera corrente. Quindi, in generale, è necessario includere quattro tessere nella ricerca a livello di zoom N. È necessario implementare la funzione che calcola queste quattro tessere.

Se hai livelli di zoom 0, 1, 2, ..., 19 inizi a cercare le quattro tessere adatte al livello di zoom 19, poi a 18, quindi a 17, ... fino a quando non avrai un risultato abbastanza grande .

Un geohash è una buona soluzione qui. Puoi fare la lunghezza secondo la precisione che ti serve e sulla tua scheda SD rendere geohash il nome del file. Ciò ti permetterà di leggere alcuni file per ottenere tutti i punti entro una certa prossimità, quindi filtrare / ordinare da lì.

Ho implementato con successo un paio di progetti usando R-Trees per questo scopo.

Un'implementazione è qui che a sua volta è una versione parzialmente convertita di una libreria java (jsi ).