查找距離最短的兩個平行線之間，任意點

Question

我需要寫一個可靠方法來檢索回答以下情形......

給定一個線段AB和任意點C，如何我是否會在平行於AB的線上找到通過點C的最接近點A？ （上面提到的可靠性是指算法能夠找到D，同時允許A，B和C的座標完全是任意的和不可預知的。我遇到了很多難以適應所有問題的解決方案可能的情況，可悲的是...）

在下面的圖片中顯示的數據的情況下，我將如何可靠地找到D的x，y座標？

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

知道AB和CD是平行的，這顯然意味着斜率是相同的。

我已經嘗試了許多不同的公式，無濟於事，並且已經爲此工作了數週。我很難過！

Answer 1

這是一個最小化問題。 （A，B）= sqrt（（A1-B1）^ 2 + ... +（AN-B）） BN）^ 2）

如果您需要找到空間曲線A（t）（嵌入一些N維空間中的一維物體）和點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.

的最小值3210

---

我們找到用於穿過沿y C中的平行線的方程= mx + b中的形式：

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）>

然後，您可以插入m和b的表達式，如果您希望以A，B，C或A想要數值解法，您可以將其計算爲三步過程：

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)> 

這對所有平行直線的情況都是有效的。一個需要注意其實現爲數值（而不是分析）代碼時：如果線被垂直定向，計算M =（AY-通過）/（AX-BX）將導致被0除，這將使您的代碼不工作。你可以在一個安全閥拋出如下：

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

對於嚴重的數值計算，你可能想要實現在由於舍入誤差和所有有趣的東西公差，而不是直接比較而言（即ABS （AX-BX）<ε，而不是斧== Bx的）