ジオポの符号化、復号化をいろんな言語で書いてみる

このエントリーをはてなブックマークに追加
はてなブックマーク - ジオポの符号化、復号化をいろんな言語で書いてみる
Facebook にシェア

位置情報をいくら短縮して色んなことに応用できるといっても、ユーザーが使ってくれるまでの敷居が高い(今のブラウザ経由の符号化じゃ、ダメってこと)とどうしようもない。

そんな理由で、まずはユーザーが接するアプリケーションの開発者サイドにジオポ実装を働きかけていきたい。そのためにも、具体的なサンプルコードをプログラミング苦手な僕が書いてみた。

と、その前に…
ジオポがネタフルで紹介されたよ!
位置情報を短縮したURLに変換するウェブサービス「ジオポ」

スクリーンショット付きで丁寧に紹介していただきありがとうございます。モチベーションあがりました!

実装するアルゴリズム

ジオポ 開発者向け情報にも書いたんだけど、ジオポの符号化はいろんな方法が考えられる。

その中でも、一番わかりやすいと思われる方法を各サンプルコードで実装することにする。

ジオポの符号化の実装

ジオポの符号化方法ですが、こちらで紹介する方法以外にもアルゴリズム(8進数化してビット演算など)はあると思います。ここでは、一番わかりやすいアルゴリズムを紹介します。また、文字ではわかりにくいと思いますので、実際にいろいろな言語で実装したコードは、付録をご覧ください。

変換する緯度・経度は度数法での度(D)表記での数値です。もし、度分(DM)表記や度分秒(DMS)表記の場合は、前もって度へと変換してください。
また、南緯と西経はそれぞれマイナス値となります。

緯度・経度からジオポへの符号化を実装するには、まず度数法で与えられる緯度・経度を十進数に変換します。
緯度と経度をそれぞれ90と180を足して正の値とします。それから、それぞれ90と180で割り、0から1までの値になります。最後に、8の10乗をかけます。

続いて、十進数化した緯度・経度がジオポ符号でのどのエリアにあたるかを算出します。
緯度は、8を9から縮尺を引いた回数だけ乗じた数字で割ってやり、さらに、その数値を8で割ったあまりを取り出します。経度も同様に、8を9から縮尺を引いた回数だけ乗じた数字で割ってやり、さらに、その数値を8で割ったあまりを取り出し、経度には8をかけてやります。その2つの数値を足すと0から63の数値となり、それに対応する文字がジオポ符号ということになります。

次の符号を上のルーチンを繰り返しますが、8を9から縮尺を引いた回数だけ乗じた数字という部分が変化する点に注意してください。この繰り返す回数により、ジオポコードの縮尺(Scale)を決定することができます。

復号化(デコード)

復号化する方法は符号化の逆をすることで実装できます(ジオポコードは可逆性を持ちます)。

ただし、ジオポは小縮尺にも対応しているため、小縮尺になるほど符号化した位置情報との誤差が大きくなります。その誤差をできるだけ平均にするため、緯度・経度をエリアの代表緯度・経度(エリアの真ん中の緯度・経度)へと変換する式が含まれています。

ジオポをクライアントソフト側で独自に復号化して緯度・経度を取り出したい場合は、ジオポURLからジオポコードを抽出する必要があります。
下記の正規表現を用いれば、ジオポコードを抽出することができます。

  • 四則演算
  • forループ
  • べき乗、切り捨て、余り の数学関数
  • 文字列の長さ、指定したサイズでの文字列の切り出し、文字列の中にある文字の位置 の文字列関数

キーとなる所はこんだけで、各言語にある関数などを言語間の違いに注意して実装してみる。

実際に実装

JavaScript
/*
 * GeoPo Encode in JavaScript
 * @author : Shintaro Inagaki
 * @param location (Object)
 * @return geopo (String)
 */
function geopoEncode(location){
	// 64characters (number + big and small letter + hyphen + underscore)
	var chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";

	var geopo = new String();
	var lat = parseFloat(location.lat); // Parse as float
	var lng = parseFloat(location.lng); // Parse as float
	var scale = parseInt(location.scale); // Parse as int
	
	// Change a degree measure to a decimal number
	lat = (lat + 90) / 180 * Math.pow(8, 10);
	lng = (lng + 180) / 360 * Math.pow(8, 10);

	// Compute a GeoPo code from head and concatenate
	for(var i = 0; i < scale; i++) {
		geopo = geopo + chars.substr(Math.floor(lat / Math.pow(8, 9 - i) % 8) + Math.floor(lng / Math.pow(8, 9 - i) % 8) * 8, 1);
	}
	return geopo;
}


/*
 * GeoPo Decode in JavaScript
 * @author : Shintaro Inagaki
 * @param geopo (String)
 * @return location (Object)
 */
function geopoDecode(geopo){
	// 64characters (number + big and small letter + hyphen + underscore)
	var chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";

	var location = new Object();
	var lat = 0;
	var lng = 0;
	var scale = geopo.length; // Scale is length of GeoPo code
	var order = 0;

	for (var i = 0; i < scale; i++) {
		// What number of character that equal to a GeoPo code (0-63)
		order = chars.indexOf(geopo.substr(i, 1));
		// Lat/Lng plus geolocation value of scale 
		lat = lat + Math.floor(order % 8) * Math.pow(8, 9 - i);
		lng = lng + Math.floor(order / 8) * Math.pow(8, 9 - i);
	}
	
	// Change a decimal number to a degree measure, and plus revised value that shift center of area
	location.lat = lat * 180 / Math.pow(8, 10) + 180 / Math.pow(8, scale) / 2 - 90;
	location.lng = lng * 360 / Math.pow(8, 10) + 360 / Math.pow(8, scale) / 2 - 180;
	location.scale = scale;

	return location;
}		

僕はジオポを最初にJavaScriptで作ったので、いわばこれが原型。

パラメーターがString型でそのまま入ってくるといけないので、最初にparseFloat()parseInt()でそれぞれ型を決めてやる。

そして、べき乗にはMath.pow()、切り捨てにはMath.floor()という数学関数があるので利用。

文字列。String.lengthは文字の長さ。JavaScriptの文字列の結合は+で、String.substr()メソッドによって文字列を切り出してやる。文字列の中にある文字の位置を取ってくるのは String.indexOf()メソッド。

JavaScriptはTry&Errorがしやすいから、実装の基本にするのに向いてるのかも。amachangさんが言ってたように、ブラウザさえあればどこでもプログラミングできるメリットもあるしね。

PHP
/*
 * GeoPo Encode in PHP
 * @author : Shintaro Inagaki
 * @param $location (Array)
 * @return $geopo (String)
 */
function geopoEncode($location) {
	// 64characters (number + big and small letter + hyphen + underscore)
	$chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";

	$geopo = "";
	$lat = $location['lat'];
	$lng = $location['lng'];
	$scale = $location['scale'];
	
	// Change a degree measure to a decimal number
	$lat = ($lat + 90) / 180 * pow(8, 10);
	$lng = ($lng + 180) / 360 * pow(8, 10);

	// Compute a GeoPo code from head and concatenate
	for($i = 0; $i < $scale; $i++) {
		$geopo .= substr($chars, floor($lat / pow(8, 9 - $i) % 8) + floor($lng / pow(8, 9 - $i) % 8) * 8, 1);
	}
	return $geopo;
}		

/*
 * GeoPo Decode in PHP
 * @author : Shintaro Inagaki
 * @param $geopo (String)
 * @return $location (Array)
 */
function geopoDecode($geopo) {
	// 64characters (number + big and small letter + hyphen + underscore)
	$chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";
	// Array for geolocation
	$location = array ();

	for ($i = 0; $i < strlen($geopo); $i++) {
		// What number of character that equal to a GeoPo code (0-63)
		$order = strpos($chars, substr($geopo, $i, 1));
		// Lat/Lng plus geolocation value of scale 
		$location['lat'] = $location['lat'] + floor($order % 8) * pow(8, 9 - $i);
		$location['lng'] = $location['lng'] + floor($order / 8) * pow(8, 9 - $i);
	}

	// Change a decimal number to a degree measure, and plus revised value that shift center of area
	$location['lat'] = $location['lat'] * 180 / pow(8, 10) + 180 / pow(8, strlen($geopo)) / 2 - 90;
	$location['lng'] = $location['lng'] * 360 / pow(8, 10) + 360 / pow(8, strlen($geopo)) / 2 - 180;
	$location['scale'] = strlen($geopo);

	return $location;
}		

なんちゃってPerlerからPHPに移行してもう何年も経つけど、やっぱりPHPが好き。未だに知らない関数ばかりだけどね ><

べき乗はpow()、切り捨てはfloor()。文字列の長さはstrlen()、文字列の切り出しはsubstr()、文字列の中にある文字の位置はstrpos()

こういう関数あるかなぁってマニュアル見ると、大抵あるから、CHM形式のマニュアルが手元にあると便利です。

Objective-C
/*
 * GeoPo Encode in Objective-C
 * @author : Shintaro Inagaki
 * @param geopo, latitude, longitude, scale (pointer)
 */
-(void)encodeGeopo:(id)geopo latitude:(double *)lat longitude:(double *)lng scale:(int *)scale {
	NSString *chars = @"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";
	
	*lat = (*lat + 90) / 180 * pow(8.0, 10.0);
	*lng = (*lng + 180) / 360 * pow(8.0, 10.0);
	
	for(int i = 0; i < *scale; i++){
		[geopo appendString:[chars substringWithRange:NSMakeRange(floor(fmod(*lat / pow(8.0, 9.0 - i), 8.0)) + floor(fmod(*lng / pow(8.0, 9.0 - i), 8.0)) * 8, 1)]];
	}
}		

/*
 * GeoPo Decode in Objective-C
 * @author : Shintaro Inagaki
 * @param geopo, latitude, longitude, scale (pointer)
 */
-(void)decodeGeopo:(id)geopo latitude:(double *)lat longitude:(double *)lng scale:(int *)scale {
	NSString *chars = @"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_";
	int order;

	*scale = [geopo length];
	
	for (int i = 0; i < *scale; i++) {
		order = NSMaxRange([chars rangeOfString:[geopo substringWithRange:NSMakeRange(i, 1)]]) - 1;
		*lat += (order % 8) * pow(8, 9 - i);
		*lng += floor(order / 8) * pow(8, 9 - i);
	}
	
	*lat = *lat * 180 / pow(8, 10) + 180 / pow(8, *scale) / 2 - 90;
	*lng = *lng * 360 / pow(8, 10) + 360 / pow(8, *scale) / 2 - 180;
}		

iPhone開発者に媚びを売るにはObjective-Cでの実装も必須だよね。でも、素直にCで書いたほうがよかったかもって後から思った。そんな、ダメダメなサンプルコード。つっこみ歓迎。

パラメーターはポインタで渡す。で、未だに理解できてないけど idやdoubleなどのプリミティブなオブジェクトを使うらしい。

整数のintなら%が余りとして利用できるんだけど、doubleなど浮動小数点になるとfmod()を使わなきゃならん。べき乗のpow()の中身も小数点付いてますよってことをアピールしてるんだけど、これって意味あったっけ?(c++の場合はこうじゃないと叱られた気がする) floor()で切り捨て。

文字列を切り出すにはsubstringWithRange: 使うんだけど、これの引数はNSRange型なので中でNSMakeRange()使ってNSRange型を作って渡してやる。そして、文字列をくっつけるにはappendString:。ただし、こうやって可変な文字列を扱うには文字列の型をNSMutableStringにしないとダメ(ここでいうgeopoの宣言)だから注意してね。

こっからが難問w 復号化のほう

文字列の中にある文字の位置を取ってきたいんだけど、一発でできるようなものはなかった><

仕方がないので、substringWithRange:で文字列を切り出してやって、それがどこの位置かをrangeOfString:で取り出すという二段構成に。ただ、それだけだとNSRange型が返ってきて、希望するintではないからNSMaxRange()で整数値にするという三段構成に。そうすると、先頭からの位置+1になり、帳尻をあわせるために最後に-1。

ひょっとすると、もっと簡単にサクッとできるような関数があるのかもしれない。あったら教えてくださいな。

しっかし、Objective-Cと他の言語を混ぜて考えると関数の形で混乱するわw

iPhoneアプリ作りは、ゆっくりとした休日にやろうと思った。

エクセル
ジオポのエンコード方法(エクセル関数)

以下で利用している【】はセルの位置です(A1、B4等)。各自読み替えて利用してください。

緯度を入力するセルの位置を【緯度】とします。
経度を入力するセルの位置を【経度】とします。
符号化に使用する文字列のあるセルを【符号】とし、
「0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_」
を入力します(「」は除いてください)。

ジオポコードの1文字目を出力したいセルに、
「=MID(【符号】,INT(MOD((【緯度】+90)/180*POWER(8,10)/POWER(8,9),8))+INT(MOD((【経度】+180)/360*POWER(8,10)/POWER(8,9),8))*8+1,1)」
とすると、1文字目のジオポコードが得られます。
同様に、
「=MID(【符号】,INT(MOD((【緯度】+90)/180*POWER(8,10)/POWER(8,8),8))+INT(MOD((【経度】+180)/360*POWER(8,10)/POWER(8,8),8))*8+1,1)」
とPOWERの2番目の引数を1引いてやると、2文字目のジオポコードとなり、2文字目以降も同じ繰り返しとなります。

それぞれのジオポコードのセルを&で結合してやれば、ジオポコードの文字列となります。

(例)
A1に緯度、B1に経度、C1に符号化文字列を入力。
A2に「=MID(C1,INT(MOD((A1+90)/180*POWER(8,10)/POWER(8,9),8))+INT(MOD((B1+180)/360*POWER(8,10)/POWER(8,9),8))*8+1,1)」と入力。
B2に「=MID(C1,INT(MOD((A1+90)/180*POWER(8,10)/POWER(8,8),8))+INT(MOD((B1+180)/360*POWER(8,10)/POWER(8,8),8))*8+1,1)」と入力。
C2に「=MID(C1,INT(MOD((A1+90)/180*POWER(8,10)/POWER(8,7),8))+INT(MOD((B1+180)/360*POWER(8,10)/POWER(8,7),8))*8+1,1)」と入力。
D2に「=MID(C1,INT(MOD((A1+90)/180*POWER(8,10)/POWER(8,6),8))+INT(MOD((B1+180)/360*POWER(8,10)/POWER(8,6),8))*8+1,1)」と入力。
E2に「=MID(C1,INT(MOD((A1+90)/180*POWER(8,10)/POWER(8,5),8))+INT(MOD((B1+180)/360*POWER(8,10)/POWER(8,5),8))*8+1,1)」と入力。
F2に「=MID(C1,INT(MOD((A1+90)/180*POWER(8,10)/POWER(8,4),8))+INT(MOD((B1+180)/360*POWER(8,10)/POWER(8,4),8))*8+1,1)」と入力。
A3に「=A2&B2&C2&D2&E2&F2」と入力すれば、A3で6文字のジオポコードが得られます。
		

最後にネタ的なエクセル関数を使った実装。

型の宣言しないで計算できるし好き。べき乗はPOWER()、切り捨てはINT()、余りはMOD()

そして、MID()は指定した範囲の文字列を取ってこれて、文字を結合するには&で繋げるだけ。

無駄が多くて関数が長くなったり、途中計算用のセルが必要になったりするけど、単純なエクセル関数でも実装できるってことが重要。Scale(縮尺)がないけど気にしない。

まとめ

簡単に実装できることを実証したかったんだけど、Objective-Cは時間がかかって気づいたら朝になってた…

いろんな言語に触れてみるのは楽しいね。今度は、C、Perl、Pythonあたりを挑戦してみるつもり。

タグ: , , , ,

コメントは受け付けていません。