3
$\begingroup$

Given two lines in the parametric form (where $p$ is a point on the line, $\hat{v}$ is a unit direction vector and $t$ is the parameter)

$q_0 = p_0 + t_0 \hat{v_0} \\ q_1 = p_1 + t_1 \hat{v_1}$

What is the general solution for detecting the intersection of lines in arbitrary dimensions?

The 3D formula I know is based on 2-ary cross product, which doesn't generalize to higher dimensions. In 2D you can use the perp dot product instead. What about dimensions 4 and higher?

| cite | improve this question | | | | |
$\endgroup$
3
$\begingroup$

The question is basically, if exists scalars $t_0$ and $t_1$ such that $$p_0 + t_0v_0 = p_1 + t_1 v_1.$$

So you just need to know if the vectors $p_1-p_0$, $v_0$, and $v_1$ are linearly independent, since the preceding sentence is the same as $$(p_0 - p_1) + t_0 v_0 - t_1 v_1 = 0.$$

So arrange $p_1-p_0$, $v_0$, and $v_1$ in a matrix and test to see if the matrix has full rank. If it does not, then you can use this fact to find a linear dependence among the columns, which will yield an intersection of the lines.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Finding the rank of a matrix computationally is very slow. Is there no simpler solution? $\endgroup$ – plasmacel Jan 13 '17 at 21:02
  • $\begingroup$ Are you doing the computation by hand? On a computer, it is not too slow, for instance. $\endgroup$ – Zach Boyd Jan 13 '17 at 21:05
  • $\begingroup$ On a computer, it is. The computational time complexity is $O(N^3)$. $\endgroup$ – plasmacel Jan 13 '17 at 21:06
  • $\begingroup$ How big is your $N$? Do you need to do this a lot of times? $\endgroup$ – Zach Boyd Jan 13 '17 at 21:07

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.