2010-06-10 10 views
6

Ich bin jetzt auf der Suche nach einem eleganten Algorithmus zum rekursiven Finden Nachbarn der Nachbarn mit dem Geohashing-Algorithmus (http://www.geohash.org).
Grundsätzlich ein zentrales geohash, und dann den ersten 'Ring' der gleichen Größe Hashes um ihn (8 Elemente), dann, im nächsten Schritt, erhalten Sie den nächsten Ring um den ersten etc. etc. Haben Sie gehört auf eine elegante Art und Weise dies zu tun?Geohashing - rekursiv Nachbarn der Nachbarn finden

Brute Force könnte jeden Nachbarn nehmen und ihre Nachbarn einfach ignorieren die massive Überlappung. Nachbarn um einen zentralen geohash wurde viele Male (hier zB in Ruby: http://github.com/masuidrive/pr_geohash/blob/master/lib/pr_geohash.rb) gelöst

Bearbeiten zur Klarstellung: Aktuelle Lösung, mit in einem Mittelschlüssel übergeben und eine Richtung, wie diese (mit entsprechenden Lookup-Tabellen):

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 

(Auszug aus Yuichiro Masui lib)

ich sagen, dieser Ansatz bald hässlich wird, weil Richtungen hässlich wird, sobald wir in Ring zwei oder drei sind. Der Algorithmus würde idealerweise einfach zwei Parameter annehmen, wobei der mittlere Bereich und der Abstand von 0 nur der zentrale Geohash ist (["u0m"] und 1 der erste Ring aus 8 gleich großen geohashs) (=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]]). Zwei sind der zweite Ring mit 16 Bereichen um den ersten Ring usw.

Haben Sie irgendeine Art und Weise zu sehen, die ‚Ringe‘ aus den Bits in einer eleganten Art und Weise?

Antwort

1

das hängt davon ab, zu folgern, was Sie mit dem Nachbarn meine. ich gehe mal davon aus dem verwendet wird, um Im Kontext einer Proximity-Suche würde ich in diesem Fall meinen, dass es am besten wäre, vom äußersten Ring aus nach innen zu suchen.

Angenommen, Sie können den Outerm finden ost set (längste Nähe) im durchsuchbaren Universum. Speichere das als das neue Universum und finde dann die nächste innere Menge in diesem Universum. Diese Suche sollte diese innere Menge vom Universum subtrahieren. Speichere das alte Universum (den äußersten Ring) und wiederhole diesen Vorgang, bis du die Mitte getroffen hast. Jede Suche nach der ersten wird Ihren Suchbereich verkleinern und Ihnen einen Klingelton geben.

0

Beginnen Sie mit der Konstruktion der Seiten unmittelbar um den zentralen Geohash, d. H. Oben, rechts, unten und links, wobei anfänglich jeder von diesen nur einen einzigen Geohash und eine Ecke umfasst. Dann rekursiv rekursiv die Seiten unter Verwendung der benachbarten Funktion mit der Richtung, die dieser Seite entspricht (d. H. Nach links für die linke Seite expandieren), während eine geeignete Ergebnismenge und die Seiten für die nächste Iteration beibehalten werden. Sie müssen auch mit dem Diagonal-/Eck-Geohash für jede Seite umgehen (z. B. links oben für links, oben rechts für oben, wenn Sie eine Zuordnung im Uhrzeigersinn verwenden). Ein Beispiel für das Verfahren finden Sie unter this implementation I did in Lua oder Javascript (aber mit zusätzlichen Funktionen), die mit einem Aufruf von Grid() beginnen.

+0

Wie viel Geohashlänge ist zu berücksichtigen, wenn Sie mit dem zentralen Geohash beginnen? – Atul

Verwandte Themen