# Algorithm for solving line line intersection in 3d

I am trying to find an algorithm that a computer can execute that finds the intersection point between two lines each defined by a point on the line and a direction vector. Does anyone know of one? It is preferable that I can do any solving ahead of time to make the code a matter of plugging numbers into a formula.

• Note that in most cases a pair of lines in 3D will be skew i.e. not intersect. However, there will always be a pair of points on the lines whose separation is smallest. So one approach is to compute those two points using a generic formula, and then check to see if they coincide. – Semiclassical Aug 27 '14 at 14:52
• Any suggestions on how to find/derriere the necessary formula? – WhatWouldKantDo Aug 27 '14 at 14:57
• Try looking at Mathworld's page on line-line intersections. Wikipedia's page on skew lines may also be useful. – Semiclassical Aug 27 '14 at 15:18

Let's call your points $A, B$, with corresponding vectors $u,v$. Then your intersection $M$, if it exists, satisfies

$$\overrightarrow{AM}=\lambda \vec{u}$$ $$\overrightarrow{BM}=\mu \vec{v}$$

That's two unknowns, which is not pleasing. But you can rewrite this as: $\overrightarrow{AM}=\lambda \vec{u}$, and $\overrightarrow{BM}$ is parallel to $\vec v$. The latter is expressed with cross product, so you have to find $\lambda$ such that $\overrightarrow{BM} \wedge \vec v=0$, with $\overrightarrow{BM}=\overrightarrow{BA}+\overrightarrow{AM}$, or:

$$\left(\overrightarrow{BA}+\lambda\vec u\right)\wedge \vec v=0$$

This will give you three linear equations (one per axis), but one is enough, the other are just safe checks, since $M$ may not exist at all.

By the way, for such a point $M$ to exist, you need that $\vec u,\vec v$ and $\overrightarrow{AB}$ be coplanar, that is

$$\det(\vec u,\vec v,\overrightarrow{AB})=0$$

It's not necessarily enough, since you could have parallel coplanar lines.

• I don't quite understand how to set up the matrix referenced in the last step. – WhatWouldKantDo Aug 27 '14 at 15:17
• @user1481112 What do you mean? once you know u, v and AB, it's immediate to build the matrix, and the determinant is easily found by the rule of Sarrus – Jean-Claude Arbaut Aug 27 '14 at 15:33