Inside of FieldAccess」カテゴリーアーカイブ

画面に表示する用にトラックの点を間引く

前回のエントリ GPSログ(トラック)の点を間引く でGPSログを保存する方法として「間引かれた点が設定した幅を越えてハミ出さないようにする」ってのを書きました。

この方法は地図の縮尺に合わせた間引き加減のトラックを用意するってのにちょうどよかったりします。

例えば20万分の1地勢図上にGPSログをプロットしていくことを考えます。
この縮尺だと地図上の0.1mmは実際の20mになりますので、20m以内の軌跡のフレは地図上の0.1mm以内のフレということでもうペンの滲みみたいなもんです。なのでこの縮尺においては前回のエントリの方法で

 幅20mを閾値として点を間引く

とすれば、間引かれたログでも元のログとほとんど変わらない形状を地図上にプロットできることが保証されます。他の縮尺の場合でも、地図上での許容幅を考えてそれに合わせてログのフレ幅の閾値を設定すればよい。

これが等時間や等距離での間引きだとこうはいかず、どの縮尺の時にどれくらいの間隔に設定したらいいのかは勘や経験則に頼る他ありません。

タイルマップに合わせてズームレベル毎に最適な点数の軌跡を用意する場合は、ズームレベルがひとつ下がると縮尺が半分なので倍の幅の閾値で間引けばいいかんじです。
名称未設定-8-のコピー
黄→青→赤→緑、と順に倍の幅で点を間引いた例。それぞれを例えばz=16、z=15、z=14、z=13のズームレベルの時に表示すれば、閾値の幅が画面上で一定になる。

この方法の欠点は

  間引かれる点の数をコントロールしずらい

ってところで、等時間や等距離で間引く場合は「半分の縮尺用に点の数を1/4に減らす」ってのは楽にやれますが、この方法だと幅wを倍にしても点の数が1/2とか1/4に減るのかというとその辺の保証が全然ない。「縮尺が変わっても点の密度を一定にしたい」と思っても困ったことになる。

でももともと等時間や等距離でやるよりも少ない点数で十分な軌跡を表示できるし、実際実装してやってみた印象では広域用に幅を大きくするとそれに見合った分以上に点の数が減ってくれるカンジがします。(個人的な感想です)

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

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

いんさいど おぶ ふぃ〜るどあくせす

おいらは生粋のうんこプログラマでどれくらいうんこかというとコレにものすごい勢いで当てはまるうんこプログラマですが、これでもプログラマの端くれとしてiOS用の地図アプリを作ってたりなんかしまして、極稀に地図描画エンジン部分のところをお褒めいただいたり、どんな実装になってるのかって質問をほんのちょびっと頂いたりするので、うんこがその気になってどんなコードで動いているかをちょっとずつつらつら書いて恥を晒していこうとかいう企画。

を、始める予定

なんだけどうんこプログラマなので目下の仕事を片付けるのが精一杯なのでいつ始まるかは未定(‘A`)