Task
Given the lines $$\vec{l_1}(t_1) = \vec{s}_1 + t_1\vec{r}_1$$ $$\vec{l_2}(t_2) = \vec{s}_2 + t_2\vec{r}_2$$ $$\vec{l_3}(t_3) = \vec{s}_3 + t_3\vec{r}_3$$
I have to find the Points $\vec{p}_1$, $\vec{p}_2$, and $\vec{p}_3$ on these lines ($\vec{p}_1$ on $\vec{l}_1$, $\vec{p}_2$ on $\vec{l}_2$, and so on). I do know the relative positions of these points towards each other: $$\vec{a} = \vec{p}_1 - \vec{p}_2$$ $$\vec{b} = \vec{p}_2 - \vec{p}_3$$ $$\vec{c} = \vec{p}_3 - \vec{p}_1$$
Finally, I know that $t_1$, $t_2$, and $t_3$ have to be positive, aka. the direction vectors $\vec{r}$ of the lines all point towards the respective point on the line.
Also, I have to create an algorithm for solving this problem, so I need to find a general solution.
My approach so far
Now my idea so far was to take the vectors between the points and substitute each $\vec{p}$ with the line it is on: $$\vec{a} = \vec{s}_1 + t_1\vec{r}_1 - \vec{s}_2 + t_2\vec{r}_2$$ $$\vec{b} = \vec{s}_2 + t_2\vec{r}_2 - \vec{s}_3 + t_3\vec{r}_3$$ $$\vec{c} = \vec{s}_3 + t_3\vec{r}_3 - \vec{s}_1 + t_1\vec{r}_1$$
Afterward, I would move all the $\vec{s}$ to the left side of the equations: $$\vec{a} - \vec{s}_1 + \vec{s}_2 = t_1\vec{r}_1 + t_2\vec{r}_2$$ $$\vec{b} - \vec{s}_2 + \vec{s}_3 = t_2\vec{r}_2 + t_3\vec{r}_3$$ $$\vec{c} - \vec{s}_3 + \vec{s}_1 = t_3\vec{r}_3 + t_1\vec{r}_1$$
Let's introduce the vectors $\vec{d}$, $\vec{e}$, and $\vec{f}$ as substitutes for the left side to make it less crowded. They are calculated from just given values: $$\vec{d} = \vec{a} - \vec{s}_1 + \vec{s}_2$$ $$\vec{e} = \vec{b} - \vec{s}_2 + \vec{s}_3$$ $$\vec{f} = \vec{c} - \vec{s}_3 + \vec{s}_1$$
Now, this looks very close to a system of linear equations ($\vec{0}=(0, 0, 0)^{T}$): $$\vec{d} = \vec{r}_1t_1 + \vec{r}_2t_2 + \vec{0}t_3$$ $$\vec{e} = \vec{0}t_1 + \vec{r}_2t_2 + \vec{r}_3t_3$$ $$\vec{f} = \vec{r}_1t_1 + \vec{0}t_2 + \vec{r}_3t_3$$
Let's split it up by components: $$d_x = r_{1x}t_1 + r_{2x}t_2 + 0t_3$$ $$d_y = r_{1y}t_1 + r_{2y}t_2 + 0t_3$$ $$d_z = r_{1z}t_1 + r_{2z}t_2 + 0t_3$$ $$e_x = 0t_1 + r_{2x}t_2 + r_{3x}t_3$$ $$e_y = 0t_1 + r_{2y}t_2 + r_{3y}t_3$$ $$e_z = 0t_1 + r_{2z}t_2 + r_{3z}t_3$$ $$f_x = r_{1x}t_1 + 0t_2 + r_{3x}t_3$$ $$f_y = r_{1y}t_1 + 0t_2 + r_{3y}t_3$$ $$f_z = r_{1z}t_1 + 0t_2 + r_{3z}t_3$$
Now I just need to solve this linear system of equations to get $t_1$, $t_2$, and $t_3$. I then insert these values into the line equations to get the points I'm looking for.
My Questions
I tried to implement this approach in my algorithm but got very wrong results. Now I'm wondering if my approach is wrong or if my implementation has a problem. So
- I could imagine multiple sets of points fulfilling the relative positions. How do I get the condition, that $t_1$, $t_2$, and $t_3$ have to be positive into my system of linear equations?
- Is this problem solvable with just three points? If not, can it be solved if more points are available in the same fashion? How many points would I need?
- Is there an easier approach I could take for the problem I described or does my approach make sense? I'd prefer to not have to solve a system of linear equations. Is there another approach that doesn't require one?
- Can I create a system of linear equations the way I described above, especially since I created it from vectors?
- The system of linear equations is overdetermined. Can I solve it, for example, with just the equations for x-components? Or do I need all the equations? I'm asking because the algorithm I found for solving the system of linear equations doesn't accept overdetermined systems so I have to limit myself to three equations.
First note that since $$\vec a = \vec p_1 - \vec p_2\\ \vec b = \vec p_2 - \vec p_3$$ If you add these two equations together, you get $$\vec a + \vec b = \vec p_1 - \vec p_3 = -\vec c$$ so $$\vec a + \vec b + \vec c = 0$$ This means your three equations are not independent. Any solution to the $\vec a$ and $\vec b$ equations will automatically satisfy the $\vec c$ equation, provided $\vec a + \vec b + \vec c = 0$. And if that equation is not true, there can be no solution at all. You have only two equations, not three.
But those two equations are 3-dimensional vector equations, which means they are six linear equations, which is still too many for your three unknowns.
This is a system of six equations, no matter how you wrote it out. Anything you do is tantamount to solving this system of six equations. There are some techniques for finding $t_1, t_2, t_3$ that may not look like solving a system of linear equations to you. But that is just window-dressing. Behind the scenes, they are still solving this system. And all methods of solving a system must give the same result, no matter how it was done - or else the "method" will have failed to solve the system.
Any system of $n$ independent linear equations in $n$ variables will have a unique solution. If the equations are not independent, then there really are not $n$ equations, as at least one of the equations can be obtained from the others, and so does not offer any new information. In this case, the system is underspecified and has infinitely many solutions. Or the equations are contradictory, so there is no solution.
This is why all the algorithms use just three equations for three unknowns. If you have more than three, choose three independent equations from among them, and solve that smaller system. The result is the necessary solution to satisfy these three equations. Any solution to the whole system has to both satisfy these three equations - and therefore cannot have any other solution than the one found - and the remaining equations. So once you find that solution, you plug it into the remaining equations and see if it works for them as well. If it also makes the remaining equations true, then that solution is a solution for the entire system, not just the three equations used to find it. But if the solution to the three equations does not satisfy one of the other equations, this means the full system has no solution. There will not be points $\vec p_1, \vec p_2, \vec p_3$ on the three lines that satisfy $\vec a = \vec p_1 - \vec p_2, \vec b = \vec p_2 - \vec p_3$.
An alternative method to solve the equations is to first note that the cross product of two vectors is always perpendicular to both of them. So:
$$(\vec r_1 \times \vec r_2)\cdot \vec a = (\vec r_1 \times \vec r_2)\cdot(\vec s_1 - \vec s_2)$$ $$(\vec r_2 \times \vec r_3)\cdot \vec b = (\vec r_2 \times \vec r_3)\cdot(\vec s_2 - \vec s_3)$$ If either of these two equations is not true, then your system cannot have a solution. Similarly,
$$((\vec s_1 - \vec s_2) \times \vec r_1)\cdot \vec a = -t_2 ((\vec s_1 - \vec s_2) \times \vec r_1)\\ ((\vec s_1 - \vec s_2) \times \vec r_2)\cdot \vec a = t_1 ((\vec s_1 - \vec s_2) \times \vec r_2)\\ ((\vec s_2 - \vec s_3) \times \vec r_2)\cdot \vec b = -t_3 ((\vec s_2 - \vec s_3) \times \vec r_2)\\ ((\vec s_2 - \vec s_3) \times \vec r_3)\cdot \vec b = t_2 ((\vec s_2 - \vec s_3) \times \vec r_3)$$ Which, assuming the denominators are not $0$, gives you the following solutions: $$t_1 = \dfrac{((\vec s_1 - \vec s_2) \times \vec r_2)\cdot \vec a}{((\vec s_1 - \vec s_2) \times \vec r_2)}\\ t_2 = \dfrac{((\vec s_2 - \vec s_1) \times \vec r_1)\cdot \vec a}{((\vec s_1 - \vec s_2) \times \vec r_1)}\\ t_2 = \dfrac{((\vec s_2 - \vec s_3) \times \vec r_3)\cdot \vec b}{((\vec s_2 - \vec s_3) \times \vec r_3)}\\ t_3 = \dfrac{((\vec s_3 - \vec s_2) \times \vec r_2)\cdot \vec b}{((\vec s_2 - \vec s_3) \times \vec r_2)}$$
If the two equations for $t_2$ do not give the same value, then once again, your system will have no solution (it may be that the earlier conditions on $\vec a, \vec b$ are enough to ensure this, but I have not checked).