3

私はOSMにとても慣れていません。MScプロジェクト用のJavaアプリをビルドする必要があります。このプロジェクトでは、アプリはOSM（XML形式）から生データをダウンロードし、解析してアプリに表示する必要があります。その後、アプリにルーティングサービスをデプロイする必要があります。正直なところ、これまでやったことがないので、今はとても混乱しています。私を助けることができるアイデアやソースコードはありますか？手伝っていただけませんか？

どうもありがとうございます。

4

2 に答える 2

16

piccolo2dのような2D描画フレームワークを使用して、マップをレンダリングできます。また、ルーティングについては、マップ上の道路/道路、それらがどのように結合するか、および表される距離を説明するグラフを作成する必要があります。マップ上で始点と終点を選択すると、星などのアルゴリズムがポイント間の最短経路を見つけるのに役立ちます。

詳細：

OSM XMLダンプは、次の3つのクラスのエンティティで構成されています（これよりも複雑です。詳細については、公式ドキュメントを参照してください）。

  • ノード：経度と緯度で定義された、マップ上の単一のポイントを表します。これらは注目すべき特徴（多種多様ですが、たとえば、お店、古代の記念碑、小道の門など）を表すか、道の一部です。
  • 方法：マップ上のポリゴンを表します。これらはノードの順序付きリスト（idで参照）で構成され、道路やパス（ルーティングの問題に関連）などの線形のものだけでなく、フィールドや森林の境界、都市部の形状、湖などの境界領域も表すことができます。 、川など。
  • 関係：ここでは取り上げませんが、公式ドキュメントでこれらの詳細を確認できます。

上記の3つのノードタイプのそれぞれには、ノード/ウェイによって表されるエンティティのタイプを指定するキーと値（文字列）のペアである「タグ」の形式でそれらに関連付けられた追加データがあります。一般的なリストはここにあり、ルーティングのリストはここにあります。小さな地方道路（この場合はドイツ）を表すOSMWebサイトから抜粋した例：

<!-- The nodes representing points along the way -->
<node id="298884269" lat="54.0901746" lon="12.2482632" ... />
<node id="261728686" lat="54.0906309" lon="12.2441924" ... />
...
<node id="298884272" lat="54.0901447" lon="12.2516513" ... />

<!-- A way, built of the points above, with a tag
     declaring it to be an unclassified road -->
<way id="26659127" ...>
    <nd ref="292403538"/>
    <nd ref="298884289"/>
    ...
    <nd ref="261728686"/>
    <tag k="highway" v="unclassified"/>
</way>

2つの道路が交差する場合（たとえば、2つの道路が交差する場合）、交差点で共通のノードを共有します。

ルーティンググラフの生成に必要なデータにフィルターをかけるには、次のことを行う必要があります。

  • 関心のある領域のXMLを読み、少なくともノードとウェイを読みます。
  • タグに基づいて必要な方法のみを残して、フィルターで除外します（たとえば、k = "highway"など）。
  • 残りの関連する方法で参照されているノードを除くすべてのノードを除外します。

必要な情報のみを分離したら、OSM形式からルーティングにより適した形式に変換する必要があります。説明したOSMグラフはルーティングに使用できますが、マップを各ウェイの開始と終了のノードのセット、およびウェイ間の交差点と交差間のパスを表すエッジのセットとして表す方が効率的です。 、長さとともに。

たとえば、次のように変換したい場合があります（ab、cd、efが交差する方法で）：

OSMノードと方法

より多くのようなものに：

ルーティンググラフ

エンドノードと交差するノードのみが残る場所。この表現では、ルーティンググラフ（ax、cx、xe、ed、xy、ey、yf、yb）の3つの方法から8つのエッジに変換し、各エッジは、ノードのノードに沿ってステップすることによって計算した関連距離を持ちます。方法、あなたが行くにつれて距離を蓄積する:(例えば、ax：200m、ey：350mなど）。ここで式を見つけることができる経度/緯度空間の隣接するポイント間の距離を計算する必要があることに注意してください。

このデータは、独自のデータ構造を使用するか、JGraphTやJungなどのサードパーティのグラフライブラリを使用して表すことができます。ここから、ルーティングは（大雑把に言えば、残りのノードのセットが必要なすべての開始点/終了点を表すのに十分にきめ細かいものであると仮定して）、旅の開始を表すノードを選択することです。最後に、A-starなどのアルゴリズム（上記のとおり）を使用して最短経路を計算します。

唯一の落とし穴は、私が覚えている限り、私が言及した2つのライブラリのどちらにもA-starの実装がないということです。ただし、ダイクストラの最短パス（両方のライブラリに存在）を低速で実行することで正しい結果を得ることができます。概念に自信がある場合は、自分でA-starを実装してください。

これらすべてをより面白くするために、距離を使用する代わりに、推定移動時間でルーティングすることができます（道路の平均速度を考慮に入れます）。または、ルートの望ましさに基づいて距離を変更することもできます。たとえば、サイクリングの場合は、交通量の少ない道路で距離を減らして、より長く安全なルートを選択します。ハイキングの代わりに、特に風光明媚なエリアを通過するパスや、古代のモニュメントやパブなどのランドマークの近くを通るパスの距離を短くします。

OSMデータ用の適切な既存のルーティングサービス（Cloudmadeなど）があることを考えると、このようなことをしたい主な理由は、独自のカスタム距離メトリックを使用するためです...

于 2012-06-20T20:50:15.583 に答える
8

アレックスの答えには重要な部分が含まれています。特にノードを必要なものだけに減らすために!!

興味のある方は、GraphHopperプロジェクトでJavaでこれらすべてを開発し、非常に大まかなSwingUIを使用しました。

また、ダイクストラ、双方向ダイクストラ、アスターが実装されています。私のテストでは、ルートの近似値を返さないように強制すると、星はダイクストラより30％遅くなります。将来、近似を可能にするために実験しますが、それまでの間、通常のダイクストラよりも約50％高速な双方向ダイクストラを使用できます;）次のように機能します。

ここに画像の説明を入力してください

于 2012-06-29T12:49:25.937 に答える