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! :)

$\endgroup$
  • $\begingroup$ 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 math.stackexchange.com/questions/19797/…. Above that distance, there will be a range of points on each line, not a unique solution. $\endgroup$ – Ross Millikan Mar 17 '11 at 13:45
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thanks for the help - this makes a lot of sense to me but I'm still trying to figure out how to calculate the values of s and t. I've put some values into this equation and I'm left with a linear equation of d = xs + yt. I've tried multiplying the equation by two and then using Cramner's rule to find the values of s and t but I didn't get valid values. Should this method work? Thanks very much again. $\endgroup$ – James Bedford Mar 17 '11 at 21:06
  • $\begingroup$ If you're left with the equation $d=xs+yt$, this method worked better than I feared. Now you can, for instance, express $s$ as a function of $t$: $s=\frac{d-yt}{x}$. Put in values for $t$ and get corresponding values for $s$. When you put each of these values into the expressions for $P_0$ and $Q_0$, you will get different points with desired distance between them. As mentioned earlier, there is usually not just one solution. $\endgroup$ – Eivind Mar 17 '11 at 21:48
  • $\begingroup$ Yea, the problem is that both s and t are unknowns which I need to find? $\endgroup$ – James Bedford Mar 17 '11 at 21:59
  • 1
    $\begingroup$ The equation $d=xs+yt$ has infinitely many solutions, because no matter what $s$ is, there is a $t$ that fits into the equation along with it. If we call this combination of $s$ and $t$ a pair, then each pair will make different pairs of points, and all of these pairs of points will have a distance of $d$ between them. Roughly, this means that you can choose an arbitrary point on the line $l$, find its $t$, plug the $t$ into the equation and get an $s$. This $s$ will determine a point on $m$ with the disance $d$ to the point on $l$. Hope this makes it clearer. $\endgroup$ – Eivind Mar 17 '11 at 22:27
  • $\begingroup$ Ahh yes I see the problem now! I was having trouble visualizing it. I think this sort of problem isn't the correct one I need to be solving for my situation, but at least I understand it now! Thanks very much for your help! $\endgroup$ – James Bedford Mar 18 '11 at 8:33
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.