Carlos Ureña / Varios

Line-to-line distance computation

$$ In this page I show how to easily compute the minimal distance between two arbitrary lines.

Assume we have two lines, each represented by a point and a normalized direction vector (first line is $({\mathbf{o}}_1,{\mathbf{v}}_1$) and second (${\mathbf{o}}_2,{\mathbf{v}}_2)$). For simplicity, we will use these definitions: $$\begin{array}{rclcrclcrcl}{a}_1& =& \mathbf{s}\cdot {\mathbf{v}}_1& & b& =& {\mathbf{v}}_1\cdot {\mathbf{v}}_2& & \mathbf{s}& =& {\mathbf{o}}_1-{\mathbf{o}}_2\\ a_2& =& \mathbf{s}\cdot {\mathbf{v}}_2& & c& =& \mathbf{s}\cdot \mathbf{s}& & & & \end{array}$$

A pair of points (one on each line) can be obtained by using two real values $t_1$ and $t_2$, by substituion on the parametric equations of the lines. These points are, obviously: $${\mathbf{p}}_1(t_1)={\mathbf{o}}_1+t_1{\mathbf{v}}_1{\mathbf{p}}_2(t_2)={\mathbf{o}}_2+t_2{\mathbf{v}}_2$$ The squared distance function $d_{sq}(t_1,t_2)$ is defined as: $$d_{sq}(t_1,t_2)=({\mathbf{p}}_1(t_1)-{\mathbf{p}}_2(t_2))\cdot ({\mathbf{p}}_1(t_1)-{\mathbf{p}}_2(t_2))$$

Non parallel lines

When the two lines are not parallel, then $b$ is not $1$. Note that ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$ are normalized, thus in the case of non-parallel lines, these two vectors are not collinear and their inner prodcut ($b$) cannot be $1$ (it is a value between $-1$ and $1$).

It can be easily shown (by equating its derivate to cero) that, in this case, function $d_{sq}$ has its (unique) minimun value for $t_1=s_1$ and $t_2=s_2$, where: $$\begin{array}{}\text{(1)}& s_1=\frac{a_{2}b-a_1}{1-b^2}{s}_2=\frac{a_2-b{a}_1}{1-b^2}\end{array}$$

The squared minimun distance ($m_{sq}$) between these two lines can be obtained by computing the pair of closest points (${\mathbf{p}}_1(s_1)$ and ${\mathbf{p}}_2(s_2)$) and then the computing the squared distance between then, that is: $$m_{sq}=d_{sq}(s_1,s_2)$$ by expanding $d$, this distance can also be written directly in terms of $s_1$ and $s_2$, as follows: $$m_{sq}=s_1^2+s_2^2+2(a_1{s}_1-a_2{s}_2-b{s}_1{s}_2)$$ by substituting $s_1$ and $s_2$ above and then simplifying, we arrive to this expression: $$m_{sq}=\frac{a_1^2+a_2^2-2b{a}_1{a}_2}{b^2-1}+c$$

Parallel lines

In the case $b=1$ then the two lines are parallel (${\mathbf{v}}_1={\mathbf{v}}_2$). The squared distance can be computed simply as the squared length of the $\mathbf{s}$ component perpendicular to the lines. To obtain this value, we observe the component of $\mathbf{s}$ parallel to the lines (${\mathbf{s}}_{||}$), and the component perpendicular to those lines (${\mathbf{s}}_{\perp }$). These vectors can be expressed as: $${\mathbf{s}}_{||}=(\mathbf{s}\cdot {\mathbf{v}}_1){\mathbf{v}}_1{\mathbf{s}}_{\perp }=\mathbf{s}-{\mathbf{s}}_{||}$$ If we consider the triangle formed by $\mathbf{s}$, ${\mathbf{s}}_{||}$ and ${\mathbf{s}}_{\perp }$, and by using Pythagoras theorem, we get this equality for the squared lengths: $$\mathbf{s}\cdot \mathbf{s}=({\mathbf{s}}_{||}\cdot {\mathbf{s}}_{||})+({\mathbf{s}}_{\perp }\cdot {\mathbf{s}}_{\perp })$$ in this expression, we can do these substitutions: $$\begin{array}{rcl}{\mathbf{s}}_{\perp }\cdot {\mathbf{s}}_{\perp }& =& m_{sq}\\ {\mathbf{s}}_{||}\cdot {\mathbf{s}}_{||}& =& (\mathbf{s}\cdot {\mathbf{v}}_1{)}^2({\mathbf{v}}_1\cdot {\mathbf{v}}_1)=(\mathbf{s}\cdot {\mathbf{v}}_1{)}^2=a_1^2\\ \mathbf{s}\cdot \mathbf{s}& =& c\end{array}$$ Thus we can finally get an expression for $m_{sq}$: $$m_{sq}=c-a_1^2$$

See also:

• Derivation of the solution by F.J. Vesely (includes segment-segment distance).
• Dan Sunday (GeomAlgorithms web site) (describes the partial derivatives solution)
• Paul Bourke (describes both partial derivtives and perpendicularity-based solution, which lead to the same equation here)
• A paper describe how to use PLucker coordinates to get distance bounds: here

(this page uses MathJax)