1 前言
在一些特殊需求中，需要计算空间中两条线段的距离，这里定义的距离为两线段上所有点相互连接中，以距离最小值作为两线段距离的度量。由于线段距离计算涉及到二次规划，因此这里单独开篇进行记录。
2 理论
对于空间中的两条线段，这里设其参数方程如下
(1)
$$
\begin{cases}
线段1: \mathbf{p}=\mathbf{n}_1t+\mathbf{p}_1&,0 \leq t \leq \alpha_1
\\
线段2:\mathbf{p}=\mathbf{n}_2t+\mathbf{p}_2&,0 \leq t \leq \alpha_2
\end{cases}
$$
为了便于后续简化，这里约定\(\mathbf{n}_1、\mathbf{n}_2\)为单位向量。进一步，设线段1上\(t=t_1\)与线段2上\(t=t_2\)的点形成的距离为两线段距离，则这时的距离求解等价于求解如下数学模型的参数\(t_1、t_2\):
(2)
$$
\begin{aligned}
\mathbf{Min}:&||(\mathbf{n}_1t_1+\mathbf{p}_1)-(\mathbf{n}_2t_2+\mathbf{p}_2)||_2^2
\\
\mathbf{s}\cdot\mathbf{t}\cdot:&\begin{cases}
0 \leq t_1 \leq \alpha_1
\\
0 \leq t_2\leq \alpha_2
\end{cases}
\end{aligned}
$$
对(2)的最小化目标函数化简有
(3)
$$
\begin{aligned}
d^2&=||(\mathbf{n}_1t_1+\mathbf{p}_1)-(\mathbf{n}_2t_2+\mathbf{p}_2)||_2^2 \\&=||\mathbf{n}_1t_1-\mathbf{n}_2t_2||_2^2+2(\mathbf{p}_1-\mathbf{p}_2)\cdot(\mathbf{n}_1t_1-\mathbf{n}_2t_2)+||\mathbf{p}_1-\mathbf{p}_2||_2^2
\\
&=t_1^2+t_2^2-2\mathbf{n}_1\cdot\mathbf{n}_2t_1t_2+2(\mathbf{p}_1-\mathbf{p}_2)\cdot \mathbf{n}_1t_1-2(\mathbf{p}_1-\mathbf{p}_2)\cdot \mathbf{n}_2t_2+||\mathbf{p}_1-\mathbf{p}_2||_2^2
\\
&=t_1^2+t_2^2+2at_1t_2+2bt_1+2ct_2+||\mathbf{p}_1-\mathbf{p}_2||_2^2
\end{aligned}
$$
上面公式里的系数\(a、b、c\)如下
(4)
$$
\begin{cases}
a=-\mathbf{n}_1\cdot \mathbf{n}_2
\\
b=(\mathbf{p}_1-\mathbf{p}_2)\cdot \mathbf{n}_1
\\
c=(\mathbf{p}_2-\mathbf{p}_1)\cdot \mathbf{n}_2
\end{cases}
$$
将(3)(4)代入(2)，最终等价求解如下问题
(5)
$$
\begin{aligned}
\mathbf{Min}:&t_1^2+t_2^2+2at_1t_2+2bt_1+2ct_2
\\
\mathbf{s}\cdot\mathbf{t}\cdot:&\begin{cases}
0 \leq t_1 \leq \alpha_1
\\
0 \leq t_2\leq \alpha_2
\end{cases}
\end{aligned}
$$
上面是一个二次规划问题，通过求解(5)得到\(t_1、t_2\)，最终两个线段的距离\(d\)可以按如下公式计算
(6)
$$
d=||(\mathbf{n}_1t_1+\mathbf{p}_1)-(\mathbf{n}_2t_2+\mathbf{p}_2)||
$$
3 二次规划求解
这里考虑(5)的二次规划模型，将模型标准化有
(7)
$$
\begin{aligned}
\mathbf{Min}:&\begin{bmatrix}t_1 & t_2\end{bmatrix}A\begin{bmatrix}t_1 \\ t_2\end{bmatrix}+\begin{bmatrix}2b & 2c\end{bmatrix}\begin{bmatrix}t_1 \\ t_2\end{bmatrix}
\\
\mathbf{s}\cdot\mathbf{t}\cdot:&\begin{cases}
0 \leq t_1 \leq \alpha_1
\\
0 \leq t_2 \leq \alpha_2
\end{cases}
\end{aligned}
$$
上面公式里的\(A\)为如下矩阵
(8)
$$
A=\begin{bmatrix}1 & a\\a&1\end{bmatrix}
$$
由于\(A\)的一阶顺序主子式为1，而二阶主子式为
(9)
$$
1-a^2=1-(\mathbf{n}_1\cdot\mathbf{n}_2)^2=1-\cos^2\theta=\sin^2\theta \geq 0
$$
上面公式的\(\theta\)为\(\mathbf{n}_1\)与\(\mathbf{n}_2\)的夹角。从(9)可以得出，当两个线段不平行时，\(A\)的顺序主子式都大于0，这时\(A\)是一个正定矩阵，(7)就是一个凸二次规划。当两线段平行时，这时可以退化成点到线段的距离。因此这里分两种情况进行求解。
3.1 两线段平行
当两线段平行时，任意选择一条线段，分别计算线段两端点到另一线段的距离，这里计距离为\(d_1、d_2\)，这时两线段的距离一定与\(d_1、d_2\)中的较小者值一致。因此算法退化成点到线段的计算。
设空间点\(\mathbf{p}_3\)以及如下线段
(10)
$$
\mathbf{p}=\mathbf{n}t+\mathbf{p}_0,0 \leq t \leq \alpha
$$
设\(\mathbf{p}_3\)在上面线段的垂点为\(\mathbf{p}_4\)，则有
(11)
$$
\begin{aligned}
\mathbf{p}_4&=\mathbf{n}t_4+\mathbf{p}_0
\\
0 &= \mathbf{n}\cdot(\mathbf{p}_4-\mathbf{p}_3) \Rightarrow t_4=\dfrac{\mathbf{n}\cdot(\mathbf{p}_3-\mathbf{p}_0)}{\mathbf{n}\cdot \mathbf{n}}
\end{aligned}
$$
这时点到线段距离按下式确定
(12)
$$
d=||\mathbf{n}t_5+\mathbf{p}_0-\mathbf{p}_3||
$$
公式里的\(t_5\)按下式确定
(13)
$$
t_5=\begin{cases}
0&,t_4<0
\\
t_4&,0 \leq t_4 \leq \alpha
\\
\alpha&,t_4>\alpha
\end{cases}
$$
3.2 两线段不平行
当两线段不平行时，就变成了一个凸二次规划问题，这时的解要么在目标函数无约束情况下的极小值处，要么就在约束的边界上。因此这里分别进行求解。
对于(5)的目标函数，由于是凸函数，为了计算其极小值，这里进行如下变化
(14)
$$
\begin{aligned}
t_1^2+t_2^2+2at_1t_2+2bt_1+2ct_2 &=(t_1+(at_2+b))^2+(1-a^2)t_2+2(c-ab)t_2-b^2
\\
&=(t_1+(at_2+b))^2+(1-a^2)(t_2+\dfrac{c-ab}{1-a^2})^2-b^2-\dfrac{(c-ab)^2}{1-a^2}
\end{aligned}
$$
上面表达式取极值得到
(15)
$$
\begin{cases}
t_1=\dfrac{ac-b}{1-a^2}
\\
\\
t_2=\dfrac{ab-c}{1-a^2}
\end{cases}
$$
如果(15)的解满足(5)的约束条件，则这时(15)的解为最佳解。
如果(15)的解不满足(5)的约束条件，则这时的解一定在约束边界上。由于\(t_1、t_2\)的约束形式一样，不失一般性，假设\(t_2\)处于边界上，则通过(14)可以得到
(16)
$$
t_1=-(at_2+b)=\begin{cases}
-b&,t_2=0
\\
-b-a\alpha_2&,t_2=\alpha_2
\end{cases}
$$
同理，假设\(t_1\)处于边界上，这时可以得到
(17)
$$
t_2=-(at_1+c)=\begin{cases}
-c&,t_1=0
\\
-c-a\alpha_1&,t_1=\alpha_1
\end{cases}
$$
结合(16)(17)可以得到如下四组候选解
(18)
$$
①
\begin{cases}
t_1=0
\\
t_2=-c
\end{cases},②
\begin{cases}
t_1=\alpha_1
\\
t_2=-c-a\alpha_1
\end{cases},③
\begin{cases}
t_1=-b
\\
t_2=0
\end{cases},④
\begin{cases}
t_1=-b-a\alpha_2
\\
t_2=\alpha_2
\end{cases}
$$
最终在(18)式里，排除不满足(5)约束的解，在剩下解中选择使得(5)目标最小的解作为最佳解。
3.3 总结
最终，对于(5)的解，将在(12)、(15)、(18)里产生。
4 空间直线距离
对于空间直线距离，这是线段距离的特例，即将(5)里的约束去掉，就变成了直线距离求解。根据(9)的结论，直线距离求解依然分为直线平行时与不平行时求解。
4.1 两直线平行
当两直线平行时，在任意一条直线上选择一个点，计算这个点到另一条直线的距离，这个距离也是两直线的距离。
4.2 两直线不平行
根据(9)的结论，这时求解一个无约束的凸二次规划问题，因此公式(15)的解为最终计算两直线距离参数的解，得到解后代入公式(6)则得最佳距离。