3

2次元平面上にある場合は、いいえです。可能性のあるすべての 2D 形状 (円、四角形、三角形、不規則な形状など) の障害物について、障害物を回避する最短経路を見つけるメカニズムをどのように実装しますか? そのような図を描画するための多くのグラフィカルクラスを提供するため、ビジュアル C++ を検討しています。

かなり遠くまで来ました

1) まず、A* search(A-star) を使用して、最小コストのパスを見つけます。

2) 直線パスからの変位が最も少ないパスがベスト パスと見なされます。（確かではありませんが）

3) 図形を回避するための最短経路 (たとえば、最初から) は、その点から までの直線です。

a) the farthest vertex in case of a polygon/quadrilateral
b) a point on the circumference such that the line drawn would be tangential to the circle, in case of a circle or arc
c) (not sure about irregular figures)

ここに画像の説明を入力

ここで 2) に戻ります。2 つ以上の経路間の最小変位は、これらの線からの垂線を、それぞれの側にあるオブジェクトの最も遠い点と比較することによって決定できます。（私が自分自身を理解したことを願っています）。

では、どのように直線経路に垂線を引くのでしょうか? ここに画像の説明を入力

x1、x2、y1、y2、k、lは既知です。a,bを見つけるだけです。

直線パスの勾配 * 垂線の勾配 = -1

=> (y2-y1)/(x2-x1) * (b-l)/(1-k) = -1
hence, b = [(x1-x2)/(y2-y1) * (a-k)] + l

ピタゴラスの定理を使うことで、座標に関して他の方程式を見つけることができると想像しました。各線の長さは次の方法で求めることができます: dx = x1-x2 dy = y1-y2 dist = sqrt(dx dx + dy dy)

そして、これらの 2 つの式を解くことで、a,bの正しい値を見つけることができます。

これ以上何も考えられません。アイデアや提案はありますか?

4

3 に答える 3

3

すべての形状に多角形 (つまり、直線セグメント) 近似を使用することは可能ですか? これにより、アルゴリズムの実装が大幅に簡素化されます。

これが実際に可能であると仮定すると、A* を使用する場合は、可能なパスのグラフ表現が必要になります。このグラフのノードは、次の組み合わせです。

  • すべての形状のすべての頂点[1]、および
  • 始点と終点
  • {開始点と終了点の間の直線セグメント} とすべての図形の間のすべての交点。

したがって、このグラフのエッジは、次の場合にのみノードの各ペアの間にあります。

  • 対応する 2 つの頂点間に直線が存在する
  • それはどの形状とも交差しません[2]。

グラフの各エッジの長さは、それが表す 2 つの頂点間の (ユークリッド) 距離であり、最短経路は常にこれらのエッジのサブセットです (私が思うに)。これは、このグラフに A* を適用することで見つけることができます。 .

[1] - 頂点の数を減らすために、すべての凹形状を凸形状にすることができます (これにより始点または終点がそのような形状の内側にある場合を除き、凹形状のままにする必要があります)。

[2] - kD や四分木などのさまざまなデータ構造を使用してこれらのクエリを高速化するか、スイープ ライン アルゴリズム ( http://en.wikipedia.org/wiki/Bentley%E2など) を使用することができます。 %80%93Ottmann_algorithm ) を二重接続エッジ リストと組み合わせて使用​​します。

于 2012-11-05T20:24:47.030 に答える
0

2 番目の点については、点 (l,k) がある場合。(l,k) から等距離にある直線 (x1,y1),(x2,y2) 上の 2 点を考えます。したがって、垂線は (x1,y1) と (x2,y2) から等距離にあるすべての点の組み合わせになります。

于 2012-11-06T10:45:46.393 に答える
0

これが役立つかどうかはよくわかりませんが、とにかく、すべての不規則なオブジェクトを円のような通常のオブジェクトの組み合わせに分割して、曲線の半径が変化し続けるようにすることができます。異なる半径。

于 2012-11-06T10:12:51.463 に答える