連結された凸多角形のグラフを生成

thisのような点の密なグラフを取得し、それを連結した凸多角形のグラフに変換しようとしています。ポリゴンは接続している間はできるだけ大きく、シンプルでなければなりません。得られたグラフは、経路探索に使用されます。誰かが私を正しい方向に向けることができますか？連結された凸多角形のグラフを生成

出典

2011-01-20 Anthony

これは以前に尋ねられなかったとは思いません。最初に検索してください。これはおそらくあなたにいくつかのアイデアを提供します。または、見つかった解決策がお客様の要件に合わない理由を説明することで、より良い質問を策定できます。 –

スタークラフトマップのように疑わしく見える... –

まさにスタークラフトマップです。これは、ナビゲーションメッシュのトップダウンビューで、2Dコリジョンマップとして使用するための設定です。私は潜在的なフィールドを使用してローカル衝突回避を行うことができますが、ローカル最適化を避けるためには実際の経路探索の解決策が必要です。本質的には、共有エッジの中点をパスファインドするために凸多角形が必要です。三角形も同様に機能しますが、より多くの点が得られます。 – Anthony

。 lurker &に参加することは難しいです。

私は、次の技術を使用して終了：

まず、距離変換を作成します。ここで説明したアルゴリズム[リンクできません]を使用して、この[リンクできません]のような画像が生成されました。次に、DTの流域変換を作成して領域に分割します。これにはいくつかの作業が必要ですが、現在は[リンクできません]のように表示されます。次に、各領域のペアを接続するポリラインの中点を使用してウェイポイントグラフを作成します。

Result

流域分割は、バンディングの原因とエイリアシングを注意、まだ完璧ではないが、私は181のエリアと、この128×128マップの中間地点281で終わります。

出典

2011-02-02 05:16:40 Anthony

これはあなたが尋ねたものではないが、ここでは、この2次元経路計画問題を解決するためのいくつかの他のアイデアです：

使用A *は。これにより、衝突のない最短経路が得られます。ビットマップを単純化しなくても、パフォーマンスは正常です。
sampling-based roadmapを使用してください。これは、ポリゴンとは別の離散表現です。検索スペースが小さいので、ビットマップ全体をトラバースして、すべてのポイントをロードマップに接続できることを確認できます。 コンパクトロードマップが重要な場合（ただし、短いパスはありません）、visibility roadmapの手法を使用できます。

とにかくグラフ表示とグラフ検索に対処する必要があるため、これらの手法はポリゴン抽出よりもはるかに簡単です。私はその問題のためのいくつかのSOの質問掘り起こさ：スペースは（おそらくツールを使用して）ポリゴンによってマッピングされた場合には

を、それが凸多角形に分割することができますか検索可能な他の表現。これはまた、ラバルで議論されている：私はリンクを投稿することができないということは非常に迷惑です

出典

2011-01-21 02:47:11 antonakos

連結された凸多角形のグラフを生成

答えて

関連する問題