9
$\begingroup$

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.

Two frames

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...

  • 0
    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?)2011-09-16
  • 0
    Also, what do you know about matrices?2011-09-16
  • 0
    @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...)2011-09-16
  • 0
    @Ben. I'm in [chat](http://chat.stackexchange.com/rooms/36/mathematics) for a moment, if you want to quiz me more...2011-09-16
  • 0
    +1 By the way, I really like this question, to the point where I'm needing to force myself to disengage from it.2011-09-16
  • 0
    @Ben, OK, take the weekend off :)2011-09-16
  • 0
    @Ben: I know the feeling :-) Hope my answer will help you sleep well tonight...2011-09-16
  • 1
    @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!2011-09-16
  • 0
    @joriki, you're right, it was a bit of hyperbole. I'll tone down the self-deprecation...2011-09-17

5 Answers 5

3

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)\;.$$

  • 0
    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!2011-09-16
  • 0
    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?2011-09-19
  • 1
    @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.2011-09-19
  • 0
    @Benjol: You're welcome!2011-09-20
  • 0
    Just one thing, if my two points *aren't* exactly the same difference in the two frames (floating point etc.), I'm guessing that that means when I start back-substituting, one value of y will just be closer than the other, is that right?2011-09-20
  • 0
    @Benjol: Exactly.2011-09-20
1

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})}$.

0

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?

  • 0
    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?)2011-09-16
  • 0
    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).2011-09-16
  • 0
    @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.2011-09-16
  • 1
    @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.2011-09-16
  • 0
    @Ben Blum-Smith: Your count of parameters isn't quite right because the points have to have the same distance in both systems. If that's not the case, the problem has no solution, and if it is, the distance doesn't add to the information, so we do need the information about the $y$ axis to make up for that missing bit of information.2011-09-16
  • 0
    @mixedmath. Uhm, could you change your letters to correspond to my diagram please? That might help me figure it out...2011-09-16
  • 0
    @joriki, sorry, yes, they *are* the same distance. (I'll update my question).2011-09-16
  • 0
    @mixedmath, thanks. I'll be around for just under an hour, then I'm off (it's afternoon my time!)2011-09-16
  • 1
    @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.2011-09-16
0

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.)

  • 0
    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.2011-09-16
  • 0
    @ 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.2011-09-16
  • 0
    exactly ${}{}{}$2011-09-16
  • 0
    @Ben, thanks for all this. I think I'll pass on the theoretical background, but the shortcut *does* interest me :)2011-09-16
0

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.