ruby - Geohashing - 递归地找到邻居的邻居

Question

我现在正在寻找一种优雅的算法，使用地理散列算法 (http://www.geohash.org) 递归查找邻居的邻居。
基本上采用中央 geohash，然后在其周围获得相同大小的散列的第一个“环”(8 个元素)，然后在下一步中，在第一个周围获得下一个环等。您听说过这样做的优雅方式吗？

蛮力可能是拿走每个邻居并让他们的邻居简单地忽略大量重叠。围绕一个中央 geohash 的邻居已经解决了很多次(这里例如在 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 的库)

我说这种方法很快就会变得难看，因为一旦我们进入二环或三环，方向就会变得难看。理想情况下，该算法只需采用两个参数，即中心区域和距 0 仅作为中心 geohash 的距离(["u0m"] 和 1 是由周围 8 个相同大小的 geohashes 组成的第一个环它 (=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]]). two 是第二个环，第一个环周围有 16 个区域等。

您有什么方法可以优雅地从位中推断出“环”吗？

Answer 1

这取决于您所说的“邻居”是什么意思。我假设这是在邻近搜索的上下文中使用的。在那种情况下，我认为您最好的选择是从最外圈向内搜索。

假设您可以在可搜索的 Universe 中找到最外层的集合(最长邻近度)。将其存储为新宇宙，然后在该宇宙中找到下一个内部集合。这个搜索应该从 Universe 中减去那个内部集合。存储旧宇宙(最外圈)并重复此过程，直到到达中心。第一次搜索后的每次搜索都会缩小您的搜索范围并给您一个响铃。