18
$\begingroup$

Find shortest distance between lines given by

$$\frac{x-2}{3}=\frac{y-6}{4}=\frac{z+9}{-4}$$ and $$\frac{x+1}{2}=\frac{y+2}{-6}=\frac{z-3}{1}$$ Is there any shortcut method for this problems?

$\endgroup$
3
  • 3
    $\begingroup$ Have you tried anything? Please show your efforts $\endgroup$
    – Lelouch
    Apr 1, 2017 at 15:11
  • 1
    $\begingroup$ No I didn't try.I don't know how to solve it. $\endgroup$
    – Amey Patil
    Apr 1, 2017 at 15:15
  • $\begingroup$ Well, see they can either be skew or intersecting. first try to solve them. $\endgroup$
    – jonsno
    Apr 1, 2017 at 15:17

7 Answers 7

54
$\begingroup$

So you have two lines defined by the points $\mathbf{r}_1=(2,6,-9)$ and $\mathbf{r}_2=(-1,-2,3)$ and the (non unit) direction vectors $\mathbf{e}_1=(3,4,-4)$ and $\mathbf{e}_2 =(2,-6,1)$.

The coordinates of all the points along the lines are given by

$$\begin{align} \mathbf{p}_1 & = \mathbf{r}_1 + t_1 \mathbf{e}_1 \\ \mathbf{p}_2 & = \mathbf{r}_2 + t_2 \mathbf{e}_2 \\ \end{align} \tag{1}$$

where $t_1$ and $t_2$ are two scalar values. To find the closest points along the lines you recognize that the line connecting the closest points has direction vector $$\mathbf{n} = \mathbf{e}_1 \times \mathbf{e}_2 = (-20,-11,-26) \tag{2}$$

If the two direction vectors $\mathbf{e}_1$ and $\mathbf{e}_2$ are parallel (not in this specific case), this method cannot be applied because the cross-product is zero:

$$\mathbf{e}_1 \times \mathbf{e}_2 = 0$$

If the points along the two lines are projected onto the cross line the distance is found in one fell swoop

$$ d = \frac{ \mathbf{n}\cdot \mathbf{p}_1}{\|\mathbf{n}\|} - \frac{ \mathbf{n}\cdot \mathbf{p}_2}{\|\mathbf{n}\|} = \frac{ \mathbf{n} \cdot ( \mathbf{p}_1-\mathbf{p}_2)}{\| \mathbf{n} \|} = \frac{ \mathbf{n} \cdot ( \mathbf{r}_1-\mathbf{r}_2+t_1 \mathbf{e}_1 -t_2 \mathbf{e}_2)}{\| \mathbf{n} \|} $$

But since $\mathbf{n}\cdot \mathbf{e}_1 = \mathbf{n}\cdot \mathbf{e}_2 = 0$, the above is

$$ \boxed{ d = \frac{| \mathbf{n} \cdot ( \mathbf{r}_1-\mathbf{r}_2) |}{\| \mathbf{n} \|} } \tag{3}$$

Here $|\,|$ is the absolute value. Don't use the absolute if you want a signed distance in the direction of $\boldsymbol{n}$.

In this case $$ d = \frac{ (-20,-11,-26) \cdot (3,8,-12) }{3 \sqrt{133}} = 4.74020116673185 $$

Finally, to find the location for $\boldsymbol{p}_1$ and $\boldsymbol{p}_2$ which are the points on each line closest to the other line use the following calculation for $t_1$ and $t_2$ and then substitute into (1)

$$\begin{aligned}t_{1} & =\frac{\left(\boldsymbol{e}_{2}\times\boldsymbol{n}\right)\cdot\left(\boldsymbol{r}_{2}-\boldsymbol{r}_{1}\right)}{\boldsymbol{n}\cdot\boldsymbol{n}} = -2.055973266499582\\ t_{2} & =\frac{\left(\boldsymbol{e}_{1}\times\boldsymbol{n}\right)\cdot\left(\boldsymbol{r}_{2}-\boldsymbol{r}_{1}\right)}{\boldsymbol{n}\cdot\boldsymbol{n}} = -0.2138680033416875 \end{aligned}$$

The closest points are

$$ \begin{aligned} \boldsymbol{p}_1 &= \pmatrix{ -4.167919799498746 \\ -2.223893065998329 \\ -0.7761069340016708 } \\ \boldsymbol{p}_2 &= \pmatrix{ -1.427736006683375 \\ -0.7167919799498746 \\ 2.786131996658312 } \end{aligned}$$

We can confirm that $d = \| \boldsymbol{p}_2 - \boldsymbol{p}_1 \| = 4.740201166731855\;\checkmark $

$\endgroup$
14
  • 1
    $\begingroup$ What to use if they are parallel? $\endgroup$
    – plasmacel
    Jul 2, 2021 at 16:39
  • 4
    $\begingroup$ @plasmacel - if the lines are parallel, then pick any point on one line and do a point-to-line calculation to the other line $$d = \sqrt{ \frac{ \left( (r_2-r_1)\times e_1 \right)^2 }{ \|e_2\|^2}}$$ $\endgroup$ Jul 11, 2021 at 13:41
  • 1
    $\begingroup$ @JoostDöbken - not from $d$. But you can get to it with some linear algebra $$\begin{pmatrix}t_{1}\\ t_{1} \end{pmatrix}=\frac{1}{1-\left(\boldsymbol{e}_{1}\cdot\boldsymbol{e}_{2}\right)^{2}}\begin{bmatrix}1 & \boldsymbol{e}_{1}\cdot\boldsymbol{e}_{2}\\ \boldsymbol{e}_{1}\cdot\boldsymbol{e}_{2} & 1 \end{bmatrix}\begin{pmatrix}\boldsymbol{e}_{1}\cdot\left(\boldsymbol{r}_{2}-\boldsymbol{r}_{1}\right)\\ -\boldsymbol{e}_{2}\cdot\left(\boldsymbol{r}_{2}-\boldsymbol{r}_{1}\right) \end{pmatrix}$$ but you have to normalize $\| \boldsymbol{e}_{1} \| =1$ and $\| \boldsymbol{e}_{2}\| =1$ before. $\endgroup$ Nov 3, 2022 at 14:55
  • 1
    $\begingroup$ @JoostDöbken - a more direct calculation of $t_1$ and $t_2$ is $$ \begin{aligned}t_{1} & =\frac{\left(\boldsymbol{e}_{2}\times\boldsymbol{n}\right)\cdot\left(\boldsymbol{r}_{2}-\boldsymbol{r}_{1}\right)}{\boldsymbol{n}\cdot\boldsymbol{n}}\\ t_{2} & =\frac{\left(\boldsymbol{e}_{1}\times\boldsymbol{n}\right)\cdot\left(\boldsymbol{r}_{2}-\boldsymbol{r}_{1}\right)}{\boldsymbol{n}\cdot\boldsymbol{n}} \end{aligned}$$ $\endgroup$ Nov 3, 2022 at 15:07
  • 1
    $\begingroup$ @JoostDöbken - yes I can confirm this. I updated the answer to include the closest points. $\endgroup$ Nov 3, 2022 at 15:27
9
$\begingroup$

Here is an approach that uses dot products instead of cross products.

This works in any number of dimensions, not just 3.

The skew lines are $L = a+bt, M=c+ds$.

The distance between two points on $L$ and $M$ is $D =(a+bt-c-ds)^2 =(e+bt-ds)^2 $ where $e = a-c$.

For this to be a minimum, taking partials, we want $D_s = D_t = 0$.

$D_s = -2d(e+bt-ds) $ and $D_t = 2b(e+bt-ds) $.

Therefore, with multiplication of vectors being dot product, $0 =d(e+bt-ds) =de+dbt-d^2s $ and $0 =b(e+bt-ds) =be+b^2t-bds) $.

These are two equations in the two unknowns $s$ and $t$:

$\begin{array}\\ de &= d^2s-dbt\\ be &= bds-b^2t\\ \end{array} $

The determinant is $A =-b^2d^2+(bd)^2 =-(b^2d^2-(bd)^2) $. By Cauchy-Schwarz, this is non-zero unless $b$ and $d$ are parallel (which is a good thing).

The solutions (by Cramer's rule) are $s =\dfrac{-(b^2)(de)+(be)(db)}{A} $ and $t =\dfrac{(d^2)(be)-(be)(db)}{A} $.

Putting these into $L = a+bt, M = c+ds, D =(e+bt-ds)^2 $ we get the endpoints of the closest line and the distance.

$\endgroup$
5
  • 1
    $\begingroup$ I think that in the solution for $t$ the second $(be)$ term should actually be $(de)$. $\endgroup$
    – Eskapp
    Feb 27, 2018 at 15:38
  • 1
    $\begingroup$ Also it is $D^2 = (e + bt - ds)^2$ One needs to take the square root to get the distance. $\endgroup$
    – Eskapp
    Feb 27, 2018 at 20:28
  • $\begingroup$ I like this because it gives not just the distance, but the points themselves (from $L$ and $M$). One comment for others that tripped me up: $t$ is the parameterization for $L$, and $s$ for $M$, so reversing the alphabetic ordering. I used a linear solver (linsolve in Matlab) . I confirmed the distance given for the example in the other answer. $\endgroup$
    – Liam
    Aug 24, 2020 at 20:44
  • $\begingroup$ This gives the value of $s$ and $t$ for which the gradient of the distance is zero. How do we infer that this extremum is in fact a minimum? Is it from the geometric observation that there is no maximum? $\endgroup$
    – Papa Smurf
    Feb 24, 2023 at 19:50
  • $\begingroup$ You can probably prove that there is no maximum by assuming that there is such a maximum and computing the distance difference from a point further and prove that it is larger. $\endgroup$
    – BlueTrin
    Dec 29, 2023 at 2:54
7
$\begingroup$

If anyone is interested on a implementation of the algorithm proposed by @John Alexiou using python there it is:

def distance_from_two_lines(e1, e2, r1, r2):
    # e1, e2 = Direction vector
    # r1, r2 = Point where the line passes through

    # Find the unit vector perpendicular to both lines
    n = np.cross(e1, e2)
    n /= np.linalg.norm(n)

    # Calculate distance
    d = np.dot(n, r1 - r2)

    return d
$\endgroup$
2
  • $\begingroup$ How could this be adapted to check the distance between half lines that start at the origin r and go to infinity only in the direction of r? $\endgroup$ Jan 3, 2023 at 15:43
  • $\begingroup$ Ok, I got it now $\endgroup$ Jan 3, 2023 at 15:51
3
$\begingroup$

I'm using a method similar to marty cohen's but without matrix/linear system

We first parametrize the two lines as: $$ \vec{L_0} = \vec{p_0}+s\vec{u}\\ \vec{L_1} = \vec{p_1}+t\vec{v} $$ The distance between any points on line 1 to line 0 is $$ d^2 = \dfrac{\left[(\vec{p_1}-\vec{p_0}+t\vec{v})\times\vec{u}\right]^2}{\vec{u}\cdot \vec{u}} $$ To find the minimum distance, we need to minimize the numerator $$ \dfrac{d\left[(\vec{p_1}-\vec{p_0})\times \vec{u}+t\vec{v}\times\vec{u}\right]^2}{dt}=\dfrac{d\left[2(\vec{p_1}-\vec{p_0})\times\vec{u}\cdot(t\vec{v}\times\vec{u})+t^2(\vec{v}\times\vec{u})^2\right]}{dt}\\ =(\vec{p_1}-\vec{p_0})\times\vec{u}\cdot(\vec{v}\times\vec{u})+t(\vec{v}\times\vec{u})^2=0 $$

Then we can get the solution of t $$ t = -\dfrac{(\vec{p_1}-\vec{p_0})\times\vec{u}\cdot(\vec{v}\times\vec{u})}{(\vec{v}\times\vec{u})^2} $$

Taking the value of $t$ back to the distance expression, $$ d^2=\dfrac{\left[(\vec{p_1}-\vec{p_0})\times\vec{u}\right]^2(\vec{v}\times\vec{u})^2-\left[((\vec{p_1}-\vec{p_0})\times\vec{u})\cdot(\vec{v}\times\vec{u})\right]^2}{\vec{u}\cdot \vec{u}(\vec{v}\times\vec{u})^2}\\ = \dfrac{\left[((\vec{p_1}-\vec{p_0})\times\vec{u})\times(\vec{v}\times\vec{u})\right]^2}{\vec{u}\cdot \vec{u}(\vec{v}\times\vec{u}^2}\\ = \dfrac{\left[\vec{u}\cdot((\vec{p_1}-\vec{p_0})\times\vec{v})\vec{u}\right]^2}{\vec{u}\cdot \vec{u}(\vec{v}\times\vec{u})^2}\\ = \dfrac{\left[\vec{u}\cdot((\vec{p_1}-\vec{p_0})\times\vec{v})\right]^2}{(\vec{v}\times\vec{u})^2}\\ = \dfrac{\left[(\vec{p_1}-\vec{p_0})\cdot(\vec{v}\times\vec{u})\right]^2}{(\vec{v}\times\vec{u})^2} $$ The final solution $$ d=\dfrac{\left|(\vec{p_1}-\vec{p_0})\cdot(\vec{v}\times\vec{u})\right|}{|\vec{v}\times\vec{u}|} $$ By simply switching the index, we can also get the solution of s $$ s = -\dfrac{(\vec{p_1}-\vec{p_0})\times\vec{v}\cdot(\vec{v}\times\vec{u})}{(\vec{v}\times\vec{u})^2}\\ $$

Then we can also get the direction of the line connecting the two point: $$ \vec{n}=\vec{p_0}+s\vec{u}-\vec{p_1}-t\vec{v} $$

$\endgroup$
2
$\begingroup$

Hint:

write the equations of the two lines in the form $\vec x=\vec p+t\vec q$: $$ r_1) \qquad \begin{pmatrix} x\\y\\z \end{pmatrix}=\begin{pmatrix} 2\\6\\-9 \end{pmatrix}+t\begin{pmatrix} 3\\4\\-4 \end{pmatrix} $$ $$ r_2) \qquad \begin{pmatrix} x\\y\\z \end{pmatrix}=\begin{pmatrix} -1\\-2\\3 \end{pmatrix}+t\begin{pmatrix} 2\\-6\\1 \end{pmatrix} $$

than, noted the the two lines are not parallel nor intersecting, use the formula from here.

$\endgroup$
1
  • $\begingroup$ "Formula" for forgetting... $\endgroup$
    – Bob Dobbs
    Nov 4, 2022 at 12:53
1
$\begingroup$

Assume you have two parametric lines: $p_1=r_1+e_1$ and $p_2=r_2+e_2$
Check if they are parallel, by checking the if the normalized directions vectors ($e$) are identical. If they are, pick any point on $p_1$, and run the point-to-line formula.

Otherwise, continue as follows: The definition of 'distance' is the minimum distance between any two points A,B on the two lines. So assume points A,B are the ones who provide the minimum distance between the lines.
Now, the line AB must be perpendicular to both lines $p_1,p_2$. Why? Because otherwise you can move a bit on one of the lines to make the distance shorter. If you move $\epsilon$, the distance will be reduced by $\epsilon \cdot cos(\alpha)$, where $\alpha \neq 90 deg$ So the only vector direction which is perpendicular to both lines is $n=e_1 \times e_2$. Let's define $\hat{n}$ as its normalized version. Great.

Now imagine that we place the coordinates origin at point B. Since $AB$ is perpendicular to any point $p_1$ and specifically to point $r_1$, we have a right angled triangle $r_1AB$, and the distance $|AB|=d$ is
$d=\hat{n} \cdot (r_1-B) $
Great now let's write B as $B=r_2 + (B-r_2)$ and we get:
$d=\hat{n} \cdot (r_1-r_2-(B-r_2))$
Now, we know that the vector $B-r_2$ in perpendicular to $\hat{n}$, by definition, so its dot product is zero. Therefore:
$d=\hat{n} \cdot (r_1 - r_2) \: \: \square$

$\endgroup$
0
$\begingroup$

This is a generalization of the code of @Leonardo Mariga to handle half-lines that start at r and go to infinity in the direction of e

def distance_from_two_lines(e1, e2, r1, r2):
    # e1, e2 = Direction vector
    # r1, r2 = Point where the line passes through

    # Find the unit vector perpendicular to both lines
    n = np.cross(e1, e2)

    # Calculate distance
    d = np.dot(n/ np.linalg.norm(n), r1 - r2)
    #print(np.dot(e1, e2))
    
    t1 = np.dot(np.cross(e2, n), (r2 - r1) ) / np.dot(n, n)
    t2 = np.dot(np.cross(e1, n), (r2 - r1) ) / np.dot(n, n)
            
    #print(t1, t2)

    return d if t1 >= 0 and t2 >= 0 else np.linalg.norm(r1 - r2)

I just check that both t1 and t2 are positive. Keep in mind that if the half-lines go in "opposite" directions, the distance is just the distance of the origins.

$\endgroup$
1
  • $\begingroup$ The correct distance can be found by setting the negative t to zero and putting it back in the half-line equation to get the first valid point to use for the distance $\endgroup$ Jan 3, 2023 at 15:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .