モールや空港などの屋内の場所を基本的に Google マップであるアプリケーションを作成したいと考えています。フロアプランからグラフを作成し、最短経路探索アルゴリズムを使用して、ある場所から別の場所への最短ルートをプロットする必要があることはわかっています。モールや空港をグラフで表現するにはどうすればよいですか? 各店舗やゲートなどをノードとして作成し、通路をエッジとして作成しますか? それとも、ノードを 5 ～ 10 フィートごとに作成するなど、もっと具体的にする必要がありますか? ノードとエッジはどの程度具体化する必要がありますか?
2 に答える
0
ここで解決したいいくつかの異なる問題があります。第一に、2つの場所の間に構造的な関係があり、第二に、幾何学的な関係があります。最短経路は、一部はジオメトリに依存し、一部は構造に依存します。例えば。経路は直線である必要はありません。構造については、モールの店舗とゲートをノードとして表し、経路をエッジとして表すことができます。ノード間の実際の距離をエッジの「重み」として置き、Dijstraのalgorihtmを使用して最短経路を見つけます。
「Aに移動してからBに移動」のように結果をテキストで表示する必要がある場合、またはメトロ（地下）スタイルのトポロジマップで表示する必要がある場合は、これで問題ありません。ただし、床の幾何学的に正確な表現で結果を表示する場合は、構造とジオメトリの間の接続を強化する必要があります。パスが曲がるところすべてにノードを追加し、x、y座標でノードにマークを付け、中間ノードであるかどうかをブール値で示すことで、上記の構造を拡張することをお勧めします。ソースと宛先として選択可能な真のノードのみを作成しますが、ダイクストラのグラフ全体を使用します。画面に結果を描画するときは、最短経路のノードを反復処理し、それらの座標を使用して、ソースから宛先まで区分的に直線を描画します。
于 2012-05-27T21:25:08.350 に答える
0
各セルがx平方メートルを表すグリッドとしてフロア プランを認識することをお勧めします。アクセス可能な領域内にある各セルにノードを配置します。エッジは各隣接セルの間にあり、すべてxのコストがあります。
このアプローチの利点は、これを効率的にメモリに配置できることです (行列に配置することができ、行列リストなどを使用する必要はありません)。経路探索には、2 点間のユークリッド距離をヒューリスティックとして使用する単純な A* 実装を使用できます。
于 2012-05-27T20:41:32.410 に答える