通过第三个二维线段，找到两条二维线段上最接近的点

Question

这个问题如果有一张图会更容易理解。可以使用CaRMetal进行辅助。

我有两条二维线段P和Q。 我想找到点Px在P上，点Qx在Q上，使得dist(Px,Qx)最小。 到目前为止，这是一个相当简单的任务。

现在有一个要求。我希望限制Px和Qx，使包含它们的直线PxQx与第三条线段C相交。 （顺便说一句，可以假设原始直线段都没有相交。)

1. 显然，未受限制的Px和Qx已经满足C相交条件的情况是存在的。
2. 也有一种不可行的情况，即C甚至不包含P和Q的凸壳。 这些情况很容易检查出来。
3. 在其他情况下，直线PxQx必须包含Ca或Cb。 这似乎不能干净地简化为线性方程组。
4. 在最后一组情况中，PxQx不仅包含C的端点，还包含P或Q的端点。这些情况似乎很容易检查。

我关心的是第3种情况，因为我不知道如何在不使用高次多项式的情况下获得它的一个好的闭合形式。 当然，可以将整个问题交给迭代的、受限制的优化器，但我想尽可能提高性能，并且在接近退化情况下的高精度可能很重要。

- Sneftel

---

如果是2D的话：直线不应该总是通过Ca，即两条线段（在上图中向左）的交点最近的点吗？因此，从所有通过Ca的线中找到与段内的2条线相交的交点，并将长度PxQx最小化。 - John Alexiou

不，C语言可能不会限制解决方案（情况1）。当“PxQx”被限制通过一个点时，特别是长度最小化变得棘手。 - Sneftel

只是为了确认一下 - 这是二维问题吗？还是你故意不提维度？ - HEKTO

抱歉，我把它放在标题中了，但也应该放在正文中。是的，2D。 - Sneftel

Answer 1

我希望能在这里写下一个简短的公式，然后说“嘿”，但事实并非如此。这个问题是寻找两条线段之间最短距离的延伸，这在Dan Sunday的线段和射线之间的距离中有很好的描述。使用此图中的标签和符号 我们可以通过P(t) = P_0 + t(P_1 - P_0)和Q(s) = Q_0 + s(Q_1 - Q_0)对P和Q进行参数化，其中点的减法是按坐标进行的，即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 

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

然而，我们还有一个约束条件——我们只考虑连接P(t)和Q(s)的线经过C的(s,t)对。在C上固定一个点Cp=(c,d)。然后，如果与一对(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

因此，方程的解是所有与它们相关联的点相连的线穿过的一对。如果我们通过对进行参数化，那么我们可以考虑与每个相关联的解集，其中我们让且解集为。在上绘制，我们可以看到这些曲线的样子。 对于我们图中的特殊情况，随着的增加，等高线也会增加，其中和的等高线形成可行区域的边界。绘图中的底色是的值。更一般地说，具有额外约束条件的可行区域（即可能是问题的解的值）是位于框之间的和等高线之间的点。当然，可能没有等高线与框相交，此时要么整个框都是可行的，要么就没有解。与以前一样，除非和在可行区域内相交，否则最小值将出现在边界上。

因此，这是一个受约束的优化问题。可行区域的边界分为三种类型：

1. 交点
2. 框的边缘
3. 对于或的等高线

前两种情况很容易检查。第三种情况则更有趣。好消息是，我们试图最小化一个二次函数，而受到二次约束。坏消息是，这意味着我们需要解决一个三次方程。最小化，同时满足的最小值的闭合形式是解方程组（参考任何微积分教材或维基百科，拉格朗日乘数法）的解。

• (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

对于三次方程式有一个闭合形式，因此在适当的边界条件下存在解。 （特别是您需要使g中的s和t系数不为零。）结果很冗长。

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

- Chris H.

Answer 2

针对您的第三个问题，似乎可以使用一些向量代数和微分来分析地找到长度最小的线段。暂时不考虑你原始线段的边界点，我们可以将它们表示为向量，并根据参数进行计算：

P(x) = P0 + p * x
Q(y) = Q0 + q * y

其中P0和Q0是位于线段P和Q上的任意点，p和q是单位向量，x和y是浮点参数。同时，我们将线段C的边界点表示为C0。

任何起点在线段P上，终点在点C0处的向量都可以表示为：

R(x) = C0 - (P0 + p * x)

此外，以线段P为起点，线段Q为终点的任意向量均可表示为：

S(x, y) = (Q0 + q * y) - (P0 + p * x)

我们希望向量 S(x, y)经过点 C0，只需要求向量 R(x)和 S(x, y)共线。使用此条件，我们可以将 y 变量表示为 x 的函数（以及所有其他参数- P0 ，p ，Q0 ，q ，C0 ），因此我们将仅得到向量 S 作为 x 的函数：

S(x) = S(x, y(x))

现在，我们可以将S的规范表示为关于x的函数。我们可以找到这个函数的一阶导数，将其设为零并找到x值，从而使得该函数达到最小值。

我在特定情况下进行了这些计算，当线P位于X轴上时，得到了一个相当复杂的向量长度表达式。然后我使用了一个在线符号微分工具来找到它的一阶导数，得到了一个三次方程。虽然这个方程可以通过解析方法求解，但是这是一个漫长而复杂的过程，因此数值解可能是另一个选择。

- HEKTO

Answer 3

Px = P(t1) = Pa · (1 - t1) + Pb · t1
Qx = Q(t2) = Qa · (1 - t2) + Qb · t2

将"How do you detect where two line segments intersect?"中的方程式用于计算：

t(t1, t2) = (Ca - Px) ⨯ (Cb - Ca) / (Qx - Px) ⨯ (Cb - Ca)
u(t1, t2) = (Ca - Px) ⨯ (Qx - Px) / (Qx - Px) ⨯ (Cb - Ca)

(⨯ = 叉积)

这两个值必须在0和1之间，才能使线段相交。 t是沿着线Px Qx的位置，u是沿着C线的位置。如果您展开公式，它们将是两个线性或二次函数的商。

由于您只需要将t和u与零和一进行比较，因此它们可以稍微简化：

t(t1, t2) = 0
当且仅当 (Ca - Px) ⨯ (Cb - Ca) / (Qx - Px) ⨯ (Cb - Ca) = 0 且 (Ca - Px) ⨯ (Cb - Ca) = 0，其中Qx ≠ Px

和

t(t1, t2) = 1
当且仅当 (Ca - Px) ⨯ (Cb - Ca) / (Qx - Px) ⨯ (Cb - Ca) = 1 且 (Ca - Px) ⨯ (Cb - Ca) - (Qx - Px) ⨯ (Cb - Ca) = 0 且 (Ca - Qx) ⨯ (Cb - Ca) = 0，其中Qx ≠ Px

和

u(t1, t2) = 0
当且仅当 (Ca - Px) ⨯ (Qx - Px) / (Qx - Px) ⨯ (Cb - Ca) = 0 且 (Ca - Px) ⨯ (Qx - Px) = 0，其中Qx ≠ Px

u(t1, t2) = 1
(Ca - Px) ⨯ (Qx - Px) / (Qx - Px) ⨯ (Cb - Ca) = 1
(Ca - Px) ⨯ (Qx - Px) - (Qx - Px) ⨯ (Cb - Ca) = 0
(Ca - Px) ⨯ (Qx - Px) + (Cb - Ca) ⨯ (Qx - Px) = 0
(Cb - Px) ⨯ (Qx - Px) = 0, Qx ≠ Px

这里有四个约束条件（或者说八个，具体看你如何计算）：

• 0 ≤ t1 ≤ 1
• 0 ≤ t2 ≤ 1
• 0 ≤ t(t1, t2) ≤ 1
• 0 ≤ u(t1, t2) ≤ 1

你有四个受约束的变量，每个变量都有两个边界。这样一来，在(t1, t2)空间中就会形成八种情况，每种情况代表着一个曲线或线段。

这些约束条件将形成一个在(t1, t2)空间中允许的值域。你需要沿着该区域的边缘寻找最小化Px和Qx之间距离的点。只要线段P和Q不相交，最小值总是位于外部边界上。但是在某些情况下，可能没有有效的解决方案。

---

为了找到最小值(t1, t2)，你需要评估所有候选点：

• 内部最小值; 线P和Q相交的点。(1个点)
• 边界最小值; 沿任何边界曲线的最小值。(8个点)
• 交点最小值; 任意两个边界曲线相交的点。(24个点)

对于每个点，您需要检查它是否符合所有其他约束条件，并选择生成 Px 和 Qx 最小距离的点。

要找到内部最小点，请解决 Px = Py 的方程，得出 t1，t2。如果此点落在其他边界内，则直线相交并通过 C 线。(非常不可能)

要找到边界最小点，您需要查看曲线沿斜率。这可以通过解决以下问题找到：

{ ∇f(t1, t2) ⨯ ∇G(t1, t2) = 0, G(t1, t2) = k }

其中 ∇ 是Nabla运算符（函数的一阶导数向量），G(t1, t2) = k 是边界条件，例如 t(t1, t2) = 1。

要找到交点最小值，您需要使两条曲线相等，并解决 t1，t2 的方程。

一种组织方法是计算每个约束曲线的多项式系数，并编写一个检查交点的函数。

(A₁ + A₂·t1 + A₃·t1² + A₄·t2 + A₅·t1·t2 + A₆·t2²) / (A₇ + A₈·t1 + A₉·t2)

- Markus Jarderot

---

是的，我知道如何将其制定为QP问题。尽管如此，我想最大化性能，并且我还希望解决方案在接近退化情况时具有鲁棒性。使用黑盒求解器库实现这两个目标都很困难。 - Sneftel