Google Maps APIのエンコード化ポリラインアルゴリズム
Google Maps APIでは線や多角形を描けますが、緯度経度の座標が多くなると、ファイルが座標で埋め尽くされてしまいます。そこで、座標を圧縮する方式として、エンコード化ポリラインアルゴリズムが用意されています。この方法では、座標列は文字列に置き換えられます。
Google Maps API V3では、ジオメトリライブラリを組み込んで、 google.maps.geometry.encoding.encodePath(path)でエンコーディングされた文字列を取得することができ、decodePath() により元の座標列に戻すことができます。
この機能を使って、エンコード化するWebサイトを作成しました。
http://ktgis.net/lab/software/encoding/index.html
しかし、JavaScriptを使用せず、他言語からエンコードするには、アルゴリズムを理解しておく必要があります。その点については、Google Developersに親切な説明があります。
https://developers.google.com/maps/documentation/utilities/polylinealgorithm?hl=ja
これを順番に見ていきます。※は私のコメントです。
１．最初の符合付き値を取得します:
-179.9832104
２．10進値を取得して 1e5 で乗算すると、結果は丸められます:
-17998321
※ここで注意すべき点は、精度が小数点以下5桁という点です。
３．この10進値を2進値に変換します。負の値は2の補数を使用して計算する必要があります。それには2進数を反転し、結果に1を加えます:
00000001 00010010 10100001 11110001
11111110 11101101 01011110 00001110
11111110 11101101 01011110 00001111
４．2進値を左に1ビットシフトします:
11111101 11011010 10111100 00011110
※３と４は、2進数に直して演算するように書いてあるりますが、実際は普通に元数値を2倍するだけであす。-17998321*2=-35996642
５．元の 10 進値が負の場合は、このエンコーディング結果を反転します:
00000010 00100101 01000011 11100001
※これもビット演算子で反転させることができます。
JavaScriptなら~-35996642=359966411
６．2進値を5ビットの集合に分割します（右側から）:
00001 00010 01010 10000 11111 00001
※ここから2進数文字列として操作する必要があります。
７．5ビットの集合を逆の順序に並べ替えます:
00001 11111 10000 01010 00010 00001
※文字列を分割して個別の6つのバイト変数に入れ、並べ替えます。
８．後続のビット集合が続く場合は、各値に 0x20 の論理和演算を行います:
100001 111111 110000 101010 100010 000001
※「後続のビット集合が続く場合」とは、6バイト目だけでなく、後ろから00000が続く場合はその直前も含まれます。そうしたケース以外は、32を加算します。
９．各値を10進値に変換します:
33 63 48 42 34 1
10．各値に 63 を加算します:
96 126 111 105 97 64
11．各値を対応する ASCII 文字に変換します:
`~oia@
※８．で書かれているように、後ろに0があるケースでは、6文字よりも少なくなります。
※元数値が0の場合は、説明には書いてありませんが、アスキーコード63の?となります。
こんな感じで変換し、緯度の場合も経度の場合も同じです。そして、緯度経度の順に文字列を追加していきます。
ただし、座標列の2地点目からは、前の地点からのオフセット値を使用します。
また、注意すべき点として、変換後の座標の文字列に\（円マーク）が含まれることがあります。JavaScriptでは、\が特殊文字として扱われるため、JavaScriptの文字列変数に代入するには、\\としておかなくてはいけません。
最後に、精度の問題があります。２．のように、小数点以下5桁までの精度となっており、その上2つめの座標からオフセット値となるため、誤差が発生していきます。単独のポリゴンであれば、目立ちませんが、隣接するポリゴンの場合、拡大して表示すると、重複したり、隙間ができたりします。
この問題を避けるためには、実際の座標値と、小数点以下精度5桁でのオフセット値の累積を比較し、誤差が大きくなったらオフセット値を調整してやる必要があります。
Google Maps API V3では、ジオメトリライブラリを組み込んで、 google.maps.geometry.encoding.encodePath(path)でエンコーディングされた文字列を取得することができ、decodePath() により元の座標列に戻すことができます。
この機能を使って、エンコード化するWebサイトを作成しました。
http://ktgis.net/lab/software/encoding/index.html
しかし、JavaScriptを使用せず、他言語からエンコードするには、アルゴリズムを理解しておく必要があります。その点については、Google Developersに親切な説明があります。
https://developers.google.com/maps/documentation/utilities/polylinealgorithm?hl=ja
これを順番に見ていきます。※は私のコメントです。
１．最初の符合付き値を取得します:
-179.9832104
２．10進値を取得して 1e5 で乗算すると、結果は丸められます:
-17998321
※ここで注意すべき点は、精度が小数点以下5桁という点です。
３．この10進値を2進値に変換します。負の値は2の補数を使用して計算する必要があります。それには2進数を反転し、結果に1を加えます:
00000001 00010010 10100001 11110001
11111110 11101101 01011110 00001110
11111110 11101101 01011110 00001111
４．2進値を左に1ビットシフトします:
11111101 11011010 10111100 00011110
※３と４は、2進数に直して演算するように書いてあるりますが、実際は普通に元数値を2倍するだけであす。-17998321*2=-35996642
５．元の 10 進値が負の場合は、このエンコーディング結果を反転します:
00000010 00100101 01000011 11100001
※これもビット演算子で反転させることができます。
JavaScriptなら~-35996642=359966411
６．2進値を5ビットの集合に分割します（右側から）:
00001 00010 01010 10000 11111 00001
※ここから2進数文字列として操作する必要があります。
７．5ビットの集合を逆の順序に並べ替えます:
00001 11111 10000 01010 00010 00001
※文字列を分割して個別の6つのバイト変数に入れ、並べ替えます。
８．後続のビット集合が続く場合は、各値に 0x20 の論理和演算を行います:
100001 111111 110000 101010 100010 000001
※「後続のビット集合が続く場合」とは、6バイト目だけでなく、後ろから00000が続く場合はその直前も含まれます。そうしたケース以外は、32を加算します。
９．各値を10進値に変換します:
33 63 48 42 34 1
10．各値に 63 を加算します:
96 126 111 105 97 64
11．各値を対応する ASCII 文字に変換します:
`~oia@
※８．で書かれているように、後ろに0があるケースでは、6文字よりも少なくなります。
※元数値が0の場合は、説明には書いてありませんが、アスキーコード63の?となります。
こんな感じで変換し、緯度の場合も経度の場合も同じです。そして、緯度経度の順に文字列を追加していきます。
ただし、座標列の2地点目からは、前の地点からのオフセット値を使用します。
また、注意すべき点として、変換後の座標の文字列に\（円マーク）が含まれることがあります。JavaScriptでは、\が特殊文字として扱われるため、JavaScriptの文字列変数に代入するには、\\としておかなくてはいけません。
最後に、精度の問題があります。２．のように、小数点以下5桁までの精度となっており、その上2つめの座標からオフセット値となるため、誤差が発生していきます。単独のポリゴンであれば、目立ちませんが、隣接するポリゴンの場合、拡大して表示すると、重複したり、隙間ができたりします。
この問題を避けるためには、実際の座標値と、小数点以下精度5桁でのオフセット値の累積を比較し、誤差が大きくなったらオフセット値を調整してやる必要があります。
この記事へのコメント