2Dメッシュサーフェスの最短経路の発見に問題があります

Question

私は3日前にこの質問をしましたが、私は十分な情報を含んでいなかったので貢献者によって燃えました。そのことについて謝ります。

私は2次元行列を持ち、各配列の位置はチャンネルの水深に関係していますが、私はDijkstraや同様の「最小コスト経路」アルゴリズムを適用して、水を渡る橋。

データをクリーンなバージョンにフォーマットするには時間がかかったので、私はいくつかの初歩的なMatlabのスキルを学びました。私は土地の大半を取り除いたので、今は海岸線が特定の値に標準化されています。私の計画は、 "西"海岸の各 "ピクセル"を通って移動し、それに対して最もコストの低いアルゴリズムを実行することです"東"海岸を通過し、最終的に最もコストの低いものを見つけるメッシュ全体を移動します。

これは私の問題です。データをアルゴリズムに当てはめてください。残念ながら、他の例が他のユースケースのためであるため、私はオプションと異なるフォーマットに圧倒されます。

私の他の考慮事項は、「最短コスト経路は、それがブリッジには適していないギザギザの線であろうと計算されたときに、私は全く可能であればパスに曲げ半径を制限する必要があると私はドンということですそれをやり遂げる方法を知っています。

チャンネルの画像：アプローチ方法で

何かアドバイスは素晴らしいことだ、私は誰かが動作するはずです方法を知っていれば、その後、私は学習時間を過ごすことになります知っている必要がありますどのようにデータを適合させるか。

Answer 1

あなたは、このようにあなたの問題にダイクストラを適用することができます。

1. あなたが値0で行列のエントリに対応して接続する二つの「ドライ」の領域は、他のセルは深度を指定する正の値を持ちます（またはコンクリートでこの場所を埋めるコスト）

2. あなたのエッジは、あなたのマトリックス内の隣接するセルの接続です。 （これは4または8近傍とすることができます）。エッジの重みは、接続されたセルの値の算術平均です。

3. 次に、ある「乾燥」領域に開始点、もう1つの「乾燥」領域に終了点を持つDijkstraアルゴリズムを適用します。

最も安いパスは値0の2つのセルを接続し、その重みは訪問されたセルのコストの合計に対応します。 （各セルの重量の半分がセルに向かうエッジから来ており、残りの半分はセルを離れるエッジから来ています）

この方法では、水の上を流れる可能性のある曲がりくねったパスが得られます安価な橋を建設するためのヒント。

計算を高速化するには、A *アルゴリズムを使用します。したがって、セルごとに相手側に到達するための残りのコストの下限が必要です。そのような下限は、リングが他の側の0セルを含まない限り、ある点の周りの「同心円の環」を調べることによって計算することができる。各リングの最小セル値の合計は、残りのコストの下限です。

Answer 2

あなたのブリッジにぎざぎざのない形状が必要であるという制約を強調する別のアプローチは、モンテカルロ、シミュレーテッドアニーリングまたは遺伝的アルゴリズムを使用することです。最初の「ブリッジ」は単純なスプライン曲線2つのランダムに選択された端点（1つの隙間の各側に1つ）と、小さな数またはランダムに選択された隙間の中間点との間にある。あなたは物理的に「現実的な」橋と合理的に最適化されたコンクリートのコストで終わるでしょう。