ジオコード(地理座標)の一つで、緯度と経度を一つの文字列で位置の範囲を表現します。
https://ja.wikipedia.org/wiki/%E3%82%B8%E3%82%AA%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5
ここでは、Googleマップで取得した緯度経度を専用サイトでGeohashに変換して、それを元の緯度経度に戻すプログラムを作成しました。Wikipediaに書かれているような、Geohashが復号される過程を確認できます。
Googleマップで名古屋駅前の緯度経度を取得します。
http://geohash.org/でGeohashに変換します。
下記コードで復号します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<stdio.h> dv(double *s, double *e, int b) { if(b == 1) *s = (*e - *s) / 2 + *s; else *e = (*e - *s) / 2 + *s; } main() { char str[] = "0123456789bcdefghjkmnpqrstuvwxyz"; char h[] = "xn324fsp2vdw"; int k1[50]; int k2[50]; int c = 0; int c1 = 0; int c2 = 0; int i = 0, j=0 , b=0; for(i=0;i<sizeof(h);i++){ printf("%c ", h[i]); } printf("\n"); for(i=0;i<sizeof(h)-1; i++){ for(j=0;j<sizeof(str)-1;j++){ if(str[j] == h[i]){ printf("%2d:%02x [%c] ", j, j, h[i]); for(b=4; b>=0 ;b--){ int t = (j >> b) & 1; printf("%d", t); if(c % 2 == 0){ k1[c1] = t; c1 ++; } else{ k2[c2] = t; c2 ++; } c ++; } printf("\n"); } } } printf("%d ", c1); for(i=0;i<c1;i++){ printf("%d", k1[i]); } printf("\n%d ",c2); for(i=0;i<c2;i++){ printf("%d", k2[i]); } printf("\n\n"); double s = -180; double e = 180; for(i=0;i<c1;i++){ dv(&s, &e, k1[i]); printf("%2d:%d) %lf \t %lf \t %lf\n",i+1, k1[i], s, e, (s+e)/2.0); } printf("\n"); s = -90; e = 90; for(i=0;i<c2;i++){ dv(&s, &e, k2[i]); printf("%2d:%d) %lf \t %lf \t %lf \n",i+1, k2[i], s, e, (s+e)/2.0); } } |
# なぜか[ ]がエスケープされたりされなかったりして見づらいので、githubにもこのコードをアップしました。(WordPressプラグインのバグ?原因不明)
https://gist.github.com/systemsblue/5bbfd3e0f0367a608b4b
メモ追記 2015/12/5) プラグインを「Syntax Highlighter for WordPress 3.0.83.3」から 「Crayon Syntax Highlighter」に変更し、記事を修正しました。他の記事でも同様のバグを随時修正していきます。
下記、実行画面。3つにわけていますが、一気に表示されます。
$ ./geohash
x n 3 2 4 f s p 2 v d w
29:1d [x] 11101
20:14 [n] 10100
3:03 [3] 00011
2:02 [2] 00010
4:04 [4] 00100
14:0e [f] 01110
24:18 [s] 11000
21:15 [p] 10101
2:02 [2] 00010
27:1b [v] 11011
12:0c [d] 01100
28:1c [w] 11100
30 111000010101011100000001101010
30 101100100000010101110110110110
それぞれのキャラクタに該当する5bitの二進数を1bitごとに上下にわりふっていきます。上下ともに30bitになりましたが、ならなくてもいいです。
1:1) 0.000000 180.000000 90.000000
2:1) 90.000000 180.000000 135.000000
3:1) 135.000000 180.000000 157.500000
4:0) 135.000000 157.500000 146.250000
5:0) 135.000000 146.250000 140.625000
6:0) 135.000000 140.625000 137.812500
7:0) 135.000000 137.812500 136.406250
8:1) 136.406250 137.812500 137.109375
9:0) 136.406250 137.109375 136.757812
10:1) 136.757812 137.109375 136.933594
11:0) 136.757812 136.933594 136.845703
12:1) 136.845703 136.933594 136.889648
13:0) 136.845703 136.889648 136.867676
14:1) 136.867676 136.889648 136.878662
15:1) 136.878662 136.889648 136.884155
16:1) 136.884155 136.889648 136.886902
17:0) 136.884155 136.886902 136.885529
18:0) 136.884155 136.885529 136.884842
19:0) 136.884155 136.884842 136.884499
20:0) 136.884155 136.884499 136.884327
21:0) 136.884155 136.884327 136.884241
22:0) 136.884155 136.884241 136.884198
23:0) 136.884155 136.884198 136.884177
24:1) 136.884177 136.884198 136.884187
25:1) 136.884187 136.884198 136.884193
26:0) 136.884187 136.884193 136.884190
27:1) 136.884190 136.884193 136.884191
28:0) 136.884190 136.884191 136.884191
29:1) 136.884191 136.884191 136.884191
30:0) 136.884191 136.884191 136.884191
まずは緯度-180から180の範囲からスタートし、上の段のビット列をフラグとして、最初は1なのでその半分の0から180を選択します。次も1なので、0,180の中間90から180を選択します。このように30ビット分選択します。
経度については-90から90の範囲からスタートして、同様に選択していきます。
1:1) 0.000000 90.000000 45.000000
2:0) 0.000000 45.000000 22.500000
3:1) 22.500000 45.000000 33.750000
4:1) 33.750000 45.000000 39.375000
5:0) 33.750000 39.375000 36.562500
6:0) 33.750000 36.562500 35.156250
7:1) 35.156250 36.562500 35.859375
8:0) 35.156250 35.859375 35.507812
9:0) 35.156250 35.507812 35.332031
10:0) 35.156250 35.332031 35.244141
11:0) 35.156250 35.244141 35.200195
12:0) 35.156250 35.200195 35.178223
13:0) 35.156250 35.178223 35.167236
14:1) 35.167236 35.178223 35.172729
15:0) 35.167236 35.172729 35.169983
16:1) 35.169983 35.172729 35.171356
17:0) 35.169983 35.171356 35.170670
18:1) 35.170670 35.171356 35.171013
19:1) 35.171013 35.171356 35.171185
20:1) 35.171185 35.171356 35.171270
21:0) 35.171185 35.171270 35.171227
22:1) 35.171227 35.171270 35.171249
23:1) 35.171249 35.171270 35.171260
24:0) 35.171249 35.171260 35.171254
25:1) 35.171254 35.171260 35.171257
26:1) 35.171257 35.171260 35.171258
27:0) 35.171257 35.171258 35.171258
28:1) 35.171258 35.171258 35.171258
29:1) 35.171258 35.171258 35.171258
30:0) 35.171258 35.171258 35.171258
12文字だと精度が高いので、緯度経度どちらも30bitにたどりつくまでに有効桁数で変化がなくなりますが、精度が低いところでは地図上の範囲を表現していることが理解できます。
緯度経度からGeohashへの変換は、その座標がどの範囲なのかを判定してフラグをビットにしていく方法でできます。
このテストで、やはりビット操作はC言語がやりやすいとあたらめた思った次第です。