Intersection between two lines 3D

Question

I'm writing the program for university project on c#. I have to find intersection between two lines in 3d space. Lines are specified by the point lying on the line and by its direction vector. I'm bad in math therefore I don't know in what direction I have to move for solving this task. I will be very grateful for the help.

Answer 1

Since in the comment I mentioned about something numerical, I would like to provide a method to compute the minimal distance between two lines in 3D. Then, if the distance is zero (or sufficiently small), you could deduce that the two lines intersects.

Let the points $a=(a_x, a_y, a_z)$, $b=(b_x, b_y, b_z)$ on the first line, and $c=(c_x, c_y, c_z)$, $d=(d_x,d_y,d_z)$ on the second line.

Let the directional vectors $v_1=b-a$, $v_2=d-c$ (component-wise operation). And another vector $w=d-a$.

The distance between two lines is the height of the following parallelepiped:

For parallelepipeds, (height) = (volume) / (base area). Compute the volume by determinant of $v_1,v_2,w$ and area by the norm of cross product $|v_1\times v_2|$:

$$\textrm{distance between lines} = \textrm{height} = \frac{|\left|\begin{matrix} v_{1x} & v_{2x} & w_x\\ v_{1y} & v_{2y} & w_y\\ v_{1z} & v_{2z} & w_z\end{matrix}\right||}{\sqrt{\left|\begin{matrix} v_{1y} & v_{1z}\\ v_{2y} & v_{2z} \end{matrix}\right|^2+\left|\begin{matrix} v_{1z} & v_{1x}\\ v_{2z} & v_{2x} \end{matrix}\right|^2+\left|\begin{matrix} v_{1x} & v_{1y}\\ v_{2x} & v_{2y} \end{matrix}\right|^2}}$$

Exception:

There is an exception that the two lines are parallel or the same. Then the denominator becomes zero. Thus you have to check that whether the two vectors $v_1, v_2$ are proportional at first:

• $v_1\parallel v_2\nparallel w\implies$ parallel lines
• $v_1\parallel v_2\parallel w\implies$ same line

---

Edit: Find the intersection

To find the intersection, we have to find how many $v_1$ for $a$ to add to arrive the intersection (and same for $c, v_2$), ie, calculate $s,t\in\mathbb R$ for $$\textrm{intersection}=a+tv_1=c+sv_2$$ in which "+" is component-wise and $s,t$ are scalar multiplications. This is totally the same as gimusi's answer.

So we are solving this set of equations:

$$\left\{\begin{aligned} a_x+tv_{1x}&=c_x+sv_{2x}\\ a_y+tv_{1y}&=c_x+sv_{2y}\\ a_z+tv_{1z}&=c_x+sv_{2z} \end{aligned}\right.$$

It only requires two equations to solve for $t,s$. So we solve the first two equations by Cramer's rule:

$$t=\frac{\left|\begin{matrix} c_x-a_x & -v_{2x}\\ c_y-a_y & -v_{2y} \end{matrix}\right|}{\left|\begin{matrix} v_{1x} & -v_{2x}\\ v_{1y} & -v_{2y} \end{matrix}\right|}$$

So the intersection is $$\textrm{intersection}=a+tv_1=(a_x,a_y,a_z)+\frac{\left|\begin{matrix} c_x-a_x & -v_{2x}\\ c_y-a_y & -v_{2y} \end{matrix}\right|}{\left|\begin{matrix} v_{1x} & -v_{2x}\\ v_{1y} & -v_{2y} \end{matrix}\right|}(v_{1x}, v_{1y},v_{1z})$$

Exception:

If the denominator of $t$ is zero, then solve $t$ by another equations:

$$t=\frac{\left|\begin{matrix} c_y-a_y & -v_{2y}\\ c_z-a_z & -v_{2z} \end{matrix}\right|}{\left|\begin{matrix} v_{1y} & -v_{2y}\\ v_{1z} & -v_{2z} \end{matrix}\right|}=\frac{\left|\begin{matrix} c_z-a_z & -v_{2z}\\ c_x-a_x & -v_{2x} \end{matrix}\right|}{\left|\begin{matrix} v_{1z} & -v_{2z}\\ v_{1x} & -v_{2x} \end{matrix}\right|}$$

Answer 2

Let consider two lines

• $P(t)=P_0+t \vec v$

• $Q(s)=Q_0+s \vec w$

then the intersection requires that

• $p_1+tv_1=q_1+sw_1$
• $p_2+tv_2=q_2+sw_2$
• $p_3+tv_3=q_3+sw_3$

from which we can find $s$ and $t$.