16

Garmin や TomTom のようなナビゲーション システムは、常に私を魅了してきました。小さなマップ/ナビゲーション アプリケーションを実装して、さまざまなパス アルゴリズムを試し、それらに関する知識を広げたいと考えていました。

これは 2 つの部分からなる質問です。

1.) 地図データはどのように保存されますか? - 道路のネットワークがある場合、このデータは通常どのように保存されますか? 後で地図を再現するために、データのどの部分が保持されますか? 各道路は、方向を変える一連のポイントとして保存されていますか? このデータはどのようなファイル形式で保存されますか? これらのファイルを簡単に解析するために公開されているライブラリはありますか? 地図/道路データがどのように保存/表現されるかについての詳細を誰かが持っていますか?それは非常に役に立ちます.

2.) ナビゲーション/パス- このマップ データ (ガーミン風) で基本的なパスを実行する場合、有向グラフに変換されるという私の仮定は正しいですか? 各道路交差点は、頂点間の距離を重み付けするエッジを持つ頂点ですか? これは私がやろうと思っていたことなので、基本的なよく知られているパスアルゴリズムを試してみて、何が得られるかを確認してください。

米国で公開されているこの地図データを見たことがありますが、それがどのように表されているか、また有向グラフを作成できるほど詳細であるかどうかはわかりません。

誰かが情報を持っていれば、私はそれを感謝します。詳しい知識があればあるほど有利です。

4

6 に答える 6

9

以前の応答はすべてGISシステムを参照しています。これは、PND（ポータブルナビゲーションデバイス）の仕組みではありません。デスクトップ/ワークスタットレベルのGISソフトウェアを実行するには単純すぎます。

代わりに、PNDはSimucalが推定したのとほぼ同じように情報を保存します。道路はセグメントに分割されています。これにより、モデルが非常にシンプルになります。セグメント内では、最高速度などの属性は変更されません。

計画の目的で、道路セグメントはグラフのエッジとして機能します。ノードごとに、着信ノードと発信ノードの両方が保存されます。次に、修正されたA*アルゴリズムを使用して計画が行われます。エッジの重みは通常、距離ではなく、推定移動時間（TomTomの場合は実際の測定時間）です。

ただし、道路網は通常階層的であり、通常のA*は遅いスターターです。ある町から別の町に移動するとき、A*はスタートタウンを這うのに過度の時間を費やします。しかし、私たち人間は、長距離を移動するときは高速道路を使用するのが最善であることを知っています。それが彼らの目的です。PNDも同様に高速道路を好みます。また、高速道路は非常にまれであるため、これにより多くのメモリが節約されます。

もう1つの最適化は、前方検索と後方検索です。両側から中間点に向かって計画します。これの大きな利点は、間違った方向に進んだ場合、新しい開始点から再度検索できることです。目的地が移動しなかったため、後方検索ツリーは変更されていません。

于 2008-12-09T14:56:33.030 に答える
6

ナビゲーション システムの単位についての詳細はわかりませんが、標準の GIS の世界では、マップ データは基本的にポリゴン、ライン、ポイントのコレクションとして格納され、それぞれが座標 (および使用される投影法とその他のパラメーター) によって記述されます。たとえば、最も一般的な形式の 1 つであるシェープファイルについてはこちらで説明されており、データベース ベースの形式標準はこちらで説明されています。

PostgreSQL、PostGIS、およびPGRoutingを使用して、このストレージ モデルを道路表示とルート計算に使用することに成功しました。計算は通常のグラフ アルゴリズムを使用して行われ、共通の形式で保存されたデータは、それらのアプリケーションを可能にするためにグラフとしても保存されます。コンピューティング能力が限られているため、その経験を組み込みデバイスに当てはめることはできません。彼らはおそらく多くのものを事前に計算しています。

ストレージへの多少異なるアプローチについては、OpenStreetMapを確認してください

于 2008-10-07T06:05:12.003 に答える
2

保存される正確な方法は、形式によって異なります。さまざまなGIS形式のヒープがあります。GDALは、（ほぼ）すべてを読むための優れた無料ライブラリです。

通常、道路は「ラインレイヤー」としてファイルに保存されます。これは、メタデータが添付されたポリラインのセットです。したがって、各道路には一連の頂点があり、データの品質に応じて、片道かどうか、速度の見積もり、ある種の接続IDなどの情報が含まれていることが望ましいです。

はい、それらは通常、解くために有向グラフに変換されます。エッジの重みは、距離、またはより便利なことに、そのエッジを移動するのにかかる時間です。

迅速に解決することは、事前計算とストレージスペースの間のトレードオフです（組み込みデバイスでは、ここでPCとは異なる選択が必要になる場合があります）。それを行うための非常に興味深いアルゴリズムがいくつかあります。

于 2008-10-08T02:55:15.193 に答える
2

Mohammed: わかりました。最初の質問はその点に関してかなり快適に思えたので、ここではあまり詳しく説明しませんでした。グラフ理論に慣れていない場合は、ここで少し読むことをお勧めします。ウィキペディアは入門としては問題ありません。

通常、GIS データでは、道路はメタデータが添付されたポリラインとして保存されます。それらを画面上に表示するなどには問題ありませんが、それらをナビゲートできるようにするには、どれが互いに接続されているかを知る必要があります。したがって、メタデータには通常、道路の両端にノード ID が含まれているため、「これは道路セグメント 457 で、ノード 332 からノード 667 まで続いています」と言うことができます。したがって、GIS データを読み込むと、アークで接続された一連のノード (つまり、グラフ) としての表現が作成されます。

そのメタデータが利用できない場合は、どの道路が同じ開始/終了座標を持っているかを推測できます (これは、あまり良くない GIS データの場合です)。「有向」ビットは、道路に方向があることを意味します。道路にはどちらの方向にも通行できるものもあれば、一方通行のものもあります。

有向グラフを通るパスを見つけるための典型的なアルゴリズムは、ダイクストラのアルゴリズムです。実際にはさまざまな派生物が使用されます。基本的には、グラフの弧に沿ってノードからノードへと移動する必要があるため、それをサポートするには適切なデータ構造が必要です。

それが役立つことを願っています...

于 2008-10-23T01:25:46.043 に答える
2

ルーティング アプリケーションがどのように機能するかを理解するためにコードを調べたい場合は、openstreetmap.org wikiからリンクされているルーティング アプリケーションをいくつか見てみてください。Navit と Gosmore はどちらもオープン ソースであり、特にセットアップがかなり簡単です。

Gosmore アプリケーションの開発者である Nic Roets は、道路ベクトル データを表現するための彼の選択について興味深い投稿を書いています。

Gosmore の動作を確認したい場合は、openstreetmap データに基づくyournavigation.orgルーティング Web サイトのバックエンドです。

于 2009-02-18T14:25:34.700 に答える
-1

より多くのストレージと制限された解像度を犠牲にして描画速度を向上させるために、多くのアプリケーションはGeoTiffなどの地理参照されたラスター形式を使用します。

その下のZichによるかなりしつこいコメントを考えると

「例外なく、すべてのナビゲーション システムでデータはベクトル化されています!」

上記の内容を少し補足したいと思います。まず、ナビゲーション システムを、現在地に基づいて行きたい場所にたどり着く方法を支援するシステムと定義します。これは通常、可能な代替ルートをいくつか計算し、最もコストの低いルートを推奨することによって行われます。可能なルートは、交通手段によって決まる場合があります。たとえば、車は道路にとどまりますが、丘を歩く人はそうしません。ルートのコストは、輸送モードやユーザーの要件によっても異なる場合があります。自動車は道路速度に基づいて最速のルートを取りたいと思うかもしれませんし、トラックは最も燃料効率の良いルートを求めているかもしれませんし、丘の歩行者は最も安全な直接ルートを求めているかもしれません。ボートや飛行機は危険な気象システムを避けながら、燃料費と費やされる時間を最小限に抑えたルートを求めているかもしれません。 .

最も単純なレベルでは、地図とコンパスはナビゲーション システムです。地図を小さな画面、スケーラブルなラスター マップ、GPS に置き換えても、ナビゲーション システムはそのままです。ローエンドからミディアム エンドの海上ナビゲーション システムのほとんどは、今でもこの方法で機能し、海岸線と海底を表すチャートと GPS を使用して位置情報を提供し、エコー サウンドで深さを確認します。

スペクトルのより高度な末端では、マーズ ローバー ナビゲーションシステムなどの自律型ロボット ナビゲーション システムが、短距離ナビゲーションの基礎としてオンザフライで DTM モデルを生成し、長距離ナビゲーションのために衛星が収集した DEM を生成します。

すべてのナビゲーション システムが消費者向け Garmin または Tom Tom デバイスのように機能することを示唆するのは、かなり単純な推定です。FWIW、多くの最新の Garmin デバイスにはラスター ベースの DEM データも含まれており、低コストの GPS 高さは非常に不正確になる可能性があります。

于 2008-10-07T06:43:04.220 に答える