GPSは近隣の道路を見つける

Question

私はGPSアプリケーションを構築しています。私は道路オブジェクトのコレクションを持っています。それぞれ、始点と終点を含んでいます（そして、道路が湾曲している他の中間点）。私はdijkstraのアルゴリズムを実装しました。最短経路（道路はグラフのノード）が見つかりましたが、実行する前にどの道路が隣り合っているかを判断してエッジを作成する必要があります。

簡単な（？）方法は、各道路を繰り返し、入れ子にされたループ内で、他の道路も同じ点で開始/終了するかどうかを確認することです。しかし、これはO（N^2）という非効率的なようです。 1つのアイデアは、道路を地域に事前に分けることでした（つまり、英国ではNW、NE、E、SE、SWなどがあります）。その後、同じ地域の隣人だけが検索スペースを縮小します。

経験豊富なプログラマーから助言を受けて、どのように問題に取り組んでいますか？

これは宿題ではなく、最近卒業しました。実践的な経験を積み、CVを少し補うためにペットプロジェクトとして取り組んでいます。

編集：私はyで最初にして、xで、道路が唯一のこれまであなたが持っているポイント全ての（x、y）を並べ替えることができ

Answer 1

スタート/エンドポイントで接続して追加する必要があります。 n点の場合、これはO（nlogn）でなければなりません。また、基数ソートを使用する場合は線形です。それからあなたはリストを通過する必要があります。隣接する2つのエントリが等しいときはいつでも、それらの対応する道路が交差する。