iPhoneマップアプリケーションの場合、グラフを作成するにはどうすればよいですか？

Question

私は、モールや空港などの屋内の場所にGoogleマップを基本的に使用してアプリケーションを作成したいと考えています。私はフロアプランからグラフを作成し、最短経路探索アルゴリズムを使用して最短経路をある場所から別の場所にプロットする必要があることを知っています。 モールや空港をグラフで表現するにはどうすればいいですか？私は各店舗やゲートや何かをノードとして、歩道をエッジとして作っていますか？あるいは、ノードを5〜10フィートごとに作るなど、もっと具体的にする必要がありますか？どのように具体的にする必要がありますか、ノードとエッジをどうすればよいですか？

Answer 1

私は、各セルがx平方メートルを表す格子として知覚することを提案します。アクセス可能な領域内にある各セルにノードを配置します。エッジは各隣接セルの間にあり、すべてがxのコストです。

このアプローチの利点は、効果的にこれをメモリにレイアウトすることです（これは、adiecencyリストなどを使用しなくても、マトリックスに入れることができます）。パス探索のために、2点間のユークリッド距離をヒューリスティックとして使用する単純なA *実装を使用することができます。

Answer 2

ここで解決したい問題がいくつかあります。まず、2つの場所の間には構造的関係があり、2つ目には幾何学的な関係があります。最短経路は、部分的に幾何形状に依存し、部分的に構造に依存する。例えば。経路は直線である必要はない。構造のために、あなたはモールストアとゲートをノードとして表現し、パスをエッジとして表現することができます。ノード間の実際の距離をエッジの「重み」に置き、Dijstra's algorihtmを使用して最短パスを見つけます。

「A、B、またはメトロ（地下）スタイルのトポロジマップで結果をテキストで表示するだけでよい場合は、これで問題ありません。しかし、床を幾何学的に正確に表現するために結果を表示するには、構造とジオメトリをより強固に接続する必要があります。私はあなたが上記の構造を増やすことをお勧めします。どこにでも追加ノードがあり、ノードがx、y座標でノードにマークするだけでなく、ノードが中間ノードであるかどうかを示すブールもマークされます。ソースとデスティネーションとして真のノードのみを選択できるようにしますが、グラフ全体をDijkstraに使用します。結果を画面に描画するときは、最短経路のノードを繰り返し処理し、その座標を使用してソースからデスティネーションまで直線的に直線を描きます。