Calculate segment of 3D line within distance from a separate line segment

Question

Given an arbitrary 3D line (infinite length) and an arbitrary 3D line segment, how do I calculate which segment of the line (if any) is within a given distance from the segment?

Answer 1

Let your infinite line be given by

$ P_1(t) = P_0 + t u $

where $u$ is a unit vector

and let you line segment be given by

$ Q_1(s) = Q_0 + s v , s_1 \le s \le s_2 $

where $v$ is a unit vector.

The squared distance between $P_1$ and $Q_1$ is

$ (Q_0 + s v - P_0 - t u )^T (Q_0 + s v - P_0 - t u) \le d^2$

where $d$ is the given distance.

If $u \cdot v = \cos \theta $ then the above equation becomes

$ t^2 + s^2 - 2 t s \cos \theta + 2 s v^T (Q_0 - P_0) - 2 t u^T (Q_0 - P_0) \le d^2 - (Q_0 - P_0)^T (Q_0 - P_0) $

Let $ -u^T (Q_0 - P_0) = a $ and $ v^T (Q_0 - P_0) = b $ and $(Q_0 - P_0)^T (Q_0 - P_0) = c^2 $. Also let $ w = [ t, s]^T $

then

$ w^T A w + B^T w \le d^2 - c^2 $

where $A = \begin{bmatrix} 1 && - \cos \theta \\ - \cos \theta && 1 \end{bmatrix} $

and

$ B = \begin{bmatrix} 2a \\ 2 b \end{bmatrix} $

Let $w_0 = - \dfrac{1}{2} A^{-1} B $ , then

$ (w - w_0)^T A (w - w_0) \le d^2 - c^2 + w_0^T A w_0 $

This is an equation of an ellipse in the $(t, s)$ plane, provided that $d^2 - c^2 + w_0^T A w_0 \gt 0 $ (otherwise, there is no solution for it, because $A$ is positive definite). Since the range for $s$ is given as $[s_1, s_2]$, we can find the possible range(s) of the parameter $t$ so that the point $(t, s)$ lies inside this ellipse.