接続された凸ポリゴンのグラフを生成します

Question

私は次のようなポイントの密なグラフを取ろうとしています これ, 、そして、それを接続された凸ポリゴンのグラフに変えます。ポリゴンは、接続を維持している間、できるだけ大きく、できるだけシンプルでなければなりません。結果のグラフは、パスファンディングに使用されます。誰かが私を正しい方向に向けることができますか？

Answer 1

リンクを投稿できないのは非常に迷惑です。潜んでいることを難しくし、たまに唯一の参加者になります。

私は次の手法を使用することになりました：

まず、距離変換を作成します。ここで説明したアルゴリズムを使用した[リンクできない]を使用して、このような画像[リンクもできない]になりました。次に、DTの分岐点変換を作成して、エリアに分割します。これにはいくつかの作業が必要ですが、現在は[リンクできない]のように見えます。その後、各エリアのペアを接続するポリリンの中間点を使用して、ウェイポイントグラフを作成します。

結果

流域分配はまだ完璧ではありません。エイリアシングがバンディングを引き起こすことに注意してください。

Answer 2

これはあなたが求めたものではありませんが、ここにこの2Dパス計画の問題を解決するための他のアイデアがあります。

• 使う*。これにより、最短の衝突自由パスが得られます。ビットマップが簡素化されていなくても、パフォーマンスは問題ない場合があります。

• 使う サンプリングベースのロードマップ. 。これは、ポリゴンよりも別の離散化された表現です。検索スペースは小さいため、ビットマップ全体を通過して、すべてのポイントがロードマップに接続できることを確認できます。もし コンパクト ロードマップは重要です（ただし、短いパスはそうではありません）、 可視性ロードマップ テクニックを使用できます。

とにかくグラフの表現とグラフの検索に対処する必要があるため、これらの手法はポリゴン抽出よりもはるかに簡単に見えます。私はその問題についていくつかの質問を掘りました：

• ビットマップをポリゴンに変換します
• 単純な形状ビットマップをベクトルに変換するにはどうすればよいですか

スペースがポリゴンによってマッピングされている場合（おそらくツールを使用している場合）、凸ポリゴンまたは検索できる他の表現に分割できます。これはLavalleによっても議論されています：

• 垂直（台形）細胞分解
• 最短パスロードマップ