7

Javaを使用して.osmマップ上の最短パスを見つけるための単純なダイクストラのアルゴリズムを実装しました。

.osmファイルから作成されたグラフのパスファインディングは非常にうまく機能します。しかし、ユーザーの現在の場所や目的地がこのグラフのノードではない場合（生の座標のみ）、パスファインディングを機能させるために、これらの座標をグラフに「リンク」するにはどうすればよいですか？

「現在のロケーションノードに最も近いものを見つけて直線を描く」という単純で単純な解決策は、現実的ではないようです。添付の写真のような状況になった場合はどうなりますか？（UPD） ここに画像の説明を入力してください

ここでの問題は、「スマートな」パスファインディングアルゴリズム（ダイクストラのような）を開始する前に、現在の位置をグラフに「リンク」することですが、これは、地理的座標とこの式は「パスファインディング」ではありません-障害物やノードのタイプを考慮に入れることはできません。

言い換えると、Bがグラフのノードであり、Aがノードではない場合、AとBの間の最短経路をどのように見つけるのでしょうか。

この問題に対する他の解決策について聞いたことがありますか？

4

5 に答える 5

3

あなたが説明しているプロセスは「マップマッチング」であり、空間インデックスを使用して最も近いノードを見つけます。

一般的なアプローチの1つは、すべてのノードを含むクワッドツリーを構築し、ポイントを含むクワッドを識別してから、ポイントからクワッド内のすべてのノードまでの距離を計算することです（縦方向の角度は緯度方向の角度よりも短いことを認識しています）。クワッドにノードがない場合は、検索を徐々に拡張します。四分木にはいくつかの注意点がありますが、これで少なくとも始めることができます。

于 2011-04-12T12:08:40.950 に答える
1

実際には、問題を無視して、提案されたアルゴリズム「最も近いノードへの直線」を使用します。ルーティング可能なエンティティにできるだけ近づけるのは、ユーザーの責任です。あなたが提案した最初の推測が誤解を招くものだった場合、ユーザーはそれに応じて開始位置を変更できます。

無人地帯で実際に旅を始めるユーザーは、対象となるエリアについて、アルゴリズムよりもはるかに多くのことを知っていることを願っています。彼を信頼してください。

ところで、これはOpenRouteServiceとGoogle Mapsが使用しているアルゴリズムです。

それでも納得できない場合は、「障害物を越えない最短の直線」を使用することをお勧めします。それでも不十分な場合は、たとえば 5mx5m の仮想グリッドとその対角線を定義します。グラフの頂点に到達するまで、最短経路アルゴリズムをスパンします。

于 2012-08-09T12:01:36.040 に答える
0

本当にいい質問です！

ノードだけでなく、ライン/エッジにもインデックスを付けることができるため、クワッドツリーはソリューションです。

しかし、この「素朴な」アプローチの問題は、これらのソリューションがメモリを大量に消費することです。たとえば、最短経路計算用の非常に大きなグラフが既にある場合は、クワッド ツリー用に同じかそれ以上のメモリが必要です (または、非常にばかげたことをしていました)。

1 つの解決策は次のとおりです。

  • 使用領域上のグリッドである配列を使用します。つまり、エリアをタイルに分割でき、タイルごとにノードのリストを含む配列エントリがあります。
  • したがって、配列エントリごとに、そのタイル内のノードのリストが表示されます。エッジの場合、両方のノードをエントリに追加できます。このタイルにノードを持たずにタイルを横切るエッジがある場合は注意してください。BresenhamLine アルゴリズムがここで役に立ちます。
  • クエリ: 入力 ala (緯度、経度) をタイル番号に変換します。配列エントリからすべてのポイントを取得します。ユークリッド幾何学を使用して、ポイント Aへのノードとエッジの最近傍を計算します(最近傍の場合のように、ノードが遠すぎない限り問題ありません)。

この説明は分かりやすいですか？

更新 これはGraphhopperに実装されました!

よりメモリ効率の高いソリューションを得るには、1 つのエントリ (タイル) に対して同一のノードを単純に除外する必要があります。

メモリ使用量を減らすためのもう少し複雑なテクニック: グラフ トラバーサルがタイル境界を尊重する場合、グラフはそのタイルのいくつかのサブグラフに分割されると想像できます (つまり、グラフ トラバーサルは他のサブグラフに到達しません)。タイル境界内のグラフ)。これで、すべてのノードが必要になるわけではなく、別のサブグラフにあるノードだけが必要になります! これによりメモリ使用量が削減されますが、クエリを実行している間は、(現在のグラフホッパーの実装のように) 1 つのエッジだけでなく、さらにトラバースする必要があります! タイル全体をトラバースする必要があるため、つまり、タイルの境界を超えない限り。

于 2012-08-09T10:52:47.477 に答える
0

現在の場所をノードとして扱い、そのノードを最も近いいくつかのノードに直線で接続できます。GPS アプリケーションは、この直線を「オフロード」と見なすため、この直線のコストはノード間の他の直線に比べて非常に高くなります。

ただし、添付の写真が表示されなかったので、これが適切な解決策かどうかわかりません。

于 2011-04-12T10:09:41.247 に答える
0

パスに制約がある場合は、同じ最短パス問題の線形計画法を使用することを検討する必要があります。

http://en.wikipedia.org/wiki/Shortest_path_problem

目的は、.osm ファイルで定義された開始と終了の「ノード」の間の各「ウェイ」の距離の合計を最小化することです。あらゆる障害は、制約として定式化されます。Java で実装するには、以下のリンクを参照してください。

http://javailp.sourceforge.net/

于 2012-09-15T11:21:24.920 に答える