このような点の密なグラフを取り、それを接続された凸多角形のグラフに変えようとしています。接続を維持しながら、ポリゴンはできるだけ大きくシンプルにする必要があります。結果のグラフは経路探索に使用されます。誰かが私を正しい方向に向けることができますか?
2 に答える
1
リンクを投稿できないのはとても迷惑です。潜伏者であり、たまにしか参加しないことを難しくします。
私は次のテクニックを使うことになりました：
まず、距離変換を作成します。ここで説明する[リンクできません]アルゴリズムを使用した結果、[リンクできません]のような画像になりました。次に、DTの流域変換を作成して、それをエリアに分割します。これには多少の作業が必要ですが、現在は次のようになっています[リンクできません]次に、領域の各ペアを接続するポリラインの中点を使用して、ウェイポイントグラフを作成します。
流域の分割はまだ完全ではありません。エイリアシングがバンディングを引き起こしていることに注意してください。しかし、この128x128マップでは181のエリアと281のウェイポイントになります。
于 2011-02-02T05:16:40.297 に答える
0
これはあなたが求めたものではありませんが、この 2D 経路計画の問題を解決するための他のアイデアを次に示します。
使う*。これにより、衝突のない最短経路が得られます。ビットマップを単純化しなくても、パフォーマンスは問題ない場合があります。
サンプリング ベースのロードマップを使用します。これは、ポリゴンとは別の離散化された表現です。検索スペースが小さいため、ビットマップ全体をトラバースして、すべてのポイントがロードマップに接続できることを確認できます。コンパクトなロードマップが重要な場合(ただし、短いパスは重要でない場合)、可視性ロードマップ手法を使用できます。
とにかくグラフ表現とグラフ検索を処理する必要があるため、これらの手法はポリゴン抽出よりもはるかに簡単に思えます。私はその問題についていくつかのSOの質問を掘り起こしました:
空間が多角形によって (おそらくツールを使用して) マッピングされている場合、凸多角形または検索可能なその他の表現に分割できます。これは、LaValle によっても議論されています。
于 2011-01-21T02:47:11.867 に答える