math - 2d线段上的最近点，穿过第三2d线段

Question

使用图更容易。 CaRMetal，发动攻击!

我有两个2D线段，P和Q。我想在Px上找到点P，在Qx上找到Q，以便将dist(Px,Qx)最小化。到现在为止还挺好;这是一个非常简单的任务。

现在是皱纹。我想约束Px和Qx，以便包含它们的PxQx行必须与第三行段C相交。 (随意假设所有原始线段都不相交，顺便说一句。)

显然存在一种情况，即不受约束的Px和Qx已经满足C交集条件。

还有一种不可行的情况，其中C甚至不包含P和Q的凸包。这些都是微不足道的情况要检查。

在其他情况下，PxQx行必须包含Ca或Cb。这似乎不能完全简化为线性方程组。

在最后一组情况下，PxQx不仅包含C的端点，而且还包含P或Q的端点。这些似乎很容易检查。

我担心的是(3)中的情况，因为我不知道如何在不调用令人讨厌的高阶多项式的情况下获得良好的封闭形式。当然，我可以在整个过程中使用迭代约束优化器，但是我想最大化性能，在接近简并的情况下实现高精度可能很重要。

Answer 1

我想在这里写下一个简短的小公式，然后说“瞧”，但这不会发生，这就是原因。这个问题是对找到两个线段之间最短距离的扩展，Dan Sunday在Distance between Segments and Rays中对此进行了很好的描述。在此图中使用标签和符号

我们可以通过P和Q参数化P(t) = P_0 + t(P_1 - P_0)和Q(s) = Q_0 + s(Q_1 - Q_0)，其中点的减法是按坐标方式进行的，即Q_1 - Q_0 = (m1-m0,n1-n0)。通过这种参数化，找到线段P和Q之间最短距离的问题就是将距离^ 2最小化，

f(s,t) =  (a0 + (a1 - a0)*t - m0 - (m1 - m0)*s)^2 + (b0 + (b1-b0)*t - n0 - (n1-n0)*s)^2 

在 s,t空间中由 0<=s<=1和 0<=t<=1界定的区域上。 (此变换避免在保留最小值的位置的同时处理平方根)。请注意，除非线段相交，否则最小值将出现在边界上。

但是，我们还有另一个约束-我们只考虑 (s,t)对，其中 P(t)和 Q(s)的连接线穿过 C。将一点 Cp = (c,d)固定在 C上。然后，如果与一对 (s,t)关联的行经过 Cp，则矢量 P(t)->Cp 和 Q(S)->Cp
必须是平行的。由于这是一个2D问题，我们将 z的方向设置为 0并使用叉积(对于并行矢量必须为零)来获取任何此类 (s,t)必须满足以下关系

g(s,t) = (a0 + (a1 - a0)*t - c)*(n0 + (n1 - n0)*s -d) - (b0 +(b1 - b0)*t - d)*(m0 + (m1 - m0)*s -d) = 0

因此， g(s,t) = 0的解决方案都是 (s,t)对，其中连接其关联点的线穿过 Cp。如果我们通过 C参数化 C(r) = C_0 + r(C_1 - C_0)，那么我们可以认为与每个 r相关联的是 g(s,t) = 0的解决方案集，我们在其中放了 Cp = C(r)。在 g(s,t)上绘制 [0,1]X[0,1]，我们可以看到这些曲线的样子。

对于我们图中的特殊情况，轮廓随着 r的增加而增加，而 C(0)和 C(1)的轮廓则形成了可行区域的边界。图中的基础颜色是 f(s,t)的值。更一般而言，具有我们额外约束的可行区域(即可能解决该问题的 (s,t)值)是 [0,1]X[0,1]框中的点，它们也在 C(0)和 C(1)的轮廓之间。当然，轮廓都不会与 [0,1]X[0,1]框相交，这时整个框都是可行的，或者没有解决方案。和以前一样，除非 P和 Q在可行区域内相交，否则最小值将出现在边界上。

因此，这是受约束的优化问题。可行区域的边界属于以下三种类型之一:

交叉点

盒子的边缘[0,1]X[0,1]

g(s,t) = 0或C(0)的轮廓C(1)

前两个相当简单。但是第三个是它变得有趣的地方。好消息是，我们正在努力使受二次约束约束的二次函数最小化。坏消息是，这意味着我们将需要解决立方问题。将 f(s,t)最小化为 g(s,t) = 0的最小值的封闭形式是方程组的解决方案(请参阅任何微积分教科书或 Wikipedia, Lagrange Multiplier)

(partial g)/(partial s) (partial f)/partial t) = (partial g)/(partial t) (partial f)/partial s)

g(s,t) = 0

也称为

-2*((b0 - b1)*((n0 - n1)*s - (b0 - b1)*t + b0 - n0) + (a0 - a1)*((m0 - m1)*s - (a0 - a1)*t + a0 - m0))*((n0 - n1)*((a0 - a1)*t - a0 + c) - (m0 - m1)*((b0 - b1)*t - b0 + d)) + 2*((b0 - b1)*((m0 - m1)*s + d - m0) - (a0 - a1)*((n0 - n1)*s + d - n0))*((n0 - n1)*((n0 - n1)*s - (b0 - b1)*t + b0 - n0) + (m0 - m1)*((m0 - m1)*s - (a0 - a1)*t + a0 - m0)) = 0

(a0 + (a1 - a0)*t - c)*(n0 + (n1 - n0)*s -d) - (b0 +(b1 - b0)*t - d)*(m0 + (m1 - m0)*s -d) = 0

三次方程式有一个封闭形式，因此存在一个受适当边界假设约束的解决方案。 (特别是，您需要 s中的 t和 g的系数不为零。)结果很冗长。

或者，我们将抛物线最小化，因此，它在漂亮的规则二次轮廓 g(s,t) = 0上是二次方的。这非常适合二进制搜索，它具有快速收敛且不需要任何平方根的额外好处。