1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Semiclassical Aug 27 '14 at 14:52
  • $\begingroup$ Any suggestions on how to find/derriere the necessary formula? $\endgroup$ – WhatWouldKantDo Aug 27 '14 at 14:57
  • $\begingroup$ Try looking at Mathworld's page on line-line intersections. Wikipedia's page on skew lines may also be useful. $\endgroup$ – Semiclassical Aug 27 '14 at 15:18
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't quite understand how to set up the matrix referenced in the last step. $\endgroup$ – WhatWouldKantDo Aug 27 '14 at 15:17
  • $\begingroup$ @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 $\endgroup$ – Jean-Claude Arbaut Aug 27 '14 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.