GPSログデータを自作コードでGPSBabel並みの精度で間引けるか?

以前「Google Mapsの地図にGPSログを描いてブログに画像として表示する方法 」という記事で、perlやGPSBabelを使って、Google Mapsの地図データ+GPSログデータを画像としてブログに貼り付ける方法をご紹介しました。自分でもこの方法でやっていたのですが、いかんせん面倒。

Polar RC3 GPSのGPXファイルをWebからダウンロードするのはいいとして、その後GPSBabelでCSV化(ファイル名を指定したりパラメタを設定したり...)してperlで整形してURLやHTMLの雛形に貼り付けて編集して...。なんとか自動化できないものでしょうか?

ここで最も重要となるのが、GPSログデータの間引き。GoogleのStatic Maps API V2には、渡せる文字数は2048バイトまでという制限があります。 逆算すると、GPSログデータは92ポイントまでしか使えません (92ポイントで、座標データ以外の文字を合わせて2016バイトになります)。RC3 GPSの場合、GPSログデータは1時間あたり3600ポイント(秒1ポイント×60秒×60分)のデータになりますから、かなり高精度に間引かないと、自分の走った軌跡がきれいに地図上に再現されません。

ネットを調べてみると、ポリラインの間引きはRamer-Douglas-Peuckerアルゴリズムというものが定番のようです。考え方が面白いですね。シンプルでいいです。

でも、他にもいろいろやり方があるんじゃないか? と思い、自分でも間引き方法を考えてみました。発想は単純で、全体の形状への寄与が小さいポイントから順に取り去っていき、所望のポイント数(今回は92ポイント)になるまで繰り返す、というものです。全体形状への寄与については、データ全体ではなく、判定対象の点とその前後の点だけで判断しています。

1. 点A,B,Cの並びが直線に近いほど、Bの寄与が小さいとみなす。
2. 点A,B,Cの間の距離が小さいほど、Bの寄与が小さいとみなす。
3. この基準で全てのポイントに点数をつける。
4. 点数が最小のポイントを取り除く。
5. その両端のポイントの点数を更新する(間のポイントがなくなったので)。
6. 所望のポイント数になるまで4,5,6を繰り返す。

すごく処理時間がかかるコードになりました。計算量のオーダーがそもそも他の方法より大きそうです。言語を変えるだけでもだいぶ速くなるでしょうけど、今日のところはお遊びなのでこの程度でよいです。結果は下の図のようになりました。南大沢と上柚木あたりを走った時のGPSデータ(GPX)で、各ラインの色の意味は以下のとおりです。

• ピンク　：オリジナルの全ポイント
• ブルー　：自作コード
• グリーン：GPSBabel v1.5.1
• グレイ　：Ramer-Douglas-Peuckerアルゴリズム

図はクリックで拡大します。

自作アルゴリズムは、若干細かな特徴にとらわれる傾向があるようですが、GPSBabel、Ramer-Douglas-Peuckerアルゴリズムに比べても(このデータだけなら)大きく劣ることはなさそうです。感覚的にはGPSBabelが最もバランスが良さそうに見えました。Ramer-Douglas-Peuckerアルゴリズムは、高速で結果も悪くないのですが、ところどころおおまかな形状に影響するポイントをスキップすることがあるみたい。またこのアルゴリズムは、残すべきポイント数を指定するのではなく、許容する誤差の大きさを指定するタイプなので、何度かパラメタを変えて92ポイント残るように試す、という手間があります。高速なので何度か実行して収束するようにコードを書けばよいでしょう。

自作コード

GPSBabel v1.5.1

Ramer-Douglas-Peuckerアルゴリズム

方法を考えるのがパズルのようで面白かったですが、結果を得るだけなら、ネットに転がっているRamer-Douglas-Peuckerアルゴリズムを持ってくるのが手っ取り早くて正解ですね。その分ランニングなりなんなり、時間を有効活用できるでしょう。せっかく作ったので、GPSBabelに精度で勝てないか、後で暇があればコードを修正してみるかもしれません。

話がGPSデータの間引きだけになってしまいましたが、それができたので、GPSデータからダイレクトにGoogle Maps画像のURL/HTMLを生成するコードは簡単にできました。めでたしめでたし。