5
$\begingroup$

I hope you can help me with a mathematical problem I'm trying to solve (for many days) and so far no success.

Given 2 sets P=[p_1,p_2,p_3] and Q=[q_1,q_2,q_3] of 3 infinite lines each in 3D space (each p_i and q_i (i=1,2,3) is a 3D line represented by a 3D point and a unit vector). so overall we have 6 lines.
I need to find a rotation matrix R (3x3) so that if I rotate all the lines in P by R then I get new lines P_rotate=[p_1_rotate, p_2_rotate, p_3_rotate] so that p_i_rotate and q_i (i=1,2,3) intersect each other.
I know there might not be such a rotation matrix and in some cases there might be infinite rotation matrices (for example if all the 6 lines are on the same plane and the axis of rotation is perpendicular to that plane). but the assumption here that for sure there exists such a rotation matrix and if there are more than one, then I can choose any of them.

This is what I tried to do so far:
It's actually solving 3 equations of 3 variables (the variables are the 3 angles around the axises x,y,z). but the equations were extremely complex that I couldn't solve them (and I'm not even sure they are solvable). You can calculate the rotated lines as a function of the 3 angles. meaning each rotated line will contain a new point and a new vector both as a function of the 3 angles. then I calculate for each line the distance to the relevant line in Q. and I need to find for which angles the 3 distances are zero. I assumed here that first I rotate around Z axis, then around Y axis and then around X axis. I think the order doesn't matter since whatever order I choose I may get different angles but the final rotation matrix will be the same. Anyway, the final 3 equations were extremely long and with many multiplications of the unknown variables so it was actually impossible for me to solve them.

I also tried to solve it in a different way. not using rotation matrix. but Rodrigues' rotation formula. in Rodrigues' formula I rotate around an axis line that passes through the origin by an angle theta. so I actually need to find v_x,v_y,theta where v_x, v_y are the x and y components of a unit vector of the axis line (v_z can be calculated by v_x and v_y since the vector is unit). and theta is an angle of rotation around this axis. again, I got 3 very long and complex equations that I couldn't solve.

Anyone has any idea of how to solve it? or can refer me to a link that (hopefully) explains about it? Will appreciate any help!

Thank you
David

$\endgroup$
2
  • $\begingroup$ If you permit rotations about axes not through the origin, I can see how to do it. If the rotations must be about axes through the origin, it might be generically impossible. $\endgroup$ May 5 '17 at 13:15
  • $\begingroup$ The axis needs to pass through the origin (the rotation matrix is 3x3). and if there's no rotation around any axis that passes through the origin that causes the three intersections, then I should mathematically get that there are no solutions for the problem. </br> But, I would very much like to hear the idea you're talking about. $\endgroup$
    – David
    May 5 '17 at 13:39
2
$\begingroup$

As you said, each line can be written, in parametric form, as $$ \left( {\matrix{ x \cr y \cr x \cr } } \right) = \left( {\matrix{ {a_x } \cr {a_y } \cr {a_z } \cr } } \right) + \lambda \left( {\matrix{ {v_x } \cr {v_y } \cr {v_z } \cr } } \right) $$

So we can represent each group of three lines in matricial notation as $$ {\bf X} = \left( {\matrix{ {x_{\,1} } & {x_{\,2} } & {x_{\,3} } \cr {y_{\,1} } & {y_{\,2} } & {y_{\,3} } \cr {z_{\,1} } & {z_{\,2} } & {z_{\,3} } \cr } } \right) = {\bf A} + {\bf V}\;{\bf \Lambda }\quad \quad {\bf X}' = \left( {\matrix{ {x'_{\,1} } & {x'_{\,2} } & {x'_{\,3} } \cr {y'_{\,1} } & {y'_{\,2} } & {y'_{\,3} } \cr {z'_{\,1} } & {z'_{\,2} } & {z'_{\,3} } \cr } } \right) = {\bf A}' + {\bf V}'\;{\bf \Lambda }' $$ where is clear the meaning of the matrices , and in particular that the ${\bf \Lambda }$ and ${\bf \Lambda }'$ matrices are diagonal.

Now if each line of the first group was to intersect the corresponding line in the second group, that means that there are specific values of $\lambda_k$ and ${\lambda '}_j$ such that ${\bf X} ={\bf X}' $, i.e. $$ {\bf A} + {\bf V}\;{\bf \Lambda } = {\bf A}' + {\bf V}'\;{\bf \Lambda }' $$ or $$ \;{\bf \Lambda } = {\bf V}^{\, - \,{\bf 1}} \left( {{\bf A}' - {\bf A}} \right) + {\bf V}^{\, - \,{\bf 1}} {\bf V}'\;{\bf \Lambda }' = diag $$

That translates into a linear system of six equations in the three unknowns $\lambda'$, which then determine the $\lambda$.

If instead each line of the first group was to intercept one line of the 2nd group, different but not necessarily the corresponding one, then we shall have ${\bf X} \, {\bf P} ={\bf X}' $, or v.v, where ${\bf P}$ is one of the $6$ Permutation matrices.

Also, if each line of the first group was to intercept one line of the 2nd group, not necessarily distinct, then we shall have ${\bf X} ={\bf X}' \, {\bf Q} $, where ${\bf Q}$ is one of the $9$ "$0/1$" matrices, having only one $1$ in each column.

Finally, as per your question, we can introduce a Rotation matrix, depending on $3$ angles, which goes to multiply ${\bf X}$ $$ {\bf R}\,\left( {{\bf A} + \,{\bf V}\;{\bf \Lambda }} \right) = \left( {{\bf A}' + {\bf V}'\;{\bf \Lambda }'} \right)\;\left( {{\bf P}\,{\rm or}\;{\bf Q}} \right) $$ to solve by imposing the diagonalization condition as above. i.e. $$ {\bf \Lambda } = {\bf V}^{\, - \,{\bf 1}} \;{\bf R}^{\, - \,{\bf 1}} \;\left( {{\bf A}'{\bf Q} - {\bf R}\,{\bf A}} \right) + {\bf V}^{\, - \,{\bf 1}} \;{\bf R}^{\, - \,{\bf 1}} {\bf V}'\;{\bf \Lambda }'{\bf Q}\; $$ By imposing that the "6" off-diagonal elements of the RHS matrix be null, we get system of $6$ equations in the $3$ unknowns ${\lambda}'$, and in the $3$ rotation angles, for each of the $9$ ${\bf Q}$ matrices we are willing to consider as "crossing conditions".
( let comprise in ${\bf Q}$ also the particular cases of unit and permutation matrices).

Now, the homogeneous system is linear in the ${\lambda}'$ but contains product of $\sin $ and $ \cos$ of the angles, and you are asking for a way to simplify that.

The first way I can see at the moment is that, restarting from the identity $$ {\bf R}\,\left( {{\bf A} + \,{\bf V}\;{\bf \Lambda }} \right) = \left( {{\bf A}' + {\bf V}'\;{\bf \Lambda }'} \right)\;{\bf Q} $$ taking the transposed (indicated by the hat) $$ \left( {\overline {\bf A} + \;{\bf \Lambda }\,\overline {\bf V} } \right){\bf R}^{\, - \,{\bf 1}} = \overline {\bf Q} \left( {\overline {{\bf A}'} + {\bf \Lambda }'\;\overline {{\bf V}'} } \right)\; $$ we can get rid of the rotation, by multiplying the first by the second on the left

$$ \left( {\overline {\bf A} + \;{\bf \Lambda }\,\overline {\bf V} } \right)\left( {{\bf A} + \,{\bf V}\;{\bf \Lambda }} \right) = \overline {\bf Q} \left( {\overline {{\bf A}'} + {\bf \Lambda }'\;\overline {{\bf V}'} } \right)\left( {{\bf A}' + {\bf V}'\;{\bf \Lambda }'} \right)\;{\bf Q} $$ however at the cost of introducing an equation between two quadratic forms, symmetric, so $6$ equations.
Yet this equation has the advantage of not requiring $\bf V$ to be invertible.

At this point might be profitable to express each line with the position vector ($\bf a$) normal to the direction vector ($\bf v$) and to normalize the latter.
That will give that $\overline {\bf A} \, {\bf V}$ has the main diagonal null, while for $\overline {\bf V} \, {\bf V}$ it is unitary.
So we might possibly start from equating the diagonals ...

Sorry for not being this actually an answer, but this is the best help I can offer.

--- P.S. -----

As per your last comment, the case of two groups of incident lines introduces many simplifications with respect to the general case of being all skew, and can be approached quite differently. It is worthy that you open another post. In any case it remains to clarify the intersection scheme (e.g. two lines 1st group could intersect the same line in 2nd group, and the third any one of the remaining?)

$\endgroup$
12
  • $\begingroup$ Thanks @GCab Sorry but I still don't understand how to find the rotation matrix $R$. I will split my comment since it's too long. In the final equation: $$ {\bf R}\,\left( {{\bf A} + \,{\bf V}\;{\bf \Lambda }} \right) = \left( {{\bf A}' + {\bf V}'\;{\bf \Lambda }'} \right)\; $$ You have 9 equations of 9 variables (the variables are the 3 angles of rotations and the 6 coeffients of the lines that cause the intersections). But I really don't see how you can solve it. $\endgroup$
    – David
    May 6 '17 at 14:13
  • $\begingroup$ $R$ itself is actually $R=R_xR_yR_z$ (or whatever order you choose) so eventually $R$ is this matrix: $$ {\bf R=R_xR_yR_z} = \left( {\matrix{ {cos\beta cos\gamma} & {-cos\beta sin\gamma} & {sin\beta} \cr {cos\alpha sin\gamma+sin\alpha sin\beta cos\gamma} & {cos\alpha cos\gamma-sin\alpha sin\beta sin\gamma} & {-sin\alpha cos\beta} \cr {sin\alpha sin\gamma-cos\alpha sin\beta cos\gamma} & {sin\alpha cos\gamma+ cos\alpha sin\beta sin\gamma} & {cos\alpha cos\beta} \cr } } \right) $$ $\endgroup$
    – David
    May 6 '17 at 14:14
  • $\begingroup$ Where $\alpha, \beta, \gamma$ are the unknown angles (that I need to find) around $x,y,z$ axes respectively. I just don't see how you can calculate $\alpha, \beta, \gamma$ when you have so many multiplications between them and it seems impossible to seperate between them and to find their values (and in addition to find the 6 coeffients of the lines). Please tell me if I'm missing something or maybe it's simpler than it seems to be. Thanks $\endgroup$
    – David
    May 6 '17 at 14:14
  • $\begingroup$ @David: ok, seems that I should add a further development to my answer. Meanwhile I prepare that, can you clarify what type of crossing configuration are you mainly interested in (P or Q) ? $\endgroup$
    – G Cab
    May 6 '17 at 14:24
  • $\begingroup$ if I understand your question correctly, in the begining all the 6 lines intersect at a single point [0,0,-R] (meaning, in the negative value of the z axis). and the goal is to rotate the lines in P such that they all intersect the lines in Q most likely in 3 different points (none of them should be [0 0 -R]). Meaning, any rotation matrix that is not the identity matrix and leads to the intersections. Q lines of course never rotate. meaning, Q lines always pass in [0 0 -R]. I didn't think this info is relevant for the question so I didn't write it in the original question. $\endgroup$
    – David
    May 6 '17 at 16:57
0
$\begingroup$

This is not an answer to the question as posed, but rather a rough sketch if the rotations could be about any axis.

Fix the set $P=\{P_1,P_2,P_3\}$ of lines. The set $Q=\{Q_1,Q_2,Q_3\}$ will be moved. Rotate $Q$ about an axis through the origin, with the axis not parallel to the directions of the three $Q$-lines, and not orthogonal to the directions of the three $P$-lines, until $Q_1$ bangs into $P_1$ at point $a$. I believe if the axis is generic enough, $Q_1$ will hit $P_1$. Not sure I have the genericity conditions correct, but some assumptions will work.

Now spin $Q$ about the vector from the origin to $a$ until $Q_2$ bangs into $P_2$ at point $b$. Again I need to assume no accidental degeneracies to ensure the collision. Note the $Q_1 \cap P_1$ intersection is maintained.

Finally, spin $Q$ about the line containing $ab$. This axis is (in general) not through the origin. Barring degeneracies, $Q_3$ will bang into $P_3$, while the $Q_1 \cap P_1$ and $Q_2 \cap P_2$ intersections remain.

$\endgroup$
5
  • $\begingroup$ Thanks! but I'm not sure your solution will work (even for axis that doesn't pass through the origin). You rotate the set $P$ 3 times around 3 different axises that only the last two pass through the point $a$. the first axis is arbitrary (and most likely doesn't pass throgh the point $a$ since in this case $P_1$ and $Q_1$ must already intersect there). if all the 3 axises would pass through the point $a$ you could say that you can rotate $P$ around some axis (none of the 3 axises) that passes through $a$. but in your case, I'm not sure you can say that. $\endgroup$
    – David
    May 5 '17 at 16:21
  • $\begingroup$ @David: I don't understand your comment, but I am not sure I have the time to make an implementation that would clarify. The basic idea is that two skew lines will meet if one is held fixed and the other rotated about a generic axis. Since this doesn't solve your problem anyway, maybe we should just agree to not understand one another. $\endgroup$ May 5 '17 at 17:57
  • $\begingroup$ In your solution, in the final result the 3 pair of lines will indeed intersect each other. But you cannot do it in a single rotation. In order to be able to do it in a single rotation (single axis line and single angle of rotation) all the three rotations that you did need to be around 3 axis lines that pass through the same point (in my case I wanted that point to be the origin. but in your case also it should be the same point otherwise you can't make it in a single rotation). $\endgroup$
    – David
    May 5 '17 at 23:35
  • 2
    $\begingroup$ @David: Correct, my procedure does not result in a single rotation. It results in a single $4 \times 4$ homogenous affine transformation matrix. $\endgroup$ May 6 '17 at 11:46
  • $\begingroup$ didn't know that :) $\endgroup$
    – David
    May 6 '17 at 18:38

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.