5
$\begingroup$

I have two linear, skew, 3D lines, and I was wondering how I could find a points on each of the lines whereby the distance between the two points are a particular distance apart?

I'm not after the points where the lines are the closest distance apart, nor the furthest distance apart, nor the point at which the lines cross! I'm after the points on the lines where the two lines are a particular distance apart. I'd like to also be able to change this distance and find the new points.

Thanks very much in advance! :)

  • 0
    As Elvind says, there is a minimum below which there is no solution. An approach to finding that minimum in one particular case is shown at http://math.stackexchange.com/questions/19797/find-the-closest-point-on-one-line-to-another-line-in-3d/19800#19. Above that distance, there will be a range of points on each line, not a unique solution.2011-03-17

3 Answers 3

2

Here is one way to do it. Assuming you have (or are able to find) a parametric equation for the lines on the form $\begin{align} l: \begin{cases} x=x_{l0}+at \\ y=y_{l0}+bt \\ z=z_{l0}+ct \end{cases}, \qquad m: \begin{cases} x=x_{m0}+ds \\ y=y_{m0}+es \\ z=z_{m0}+fs \end{cases}. \end{align}$

Then, $P_0=(x_{l0}+at,y_{l0}+bt,z_{l0}+ct)$ is a general point on the line $l$ and $Q_0=(x_{m0}+ds,y_{m0}+es,z_{m0}+fs)$ a point on $m$.

We can find a vector $\overrightarrow{P_0Q_0}$ from a point on $l$ to a point on $m$: $\overrightarrow{P_0Q_0} = (x_{m0}+ds-x_{l0}-at,y_{m0}+es-y_{l0}-bt,z_{m0}+fs - z_{l0}-at)$ The distance of the vector is given by $||\overrightarrow{P_0Q_0}|| = \sqrt{(x_{m0}+ds-x_{l0}-at)^2 +(y_{m0}+es-y_{l0}-bt)^2 + (z_{m0}+fs - z_{l0}-at)^2}.$ In other words, if we let $D$ denote your distance, then $D^2=(x_{m0}+ds-x_{l0}-at)^2 +(y_{m0}+es-y_{l0}-bt)^2 + (z_{m0}+fs - z_{l0}-at)^2 .$ This may not be the best way to do it. It could be difficult to find a $t$ and an $s$ that fits, and there will probably be several. If you are able to first choose a point on one line, and then find a point on the other line with desired distance, it will be easier and you will only get two solutions (at most).

  • 0
    Hi; it looks like the at in the third parentheses of the D^2 equation should be ct.2015-06-21
1

In general, this is not possible for all distances. If the lines do not cross, there willl be a minimum distance between the lines which you can never reach below, but you should be able to solve it for all distances equal to or larger than this minimum distance.

Since the general case has been shown by Eivind, I will take the special case where the lines do cross, so a solution is guaranteed.

If the lines, say $l$ and $m$, do cross, you can write them as:

$\begin{align} l(t)&= \mathbf a + t \mathbf b \\ m(s)&= \mathbf a + s \mathbf c \end{align}$

The distance between two lines will be $\|l(t) - m(s)\| = \| t \mathbf b - s \mathbf c\|$. Say you want this to be equal to $d$, then you can solve for $d^2$ (I am here assuming that you are working in $\mathbb R^3$):

$\begin{align} d^2 &= \langle \mathbf b t - \mathbf c s, \mathbf b t - \mathbf c s \rangle = \langle \mathbf b t, \mathbf b t - \mathbf c s \rangle - \langle \mathbf c s, \mathbf b t - \mathbf c s \rangle \\ &= \langle \mathbf b t, \mathbf b t \rangle - 2 \langle \mathbf b t, \mathbf c s \rangle + \langle \mathbf c s, \mathbf c s \rangle = \\ &= t^2\|b\|^2 + s^2 \|c\|^2 - 2 \langle \mathbf b t, \mathbf c s \rangle \end{align}$

If you have normalized $\mathbf b$ and $\mathbf c$, this will reduce to:

$d^2 = t^2 + s^2 - 2 (b_1c_1 + b_2c_2 + b_3c_3) ts$

Which you can solve. You can here choose a value for $t$ (which will tell you how far the crossing point the point on line $l$ is) and then solve for $s$. If you want the points to be on equal distance from the crossing point, take $t = s$.

0

I know this is an old post, but I also needed a formula for finding the points at which two 3-dimensional lines are a specific distance apart from each other (or the range in which two lines are within a specific distance of each other), if any, but was unable to find anything on google (except for this), so i decided on solving it myself. This is what i ended up with:

Note that the way i understand the OP's question (especially due to his follow up question) is that he wants to find the points on the two lines where the distance between the lines is exactly $D$. The other two answers seem to try to find all point-pairs on the two lines which has distance $D$ between them. (If it is what you are looking for, this does give you the range at which such point-pairs can exists).

How to find the points where 2 lines are distance D apart:

If you have two lines:

  • $l_1:\overset⃗p{(t)}=\overset⃗at+\overset⃗b$
  • $l_2:\overset⃗q{(s)}=\overset⃗gs+\overset⃗h$

which are non-parallel (i.e. $\mid\text{ }\overset⃗k\mid\neq0$) and non-degenerate (i.e. $\mid\text{ }\overset⃗a\mid\neq0$ and $\mid\text{ }\overset⃗g\mid\neq0$), and you want to find the points (or $t$-parameters) on line $l_1$ which are exactly at (shortest) distance $D$ from line $l_2$, you can use:

$ \begin{array}{ccc}t&\text{=}&\frac{-2{(\overset⃗k⋅\overset⃗c)}\pm\sqrt d}{2\mid\overset⃗k\mid^2}\text{ , where }d=4{(\overset⃗k⋅\overset⃗c)}^2-4\mid\overset⃗k\mid^2{(\mid\overset⃗c\mid^2-D^2)}\text{ and }\overset⃗k=\frac{(\overset⃗g\times\overset⃗a)}{\mid\overset⃗g\mid}\text{ and }\overset⃗c=\frac{\overset⃗g\times{(\overset⃗b-\overset⃗h)}}{\mid\overset⃗g\mid}\end{array} $

The number of solutions this has depends on $d$:

  • $d<0$ : no solutions (the lines never come within distance $D$ of each other)
  • $d=0$ : one solution (the two solutions are the same)
  • $d>0$ : two solutions (in place of "$\pm$" use "$+$" for one solution and "$-$" for the other)

(if needed, the actual points on $l_1$ can be found by plugging the found $t$-parameters into the equation of line $l_1$)


Notes:

  • How to use: First calculate $\overset⃗k$ and $\overset⃗c$, then calculate $d$ and, depending on $d$, calculate the 0, 1 or 2 solutions of $t$. If you want the points, insert the found $t$ solutions into the equation of $l_1$.
  • This only finds the points on line $l_1$ at which the two lines are exactly distance D apart. This was what i needed. If you also want to find the corresponding points on line $l_2$, you can just "swap the lines" and insert into the formula again (i.e. run it two times).
  • Obviously, at and between the two found points on the line $l_1$, the distance between the lines will be $\le D$. The distance is $\gt D$ everywhere else. So this method can actually also be used to find the range $[t_1, t_2]$ in which the lines are within a specific distance from each other.
  • Note that if you set $D = 0$, this actually finds the intersection point betwen the 2 lines (only at most 1 solution in that case). (Another case with only 1 solution, would be when the shortest distance between the lines is exactly $D$. In that case, the two lines are only within distance $D$ of each other at exactly one point).

  • You can think of what this formula does, as placing an infinitely long cylinder with radius $D$ around line $l_2$ and then checking for intersection between line $l_1$ and the cylinder. So this is formula is actually line-cylinder intersection - Maybe i should have googled that instead... :)

  • As mentioned earlier, it must be noted that this formula reports the points at which the shortest distance between the two lines is exactly $D$. The shortest distance is normally what we refer to when we say distance between lines, points and lines, etc... (perpendicular)
    $~$
    Inside the range $]t_1, t_2[$ (if it exists), where the shortest distance between the two lines is less than $D$, you can always find other point-pairs (infinitely many) on the two lines which has distance equal to $D$. I think this is what the other two answers are referring to. I.e. you can always find a distance which is longer than the shortest distance, and within this range you can find infinitely many point-pairs with distance $D$ between them (pick a point $p$ on line $l_1$. Instead of picking the point on line $l_2$ which is closest to $p$, pick one which is further away - such as the one which is distance $D$ away). But you can of course only do this within this range (not when the shortest distance is $D$ or greater - since in this case, you cannot pick a point on $l_2$ at which the distance between the points is both 1) longer than the shortest distance and 2) equal to $D$ at the same time).
    $~$
    While a bit unclear, I don't believe the OP was interested in getting all of these infinitely many point-pairs listed (especially based on his follow up question).
    $~$
    This formula reports the end-points $t_1$, $t_2$ of the range at which the two lines are within distance $D$ of eachother. In other words, it reports the points at which the shortest distance between the two lines is $D$ (not when any of the distances longer than the shortest distance is $D$).


The derivation: (This section can be skipped)

This section shows how i arrived at the result above. Hopefully it is helpful (i've tried not to skip too many steps in the calculations, so it should be possible to follow). If you spot an error or something i've overlooked, or if you find a way to "optimize" it, please tell me in a comment.

Assume we have these non-parallel non-degenerate lines:

  • $l_1:\overset⃗p{(t)}=\overset⃗at+\overset⃗b$
  • $l_2:\overset⃗q{(s)}=\overset⃗gs+\overset⃗h$

Our starting point will be the usual "shortest distance between line and point" formula, where we insert $l_2$ as the line and we insert the expression for $l_1$ as the point. We do a bit of algebra on it and see what we get. (Basically we're just rewriting things in the equation, and at the end we end up with a 2nd degree equation which we know how to solve. Nothing too complicated.)

We want to find the points $\vec p(t)$ on $l_1$ where $dist(\vec p(t), l_2) = D$:

$\begin{array}{rll}\text{}D&\text =&\mathit{dist}(\vec p(t),l_2)&\\&\text =&\mathit{dist}(\vec at+\vec b,l_2)&\text{insert expression for }\vec p(t)\\&\text =&\frac{\left|\vec g\times ((\vec at+\vec b)-\vec h)\right|}{|\vec g|}&\text{note: it is assumed that }|\vec g|\neq 0\\&\text =&\frac{\left|t(\vec g\times \vec a)+\vec g\times \vec b-\vec g\times \vec h\right|}{|\vec g|}&\begin{matrix}\text{using }\vec a\times (\vec b+\vec c)=\vec a\times \vec b+\vec a\times \vec c\hfill \\\text{and }(r\vec a)\times \vec b=\vec a\times (r\vec b)=r(\vec a\times \vec b)\hfill \end{matrix}\hfill \\&\text =&\frac{\left|(\vec g\times \vec a)t+\vec g\times (\vec b-\vec h)\right|}{|\vec g|}&\text{combine constant terms (without t) again}\\&\text =&\left|\frac{(\vec g\times \vec a)}{|\vec g|}t+\frac{\vec g\times (\vec b-\vec h)}{|\vec g|}\right|&\text{shorten fraction by }\frac 1{|\vec g|}\text{ and use }s|\vec x|=|s\vec x|\\&\text =&\left|\vec kt+\vec c\right|&\text{cleanup: introduce constants }\vec k\text{ and }\vec c\\&\text =&\sqrt{(k_1t+c_1)^2+(k_2t+c_2)^2+(k_3t+c_3)^2}&\text{expand length expression}\\D^2&\text =&(k_1t+c_1)^2+(k_2t+c_2)^2+(k_3t+c_3)^2&\text{multiply each side by itself}\\&\text =&\begin{matrix}k_1^2t^2\ +\ 2k_1c_1t\ +\ c_1^2\ +\ \hfill \\k_2^2t^2\ +\ 2k_2c_2t\ +\ c_2^2\ +\ \hfill \\k_3^2t^2\ +\ 2k_3c_3t\ +\ c_3^2\hfill \end{matrix}\hfill &\text{expanding parentheses}\\&\text =&(k_1^2+k_2^2+k_3^2)t^2+2(k_1c_1+k_2c_2+k_3c_3)t+(c_1^2+c_2^2+c_3^2)&\text{arrange terms into }at^2+bt+c\text{ form}\\&\text =&(\vec k\cdot \vec k)t^2+2(\vec k\cdot \vec c)t+(\vec c\cdot \vec c)&\text{cleanup using dot product}\\&\text =&|\vec k|^2t^2+2(\vec k\cdot \vec c)t+(|\vec c|^2)&\text{cleanup using }\vec x\cdot \vec x=|\vec x|^2\\\hfill 0&\text =&|\vec k|^2t^2+2(\vec k\cdot \vec c)t+(|\vec c|^2-D^2)&\text{move }D^2\text{ onto the right side}\end{array}$

So this has been reduced to a 2nd degree equation which can be solved as usual:

$\begin{matrix}t&\text =&\frac{-2(\vec k\cdot \vec c)\pm \sqrt d}{2|\vec k|^2},\text{where }d=4(\vec k\cdot \vec c)^2-4|\vec k|^2(|\vec c|^2-D^2)\text{ and }\vec k=\frac{(\vec g\times \vec a)}{|\vec g|}\text{ and }\vec c=\frac{\vec g\times (\vec b-\vec h)}{|\vec g|}\end{matrix}$

which has the following number of solutions depending on $d$:

  • $d < 0$ : no solutions
  • $d = 0$ : one solution (the two solutions are the same)
  • $d > 0$ : two solutions

$\text{ }$

And remember that we assumed:

  • the lines are not parallel. Otherwise, we have $\overset⃗k=\overset⃗0$ since:
               $\begin{align} \overset⃗k=\frac{(\overset⃗g\times\overset⃗a)}{\mid\overset⃗g\mid}=\mid\overset⃗g\mid\mid\overset⃗a\mid\sin\operatorname\theta\overset⃗n=\overset⃗0\text{, since}\sin\operatorname\theta=0 \end{align}$
    and therefore $\mid\text{ }\overset⃗k\mid=0$ and we will divide by zero.
  • line 2 is not degenerate – i.e. $\mid\text{ }\overset⃗g\mid\neq0$. Otherwise we would divide by zero.
  • line 1 is not degenerate – i.e. $\mid\text{ }\overset⃗a\mid\neq0$. Otherwise $\mid\text{ }\overset⃗k\mid=0$ and we would divide by zero when finding our solution (solving the 2nd degree equation).

(If these assumptions are not met, you can still find an answer: If they are parallel, you can use use the normal line-point distance formula, and see if the distance is equal to $D$ or not (either all points of the lines have distance $D$ to the other line or none of them have). If only one of them are degenerate, you can also use point-line distance. If both are degenerate, you can use point-point distance.)