7

私は現在、ジオハッシュ アルゴリズム ( http://www.geohash.org ) を使用して隣人の隣人を再帰的に見つけるためのエレガントなアルゴリズムを探しています。
基本的に、中央の geohash を取り、その周りに同じサイズのハッシュ (8 要素) の最初の「リング」を取得し、次のステップで、最初のリングの周りに次のリングを取得します。そうする方法？

力ずくで各隣人を取得し、その隣人に大規模な重複を単純に無視させることができます。1 つの中央 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

(増井雄一郎のlibより抜粋)

リング 2 または 3 に入ると方向が見にくくなるため、このアプローチはすぐに見苦しくなると思います。アルゴリズムは、理想的には単純に 2 つのパラメータを取ります。中央の領域と 0 からの距離は、中央のジオハッシュのみです ( ["u0m"]1 は、周囲に同じサイズの 8 つのジオハッシュで構成される最初のリングです。2 は、(=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]])周囲に 16 の領域を持つ 2 番目のリングです)。ファーストリングなど

ビットからエレガントな方法で「リング」を推測する方法はありますか?

4

2 に答える 2

1

それは、隣人が何を意味するかによって異なります。これは、近接検索のコンテキストで使用されていると想定しています。その場合、最も外側のリングから内側に向​​かって検索するのが最善の策だと思います。

検索可能なユニバースで最も外側のセット (最長近接) を見つけることができると仮定します。それを新しいユニバースとして保存し、そのユニバース内の次の内部セットを見つけます。この検索により、その内部セットがユニバースから差し引かれます。古いユニバース (最も外側のリング) を保存し、中心に到達するまでこのプロセスを繰り返します。最初の検索以降の各検索では、検索範囲が縮小され、リングが表示されます。

于 2011-01-07T04:13:35.160 に答える
0

まず、中央のジオハッシュのすぐ周囲、つまり上、右、下、左の側面を構築することから始めます。最初は、これらのそれぞれが 1 つのジオハッシュと角だけで構成されます。次に、次の反復のために適切な結果セットと辺を維持しながら、その辺に対応する方向で隣接する関数を使用して辺を再帰的に繰り返します (つまり、左側を左に展開します)。また、各辺の対角線/コーナー ジオハッシュを処理する必要があります (たとえば、時計回りの関連付けを使用している場合は、左は左上、上は右上)。手順の例については、私が LuaまたはJavascriptで行ったこの実装を参照してください(ただし、機能が追加されています)。これは、Grid() の呼び出しで始まります。

于 2013-05-29T08:46:09.027 に答える