GPSルート探索スクリプト「電猫」――1ピクセルの勝負と高速化

先日、「点群道路の生成はともかくとして」等と楽観視していましたが、これがとんでもない食わせ物でした。点群道路地図のインデックス作成は、それぞれの点が他の全点をスキャン＆ソートしていくため、点の数の「二乗」に比例して処理時間が増大してきます。とはいえ、たかが知れているだろうと思ってベタにスクリプトへ実装し、7.5×6.25kmの点群道路地図の生成を試みてみました。

・・・・・・・・・・・・・・・・・・・・

Pentium4(Willamette)1.4GHzのCPU時間を6時間50分消費しておきながら、進捗状況は現在5515/110950≒5%・・・・・たかだかこれだけの規模の地図生成に掛かる時間としては、既に異常の域です。ろくに動作確認すら出来ません＿|￣|○
ルート探索の方は、距離に対して比例する程度（現在は2kmルートで探索時間は4秒位）で、ノード分岐数が過剰でなければ、こちらの方はまだ我慢できる範囲で収まるかもしれません。先日の予想が、見事に逆転してしまいました（＾＾;;

とはいえ、点群道路地図生成は片手間で制作したものなので、一ノードに対して全点のソート処理が入っていたりと、まだまだ改善の余地があります。この辺をなんとかして、処理時間を1/10以下にしたいところです。

また、複数のラスタ地図にまたがって点群道路地図を生成する場合、地図同士のオーバーラップが無い状態でぴったり隣り合っていなければなりません。そのため、地図DLの座標オフセット部を見直して、XYの固定スケールから、地球を球体とした近似座標系に改善して計算を行ってみました（単純な計算なので、コサイン1個で済みます）。が、さすがに地図サイトの座標系は、厳密な楕円座標系で組んであるらしく、どうしても1〜2ピクセルのオーバーラップを生じています。点群地図は1/5に縮小した地図で生成しているので、このオーバーラップは許容できるか出来ないかギリギリの線な気がします。このズレが大丈夫なのかどうかを検証するためにも、早く上の高速化を実現しないといけませんね（＾＾;;