Let us assume that we have N lines in a three dimensional space. How can we figure out if any of these lines intersects any other line?
It would be great, if the problem was solved in terms of linear algebra. If it is not possible, why?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ A single linear equation (i.e. a row of $Ax=b$) determines a 2D plane, not a line. $\endgroup$– lisyarusCommented Aug 22, 2019 at 13:10
-
$\begingroup$ Indeed, it is true what you say. Thank you for pointing it out. I am thinking right now how to rephrase the question to get the same result (figuring out if any of the lines in 3D intersect). $\endgroup$– MikeCommented Aug 22, 2019 at 13:19
-
$\begingroup$ You can use linear algebra to find the distance between any pair of lines: math.stackexchange.com/questions/13734/…. If the distance is zero, the lines intersect. $\endgroup$– David KCommented Aug 26, 2019 at 12:21
-
$\begingroup$ One good answer that can be used as a less algebraic solution can be found here. $\endgroup$– MikeCommented Sep 26, 2019 at 12:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
According to the section about the shortest line between two lines in 3D here : if there are $\mu_a$ and $\mu_b$ (the formulas are given) and $P_a(\mu_a)-P_b(\mu_b)=0$, then there is an intersection point. This is how you might want to find out, if two given lines in 3D intersect.
If you are given $N$ lines, then just make that test as often as needed, which is $$\binom{N}{2}=N(N-1)/2$$ times.
$\begingroup$
$\endgroup$
So far, an intuitive explanation why it is not possible was posted here and here. Namely, if we have a three dimensional real space and no equation, the solution is whole space. Each succeeding equation tends to eliminate one "free" dimension out of the remaining ones.
For example, if we want a line, which is an one dimensional object, we need to eliminate two dimensions. This requires two equations, which represent two planes in the space. However, the planes should not be parallel.
The most algebraic answer so far comes from Gilbert Strang himself:
The case with N=2 lines makes it clear
Line 1 all points a t + b where a and b have 3 real components and t is a real number from -inf to +inf
Line 2 all points AT + B where A and B have 3 real components and T is a real number ....
If those lines meet then there are numbers t and T such that at + b = AT + B
This is 3 eqns in 2 unknowns t and T Create the vector x with components t and -T
In matrix - vector form the 3 equations for x are [ a A ] [ x ] = [B - b]
With N lines you could check them 2 at a time -- or you could look for a better way
If the linear system has no solution, there is no intersection.