Geohash とは

Geohash は、Gustavo Niemeyer が geohash.org というWebサービスを作成中に発明した、
ジオコーディング方法の一つ。
Geohash を使うと地球を矩形単位で分割して、それをBase32のハッシュで表すことができる。

geohash は何が便利？

矩形のサイズは桁数に比例して変わり、10桁になると0.59m × 0.97mなので、実質的に位置として扱える。
矩形単位で位置情報を管理できる。
- 一定範囲ごとのグループ化などがし易い。例えば上位5桁なら4872.66m × 3955.08mの、上位4桁なら19490.62m × 31640.62mの範囲でグループ化できる。
上位の桁が同じ場所は近い位置にある。
- 前方一致検索ができる。
- 曖昧な検索ができる。

Geohashの仕組み

緯度軽度はそれぞれ-90〜+90、-180〜+180の範囲がある。
geohashでは、それを交互に分割していく。
例えば緯度経度が 35.68, 139.70 の場合

139.70 は-180と+180の中央(0)よりは+180側【大きい】
35.68 は-90と+90の中央(0)よりは+90側【大きい】
139.70 は0と+180の中央(90)よりは+180側【大きい】
35.68 は0と+90の中央(+45)よりは+0側【小さい】
139.70 は90と+180の中央(135)よりは+180側【大きい】

このような処理を繰り返す。
そして、これを5回ごとに分割し、大きい側の場合は1、小さい側の場合は0とすると、
11101(2進数)=29(10進数)になる。
この値をBase32に変換すると、xになる。
(値が0はじまりなので、30番目の文字)

Base32の文字列： 0123456789bcdefghjkmnpqrstuvwxyz

geohashから緯度経度を調べたい場合はこの逆の処理を行い、
Base32(x)から番号(29)に変換し、前述のような判定をしていくのだが、
当然だが座標から座標を含む範囲を求めることは可能だが、
範囲から特定の座標を求めることはできない。
そのため、結果としては矩形の東西南北の緯度経度を求めることになる。
ただし、geohashの桁数が高い場合はほとんど元の位置がわかる
例えば xn774cneps から変換した結果は以下。

位置	値
緯度(大)	35.68962872028351
緯度(小)	35.68962335586548
経度(大)	139.7004210948944
経度(小)	139.70041036605835

サンプルコード(Java)

緯度軽度からgeohashへの変換

String encode(final double latitude,
              final double longitude,
              final int precision) {
    final char[] chars = new char[precision];
    final double[] latLng = { latitude, longitude };
    final double[][] points = {{ 90.0, -90.0 }, { 180.0, -180.0 }};
    int latLngIdx = 1;
    for (int i = 0; i < precision; i++){
        int ch = 0;
        for(int j = 0; j < 5; j++){
            final double mid = (points[latLngIdx][0] + points[latLngIdx][1]) / 2;
            final int b = latLng[latLngIdx] > mid ? 1 : 0;
            points[latLngIdx][b] = mid;
            ch <<= 1;
            ch |= b;
            latLngIdx ^= 1;
        }
        chars[i] = "0123456789bcdefghjkmnpqrstuvwxyz".charAt(ch);
    }
    return new String(chars);
}

ググって出てきたRubyやPythonのサンプルだと文字列を使う例が多かったが、
上記の例では効率化のためにビット演算を使用している。

geohashから緯度経度へ変換

double[][] decode(final String geohash) {
    final double[][] latLng = { { 90.0, -90.0 }, { 180.0, -180.0 } };
    int isLng = 1;
    final String v = geohash.toLowerCase(); // Base32は大文字小文字区別しない
    for (int i = 0; i < v.length(); i++) {
        final int ch = v.charAt(i);
        final int chIdx = "0123456789bcdefghjkmnpqrstuvwxyz".indexOf(ch);
        for (int j = 5; j > 0; j--) {
            final int idx = (chIdx >> (j - 1)) & 1;
            latLng[isLng][idx] = (latLng[isLng][0] + latLng[isLng][1]) / 2;
            isLng ^= 1;
        }
    }
    return latLng;
}

参考