GPSルート探索スクリプト「電猫」――実地テストはまだ見えず

懸案だった点群道路地図生成の高速化を試みて見ましたが、未だに2倍程度しか速くなって無いようです。これではまだ実用には程遠いことには変わりません。「ランダムにプロットされた全点に対して、4つの近接点を選んでインデックスとして記録する」という単純な動作なのですが、極上位の数値だけ優先的に高速ソートしてくれる良いアルゴリズムは無いものでしょうか。

もしくは、全体構造を変化させて、点群道路地図を分割生成させて（同じ面積でも、小さい地図生成の方がずっと速い）、いちいちナビを開始・終了させるような感じにした方が良いのでしょうか？長距離のナビ時に分割した検索を行う事も可能になるので、一見良い様に思えるのですが、どの範囲の点群地図を使うかでルート生成に制限が生じるため、おそらくルートの質が低下します。悩み所です。