9
$\begingroup$

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

  • 0
    Yeah, accidentally clicked add comment before I was finished! $A$dded stuff to the initial question.2011-03-22

3 Answers 3

11

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

  • 0
    "ratio", the way I read it, means the distance/length of the line-segment from A to intersection-point, divided by the length of the segment from intersection-point to B: ||X-A|| / ||B-X|| ?2017-04-22
1

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

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.

  • 0
    (This solution is essentially the same as the one given by Arturo.)2011-03-22