GPSルート探索スクリプト「電猫」――久々の改善案

あまりに遅い点群道路地図生成で行き詰まっていた電猫ですが、一応一つ改善案が浮かんだので、備忘録的に書いてみます。方針としては、極端に時間を食う大型データのソート回数を減らしたい、という感じです。

• 現状の変換アルゴリズム

1.地図読み込み
2.中心＋オフセット→全点群プロット
3.点群の相互距離計算
4.相互距離から近接点選び出し、上位から点群同士のリンク付け

• 改良アルゴリズム

1.地図読み込み
2.中心＋オフセット→全点群プロット
3.点群の相互距離計算
4.各点の相互距離を距離順にソート
5.各点の近接点を、ソートされた距離の上位から検索してリンク付け

こうして見ると手順は増えている様に感じますが、全ての点ごとにソートを行わず、一括したソートを行いたい、という感じです。逆に遅くなるかもしれませんが、打開策の一つとしてちょっと実装してみようと思います。