How to find intersection of two lines in 3D?

Given two lines joining A,B and C, D in 3D how do I figure out if they intersect, where they intersect and the ratio along AB at which the intersection happens?

I can quite hapilly work out the equation for the lines in different forms. I'm guessing that you need to change them to parametric form, equate the equations and do some algebra manipulation

-
(i) How are you "given" the lines? Vector form? Symmetric form? Two points? (ii) What have you tried? Where are you stuck? –  Arturo Magidin Mar 22 '11 at 15:29
The lines are given as four points (A,B,C,D). Lines join A, B and C, D –  user8578 Mar 22 '11 at 15:37
That (partially) answers my first question, but remains mum on the second (information that should be added to the question, by the way). –  Arturo Magidin Mar 22 '11 at 15:38
I can quite hapilly work out the equation for the lines in different forms. I'm guessing that you need to change them to parametric form, equate the equations and do some algebra manipulation. –  user8578 Mar 22 '11 at 15:39
Yeah, accidentally clicked add comment before I was finished! Added stuff to the initial question. –  user8578 Mar 22 '11 at 15:41

If you are given two points for each line, $A=(a_1,a_2,a_3)$, $B=(b_1,b_2,b_3)$ to determine the first line, $C=(c_1,c_2,c_3)$ and $D=(d_1,d_2,d_3)$ to the determine the second line, the simplest way is to write both lines in vector/parametric form:

• Line $1$ through $A$ and $B$ has vector form $$\left(\begin{array}{c}x\\y\\z\end{array}\right) = A + t(B-A) = \left(\begin{array}{c}a_1\\a_2\\a_3\end{array}\right) + t\left(\begin{array}{c}b_1-a_1\\b_2-a_2\\b_3-a_3\end{array}\right),\quad t\in\mathbb{R}.$$

• Line $2$ through $C$ and $D$ has vector form $$\left(\begin{array}{c}x\\y\\z\end{array}\right) = C + s(D-C) = \left(\begin{array}{c}c_1\\c_2\\c_3\end{array}\right) + s\left(\begin{array}{c}d_1-c_1\\d_2-c_2\\d_3-c_3\end{array}\right),\quad s\in\mathbb{R}.$$

The two lines intersect if and only if there is a solution $s,t$ to the system of linear equations $$\begin{array}{rcl} a_1 + t(b_1-a_1) &= c_1 + s(d_1-c_1)\\ a_2 + t(b_2-a_2) &= c_2 + s(d_2-c_2)\\ a_3 + t(b_3-a_3) &= c_3 + s(d_3-c_3). \end{array}$$ If $(s_0,t_0)$ is a solution to this system, then plugging in $t_0$ to the equation for $L_1$ or $s_0$ to the equation for $L_2$ yields thep oint of intersection.

I confess i don't know what "The ratio at which the intersection happens" means. Perhaps it refers to the value of $t$ (which is $0$ for the point $A$ and $1$ for the point $B$, and for example $t = \frac{1}{2}$ for the point midway between $A$ and $B$).

-

Assume the points are known to be distinct, since otherwise the problem is either trivial or degenerate. Of course numerical accuracy is an issue, if we are to distinguish a pair of lines that nearly intersect from a pair that would exactly intersect except for round-off in computation.

First dispose of the case where AB is parallel to CD by checking the linear independence of {A-B,C-D}. If they are parallel, then either there is no point of intersection or the intersection is not unique (since the lines coincide).

Then the question of whether nonparallel lines AB and CD intersect is the same as coplanarity of A,B,C,D.

By translation we can assume D $= (0,0,0)$ is the origin. Check the rank of the matrix M whose rows are A,B,C. The lines intersect if and only if that rank is less than 3.

Suppose $u$ M $= 0$ is a nontrivial solution of the homogeneous problem, scaled so that:

$$u_1 + u_2 = 1$$

[Note that if $u_1 + u_2 = 0$, it would imply C = D is also the origin.]

Then $u_1$ A + $u_2$ B belongs to AB as well as CD.

If the question intended was whether line segments AB and CD intersect, i.e. whether any point of intersection falls strictly in between A and B, as well as between C and D, then this can also be decided from the computation outlined above. The additional requirement would be that $u_1,u_2$ are in [0,1], and that $-1 \leq u_3 \leq 0$.

-

The lines can be parameterized as:

$$(t*Ax + (1-t)Bx, t*Ay+(1-t)By, t*Az + (1-t)*Bz)$$

and

$$(s*Cx + (1-s)Dx, s*Cy+(1-s)Dy, s*Cz + (1-s)*Dz)$$

Apply some algebra, and you get a system of three equations on two variables (s and t). If system is consistent, then the lines intersect. Plug these solutions into the parameterization above to obtain your answer.

The value "t" (if between 0 and 1) will give you the "ratio" along line segment AB at which the intersection occurs.

-
That's not right -- this is a 3-dimensional problem. –  TonyK Mar 22 '11 at 15:47
I corrected my solution. –  Justin W Smith Mar 22 '11 at 15:53
Actually a value of t=1, means that the intersection is at A; so you might need to use (1-t) to determine the "ratio". –  Justin W Smith Mar 22 '11 at 15:56
(This solution is essentially the same as the one given by Arturo.) –  Justin W Smith Mar 22 '11 at 16:00