7

我现在正在寻找一种优雅的算法来递归地使用 geohashing 算法（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 个相同大小的 geohash 组成的第一个环(=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]])。两个是第二个环，周围有 16 个区域第一环等

你有什么方法可以优雅地从比特中推断出“戒指”吗？

4

2 回答 2

1

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

假设您可以在可搜索的宇宙中找到最外层的集合（最长的接近度）。将其存储为新宇宙，然后在该宇宙中找到下一个内部集合。这个搜索应该从宇宙中减去那个内部集合。存储旧的宇宙（最外圈）并重复此过程，直到您到达中心。第一次之后的每次搜索都会减少您的搜索区域并给您一个戒指。

于 2011-01-07T04:13:35.160 回答
0

首先在中央 geohash 周围构建侧面，即顶部、右侧、底部和左侧，最初这些边中的每一个将仅包含一个 geohash 和一个角。然后使用与该边相对应的方向的相邻函数递归迭代边（即向左侧扩展），同时保持适当的结果集和边用于下一次迭代。您还需要处理每一侧的对角线/角geohash（例如，如果使用顺时针关联，则左上为左，右上为上）。有关该过程的示例，请参见我在 Lua或Javascript（但具有附加功能）中所做的这个实现，它从调用 Grid() 开始。

于 2013-05-29T08:46:09.027 回答