ルートの簡略化

アメリカでのドライブ旅行中に記録したGPSログは全部で15,587ポイントになっていた。全体を見たい時にこれらを全て使用してしまうと大変だ。重くて使い物にならない。ということでルートを簡略化するツールを作ってみた。

単純に一定間隔で間引くだけだと大きく形状が損なわれてしまう可能性があるので、なるべく誤差を小さくしつつ間引くことが出来るか以下のようにやってみた。

foreach( i:= 全ての点 )
{
　点iを間引いた場合に発生する誤差を求める
}

while( 点の数が目的の数になるまで )
{
　誤差が一番小さい点を間引く
　間引いた点に隣接する二点の誤差を再計算する
}

（始点と終点の誤差は無限大として、絶対に間引かれないようにした。）
この方法で15,587ポイントのログを1/100の155ポイントに簡略化した結果が以下の通り。全体図で見るとまあうまく出来てる気がする。

●オリジナル


●1/100に簡略化したもの


細部を見てみる。

フェニックスの辺り。思いっきり簡略化されているけど、まあ許容レベルだと思う。

オリジナル	1/100

モニュメントバレーの辺り。ここもまあいいかな。

オリジナル	1/100

アーチーズ。公園内の三箇所のポイントに行ったことが表現できてて満足。

オリジナル	1/100

ブライスキャニオン。途中で途切れててこれは少し失敗かな。。。

オリジナル	1/100

まだ多少の不満はあるので、今後は誤差に重みを付けてもう少し試してみよう。周辺に点がたくさんあるかどうかや、その頂点が鋭角だったら優先度を上げたりしてやってみようかな。あとは点を削除した後に周辺の点を動かして誤差を小さくするようにするとか。

ちなみに1/100のやつをGoogle Mapsに貼り付けたルートはココ。これなら軽くてイイ感じ。