find a point on a line segment so that it is at a certain distance from an arbitrary point in 3D

Question

let's say there is 3 points in 3D $p0$ , $p1$ , $p2$ , $l = p2-p1$ forms the line segment
and $p0$ is like isolated on its own. how can I find a point $q$ on $l$ that is away from $p0$ such that $||p0-q|| = d$ ? ($d$ is any distance)

my attempt :

$q = p1+s(p2-p1) = p1+sl$ for $0 =< s =< 1$
now $||p0-p1+sl|| = d $ ? I'm stuck here

I know that terms like s are revealed with dotProduct equations but I can't seem to find a meaningful one here, so how to find s essentially? Ho and every variable is known but s of course

here is a figure

Answer 1

Say that $p_{0}=(y_{1}, y_{2}, y_{3})$, $p_{1}=(x_{1}, x_{2}, x_{3})$ and $l=(z_{1}, z_{1}, z_{3})$

Call $v$ the vector $v = p_{0}-p_{1}-sl$, then $v=(y_{1}-x_{1}-sz_{1}, y_{2}-x_{2}-sz_{2}, y_{3}-x_{2}-sz_{3})$

You must solve $v^2 = d^2$, or $v \cdot v = d^2$. Just apply the dot product of $v$ with itself and you will get a second degree equation in $s$ (note that every other variable is known). The trick here is to square.

You will get $(y_{1}-x_{1}-sz_{1})^2 + (y_2-x_2-sz_2)^2 + (y_3-x_3-sz_3)^2 = d^2$, which you only have to develop, giving you:

$(z_1^2+z_2^2+z_3^2) s^2 + 2(x_1z_1 + x_2z_2 + x_3z_3 - y_1z_1 - y_2z_2 - y_3z_3)s + (y_1^2+x_1^2+y_2^2+x_2^2+y_3^2+x_3^2 - 2y_1x_1 - 2y_2x_2 - 2y_3x_3 -d^2) = 0$

Answer 2

Here is how I would approach the problem, step by step.

Let's say the line segment is between points $\vec{p}_1 = ( x_1 , y_1 , z_1)$ and $\vec{p}_2 = ( x_2 , y_2 , z_2 )$. If we parametrize that using $s$, $0 \le s \le 1$, we have $$\vec{p}(s) = (1-s)\vec{p}_1 + s\vec{p}_2 = \vec{p}_1 + s \left ( \vec{p}_2 - \vec{p}_1 \right ) \tag{1}\label{NA1}$$ (By the way, I almost always parametrise my line segments that way: it seems to be a good starting point in general for this kind of problems. Note that $\vec{p}(0) = \vec{p}_1$ and $\vec{p}(1) = \vec{p}_2$.)

We want to find the point $\vec{p}(s)$ that is at distance $d$ from point $\vec{p}_0 = ( x_0 , y_0 , z_0 )$, i.e. solve $s$ from $$\left\lVert \vec{p}(s) - \vec{p}_0 \right\rVert = d \tag{2}\label{NA2}$$ Because both sides are nonnegative, we can square both sides. The above is equivalent to $$\sqrt{\left(\vec{p}(s) - \vec{p}_0 \right)\cdot\left(\vec{p}(s) - \vec{p}_0 \right)} = d$$ which when squared, is $$\left(\vec{p}(s) - \vec{p}_0 \right)\cdot\left(\vec{p}(s) - \vec{p}_0 \right) = d^2 \tag{3}\label{NA3}$$ which expands to $$\left( (1-s) x_1 + s x_2 - x_0 \right)^2 + \left( (1-s) y_1 + s y_2 - y_0 \right)^2 + \left( (1-s) z_1 + s z_2 - z_0 \right)^2 = d^2 \tag{4}\label{NA4}$$ Since we are interested in $s$, we rewrite that as a polynomial in $s$, collecting the factors of powers of $s$. We get $$\begin{array}{rl} \left( (x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2 \right) s^2 & + \\ 2 \left( (x_1-x_0)(x_2-x_1) + (y_1-y_0)(y_2-y_1) + (z_1-z_0)(z_2-z_1) \right) s & + \\ (x_1-x_0)^2 + (y_1-y_0)^2 + (z_1-z_0)^2 - d^2 & = 0 \end{array} \tag{5}\label{NA5}$$ which is a simple quadratic equation.

If we rewrite $\eqref{NA5}$ using $$\begin{array}{l} C_2 = (x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2 \\ C_1 = 2\left( (x_1-x_0)(x_2-x_1) + (y_1-y_0)(y_2-y_1) + (z_1-z_0)(z_2-z_1) \right) \\ C_0 = (x_1-x_0)^2 + (y_1-y_0)^2 + (z_1-z_0)^2 - d^2 \end{array}$$ then the equation to solve is $$C_2 s^2 + C_1 s + C_0 = 0$$ and therefore:

• If $C_1^2 \gt 4 C_2 C_0$, there are two possible solutions $s$: $$s = \frac{-C_1 \pm \sqrt{C_1^2 - 4 C_2 C_0}}{2 C_2} \tag{6a}\label{NA6a}$$

• If $C_1^2 = 4 C_2 C_0$, there is one possible solution $s$: $$s = \frac{-C_1}{2 C_2} \tag{6b}\label{NA6b}$$

• Otherwise, $C_1^2 \lt 4 C_2 C_0$, and there are no solutions.

But do note that only $0 \le s \le 1$ are on the line segment. You do need to verify each possible $s$ to find the point. When you do find such an $s$, substitute that $s$ into $\eqref{NA1}$ to get the actual point (that is exactly at distance $d$ from $\vec{p}_0$, but on the line segment between $\vec{p}_1$ and $\vec{p}_2$).

Answer 3

Effectively, what you’re trying to find is the intersection of the line segment with a sphere of radius $d$ centered at $p_0$. One approach, described in other answers, is to parameterize the the line segment and then develop and solve a quadratic equation in the parameter. It’s also possible to crank out the intersections directly, without having to solve any equations.

It’s convenient to work in homogeneous coordinates to do some parts of this. Since I’ll be jumping back and forth between homogeneous and (inhomogeneous) Cartesian coordinates, I’ll use boldface names to indicate homogeneous coordinate vectors and boldface names with a tilde above for inhomogeneous Cartesian coordinates.

Start by finding the nearest point on the line $\mathbf l = \overline{\mathbf p_1\mathbf p_2}$ to $\mathbf p_0$. This can be done by finding the intersection of the line with the plane through $\mathbf p_0$ that’s perpendicular to $\mathbf l$. Let $\tilde{\mathbf v}=\tilde{\mathbf p}_2-\tilde{\mathbf p}_1$ be a direction vector of $\mathbf l$. The plane through $\mathbf p_0$ with this normal vector can be represented by the homogeneous vector $\mathbf\pi = \begin{bmatrix}\tilde{\mathbf v}^T; -\tilde{\mathbf v}^T\tilde{\mathbf p}_0 \end{bmatrix}$, i.e., $\tilde{\mathbf v}$ with the negative of its dot product with $\tilde{\mathbf p}_0$ appended. The components of this vector are just the coefficients of an equation $f(x,y,z)=ax+by+cz+d=0$ of the plane. The intersection of this plane with $\mathbf l$ can be found by multiplying $\mathbf\pi$ by the Plücker matrix of the line: $$\mathbf q = (\mathbf p_1\mathbf p_2^T-\mathbf p_2\mathbf p_1^T)\mathbf\pi = (\mathbf p_2^T\mathbf\pi)\mathbf p_1-(\mathbf p_1^T\mathbf\pi)\mathbf p_2.$$ In terms of the above equation of the plane $\mathbf\pi$, this expression says to plug $\tilde{\mathbf p}_2$ into $f$ and multiply $\mathbf p_1$ by the result, and vice-versa, and then take the difference of the resulting vectors. After converting this back into inhomogeneous Cartesian coordinates $\tilde{\mathbf q}$ by dividing through by the last component of $\mathbf q$, finding the two intersection points is a straightforward application of the Pythagorean theorem: the intersections of $\mathbf l$ with the sphere are located at a distance of $$d' = \sqrt{d^2 - \|\tilde{\mathbf q}-\tilde{\mathbf p}_0\|^2} = \sqrt{d^2-(\tilde{\mathbf q}-\tilde{\mathbf p}_0)\cdot(\tilde{\mathbf q}-\tilde{\mathbf p}_0)}$$ along the line in either direction from $\tilde{\mathbf q}$, i.e., they are the points $$\tilde{\mathbf q} \pm d'{\tilde{\mathbf v}\over\|\tilde{\mathbf v}\|}.$$ If the quantity under the radial is negative, that means that the line segment is too far away from $\mathbf p_0$ and there’s no solution.

You’ll still need to check that these points are actually within the line segment, just as with the “solve a quadratic equation” approach, but that can be done with some range checks. You can, of course, use the normalized direction vector ${\tilde{\mathbf v}\over\|\tilde{\mathbf v}\|}$ to form $\mathbf\pi$, since a homogeneous vector can be multiplied by a non-zero constant without affecting what it represents.

For example, take $\tilde{\mathbf p}_0=(0,-3,-1)^T$, $\tilde{\mathbf p}_1=(3,2,5)^T$, $\tilde{\mathbf p}_2=(-1,0,2)^T$ and $d=5$. Then $\tilde{\mathbf v}=(-4,-2,-3)^T$ and $\mathbf\pi=[-4,-2,-3,-9]^T$. This gives $$\begin{align} \mathbf q &= ([-1,0,2,1]\cdot[-4,-2,-3,-9])[3,2,5,1]^T-([3,2,5,1]^T\cdot[-1,0,2,1])[-1,0,2,1]^T \\ &= [-73,-22,25,29]^T, \end{align}$$ and so $$\tilde{\mathbf q} \approx (-2.517,-0.759,0.862).$$ From this we get $d' \approx 3.189$, therefore the intersections of $\mathbf l$ with the sphere are $(-4.886,-1.943,-0.915)$ and $(-0.148,0.426,2.638)$. The former is out of range for the line segment, but the latter is not, so in this example there’s one solution.

Answer 4

thanks a lot guys! I followed the path of @ElieLouis (by the way you made some mistake at the beginning tho) , and used the quadratic formula to be done with it. Also @amd your solution seemed the most elegant , but I couldn't use it because of the extra w coordinates , never had experience with it and I didn't understand your method fully either..

$z$ is the line segment $(p2-p1)~$ , $x,y,z~$ are respective components; $a,b,c~$ are the terms of the quadratic(pre-computed).

$a = z·z$

$b = 2(z_xp1_x - z_xp0_x + z_yp1_y - z_yp0_y + z_zp1_z - z_zp0_z)$

$c = p0_x^2 + p1_x^2 + p0_y^2 + p1_y^2 + p0_z^2 + p1_z^2 - 2p0_xp1_x - 2p0_yp1_y - 2p0_zp1_z - d^2$

for $~~p0 = (1, 0, 3) , p1 = (0, 0, 2) , p2 = (2, 0, 0)$ and $d = 1.8$

$s = 0.393700393701~~or~~-0.393700393701$

verifying:
||($p1+sz)- p0|| = 1.8$ and that happens to be true.