GPSログ(トラック)の点を間引く

GPSの座標情報は大抵の場合1秒に1回やってきます。これを全部保存すると1時間で3600、半日で43200もの位置情報になり、保存するにもファイルが無駄に大きくなるし表示するにも無駄に重くなる。

このため実用に必要十分な数に点を間引くのですが、主にやられるのがこの二つ。

・一定時間で間引く(例えば10秒毎に記録
・一定距離で間引く(例えば10m進んだら記録

ただし、この2つはどちらもあんましよろしくない。
単に等時間や等距離で無造作に点をピックアップしていくため、データを軽くしようと時間や距離を大きくとると元の軌跡との乖離がどんどん大きくなってしまいます。かといって間隔を狭めるとそれに反比例してデータが肥大します。
等間隔による間引き

これはかなりいただけないのでできるだけ元の軌跡との乖離が少なくなるような別の方法を考えます。でも「乖離が一番小さくなる最適解」を求めるのは計算が面倒くなるのでやりません。GPSから送られてくる位置情報を保存する手前に挟むフィルターとして実装しやすいってことで、次のような方法で間引きます。
 「開始点P(0)から連続する点が一定の幅に収まる一番先の点P(N)を探し、その間のP(1)〜P(N-1)を削除」
P(N)を探してその間の点を削除したら、P(N)を基準(P(0))にして次の間引きをやります。

名称未設定-1
位置情報がGPSから徐々に送られてきます。ベースの点と最新の点に線を引き、その間の点がこの線の幅wに収まる間は取り敢えずバッファに溜めときます。

名称未設定-2
まだまだ収まるのでバッファに溜めます。

名称未設定-3
ところが次の点は中間の点が幅wに収まらなくなってしまいました。
なのでその手前の点が「幅wに収まる一番遠い点」になります。

名称未設定-4
というわけでその点を保存します。中間の点はフィルタアウト。

名称未設定-5
最後に確定した点をベースとして、同様の作業を続けます。

名称未設定-6
で、こんなカンジにデータを間引くことができます。

GPSのログは真っすぐ進む時は割と真っすぐ進み曲がる時はカクっと曲がることが多いので等時や等距離でやるよりもより少ない点数でより好ましい形にすることができます。
先に書いたように最適解じゃないけど楽に実装できる現実的な落としどころということで。

幅wはおいらのアプリでは2mくらいです。テキトーなのは緯度経度から平面座標への変換をものすごいいい加減にやってるためw

蛇足ながら実際の計算はというとまず基点(P0)と最新の点(P3)を結ぶ線の単位法線ベクトル(N3)を計算して、あとは基点と中間の点を結ぶベクトルとその法線ベクトルの内積をとればその絶対値が基点と最新の点を結ぶ線に降ろした垂線の長さになるよね的な。これが閾値を越えたらアウアウ。
名称未設定-7

んで、このアルゴリズムはログの保存だけでなく画面に表示する用に点を間引くためにも使います。一言で説明が終わるハナシではあるんですがもったいぶって次のエントリーで。