Geohashing - рекурсивно найти соседей соседей - PullRequest
Новая
       1

Geohashing - рекурсивно найти соседей соседей

7 голосов
/ 11 июня 2010

Я сейчас ищу элегантный алгоритм для рекурсивного поиска соседей соседей с помощью алгоритма гео-хеширования (http://www.geohash.org).
В основном возьмите центральный гео-хеш, а затем получите первое «кольцо» хэшей того же размера вокруг него (8 элементов), затем, на следующем шаге, получите следующее кольцо вокруг первого и т. Д. И т. Д. Вы слышали об элегантном способе сделать это?

Грубая сила может заключаться в том, чтобы взять каждого соседа и получить ихсоседи просто игнорируют массивное перекрытие. Соседи вокруг одного центрального геохеша решались много раз (здесь, например, в Ruby: http://github.com/masuidrive/pr_geohash/blob/master/lib/pr_geohash.rb)

Редактировать для уточнения: Текущее решение с прохождением по центруключ и направление, как это (с соответствующими справочными таблицами): 

  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

(извлечение из библиотеки Yuichiro MASUI)

Я говорю, что этот подход скоро станет уродливым, потому что указания становятся безобразнымикак только мы окажемся в кольце два или 3. В идеале алгоритм будет просто принимать два параметра: центр и расстояние от 0 до центратолько геохэш (["u0m"] и 1 - первое кольцо из 8 геохэш одинакового размера вокруг него (=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]]).два - второе кольцо с 16 областями вокруг первого кольца и т. д.

Видите ли вы какой-нибудь способ изящно вывести «кольца» из бит?

Ответы [ 2 ]

1 голос
/ 07 января 2011

Это зависит от того, что вы подразумеваете под Соседом. Я предполагаю, что это используется в контексте поиска близости. В этом случае я думаю, что вам лучше всего искать от самого дальнего кольца внутрь.

Предположим, вы можете найти самый дальний набор (самая длинная близость) в доступной для поиска Вселенной. Сохраните это как новую вселенную, а затем найдите следующий внутренний набор в этой вселенной. Этот поиск должен вычесть этот внутренний набор из Вселенной. Сохраните старую Вселенную (самое дальнее кольцо) и повторяйте этот процесс, пока не достигнете центра. Каждый поиск после первого уменьшит вашу область поиска и даст вам звонок.

0 голосов
/ 29 мая 2013

Начните с построения сторон непосредственно вокруг центрального геохеша, то есть сверху, справа, снизу и слева, первоначально каждый из них будет содержать только один геохэш и угол. Затем рекурсивно итерируйте стороны, используя смежную функцию с направлением, соответствующим этой стороне (то есть расширяйте влево для левой стороны), сохраняя при этом соответствующий набор результатов и стороны для следующей итерации. Вам также необходимо обрабатывать геохэш по диагонали / углу для каждой стороны (например, слева-сверху слева, сверху-справа сверху, если используется связь по часовой стрелке). Для примера процедуры см. эту реализацию, которую я сделал в Lua или Javascript (но с дополнительными функциями), которые начинаются с вызова Grid ().

...