緯度経度を文字列で表すGeoHash

　なんか世間的に位置情報アプリが流行ってるらしいし、Google App Engine(GAE)も楽しそう。どうせだから、GAEでなんか位置情報アプリでも作ってみよう！と思ってTwitterに書き込んだところ、Geohashという、位置情報のプロトコル？を教えてもらいました。

　これは、その名の通り、位置情報をハッシュで表す規格なのですが、いろいろおもしろい特徴があり、調べているうちに楽しくなってきたので、勢い余ってPure Rubyのライブラリまで書いちゃいました。

　そのあと、結局ライブラリを作ったところで満足して、アプリは何も作らなかったので、せめてGeohashの解説でも書いておこうと思います。

　位置情報は通常、緯度経度で表します。たとえば東京タワーの緯度経度は35.65861, 139.745447です。
北を上にした地図でいうと、緯度がY座標で経度がX座標です。英語では緯度をlatitude、経度をlongitudeと呼びます。

　この緯度経度は測地系によって値が違いますが、ここではGPSなどで使われている世界測地系を前提にします。

　位置情報系のアプリでは、「今いる場所をGPSで取得して、その近くにあるランドマークを表示する」ということがよく行われます。
　これをGoogle App EngineのDataStoreで行おうと思うと、2つのカラムで比較ができないという、DataStoreの制約が問題になります。(例: x>1 and y>1の様なことができない)

　そこで、GeoHashの登場です。GeoHashは、緯度経度の二つの座標を、一つの文字列にまとめたものです。

　東京タワーをGeoHashで表現すると「xn76ggrw26」になります。GeoHashはグリッドになるので、緯度経度のようにポイントではありません。
　先のハッシュが8文字あると、19m*31mのグリッドになります。

　GeoHashの最大の特徴は、その長さによって精度が変わることです。
東京タワーを中心とした 19m*31mのエリアは「xn76ggrw」ですが、これを頭5文字「xn76gg」だけ取り出すと、下の図の様なエリアを表します。

　データベースから、「xn76gg」の前方一致で検索することで、エリア内のポイントを簡単に取り出すことができます。

　しかし、これでは、上の図の様に、ランドマークがメッシュの端にある場合、すぐ近くのポイントもヒットしなくなってしまいます。
　
　そこで、geohashで検索する場合は、右の図の様に隣接するブロックも同時に検索します。東京タワーの周りを探す場合は、「xn76gg」だけを検索するのではなく、’xn76gu’,’xn76gf’,’xn76u5′,’xn76ge’,’xn76gs’,’xn76uh’,’xn76u4′,’xn76gd’,’xn76gg’も同時に検索することで、おおよそ2km*3kmの範囲で検索が可能です。

　多くのGeohashライブラリには、隣接するGeohashコードを計算する関数が用意されています。
それを使い、上記のように近接のブロックのGeohashコードを同時に検索することで、東京タワーからおおよそ1〜1.5kmのポイントを割り出すことができます。

　GAEのDataStoreは、文字列の前方一致が高速に行えるので、Geohashで場所の絞り込み検索などを容易に行うことができます。

　緯度経度から、Geohashで計算するライブラリは各種言語用にリリースされています。
Pure Rubyで書かれたライブラリが無かったで、自作したライブラリもありますので、Rubyの人はぜひ下記のコマンドでインストールしてみてください。

gem install pr_geohash

使い方は、READMEをご覧ください。

　実際にGeohashを試すことの出来るデモを下記のURLに設置しました。興味のある人は、直接触ってみると簡単に使い方が分かると思います。
http://blog.masuidrive.jp/wordpress/wp-content/uploads/2010/01/geohash.html

　緯度経度を精度も含めて、文字列一つで扱えるのでURLに位置情報を入れたい場合など、便利なケースがあるんじゃないかと思います。

　Twitterでも緯度経度じゃなくて、Geohashで位置情報を管理してくれたらよかったのに。
そしたら、5文字ぐらいにすることで「だいたいシアトルにいる」みたいな大まかな位置情報だけ公開するとかできて、プライバシー的にも利点があったのになー。

p.s
　Geohashのエンコーディング方法の解説も欲しいって人います？
もし居たらコメントください。

追記 01/13 0:34
　Geohashのアルゴリズムを書きました。

参考データ:

=begin
東京付近のGeoHashの精度を算出するRubyスクリプト
 
|文字数|   南北  |   東西  |
|    6 | 609.08m | 988.77m |
|    7 | 152.27m | 123.60m |
|    8 |  19.03m |  30.90m |
|    9 |   4.76m |   3.86m |
|   10 |   0.59m |   0.97m |
=end
 
puts (6..10).map {|i|
  lng_bit = (5 * i / 2.0).ceil
  lat_bit = (5 * i / 2.0).floor
  lng_grid_size = sprintf("%6.2fm", (360.0 / (2 ** lng_bit))*(25.0*60*60))
  lat_grid_size = sprintf("%6.2fm", (180.0 / (2 ** lat_bit))*(30.8*60*60))
  [i, lat_bit, lng_bit, lat_grid_size, lng_grid_size]
}.map{|r| "|#{r.join('|')}|"}.join("n")