4

次のシナリオへの回答を取得するための信頼できるメソッドを作成する必要があります...

線分 AB と任意の点 C が与えられたとき、点 C を通り AB に平行な線上で A に最も近い点を見つけるにはどうすればよいでしょうか? (上記の信頼性とは、A、B、および C の座標を完全に恣意的で予測不可能にすることを許可しながら、D を見つけるアルゴリズムの能力を指します。考えられるシナリオ、悲しいことに...)

下の図に表示されているデータの場合、D の x、y 座標を確実に見つけるにはどうすればよいでしょうか?

A = <425, 473>
B = <584, 533>
C = <371, 401>
D = <???, ???>

AB と CD が平行であるということは、傾きが同じであることを意味します。

私は多くの異なる式を無駄に試しましたが、これに数週間取り組んでいます. 私は困惑しています！

ダイアグラム

4

1 に答える 1

3

最小化問題です。

一般に、N 次元空間の 2 点 (A と B) 間のユークリッド距離は、 Dist(A,B) = sqrt((A1-B1)^2 + ... + (AN-BN)^2) で与えられます。

空間曲線 A(t) (ある N 次元空間に埋め込まれた 1 次元オブジェクト) と点 B の間の最小距離を見つける必要がある場合は、次の方程式を解く必要があります。

d Dist(A(t),B) / dt = 0    // (this is straightforward calculus: we're at either a minimum or maximum when the rate of change is 0)

そして、その根のセット (t1、t2 など) を距離関数に対してテストして、D の値が最も小さいものを見つけます。

ここで、y=mx+b 形式で C を通る平行線の方程式を見つけます。

m = (Ay - By)/(Ax-Bx)
b = Cy - mCx

これを空間曲線形式で書き、パート 1 の式に当てはめます。

Dist(D(t),A) = sqrt((t-Ax)^2 + (m*t+b-Ay)^2)

私たちの導関数を取る：

d Dist(D(t),A)/ dt = d sqrt((t-Ax)^2 + (m*t+b-Ay)^2) / dt 

= (t + (m^2)*t - Ax + m*b - m*Ay)/sqrt(t^2 + (m^2)t^2 - 2*t*Ax + 2*m*t*b - 2*m*t*Ay + (Ax)^2 + (Ay)^2 + b^2 - 2*b*Ay )
= ((1+m^2)*t - Ax + m*b - m*Ay)/sqrt((1+m^2)*(t^2)  + 2*t*(m*b - Ax - m*Ay) + (Ax)^2 + (Ay)^2 + b^2 - 2*b*Ay )

これを 0 に設定し、t について解くと、t = (Ax-m*b+m*Ay)/(1+m^2) が唯一の根として得られます (これを自分で代入して検証することで確認できます)。すべてが必要に応じてキャンセルされます）。

この t の値を空間曲線に戻すと、次のようになります。 D=<(Ax-m*b+m*Ay)/(1+m^2),b+m*(Ax-m*b+m *Ay)/(1+m^2)>

A、B、C の項で明示的な解が必要な場合は、m と b の式をプラグインできます。数値解のみが必要な場合は、3 つのステップのプロセスとして計算できます。

m = (Ay - By)/(Ax-Bx)
b = Cy - mCx
D=<(Ax-m*b+m*Ay)/(1+m^2),b+m*(Ax-m*b+m*Ay)/(1+m^2)>

これは、平行な直線があるすべての場合に有効です。(分析ではなく) 数値コードとして実装する場合の 1 つの注意点: 行が垂直方向にある場合、m = (Ay-By)/(Ax-Bx) を計算すると 0 で除算され、コードが機能しなくなります。 . 次のように安全弁を投入できます。

if( Ax == Bx) {
    D = <Cx,Ay>
} else {
    // normal calculation here
}

本格的な数値計算の場合、丸め誤差や楽しいこと (つまり、Ax==Bx ではなく abs(Ax-Bx) < イプシロン) が原因で、直接比較ではなく許容誤差の観点から実装することをお勧めします。

于 2013-04-06T14:34:40.393 に答える