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;
}