Geohashing - Trova in modo ricorsivo i vicini dei vicini

Question

Ora sto cercando un algoritmo elegante per trovare ricorsivamente i vicini dei vicini con l'algoritmo di geohashing (http://www.geohash.org).
Prendete fondamentalmente un geohash centrale, quindi prendete il primo "anello" di hash della stessa dimensione attorno ad esso (8 elementi), quindi, nel passaggio successivo, prendete l'anello successivo attorno al primo ecc. Ecc. Avete sentito di un modo elegante per farlo?

La forza bruta potrebbe essere quella di prendere ogni vicino e ottenere i propri vicini semplicemente ignorando la massiccia sovrapposizione. Vicini circa un geohash centrale è stato risolto molti volte (qui ad esempio in Ruby: http://github.com/masuidrive/pr_geohash/blob/master/lib/pr_geohash.rb)

Edit chiarimenti: soluzione corrente, con il passaggio in un tasto centrale e una direzione, come questo (con corrispondenti di ricerca tavoli):

def adjacent(geohash, dir) 
    base, lastChr = geohash[0..-2], geohash[-1,1] 
    type = (geohash.length % 2)==1 ? :odd : :even 
    if BORDERS[dir][type].include?(lastChr) 
     base = adjacent(base, dir) 
    end 
    base + BASE32[NEIGHBORS[dir][type].index(lastChr),1] 
    end 

(estratto lib di Yuichiro MASUI)

dico questo approccio otterrà brutto presto, perché le direzioni diventa brutto una volta che siamo in anello di due o tre. L'algoritmo idealmente prenderebbe semplicemente due parametri, l'area centrale e la distanza da 0 solo al centro geohash (["u0m"] e 1 è il primo anello composto da 8 geohashes della stessa dimensione attorno ad esso (=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]]). due sono il secondo anello con 16 aree intorno al primo anello ecc

vedete un modo per dedurre i 'anelli' dai bit in modo elegante?

Answer 1

questo dipende da cosa si intende per il prossimo. sto assumendo questo è in uso Nel contesto di una ricerca di prossimità, in questo caso, la tua migliore scommessa sarebbe quella di cercare dall'anello più esterno verso l'interno:

Supponiamo che tu possa trovare l'outerm ost (la più lunga prossimità) nell'Unesco ricercabile. Conservalo come il nuovo universo e poi trova il prossimo set interiore in quell'universo. Questa ricerca dovrebbe sottrarre quel set interiore dall'universo. Conserva il vecchio universo (l'anello più esterno) e ripeti questo processo finché non colpisci il centro. Ogni ricerca dopo la prima ridurrà la tua area di ricerca e ti darà un anello.

Answer 2

Inizia costruendo i lati immediatamente attorno al geohash centrale, cioè in alto, a destra, in basso ea sinistra, inizialmente ognuno di questi comprenderà solo un singolo geohash e un angolo. Quindi, ripetete ricorsivamente i lati usando la funzione adiacente con direzione corrispondente a quel lato (ad esempio, espandete a sinistra per il lato sinistro) mantenendo un set di risultati appropriato e i lati per l'iterazione successiva. È inoltre necessario gestire il geohash diagonale/angolare per ciascun lato (ad esempio, a sinistra in alto per sinistra, in alto a destra in alto, se si utilizza un'associazione in senso orario). Per un esempio della procedura vedere this implementation I did in Lua o Javascript (ma con funzionalità aggiuntive), che inizia con una chiamata a Grid().