土地を描いたポリゴンで構成された（地理的な）地図と、土地にぶつからずにAからBに移動しようとしているボートがあります。できれば、利用可能な最短のパスをたどる必要があります。
私はほとんどの場合機能するアルゴリズムを持っていますが、それはかなり不器用で非効率的です。私が使用できるアルゴリズムへのヒントや参照は大歓迎です。
質問する
451 次
1 に答える
8
グラフを作成します。
- 各ポリゴンの各頂点、始点と終点に対して 1 つのノードを作成します。
- 障害物を通過せずに一方から他方に向かう直線がある場合、2 つのノード間にエッジを作成します。
A* アルゴリズム ( http://en.wikipedia.org/wiki/A_star ) を使用して、結果のグラフで最短パスを見つけます。直線距離として距離を推定します。
「興味深い」点のセットを決定できる限り、あらゆる種類の障害物を使用できます。それらは、障害物の各ペアのすべての接線の接触点です (凸多角形のほぼすべての頂点が「興味深い」ものです。 ) および同じ (非凸) 障害物に 2 回接触するすべての線。
于 2012-06-26T23:11:12.180 に答える