2点間の最短経路を見つけるプログラムを作ろうとしています。
私が思いついたのは、開始点をすべての形状のすべての頂点に接続することです。これらの各ポイントは他のすべてのポイントに接続され、一種のツリーを形成します。円形の場合-線は、円または円弧の接線を形成する点までになります（これがオブジェクトの周りの最短経路であるため）。ただし、他のオブジェクトを通過する線は破棄されます。残りのパスは*A**検索の対象になります。
しかし、他の図を通過する線をプログラムに識別させるにはどうすればよいですか？Visual C ++を使用しているので、特定の座標をそれぞれの関数（eg LineTo(21,23)）に渡すことで、クライアント領域に図形を描画できます。線が別の図に入っていることをどのようにして知ることができますか？
これまでに行ったことを考慮した単純なアルゴリズム：
ラインとエッジの交差をチェックすることは、ジオメトリの問題です。チェックしている線の境界点がP1 =（x 1、y 1）およびP 2 =（x 2、y 2）であり、エッジの境界点がP 3 =（x 3、y 3）およびPである場合4 =（x 4、y 4）次に、線形システムを解く必要があります。
（x 2 -x 1）y +（y 1 -y 2）x = x 1 y 2 -x 2 y 1、
（x 4 -x 3）y +（y 3 -y 4）x = x 3 y 4 --x 4y3。 _ _
（x、y）の値を取得したら、両方の線（チェックしている線とエッジ）の境界点の間の部分にあることを確認する必要があります。それが本当なら、あなたの線は互いに交差します。
注：衝突をチェックするときにすべてのオブジェクトのエッジを反復処理するのではなく、ラインのパスにあるオブジェクトのみを反復処理することで、実行時間を改善できます。これは、たとえば、すべてのオブジェクトを含む最小の長方形を計算し、線が長方形を通過するかどうかをチェックし、オブジェクトが通過しないかどうかをさらにチェックしないようにすることで実現できます。
あなたは2つのケースを区別することができます：
どちらかの線が別の線を介して図に入っています。その場合、最も簡単な方法は、方程式（のようになります）によって線（障害物の境界を含む）を表すことですa*x + b*y +c = 0。次に、2本の線が交差するかどうかを決定するのは非常に簡単なことです。
2本の線ax+by + c=0とdx+ey + f = 0は、それらが平行でない場合、つまりa * eb * d！= 0の場合にのみ、交差します。
次に、これら2つの線の交点が、実際に検討しているセグメントの内側にあるかどうかを確認する必要があります。交点には座標があります：
円がある場合は扱いにくくなりますが（これが通常、ポリゴンのみを障害物と見なす理由です）、基本的には同じ考えです：-線ax + by + c = 0と円（xa）^ 2 + （yb）^ 2 = r ^ 2（中心（a、b）と半径rの円）。次に、それらが交差するかどうか、交差点、およびそれが検討するセグメントに属するかどうかを判断する必要があります。計算はあなたにお任せします。
障害物のある2点間のパスを見つけるためのさまざまな方法に興味がある場合は、使用できる他のアルゴリズムがありますが、これらは最短パスを提供せず、パスのみを提供します。
作成している可視性図と比較したこれらのアルゴリズムの関心は、これら2つがどの次元でも機能することです。アルゴリズムを次元にアップグレードする場合、アルゴリズムの複雑さが増します（見つけるのに時間がかかります）。パス）次に、これら2つであり、最短パスは生成されません。