Geohashing: recursivamente encuentra vecinos de vecinos

Question

Ahora estoy buscando un algoritmo elegante para encontrar recursivamente vecinos de vecinos con el algoritmo de geohashing (http://www.geohash.org).
Básicamente tomar un geohash central, y luego obtener el primer 'anillo' de hash del mismo tamaño a su alrededor (8 elementos), luego, en el siguiente paso, obtener el siguiente anillo alrededor del primero, etc. ¿Has oído de una manera elegante de hacerlo?

La fuerza bruta podría ser tomar a cada vecino y hacer que sus vecinos simplemente ignoren la superposición masiva. Vecinos alrededor de un geohash central ha sido resuelto muchas veces (aquí por ejemplo en Ruby: http://github.com/masuidrive/pr_geohash/blob/master/lib/pr_geohash.rb)

Editar una aclaración: solución actual, con el paso de una tecla central y una dirección, así (con las correspondientes operaciones de búsqueda mesas):

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 

(extracto de lib de Yuichiro Masui)

digo este enfoque se ponen feas pronto, porque las direcciones pone feo una vez que estamos en el anillo de dos o tres. El algoritmo idealmente tomaría simplemente dos parámetros, el área central y la distancia desde 0 es el centro del geohash solamente (["u0m"] y 1 es el primer anillo compuesto por 8 geoashes del mismo tamaño alrededor de él (=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]]). Dos es el segundo anillo con 16 áreas alrededor del primer anillo etc.

¿ves alguna manera de deducir los 'anillos' de los bits de una manera elegante?

Answer 1

Eso depende de lo que entendemos por Vecino. Asumo que este está siendo utilizado en el contexto de una búsqueda de proximidad. En ese caso, creo que su mejor opción sería buscar desde el anillo más externo hacia adentro.

Supongamos que puede encontrar la parte externa ost set (la proximidad más larga) en el Universo de búsqueda. Almacene eso como el nuevo Universo y luego encuentre el siguiente conjunto interno en ese Universo. Esta búsqueda debe restar ese conjunto interno del Universo. Almacene el viejo Universo (el anillo más externo) y repita este proceso hasta que llegue al centro. Cada búsqueda después de la primera reducirá su área de búsqueda y le dará un anillo.

Answer 2

Comience construyendo los lados inmediatamente alrededor del geohash central, es decir, arriba, derecha, abajo e izquierda, inicialmente cada uno de estos solo comprenderá un solo geohash y una esquina. A continuación, itere recursivamente los lados usando la función adyacente con la dirección correspondiente a ese lado (es decir, expanda hacia la izquierda para el lado izquierdo) mientras mantiene un conjunto de resultados apropiado y los lados para la siguiente iteración. También necesita manejar el geohash diagonal/de esquina para cada lado (por ejemplo, arriba a la izquierda para arriba, arriba a derecha para arriba, si usa una asociación a favor del reloj). Para ver un ejemplo del procedimiento, vea this implementation I did in Lua o Javascript (pero con funcionalidad adicional), que comienza con una llamada a Grid().