Converting between two frames of reference given two points

I have two points ($P_1$ & $P_2$) with their coordinates given in two different frames of reference ($A$ & $B$). Given these, what I'd like to do is derive the transformation to be able to transform any point $P$ ssfrom one to the other.

There is no third point, but there is an extra constraint, which is that the y axis of Frame $B$ is parallel to the $X$-$Y$ plane of Frame $A$ (see sketch below). I believe that is enough information to be able to do the transformation.

Also:

• The points are the same distance apart in both frames (no scaling).
• The points don't coincide.
• The origins don't necessarily coincide.

As you may have gathered, I'm not a mathematician (ultimately this will end up as code), so please be gentle...

I've seen this question (Finding a Rotation Transformation from two Coordinate Frames in 3-Space), but it's not quite the same as my problem, and unfortunately I'm not good enough at math to extrapolate from that case to mine.

EDIT I've updated the diagram, which makes it a bit cluttered, but (I hope) shows all the 'bits': $P3_B$ is what I'm trying to calculate...

-
Do the 2 frames of reference necessarily have the same orientation? (I.e. as you've drawn them they are both right-handed in the sense that if your index finger is pointing like the $x$-axis and your middle finger like the $y$-axis, then your thumb points in the direction of the $z$-axis; is this guaranteed?) – Ben Blum-Smith Sep 16 '11 at 12:38
Also, what do you know about matrices? – Ben Blum-Smith Sep 16 '11 at 12:38
@Ben, yes they're both right-handed. Yes I know about matrices, but if you show me one, I wouldn't be able to tell you if it was rotating, translating, scaling or a combination of the three (though I could look it up...) – Benjol Sep 16 '11 at 12:49
@Ben. I'm in chat for a moment, if you want to quiz me more... – Benjol Sep 16 '11 at 12:52
@Benjol: I don't think you've ever seen a diagram that's ugly as hell, or you wouldn't say that :-) I think yours is pretty neat! – joriki Sep 16 '11 at 16:03

The problem is to find a rotation matrix $R$ and a translation vector $\vec t$ such that

$$R\vec p_{1B}+\vec t=\vec p_{1A}\;,\tag1$$ $$R\vec p_{2B}+\vec t=\vec p_{2A}\;.\tag2$$

Subtracting these yields

$$R\left(\vec p_{1B}-\vec p_{2B}\right)=\vec p_{1A}-\vec p_{2A}\;.\tag3$$

Since the $y$ axis of system $B$ is parallel to the $x$-$y$ plane of system $A$, we can obtain the rotation by first rotating around the $y$ axis and then rotating around the $z$ axis, so $R$ must have the form

$$\begin{pmatrix}\cos\alpha&\sin\alpha\\-\sin\alpha&\cos\alpha\\&&1\end{pmatrix} \begin{pmatrix}\cos\beta&&\sin\beta\\&1&\\-\sin\beta&&\cos\beta\end{pmatrix} = \begin{pmatrix} \cos\alpha\cos\beta&\sin\alpha&\cos\alpha\sin\beta\\ -\sin\alpha\cos\beta&\cos\alpha&-\sin\alpha\sin\beta\\ -\sin\beta&&\cos\beta \end{pmatrix} \;.$$

So the third row depends only on $\beta$, and writing out the corresponding row of $(3)$ yields a trigonometric equation for $\beta$:

$$-\sin\beta(p_{1Bx}-p_{2Bx})+\cos\beta(p_{1Bz}-p_{2Bz})=p_{1Az}-p_{2Az}\;.$$

Since we'll get another equation of the form

$$a\sin\phi+b\cos\phi=c\tag4$$

shortly, I'll solve it in that general form, and you can substitute

$$\begin{eqnarray} a&=&p_{2Bx}-p_{1Bx}\;,\\ b&=&p_{1Bz}-p_{2Bz}\;,\\ c&=&p_{1Az}-p_{2Az} \end{eqnarray}$$

to solve this one. Writing $a$ and $b$ in polar form, $a=r\cos\xi$, $b=r\sin\xi$, leads to

$$r\cos\xi\sin\phi+r\sin\xi\cos\phi=c\;,$$

$$\sin(\xi+\phi)=\frac cr\;.$$

You can get one solution from

$$\phi_1=\arcsin\frac cr-\xi\;,$$

but note that in general there's a second one, $\phi_2=\pi-\phi_1$, which makes sense, since there are in general two different angles through which you can turn a vector around the $y$ axis to give it a certain $z$ component.

You can determine $r$ and $\xi$ using $r=\sqrt{a^2+b^2}$ and $\xi=\text{atan}(b,a)$, where $\text{atan}$ is the two-argument arctangent function found in many programming environments, which takes into account the signs of both arguments to disambiguate the arctangent on the full range of angles.

Now you have two values of $\beta$, and you can substitute them into the rotation matrix. For instance, substituting into the first row of $(3)$ yields

$$\cos\alpha\cos\beta(p_{1Bx}-p_{2Bx})+\sin\alpha(p_{1By}-p_{2By})+\cos\alpha\sin\beta(p_{1Bz}-p_{2Bz})=p_{1Ax}-p_{2Ax}\;,$$

which is again a trigonometric equation for $\alpha$ of the form $(4)$, with

$$\begin{eqnarray} a &=& p_{1By}-p_{2By}\;, \\ b &=& \cos\beta(p_{1Bx}-p_{2Bx})+\sin\beta(p_{1Bz}-p_{2Bz}) \;, \\ c &=& p_{1Ax}-p_{2Ax} \;. \end{eqnarray}$$

You can solve it just like the other one, to obtain two values of $\alpha$ for each of the two values of $\beta$. Again, this makes sense, since we've only used the first row of $(3)$ so far and there are two different angles through which you can turn a vector around the $z$ axis to give it a certain $x$ component. However, only one of each of these two pairs of values of $\alpha$ will also solve the second row of $(3)$ (that is, the other one would produce a wrong $y$ component), so in the end you obtain two sets of solutions for $\alpha$ and $\beta$. You can substitute each of these into either $(1)$ or $(2)$ to get the corresponding value of $\vec t$.

So in general you get two different affine transformations for valid point coordinates, though sometimes, e. g. if $a=b=c=0$ in either trigonometric equation, the solution will be a lot more underdetermined than that, and if you substitute invalid point coordinates (e. g. for points at different distances from each other, or such that $|c|>r$ in either trigonometric equation), there will be no solutions at all.

I wrote the affine transform for transforming from $B$ to $A$ to simplify the calculations, but you can easily obtain the transform in the other direction as

$$\vec p_B=R^T(\vec p_A-\vec t)\;.$$

-
Wow! I've read it twice, and I get the feeling that my brain could be brought to understand, with a bit of head-banging. I'll come back to this after my neurones have cooled down, and maybe ask you a question or two. Pending that, thanks a lot! – Benjol Sep 16 '11 at 18:56
The 'only' thing I don't get is the switch to polar coordinates in the middle: is it just because $a\sin\phi+b\cos\phi=c$ has the right form for manipulating this way, or is it because the third row of $(3)$ is a vector which can be expressed in polar coordinates? – Benjol Sep 19 '11 at 13:20
@Benjol: I saw it mainly as a formal manipulation that allows us to write the sum of a sine and a cosine as a single sinusoidal (which is also why I called it "polar form", not "polar coordinates"). If you like you can view each row of $(3)$ as expressing that the corresponding row vector of $R$ has to lie in a certain plane normal to $\vec p_{1B}-\vec p_{2B}$, and then up to a sign $a$ and $b$ are the $x$ and $z$ components, respectively, of that normal vector -- but I don't see any added value in this interpretation. – joriki Sep 19 '11 at 13:49
thanks for all this! – Benjol Sep 20 '11 at 5:43
@Benjol: You're welcome! – joriki Sep 20 '11 at 6:00

So given two points, an initial frame of reference, and the fact that the 'new y axis', which I will designate $y'$, is in the $xy$ plane, we do not have enough information to determine a unique new frame of reference around the new point. Even if $y'$ were parallel to $y$, we still don't quite have enough information. We need one more constraint, somewhere.

But let's say for a moment that you know both the new and the old frame of reference. By this, I mean that you know the vectors of the three mutually perpendicular basis elements (the vectors along the axes). Then, you are in business. As long as there is no scaling (vectors in the first frame don't get shorter or longer in the second), this is a simple process. I don't know what math you do or don't know, so I'll say it in some sort of general way and if it doesn't make sense to you, I can edit in more.

I assume throughout that the first frame of reference is at the origin (this is not unreasonable, and if we can't keep it then that's okay too). Assume for a moment that the two frames of reference are actually at the origin (i.e. that the second frame is at the origin too, but only for a moment). Then your task is to find the unique matrix transformation that rotates the original basis to the new basis. There are a few ways to do this, but the big idea is to remember that the columns of a matrix take one basis element to another. Good. Call this matrix $T$, so I can refer to it later.

Now find the difference between the two points. If $x_1$ is in the old frame, and $x_2$ is in the new frame, then find the vector $d = x_2 - x_1$. Then any element, given by the vector $v$ in the old frame will be given by the new vector $v' = [T][v] - d$, where I used brackets to emphasize the fact that there is a matrix multiplication.

Does that make any sense?

-
I think I disagree! The OP seems to want an affine transformation whose linear part is orthogonal. The orthogonal group is a 3-dimensional manifold, and the translation has 3 degrees of freedom, so it should take 6 real parameters to fix the transformation. We have 6! (The coordinates of 2 points.) I don't even think we should need the information about the $y$-axis, except perhaps to choose among a finite number of choices. (Intuitively, at most 2, because the orthogonal group is defined by quadratic equations?) – Ben Blum-Smith Sep 16 '11 at 12:27
Eh... I don't understand when you say that the first frame of reference is at the origin. Which origin? It is at its own origin, by definition, surely? (There is no scaling, sorry, I forgot to mention that). – Benjol Sep 16 '11 at 12:28
@Ben: It seems to me that we might have the case where, as it happens, the two points might be the same. Maybe. Then the coordinates tell us absolutely nothing, and we need to pull our information only from the bases. In this case, knowing only 1 basis element of the new reference allows the other two to rotate in infinitely many places. So I don't think that we know. – mixedmath Sep 16 '11 at 12:38
@Benjol: Well, the problem with "line so-and-so is parallel to plane blablabla" is that there are infinitely many lines that are parallel to a plane. If you have one line parallel to a plane, all the other members of the infinite family are obtainable through a rotation about the axis perpendicular to the plane, and translation. – J. M. Sep 16 '11 at 12:54
@mixedmath - the case of the two points being the same will clearly render the problem unsolvable but this doesn't mean it's not solvable when the points aren't the same. 2 distinct points determine a line but if the points become the same there are infinitely many lines. But the problem is solvable if the points are distinct. – Ben Blum-Smith Sep 16 '11 at 13:20

I think that the two points should be enough information even without the additional information about the $y$-axis of the second frame. EDIT: joriki pointed out that this isn't true (see comments). The additional piece of information about the $y$-axis is needed, but then the problem should be solvable.

The transformation you want is affine because it sends lines to lines and its linear part is orthogonal because it preserves distances. This means it will have the form

\begin{align} x' &= a_{11}x+a_{12}y+a_{13}z +b_1\\ y' &= a_{21}x+a_{22}y+a_{23}z +b_2\\ z' &= a_{31}x+a_{32}y+a_{33}z +b_3\\ \end{align}

This form makes it affine. To make sure it is orthogonal the $a$'s are subject to the constraints

\begin{align} &a_{11}^2+a_{21}^2+a_{31}^2=\\ &a_{12}^2+a_{22}^2+a_{32}^2=\\ &a_{13}^2+a_{23}^2+a_{33}^2=1 \end{align}

and

\begin{align} &a_{11}a_{12}+a_{21}a_{22}+a_{31}a_{32}=\\ &a_{11}a_{13}+a_{21}a_{23}+a_{31}a_{33}=\\ &a_{12}a_{13}+a_{22}a_{23}+a_{32}a_{33}=0 \end{align}

EDIT: The fact that the new $y$-axis is parallel to the old $xy$-plane means that $a_{23}=0$.

Right now there are 11 unknown quantities (the $a$'s and $b$'s).

If you plug in one of your points (with both old and new coordinates) to the transformation at the top, you will get 3 equations. If you plug in the other point (both old and new coordinates) you will get 3 more. The constraints on the $a$'s give 6 more equations; there are 12 in all. EDIT: Due to joriki's point, one of these equations will be redundant, but we should still have enough information to solve them. (There may be a small finite number of solutions because the equations in the $a$'s are quadratic.)

Of course, solving this system of equations is its own challenge. A general method is elimination using Grobner bases, which is too elaborate for me to explain quickly. But the problem has many special features that make it seem like a shortcut should be available. I'll look for a shortcut and add it to this answer if I find one.

(P.S. I am taking your question as primarily practical, so not justifying my claims above about the form of the transformation. If you would like some theoretical background let me know and I will either explain briefly if I can or point you to good sources.)

-
As I wrote in a comment under @mixedmath's answer that you probably hadn't had a chance to read yet, this isn't quite right because the distance between the two points has to be the same in both systems, so it doesn't add to the information and we do need the information about the $y$ axes to make up for that. – joriki Sep 16 '11 at 13:07
@ Oh, yes, so you're saying that the 2 points really only give us 5 parameters, so there should be some redundancy in my 12 equations. – Ben Blum-Smith Sep 16 '11 at 13:15
exactly ${}{}{}$ – joriki Sep 16 '11 at 13:16
@Ben, thanks for all this. I think I'll pass on the theoretical background, but the shortcut does interest me :) – Benjol Sep 16 '11 at 13:46

OK, I've been thinking about this (like an engineer, not a mathematician), and here's my (half-baked) take:

I take Frame A, and translate it (TA) such that it's origin is at P1, then rotate it (RA) around Z and Y such that P2 is on the X axis: this gives me a new Frame A'.

I do the same thing with Frame B, translate (TB), and rotate (RB), which gives me Frame B'.

At this point, Frame A' = Frame B', and I have a 'route' from A to B:

$$TA \rightarrow RA \rightarrow -RB \rightarrow -TA$$

It's not the answer, but it's a start. Please tell me if I'm completely up the creek.

-

I have a simplified way of thinking of the problem (imo). Suppose you have a reference frame

$$\mathcal{R} = (r_1,r_2,r_3,o)$$

where $r_1,r_2,r_3$ are the normalized basis vectors and $o$ is the origin. We assume that these are all given in Euclidean space, which I will call world space $\mathcal{W}$. Things are more complicated for more generalized coordinates (eg. spherical coordinates). Suppose we are given a point in world space $p^{(\mathcal{W})}$. For notational convenience I will drop the superscript whenever a vector is in world space. To find $p$ with respect to your reference frame you take the vector from $o$ to $p$ and project it onto the basis vectors.

$$\text{World to Reference Frame: } p \rightarrow p^{(\mathcal{R})} \\ p^{(\mathcal{R})} = [ (p-o) \bullet r_1, \; (p-o) \bullet r_2, \; (p-o) \bullet r_3 ]$$

where $\bullet$ represents the dot product. To convert back to world space we just need to multiply the $p^{(\mathcal{R})}$ coordinates by the basis vectors.

$$\text{Reference Frame to World: } p^{(\mathcal{R})} \rightarrow p \\ p= o + [ (p^{(\mathcal{R})}_1 \cdot r_1, \; p^{(\mathcal{R})}_1 \cdot r_2, \; p^{(\mathcal{R})}_1 \cdot r_3 ]$$

Note the $\cdot$ denotes a scalar-vector multiply. Now to answer your question. Suppose we want to convert a point in one reference frame to another, from say $\mathcal{R}$ and $\mathcal{S}$. We can use $W$ as a middle man. Using the above transformations we go from spaces $\mathcal{R} \rightarrow \mathcal{W} \rightarrow \mathcal{S}$, giving us points $p^{(\mathcal{R})} \rightarrow p \rightarrow p^{(\mathcal{S})}$.

-