地理哈希-递归查找邻居的邻居

Question

现在，我正在寻找一种优雅的算法，使用geohashing (http://www.geohash.org)递归地查找邻居的邻居。

基本上，取一个中心地散列，然后在它周围得到第一个大小相同的散列环(8个元素)，然后，在下一步，在第一个地方得到下一个环等等。你听说过这样做的优雅方法吗？

蛮力可以是把每一个邻居都带走，让他们的邻居无视巨大的重叠。围绕一个中心地哈希的邻居已经被解决了很多次(例如在Ruby：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

(摘自玉井悦一郎的自由)

我说这种方法很快就会变丑，因为一旦我们进入二三圈，方向就会变得丑陋。理想情况下，该算法只需取两个参数，中心面积和距0的距离仅为中心地散列(["u0m"]和1是由8条相同大小的(=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]])环组成的第一个环)。两个是第二个环，第一个环周围有16个区域，等等。

你认为有什么方法可以用优雅的方式从比特中推断出“环”吗？

Answer 1

这取决于你对邻居的理解。我假设这是在附近搜索的上下文中使用的。在这种情况下，我认为你最好的选择是从最外层的圆环向内搜索。

假设你可以在可搜索的宇宙中找到最外层的集合(最长的接近)。将其存储为新的宇宙，然后在该宇宙中找到下一个内部集。这个搜索应该从宇宙中减去这个内部集。保存旧的宇宙(最外层的环)，并重复这个过程，直到你到达中心。第一次搜索后的每一次搜索都会减少搜索区域，并给您一个电话。

Answer 2

首先，在中央地理哈希(即上、右、下和左)周围构造边，最初，每个边将只包含一个地哈希和一个角。然后递归地迭代边，使用与该边相对应的方向的相邻函数(即左侧展开)，同时保持适当的结果集和下一次迭代的边。您还需要处理每一边的对角线/角地散列(例如，左顶表示左，右上角表示顶，如果使用顺时针关联)。有关该过程的示例，请参见我在Lua做的这个实现或Javascript (但附带其他功能)，它们以调用Grid()开始。