Google Map エンコードポリライン

私のホームページ(http://www.gps-walk.com/yama/110521/map.html)や
弟のホームページ(http://www.55walking.sakura.ne.jp/yama/110723/map.html
そして私が担当している「清水北山好会」のホームページ(http://sks.dojin.com/report/110828/map.html)のGoogle Map は、10進法のデータを64進法に変換してデータ量を少なくし表示速度を得ている。
この変換は Google サイト(http://code.google.com/intl/ja/apis/maps/documentation/utilities/polylinealgorithm.html)のアルゴリズムを見ると、とても面倒なように見え、かなり敷居が高そうだ。

同じことを感じているページが、ここにもあった。 http://blog.livedoor.jp/g0031067/archives/51496182.html
ところが、そのページの下の方に

3番~5番までの処理がわずか4行で記述されていました。
function conv(lat){
  var num = lat<<1; //1ビット右へシフト
  if ( lat < 0 ) { //マイナスの場合は
    num = ~(num); //not値を取得
  }
  return num;
}

と書いてある。
つまり、Google のアルゴリズムのページに書いてある下記の3~5番の処理を上記の function conv(lat) と言う簡単なファンクションで処理できるらしい。これは凄い!!
これなら自分にもできるかも知れない。

1.最初の符合付き値を取得します:
   -179.9832104
2.10 進値を取得して 1e5 で乗算すると、結果は丸められます:
   -17998321
3.この 10 進値を 2 進値に変換します。
  負の値は2 進値に変換し、2 の補数を使用して算出して、1 を加える必要があることに
  注意してください。
   00000001 00010010 10100001 11110001
   11111110 11101101 01011110 00001110
   11111110 11101101 01011110 00001111
4.2 進値の 1 ビットを左にシフトします。
   11111101 11011010 10111100 00011110
5.元の 10 進値が負の場合は、このエンコーディング結果を反転します。
   00000010 00100101 01000011 11100001
6.2 進値を 5 ビット単位に分割します(右側から)。
   00001 00010 01010 10000 11111 00001
7.5 ビットの集合を逆の順序に並べ替えます。
   00001 11111 10000 01010 00010 00001
8.後続のビット集合が続く場合は、各値に 0x20 の論理和演算を行います。
   100001 111111 110000 101010 100010 000001
9.各値を 10 進値に変換します。
   33 63 48 42 34 1
10.各値に 63 を加算します。
   96 126 111 105 97 64
11.各値を対応する ASCII 文字に変換します。
   `~oia@

そこで、2~3年前に参考にしてやってみようと思った「hiroaki氏」のホームページ「What hwat?」のエンコードポリライン関連ページを読み返してみた。

「hiroaki氏」の制作過程の記事と Java Script で書かれた「GPX Casual Editor」のソースとGoogleページのアルゴリズムとを比較しながら1行ずつ読んでいった。

「hiroaki氏」の「GPX Casual Editor」は Java Script で書かれている。
私のツールは VBScript で書いている。
Java Script に書き直してもいいが、どうやら Java Script にはファイルをコピーしたり、追加したりする機能はないというようなことが、どこかに書いてあった気がするので、書き慣れた VBScript から離れられずにいた。

しかし、VBScript はビット演算をすることができないらしい。
ネットを探したが、ビット演算子はついに見つけることができなかった。
代わりにややこしい方法でビット演算を試みているページが見つかった。
http://www.geocities.co.jp/SiliconValley/4334/unibon/asp/bitshift2.html
この通りにやればできるのかも知れないが、JavaScript なら a = b << 1; という簡単な方法でできることが、余りにも複雑な手順を踏まないとできないことに嫌気がして、VBScript のビット演算は諦めた。

参考にした「hiroaki氏」の「GPX Casual Editor」のJavaScript ソースは複雑でかつ膨大であるため全部は解読できなかったが、EncordPolyline の処理過程は良く分かるように書いてある。

Googleのアルゴリズムの6番から11番までの処理を「hiroaki氏」は、たった9行で実現している。素晴らしい!!

var encodeNumber = function(num){
  var encodeString = '';
  while( num >= 0x20 ){
    encodeString += (String.fromCharCode((0x20 | (num & 0x1f)) + 63));
    num >>= 5;
  }
  encodeString += (String.fromCharCode(num + 63));
  return encodeString;
};

また、Googleのアルゴリズムの3番から5番の処理は、上の囲い枠の中と全く同じ処理で実行していた。
多分こうした処理は、分かっている人にとっては当たり前の処理法なのだろう。誰がやってもこうなるしかない処理なのかも知れない。

var encodeSignedNumber = function(num){
  var sgn_num = num << 1;
  if( num < 0 ){
    sgn_num = ~(sgn_num);
  }
  return(encodeNumber(sgn_num));
};

実に明快な処理だ。
感心するほかない。

GoogleMap の縮尺を高縮尺率にした場合、省略するポイントを決める「num level」という値を決め、エンコードする部分は多少面倒な処理が行われていたが、「hiroaki氏」の処理は簡潔明瞭で無駄がない。
私が考えたら、ポリラインのポイントのエンコードと表示レベルのエンコードは別々にしそうだが、それを一度に同じルーチンを使って処理しているところが凄い。

事前に悩んだのは、VBscript と JavaScript は混在できることは分かっていたが、VBScript でGPXデータを取り込んだのは、2次元配列だ。
JavaScript には1次元配列しか認められてないらしいので、2次元配列に取り込んであるGPSデータを、果して JavaScript から読めるのかどうかが心配だった。

取り敢えず、恐る恐る2次元配列のGPSデータの3番目ぐらいのデータを読んで表示させてみた。
ところが不思議、ちゃんと読めている。
半信半疑だったので
  alert(gpsData( i, 1 ))
で、i を順次変化させて、元のGPXデータを比較してみたが、どれも全く同じ値が取れている。
i = 100 にしても、i = 200 にしても、どんな値を代入しても、全く同じ値が取れている。
これは、行ける!!! たまたま偶然に値が一致しているだけではなさそうだ。
へー! JavaScript でも、ちゃんと2次元配列の値が読めるのか・・・・!!
しかも、配列の書き方は角カッコ([ ])ではなく VBScript の丸カッコのままでOKなんだ・・・。

今までのGPS軌跡作成ツールに、JavaScript の EncordPolyline の部分を追加して書き上げたツールで、山好会の会長が登った「乗鞍岳」の軌跡(http://sks.dojin.com/report/110828/map.html)を描いてみたら、見事に描くことができた。
これに気を良くして、私の「ホノケ山」の軌跡(http://www.gps-walk.com/yama/110521/map.html)を描かせてみたら、何故か表示しない。
撮影地点のマーカーは描けるが、GPS軌跡は描けてない。
何度試しても結果は同じ。

「hiroaki氏」のソースはオブジェクトとして結果を吐き出しているが、私の場合は単なる文字列として吐き出している。
この事が原因かもしれないと思って、「hiroaki氏」のツールで得た64進文字列と、私のツールで得た文字列を比較してみたら、途中まではきっちり文字列が一致しているが、「\」のところで「hiroaki氏」の文字列は「\\」に、私のは「\」のままだ。
なるほど、これだ。

先の「乗鞍岳」はたまたま「\」に変換される「29」の数値が出現しなかっただけのようだ。
メタキャラクタをそのまま使っていることがダメだったのだ。単なる文字列として「\」を使うために、メタキャラクタの機能を打ち消す必要があるのか・・・・。
「hiroaki氏」のツールでは、それを自動的に行えるらしい。
私の場合は、それができていない。そこで、正規表現で文字列変換する

newpolyline = encordline.replace(/\\/g,"\\\\");

の1行を最後に追加してみた。
結果は上々。見事表示に漕ぎ着けることができ、めでたし! めでたし!

最後に「hiroaki氏」の「GPX Casual Editor」をほとんどコピーして作成したコードは下記の通り

' [EncodedPolylineの64進数を作成する部分]
'--------------------------------------------
'EncodedPolyline作成
'--------------------------------------------
<script language="Javascript">

function createEncodedPolyline(){

	var DFLT_BASE_DISTANCE = 500000;
	var DFLT_ZOOM_FACTOR   = 2;
	var DFLT_NUM_LEVELS    = 18;

	var gpolylinepoint0 = '';
	gpolylinelevels     = '';


	// 符号なし値
	var encodeNumber = function(num){
		var encodeString = '';
		while( num >= 0x20 ){
			encodeString += (String.fromCharCode((0x20 | (num & 0x1f)) + 63));
			num >>= 5;
		}
		encodeString += (String.fromCharCode(num + 63));
		return encodeString;
	};

	// 符号付き値
	var encodeSignedNumber = function(num){
		var sgn_num = num << 1;
		if( num < 0 ){
			sgn_num = ~(sgn_num);
		}
		return(encodeNumber(sgn_num));
	};

	// ズームレベル
	var segments = new Array(DFLT_NUM_LEVELS);
	for( var z = DFLT_NUM_LEVELS - 1; 0 <= z; --z ){
		segments[z] = DFLT_BASE_DISTANCE * Math.pow( DFLT_ZOOM_FACTOR, -1 * z );
	}

	// 緯度・経度をエンコードする
	var firstPoint  = null;
	if( 0 < maxRow ){
		firstPoint = new GLatLng( gpsData(2,1), gpsData(2,2) );
	}
    	var lastGlatlng = new Array(DFLT_NUM_LEVELS);
    	for( var j = 0; j < DFLT_NUM_LEVELS; ++j ){
        	lastGlatlng[j] = firstPoint;
    	}

	var plat = 0;
	var plon = 0;
	for( var j = 2; j < maxRow; ++j ){
		var lat = parseFloat(gpsData(j,1));
		var lon = parseFloat(gpsData(j,2));
		var level = 0;
		if( j == 2 || j == maxRow - 1 ){
			/* first and last point have to be visible */
			level = DFLT_NUM_LEVELS - 1;
		}else{
			var glatlng = new GLatLng(lat,lon);
			for( var z = DFLT_NUM_LEVELS - 1 ; 0 <= z  ; --z ){
				var distance = glatlng.distanceFrom(lastGlatlng[z]);
				if( segments[z] < distance ){
  					level = DFLT_NUM_LEVELS - 1 - z;
					lastGlatlng[z] = glatlng;
				}
			}
		}
		var late5 = Math.floor(lat * 1e5);
		var lone5 = Math.floor(lon * 1e5);
		dlat = late5 - plat;
		dlon = lone5 - plon;
		plat = late5;
		plon = lone5;
		gpolylinepoint0 += encodeSignedNumber(dlat) + encodeSignedNumber(dlon);
		gpolylinelevels += encodeNumber(level);
	}
	gpolylinepoints = gpolylinepoint0.replace(/\\/g, "\\\\");
}

</script>
データ
  • 2011.09.06(火)
ほかの参考サイト
アーカイブ

現在位置: ホームなんでも日記メニュー > このページ