4

我需要编写一个可靠的方法来检索以下场景的答案......

给定一条线段 AB 和一个任意点 C，我将如何在与 AB 平行且穿过点 C 的线上找到离 A 最近的点？（上面提到的可靠是指算法能够找到 D，同时允许 A、B 和 C 的坐标是完全任意且不可预测的。我遇到了很多我无法适应的解决方案可能的情况，可悲的是......）

在下图中显示的数据的情况下，我如何可靠地找到 D 的 x,y 坐标？

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

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

我尝试了许多不同的公式都无济于事，并且已经为此工作了数周。我难住了！

图表

4

1 回答 1

3

这是一个最小化问题。

一般来说，N维空间中两点（A和B）之间的欧几里得距离由Dist(A,B) = sqrt((A1-B1)^2 + ... + (AN-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 的最小值。

现在以 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 的表达式，您可以将其计算为一个三步过程：

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-By)/(Ax-Bx) 将导致除以 0，这将使您的代码不起作用. 您可以按如下方式投入安全阀：

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

对于严肃的数值工作，由于舍入误差和所有有趣的东西（即 abs(Ax-Bx) < epsilon，而不是 Ax==Bx），您可能希望根据公差而不是直接比较来实现它

于 2013-04-06T14:34:40.393 回答