Greedy algorithm for Egyptian fractions

2013-12-29T15:09:31Z

80.175.7.191:

In [[geometry]], various '''formalisms''' exist to express a [[rotation (mathematics)|rotation]] in three [[dimension (vector space)|dimensions]] as a mathematical [[transformation (geometry)|transformation]]. In physics, this concept is applied to [[classical mechanics]] where rotational (or angular) [[kinematics]] is the science of [[quantity|quantitative]] description of a purely rotational [[motion (physics)|motion]]. The [[orientation (geometry)|orientation]] of an object at a given instant is described with the same tools, as it is defined as an imaginary rotation from a reference placement in space, rather than an actually observed rotation from a previous placement in space.

According to [[Euler's rotation theorem]] the rotation of a [[rigid body]] (or three-dimensional [[coordinate system]] with the fixed [[origin (mathematics)|origin]]) is described by a single rotation about some axis. Such a rotation may be uniquely described by a minimum of three [[real number|real]] parameters. However, for various reasons, there are several ways to represent it. Many of these representations use more than the necessary minimum of three parameters, although each of them still has only three [[degrees of freedom (mechanics)|degrees of freedom]].

An example where rotation representation is used is in [[computer vision]], where an [[automation|automated]] observer needs to track a target. Let's consider a rigid body, with three [[orthonormal basis|orthogonal unit vectors]] fixed to its body (representing the three axes of the object's local [[Cartesian coordinate system|coordinate system]]). The basic problem is to specify the orientation of these three [[unit vector]]s, and hence the rigid body, with respect to the observer's coordinate system, regarded as a reference placement in space.

==Rotations and motions==
{{main|Motion (geometry)|Rotation (mathematics)}}
Rotation formalisms are focused on proper ([[orientation (vector space)|orientation-preserving]]) motions of the [[Euclidean space]] with [[stabilizer (group theory)|one fixed point]], that a ''rotation'' refers to. Although physical motions with a fixed point are an important case (such as ones described in the [[center-of-mass frame]], or motions of a [[joint (mechanics)|joint]]), this approach creates a knowledge about all motions. Any proper motion of the Euclidean space decomposes to a rotation around the origin and a [[translation (geometry)|translation]]. Whichever the order of their [[function composition|composition]] will be, the "pure" rotation component wouldn't change, uniquely determined by the complete motion.

One can also understand "pure" rotations as [[linear map]]s in a [[vector space]] equipped with Euclidean structure, not as maps of [[point (geometry)|points]] of a corresponding [[affine space]]. In other words, a rotation formalism captures only the rotational part of a motion, that contains three degrees of freedom, and ignores the translational part, that contains another three.

==Formalism alternatives==

===Rotation matrix===
{{Main|Rotation matrix}}

The above mentioned triad of [[unit vector]]s is also called a [[basis (linear algebra)|basis]]. Specifying [[real coordinate space|the coordinates]] (''components'') of vectors of this basis in its current (rotated) position, in terms of the reference (non-rotated) coordinate axes, will completely describe the rotation. The three unit vectors <math>\scriptstyle \hat{\mathbf{u}}</math>, <math>\scriptstyle \hat{\mathbf{v}}</math> and <math>\scriptstyle \hat{\mathbf{w}}</math> which form the rotated basis each consist of 3 coordinates, yielding a total of 9 parameters. These parameters can be written as the elements of a {{gaps|3|×|3}} matrix <math>\scriptstyle \mathbf{A}</math>, called a '''rotation matrix'''. Typically, the coordinates of each of these vectors are arranged along a column of the matrix (however, beware that an alternative definition of rotation matrix exists and is widely used, where the vectors coordinates defined above are arranged by rows<ref>Rotation Matrix, http://mathworld.wolfram.com/RotationMatrix.html</ref>)

:<math>
\mathbf{A} =
\left[ {\begin{array}{ccc}
\hat{\mathbf{u}}_x & \hat{\mathbf{v}}_x & \hat{\mathbf{w}}_x \\
\hat{\mathbf{u}}_y & \hat{\mathbf{v}}_y & \hat{\mathbf{w}}_y \\
\hat{\mathbf{u}}_z & \hat{\mathbf{v}}_z & \hat{\mathbf{w}}_z \\
\end{array}} \right]
</math>

The elements of the rotation matrix are not all independent—as Euler's rotation theorem dictates, the rotation matrix has only three degrees of freedom. The rotation matrix has the following properties:
* ''A'' is a real, [[orthogonal matrix]], hence each of its rows or columns represents a [[unit vector]].
* The [[eigenvalues]] of ''A'' are
::<math>\{1, e^{\pm i\theta} \} = \{1,\ \cos(\theta)+i\sin(\theta),\ \cos(\theta)-i\sin(\theta)\}</math>
:where ''i'' is the standard [[imaginary unit]] with the property ''i''2 = −1
* The [[determinant]] of ''A'' is +1, equivalent to the product of its eigenvalues.
* The [[Trace (linear algebra)|trace]] of ''A'' is <math>\scriptstyle 1 \,+\, 2\cos(\theta)</math>, equivalent to the sum of its eigenvalues.

The angle <math>\scriptstyle \theta</math> which appears in the eigenvalue expression corresponds to the angle of the Euler axis and angle representation. The [[eigenvector]] corresponding with the eigenvalue of 1 is the accompanying Euler axis, since the axis is the only (nonzero) vector which remains unchanged by left-multiplying (rotating) it with the rotation matrix.

The above properties are equivalent to:
:<math>\begin{align}
|\hat{\mathbf u}| = |\hat{\mathbf v}| &= 1\\
\hat{\mathbf u} \cdot \hat{\mathbf v} &= 0\\
\hat{\mathbf u} \times \hat{\mathbf v} &= \hat{\mathbf w}
\end{align}</math>

which is another way of stating that <math>\scriptstyle \hat{\mathbf u},\, \hat{\mathbf v},\, \hat{\mathbf w}</math> form a 3D [[orthonormal basis]]. Note that the statements above constitute a total of 6 conditions (the cross product contains 3), leaving the rotation matrix with just 3 degrees of freedom as required.

Two successive rotations represented by matrices <math>\scriptstyle \mathbf{A}_1</math> and <math>\scriptstyle \mathbf{A}_2</math> are easily combined as follows:
<math>\scriptstyle \mathbf{A}_\text{total} \;=\; \mathbf{A}_2\mathbf{A}_1</math> (Note the order, since the vector being rotated is multiplied from the right).
The ease by which vectors can be rotated using a rotation matrix, as well as the ease of combining successive rotations, make the rotation matrix a very useful and popular way to represent rotations, even though it is less concise than other representations.

===Euler axis and angle (rotation vector)===
[[Image:Euler AxisAngle.png|thumb|right|A visualization of a rotation represented by an Euler axis and angle.]]
{{Main|Axis angle}}
From [[Euler's rotation theorem]] we know that any rotation can be expressed as a single rotation about some axis. The axis is the unit vector (unique except for sign) which remains unchanged by the rotation. The magnitude of the angle is also unique, with its sign being determined by the sign of the rotation axis.

The axis can be represented as a three-dimensional [[unit vector]] <math>\scriptstyle \hat{\mathbf{e}} \;=\; [e_x\ e_y\ e_z]^\mathrm{T}</math>, and the angle by a scalar <math>\scriptstyle \theta</math>.

Since the axis is normalized, it has only two [[Degrees of freedom (mechanics)|degrees of freedom]]. The angle adds the third degree of freedom to this rotation representation.

One may wish to express rotation as a '''rotation vector''', a non-normalized three-dimensional vector the direction of which specifies the axis, and the length of which is <math>\theta</math>:
:<math>v = \theta \hat{\mathbf{e}}</math>

The rotation vector is in some contexts useful, as it represents a three-dimensional rotation with only three [[scalar (mathematics)|scalar]] values (its components), representing the three degrees of freedom. This is also true for representations based on sequences of three Euler angles (see below).

If the rotation angle <math>\scriptstyle \theta</math> is zero, the axis is not uniquely defined. Combining two successive rotations, each represented by an Euler axis and angle, is not straightforward, and in fact does not satisfy the law of vector addition, which shows that finite rotations are not really vectors at all. It is best to employ the rotation matrix or quaternion notation, calculate the product, and then convert back to Euler axis and angle.

===Euler rotations===
[[Image:Praezession.svg|thumb|170px|Euler rotations of the Earth. [[Earth's rotation|Intrinsic]] (green), [[Axial precession|Precession]] (blue) and [[Nutation]] (red)]]
{{Main|Euler angles#Euler rotations}}
The idea behind Euler rotations is to split the complete rotation of the coordinate system into three simpler constitutive rotations, called [[Precession]], [[Nutation]], and [[rotation|intrinsic rotation]], being each one of them an increment on one of the [[Euler angles]]. Notice that the outer matrix will represent a rotation around one of the axes of the reference frame, and the inner matrix represents a rotation around one of the moving frame axis. The middle matrix represent a rotation around an intermediate axis called '''line of nodes'''.

Unfortunately, the definition of Euler angles is not unique and in the literature many different conventions are used. These conventions depend on the axes about which the rotations are carried out, and their sequence (since rotations are not [[commutativity|commutative]]).

The convention being used is usually indicated by specifying the axes about which the consecutive rotations (before being composed) take place, referring to them by index (1, 2, 3) or letter (X, Y, Z). The engineering and robotics communities typically use 3-1-3 Euler angles. Notice that after composing the independent rotations, they do not rotate about their axis anymore. The most external matrix rotates the other two, leaving the second rotation matrix over the line of nodes, and the third one in a frame comoving with the body. There are {{gaps|3|×|3|×|3}} = 27 possible combinations of three basic rotations but only {{gaps|3|×|2|×|2}} = 12 of them can be used for representing arbitrary 3D rotations as Euler angles. These 12 combinations avoid consecutive rotations around the same axis (such as XXY) which would reduce the degrees of freedom that can be represented.

Therefore Euler angles are never expressed in terms of the external frame, or in terms of the co-moving rotated body frame, but in a mixture. Other conventions (e.g., [[rotation matrix]] or [[Quaternions and spatial rotation|quaternions]]) are used to avoid this problem.

===Quaternions===
{{Main|Quaternions and spatial rotation}}

[[Quaternion]]s, that form a four-dimensional [[vector space]], have proven very useful in representing rotations due to several advantages above the other representations mentioned in this article.

A quaternion representation of rotation is written as a [[versor]] (normalized quaternion)
:<math>\hat{\mathbf{q}} = [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math>

In terms of the Euler axis
:<math>\hat{\mathbf{e}} = [e_x\ e_y\ e_z]^\mathrm{T}</math>

and angle
:<math>\theta</math>

this versor's components are expressed as follows:
:<math>\begin{align}
q_1 &= e_x\sin\left(\frac{\theta}{2}\right)\\
q_2 &= e_y\sin\left(\frac{\theta}{2}\right)\\
q_3 &= e_z\sin\left(\frac{\theta}{2}\right)\\
q_4 &= \cos\left(\frac{\theta}{2}\right)
\end{align}</math>

The above definition follows the convention as used in (Wertz 1980) and (Markley 2003). An alternative definition used in some publications defines the "scalar" term as the first quaternion element, with the other elements shifted down one position. (Coutsias 1999), (Schmidt 2001)

Inspection shows that the quaternion parametrization obeys the following constraint:
:<math>q_1^2 + q_2^2 + q_3^2 + q_4^2 = 1</math>

The last term (in our definition) is often called the scalar term, which has its origin in quaternions when understood as the mathematical extension of the complex numbers, written as
:<math>a + b i + c j + d k</math> with <math>\{a, b, c, d\} \in \mathbb{R}</math>

and where <math>\scriptstyle \{i,\, j,\, k\}</math> are the [[hypercomplex number]]s satisfying
:<math>
\begin{array}{lclrlcl}
i^2 &=& j^2 &=& k^2 &=& -1\\
ij &=& -ji &=& k&&\\
jk &=& -kj &=& i&&\\
ki &=& -ik &=& j&&
\end{array}
</math>

Quaternion multiplication, that is used to specify a [[function composition|composite]] rotation, is performed in the same manner as multiplication of [[complex numbers]], except that the order of elements must be taken into account, since multiplication is not commutative. In matrix notation we can write quaternion multiplication as
:<math>
\tilde{\mathbf{q}}\otimes\mathbf{q} =
\left[ {\begin{array}{rrrr}
q_4 & q_3 & -q_2 & q_1\\
-q_3 & q_4 & q_1 & q_2\\
q_2 & -q_1 & q_4 & q_3\\
-q_1 & -q_2 & -q_3 & q_4
\end{array}} \right]
\left[ {\begin{array}{c}
\tilde{q}_1\\
\tilde{q}_2\\
\tilde{q}_3\\
\tilde{q}_4
\end{array}} \right] =
\left[ {\begin{array}{rrrr}
\tilde{q}_4 & -\tilde{q}_3 & \tilde{q}_2 & \tilde{q}_1\\
\tilde{q}_3 & \tilde{q}_4 & -\tilde{q}_1 & \tilde{q}_2\\
-\tilde{q}_2 & \tilde{q}_1 & \tilde{q}_4 & \tilde{q}_3\\
-\tilde{q}_1 & -\tilde{q}_2 & -\tilde{q}_3 & \tilde{q}_4
\end{array}} \right]
\left[ {\begin{array}{c}
q_1\\
q_2\\
q_3\\
q_4
\end{array}} \right]
</math>

Combining two consecutive quaternion rotations is therefore just as simple as using the rotation matrix. Remember that two successive rotation matrices, <math>\scriptstyle \mathbf{A}_1</math> followed by <math>\scriptstyle \mathbf{A}_2</math>, are combined as follows:
:<math>\mathbf{A}_3 = \mathbf{A}_2\mathbf{A}_1</math>

We can represent this with quaternion parameters in a similarly concise way:
:<math>\mathbf{q}_3 = \mathbf{q}_2 \otimes \mathbf{q}_1</math>

Quaternions are a very popular parametrization due to the following properties:
*More compact than the matrix representation and less susceptible to [[round-off error]]s
*The quaternion elements vary continuously over the unit sphere in <math>\scriptstyle \mathbb{R}^4</math>, (denoted by <math>\scriptstyle S^3</math>) as the orientation changes, avoiding [[classification of discontinuities|discontinuous]] jumps (inherent to three-dimensional parameterizations)
*Expression of the rotation matrix in terms of quaternion parameters involves no [[trigonometric function]]s
*It is simple to combine two individual rotations represented as quaternions using a quaternion product

Like rotation matrices, quaternions must sometimes be re-normalized due to rounding errors, to make sure that they correspond to valid rotations. The computational cost of re-normalizing a quaternion, however, is much less than for normalizing a {{gaps|3|×|3}} matrix.

===Rodrigues parameters===
{{main|Euler–Rodrigues parameters}}
{{See also|Rodrigues' rotation formula}}

Rodrigues parameters can be expressed in terms of Euler axis and angle as follows:
:<math>\mathbf{r} = \hat{\mathbf{e}}\theta</math>

This has a discontinuity at 180° (π radians): each vector, '''r''', with a norm of π radians represent the same rotation as −'''r'''.

Similarly, the Gibbs representation can be expressed as follows:
:<math>\mathbf{g} = \hat{\mathbf{e}}\tan\left(\frac{\theta}{2}\right)</math>
A rotation g followed by a rotation f in Gibbs representation has the form
:<math>(\mathbf{g},\mathbf{f}) = \frac{\mathbf{g}+\mathbf{f}-\mathbf{f}\times\mathbf{g}}{1-\mathbf{g}\cdot\mathbf{f}}</math>

The '''Gibbs vector''' has the advantage (or disadvantage, depending on context) that 180° rotations cannot be represented. (Even using [[floating point]] numbers that include infinity, rotation direction cannot be well-defined; for example, naively a 180° rotation about the axis (1, 1, 0) would be <math>\scriptstyle (\infty,\, \infty,\, 0)</math>, which is the same representation as 180° rotation about (1, 0.0001, 0).)

Modified Rodrigues parameters (MRPs) can be expressed in terms of Euler axis and angle by:
:<math>\mathbf{p} = \hat{\mathbf{e}}\tan\left(\frac{\theta}{4}\right)</math>

The modified Rodrigues parameterization shares many characteristics with the rotation vector parametrization, including the occurrence of discontinuous jumps in the parameter space when incrementing the rotation.

===Cayley–Klein parameters===
{{section stub|date=September 2013}}
See definition at [http://mathworld.wolfram.com/Cayley-KleinParameters.html Wolfram Mathworld].

===Higher dimensional analogues===
{{See also|Rotations in 4-dimensional Euclidean space}}

==Conversion formulae between formalisms==

===Rotation matrix ↔ Euler angles===
The Euler angles <math>\scriptstyle (\phi,\, \theta,\, \psi)</math> can be extracted from the rotation matrix <math>\scriptstyle \mathbf{A}</math> by inspecting the rotation matrix in analytical form.

Using the x-convention, the 3-1-3 Euler angles <math>\scriptstyle \phi</math>, <math>\scriptstyle \theta</math> and <math>\scriptstyle \psi</math> (around the <math>\scriptstyle Z</math>, <math>\scriptstyle X</math> and again the <math>\scriptstyle Z</math>-axis) can be obtained as follows:
:<math>
\begin{align}
\phi &= \operatorname{arctan2}(A_{31}, A_{32})\\
\theta &= \arccos(A_{33})\\
\psi &= -\operatorname{arctan2}(A_{13}, A_{23})
\end{align}
</math>

Note that <math>\scriptstyle \operatorname{arctan2}(a,\, b)</math> is equivalent to <math>\scriptstyle \arctan(a/b)</math> where it also takes into account the [[Cartesian coordinate system#Cartesian coordinates in two dimensions|quadrant]] that the point <math>\scriptstyle (a,\, b)</math> is in; see [[atan2]].

When implementing the conversion, one has to take into account several situations:<ref>[http://cmp.felk.cvut.cz/cmp/courses/ROB/roblec/serial-noteeng.pdf Direct and inverse kinematics] lecture notes, page 5</ref>
* There are generally two solutions in (−π, π]3 interval. The above formula works only when <math>\theta </math> is from the interval [0, π)3.
* For special case <math>\scriptstyle A_{33} \;=\; 0</math>, <math>\scriptstyle \phi,\, \psi</math> shall be derived from <math>\scriptstyle A_{11},\, A_{12}</math>.
* There is infinitely many but countably many solutions outside of interval (−π, π]3.
* Whether all mathematical solutions apply for given application depends on the situation.

The rotation matrix <math>\scriptstyle \mathbf{A}</math> is generated from the Euler angles by multiplying the three matrices generated by rotations about the axes.
:<math>\mathbf{A} = \mathbf{A}_3\mathbf{A}_2\mathbf{A}_1 = \mathbf{A}_Z\mathbf{A}_Y\mathbf{A}_X</math>

The axes of the rotation depend on the specific convention being used. For the ''x''-convention the rotations are about the <math>\scriptstyle X</math>, <math>\scriptstyle Y</math> and <math>\scriptstyle Z</math> axes with angles <math>\scriptstyle \phi</math>, <math>\scriptstyle \theta</math> and <math>\scriptstyle \psi</math>, the individual matrices are as follows:
:<math>\begin{align}
\mathbf{A}_X &= \left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & \cos\phi & \sin\phi\\ 0 & -\sin\phi & \cos\phi \end{array} \right]\\
\mathbf{A}_Y &= \left[\begin{array}{ccc} \cos\theta & 0 & -\sin\theta\\ 0 & 1 & 0\\ \sin\theta & 0 & \cos\theta \end{array} \right]\\
\mathbf{A}_Z &= \left[\begin{array}{ccc} \cos\psi & \sin\psi & 0\\ -\sin\psi & \cos\psi & 0\\ 0 & 0 & 1 \end{array} \right]
\end{align}</math>

This yields
:<math>\begin{array}{lcl}
\mathbf{A} &=& \begin{bmatrix}
\cos\theta \cos\psi & \cos\phi \sin\psi + \sin\phi \sin\theta \cos\psi & \sin\phi \sin\psi - \cos\phi \sin\theta \cos\psi \\
-\cos\theta \sin\psi & \cos\phi \cos\psi - \sin\phi \sin\theta \sin\psi & \sin\phi \cos\psi + \cos\phi \sin\theta \sin\psi \\
\sin\theta & -\sin\phi \cos\theta & \cos\phi \cos\theta \\
\end{bmatrix}
\end{array}</math>
Note: This is valid for a right-hand system, which is the convention used in almost all engineering and physics disciplines.

===Rotation matrix ↔ Euler axis/angle===
{{merge section from|Rotation matrix#Conversion from and to axis-angle|date=September 2013}}
If the Euler angle <math>\scriptstyle \theta</math> is not a multiple of <math>\scriptstyle \pi</math>, the Euler axis <math>\scriptstyle \hat{\mathbf{e}} \;=\; [e_1\ e_2\ e_3]^\mathrm{T}</math> and angle <math>\scriptstyle \theta</math> can be computed from the elements of the rotation matrix <math>\scriptstyle \mathbf{A}</math> as follows:
:<math>
\begin{align}
\theta &= \arccos\left(\frac{1}{2}[A_{11}+A_{22}+A_{33}-1]\right)\\
e_1 &= \frac{A_{32}-A_{23}}{2\sin\theta}\\
e_2 &= \frac{A_{13}-A_{31}}{2\sin\theta}\\
e_3 &= \frac{A_{21}-A_{12}}{2\sin\theta}
\end{align}
</math>

Alternatively, the following method can be used:

Eigen-decomposition of the rotation matrix yields the eigenvalues 1, and <math>\scriptstyle \cos\theta \pm i\sin\theta</math>.
The Euler axis is the eigenvector corresponding to the eigenvalue of 1, and the <math>\scriptstyle \theta</math> can be computed from the remaining eigenvalues.

The Euler axis can be also found using Singular Value Decomposition since it is the normalized vector spanning the null-space of the matrix <math>\scriptstyle I \,-\, A</math>.

To convert the other way the rotation matrix corresponding to an Euler axis <math>\scriptstyle \hat{\mathbf{e}} \;=\; [e_1\ e_2\ e_3]^\mathrm{T}</math> and angle <math>\scriptstyle \theta</math> can be computed according to the [[Rodrigues' rotation formula]] (with appropriate modification) as follows:
:<math>\mathbf{A} = \mathbf{I}_3\cos\theta + (1-\cos\theta)\hat{\mathbf{e}}\hat{\mathbf{e}}^\mathrm{T} + [\hat{\mathbf{e}}]_{\times} \sin\theta</math>

with <math>\scriptstyle \mathbf{I}_3</math> the {{gaps|3|×|3}} [[identity matrix]], and
:<math>[\hat{\mathbf{e}}]_{\times} = \left[\begin{array}{ccc} 0 & -e_3 & e_2\\ e_3 & 0 & -e_1\\ -e_2 & e_1 & 0 \end{array} \right]</math>

is the [[Cross product#Conversion to matrix multiplication|cross-product matrix]].

===Rotation matrix ↔ quaternion===
When computing a quaternion from the rotation matrix there is a sign ambiguity, since <math>\scriptstyle \mathbf{q}</math> and <math>\scriptstyle -\mathbf{q}</math> represent the same rotation.

One way of computing the quaternion <math>\scriptstyle \mathbf{q} \;=\; [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math> from the rotation matrix <math>\scriptstyle \mathbf{A}</math> is as follows:
:<math>
\begin{align}
q_4 &= \frac{1}{2}\sqrt{1+A_{11}+A_{22}+A_{33}}\\
q_1 &= \frac{1}{4q_4}(A_{32}- A_{23})\\
q_2 &= \frac{1}{4q_4}(A_{13}- A_{31})\\
q_3 &= \frac{1}{4q_4}(A_{21}- A_{12})
\end{align}
</math>

There are three other mathematically equivalent ways to compute <math>\scriptstyle \mathbf{q}</math>. Numerical inaccuracy can be reduced by avoiding situations in which the denominator is close to zero. One of the other three methods looks as follows:<ref>{{cite arxiv|last = Mebius|first = Johan|arxiv = math/0701759|title = Derivation of the Euler–Rodrigues formula for three-dimensional rotations from the general formula for four-dimensional rotations| year = 2007}}</ref>
:<math>
\begin{align}
q_1 &= \frac{1}{2}\sqrt{1 + A_{11} - A_{22} - A_{33}}\\
q_2 &= \frac{1}{4q_1}(A_{12} + A_{21})\\
q_3 &= \frac{1}{4q_1}(A_{13} + A_{31})\\
q_4 &= \frac{1}{4q_1}(A_{32} - A_{23})
\end{align}
</math>

The rotation matrix corresponding to the quaternion <math>\scriptstyle \mathbf{q} \;=\; [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math> can be computed as follows:
:<math>\mathbf{A} = (q_4^2 - \check{\mathbf{q}}^\mathrm{T}\check{\mathbf{q}})\mathbf{I}_3 + 2\check{\mathbf{q}}\check{\mathbf{q}}^\mathrm{T} + 2q_4\mathbf{\mathcal{Q}}</math>

with <math>\scriptstyle \mathbf{I}_3</math> the {{gaps|3|×|3}} identity matrix, and
:<math>\check{\mathbf{q}} = \left[\begin{array}{c} q_1\\q_2\\q_3\end{array} \right],\ \ \ \mathbf{\mathcal{Q}} = \left[\begin{array}{ccc} 0 & -q_3 & q_2\\ q_3 & 0 & -q_1\\ -q_2 & q_1 & 0 \end{array} \right]</math>

which gives
:<math>\mathbf{A} = \left[\begin{array}{ccc}
1 - 2q_2^2 - 2q_3^2 & 2(q_1q_2 - q_3q_4) & 2(q_1q_3 + q_2q_4)\\
2(q_1q_2 + q_3q_4) & 1 - 2q_1^2- 2 q_3^2 & 2(q_2q_3 - q_1q_4)\\
2(q_1q_3 - q_2q_4) & 2(q_1q_4 + q_2q_3) & 1 - 2q_1^2 - 2q_2^2
\end{array} \right]</math>

or equivalently
:<math>\mathbf{A} = \left[\begin{array}{ccc}
-1 + 2q_1^2 + 2q_4^2 & 2(q_1q_2 - q_3q_4) & 2(q_1q_3 + q_2q_4)\\
2(q_1q_2 + q_3q_4) & -1 + 2q_2^2 + 2q_4^2 & 2(q_2q_3 - q_1q_4)\\
2(q_1q_3 - q_2q_4) & 2(q_1q_4 + q_2q_3) & -1 + 2q_3^2 + 2q_4^2
\end{array} \right]</math>

===Euler angles ↔ quaternion===
{{main|Conversion between quaternions and Euler angles}}
We will consider the x-convention 3-1-3 Euler Angles for the following algorithm. The terms of the algorithm depend on the convention used.

We can compute the quaternion <math>\scriptstyle \mathbf{q} = [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math> from the Euler angles <math>\scriptstyle (\phi,\, \theta,\, \psi)</math> as follows:

:<math>
\begin{align}
q_1 &= \cos\left(\frac{\phi - \psi}{2}\right)\sin\left(\frac{\theta}{2}\right)\\
q_2 &= \sin\left(\frac{\phi - \psi}{2}\right)\sin\left(\frac{\theta}{2}\right)\\
q_3 &= \sin\left(\frac{\phi + \psi}{2}\right)\cos\left(\frac{\theta}{2}\right)\\
q_4 &= \cos\left(\frac{\phi + \psi}{2}\right)\cos\left(\frac{\theta}{2}\right)
\end{align}
</math>

Given the rotation quaternion <math>\scriptstyle \mathbf{q} = [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math>, the x-convention 3-1-3 Euler angles <math>\scriptstyle (\phi,\, \theta,\, \psi)</math> can be computed by

:<math>
\begin{align}
\phi &= \arctan2((q_1q_3 + q_2q_4), -(q_2q_3 - q_1q_4))\\
\theta &= \arccos(-q_1^2 - q_2^2 + q_3^2+q_4^2)\\
\psi &= \arctan2((q_1q_3 - q_2q_4), (q_2q_3 + q_1q_4))
\end{align}
</math>

===Euler axis/angle ↔ quaternion===
Given the Euler axis <math>\scriptstyle \hat{\mathbf{e}}</math> and angle <math>\scriptstyle \theta</math>, the quaternion
:<math>\mathbf{q} = [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math>

can be computed by
:<math>
\begin{align}
q_1 &= \hat{e}_1\sin\left(\frac{\theta}{2}\right) \\
q_2 &= \hat{e}_2\sin\left(\frac{\theta}{2}\right) \\
q_3 &= \hat{e}_3\sin\left(\frac{\theta}{2}\right) \\
q_4 &= \cos\left(\frac{\theta}{2}\right)
\end{align}
</math>

Given the rotation quaternion <math>\scriptstyle \mathbf{q} \;=\; [q_1\ q_2\ q_3\ q_4]^\mathrm{T}</math>, define <math>\scriptstyle \check{\mathbf{q}} \;=\; [q_1\ q_2\ q_3]^\mathrm{T}</math>. Then the Euler axis <math>\scriptstyle \hat{\mathbf{e}}</math> and angle <math>\scriptstyle \theta</math> can be computed by
:<math>
\begin{align}
\hat{\mathbf{e}} &= \frac{\check{\mathbf{q}}}{\|\check{\mathbf{q}}\|} \\
\theta &= 2\arccos(q_4)
\end{align}
</math>

==Conversion formulae for derivatives==

===Rotation matrix ↔ angular velocities===
The angular velocity vector <math>\scriptstyle \mathbf{\omega} \;=\; (\omega_x,\, \omega_y,\, \omega_z)</math> can be extracted from the derivative of the rotation matrix <math>\scriptstyle \frac{d\mathbf{A}}{dt}</math> by the following relation:
:<math>[\mathbf{\omega}]_\times = \left[\begin{array}{ccc} 0 & -\omega_z & \omega_y \\ \omega_z & 0 & -\omega_x \\ -\omega_y & \omega_x & 0 \end{array} \right] = \frac{d\mathbf{A}}{dt}\mathbf{A}^\mathrm{T}</math>

The derivation is adapted from <ref>[http://www.euclideanspace.com/physics/kinematics/angularvelocity/mark.htm] Physics - Mark Ioffe - W(t) in terms of matrices</ref> as follows:

For any vector <math>\scriptstyle r_0</math> consider <math>\scriptstyle r(t) \;=\; \mathbf{A}(t) r_0</math> and differentiate it:
:<math>\frac{dr}{dt} = \frac{d\mathbf{A}}{dt} r_0 = \frac{d\mathbf{A}}{dt} \mathbf{A}^\mathrm{T}(t) r(t)</math>

The derivative of a vector is the [[Velocity vector|linear velocity]] of its tip. Since ''A'' is a rotation matrix, by definition the length of <math>\scriptstyle r(t)</math> is always equal to the length of <math>\scriptstyle r_0</math>, and hence it does not change with time. Thus, when <math>\scriptstyle r(t)</math> rotates, its tip moves along a circle, and the linear velocity of its tip is tangential to the circle; i.e., always perpendicular to <math>\scriptstyle r(t)</math>. In this specific case, the relationship between the linear velocity vector and the angular velocity vector is
:<math>\frac{dr}{dt} = \mathbf{\omega}(t)\times r(t) = [\mathbf{\omega}]_\times r(t)</math> (see [[circular motion]] and [[Cross product#Conversion to matrix multiplication|Cross product]]).

By the [[transitive relation|transitivity]] of the above mentioned equations,
:<math>\frac{d\mathbf{A}}{dt} \mathbf{A}^\mathrm{T}(t) r(t) = [\mathbf{\omega}]_\times r(t)</math>

which implies ([[Q.E.D.]]),
:<math>\frac{d\mathbf{A}}{dt} \mathbf{A}^\mathrm{T}(t) = [\mathbf{\omega}]_\times</math>

===Quaternion ↔ angular velocities===
The angular velocity vector <math>\scriptstyle \mathbf{\omega} \;=\; (\omega_x,\, \omega_y,\, \omega_z)</math> can be obtained from the derivative of the quaternion <math>\scriptstyle \frac{d\mathbf{q}}{dt}</math> as follows:<ref>[http://www.euclideanspace.com/physics/kinematics/angularvelocity/] Physics - Kinematics - Angular Velocity</ref>
:<math> \left[ {\begin{array}{c}
0 \\
\omega_x \\
\omega_y \\
\omega_z
\end{array}} \right] = 2 \frac{d\mathbf{q}}{dt} \otimes \tilde{\mathbf{q}}
</math>
where <math> \tilde{\mathbf{q}} </math> is the inverse of <math> \mathbf{q} </math>.

Conversely, the derivative of the quaternion is
:<math> \frac{d\mathbf{q}}{dt} = \frac{1}{2}\left[ {\begin{array}{c}
0 \\
\omega_x\\
\omega_y\\
\omega_z
\end{array}} \right] \otimes \mathbf{q}
</math>

==Rotors in a geometric algebra==
{{merge section to|Geometric algebra#Rotations|date=September 2013}}
The formalism of [[geometric algebra]] (GA) provides an extension and interpretation of the quaternion method. Central to GA is the geometric product of vectors, an extension of the traditional [[inner product|inner]] and [[cross product]]s, given by
:<math>ab = a \cdot b + a \wedge b</math>

where the symbol <math>\scriptstyle \wedge</math> denotes the [[outer product]]. This product of vectors <math>\scriptstyle a,\, b</math> produces two terms: a scalar part from the inner product and a [[bivector]] part from the outer product. This bivector describes the plane perpendicular to what the cross product of the vectors would return.

Bivectors in GA have some unusual properties compared to vectors. Under the geometric product, bivectors have negative square: the bivector <math>\scriptstyle \hat x \hat y</math> describes the <math>\scriptstyle xy</math>-plane. Its square is <math>\scriptstyle (\hat x \hat y)^2 \;=\; \hat x \hat y \hat x \hat y</math>. Because the unit basis vectors are orthogonal to each other, the geometric product reduces to the antisymmetric outer product – <math>\scriptstyle \hat x</math> and <math>\scriptstyle \hat y</math> can be swapped freely at the cost of a factor of −1. The square reduces to <math>\scriptstyle -\hat x \hat x \hat y \hat y \;=\; -1</math> since the basis vectors themselves square to +1.

This result holds generally for all bivectors, and as a result the bivector plays a role similar to the [[imaginary unit]]. Geometric algebra uses bivectors in its analogue to the quaternion, the ''rotor,'' given by <math>\scriptstyle R \;=\; \exp\left(\frac{-\hat B\theta}{2}\right) \;=\; \cos \frac{\theta}{2} \,-\, \hat B \sin \frac{\theta}{2}</math>, where <math> \scriptstyle \hat B</math> is a unit bivector that describes the [[plane of rotation]]. Because <math> \scriptstyle \hat B</math> squares to −1, the [[power series]] expansion of <math>\scriptstyle R</math> generates the [[trigonometric function]]s. The rotation formula that maps a vector <math>\scriptstyle a</math> to a rotated vector <math>\scriptstyle b </math> is then
:<math>b = R a R^\dagger</math>

where <math>\scriptstyle R^\dagger \;=\; \exp\left(\frac{1}{2}\hat B \theta\right) \;=\; \cos \frac{1}{2}\theta \,+\, \hat B \sin \frac{1}{2}\theta</math> is the ''reverse'' of <math>\scriptstyle R</math> (reversing the order of the vectors in <math>\scriptstyle B</math> is equivalent to changing its sign).

'''Example.''' A rotation about the axis <math>\scriptstyle \hat v \;=\; \frac{1}{\sqrt{3}}(\hat x \,+\, \hat y \,+\, \hat z)</math> can be accomplished by converting <math>\scriptstyle \hat v</math> to its dual bivector, <math>\scriptstyle \hat B \;=\; \hat x \hat y \hat z \hat v \;=\; i \hat v</math>, where <math>\scriptstyle i \;=\; \hat x \hat y \hat z</math> is the unit volume element, the only trivector (pseudoscalar) in three-dimensional space. The result is <math>\scriptstyle \hat B \;=\; \frac{1}{\sqrt{3}}(\hat y \hat z \,+\, \hat z \hat x \,+\, \hat x \hat y)</math>. In three-dimensional space, however, it is often simpler to leave the expression for <math>\scriptstyle \hat B \;=\; i \hat v</math>, using the fact that <math>\scriptstyle i</math> commutes with all objects in 3D and also squares to −1. A rotation of the <math>\scriptstyle \hat x</math> vector in this plane by an angle <math>\scriptstyle \theta</math> is then

:<math>\hat x' = R \hat x R^\dagger = e^{-i\hat v \frac{\theta}{2}} \hat x e^{i \hat v \frac{\theta}{2}} = \hat x \cos^2 \frac{\theta}{2} + i (\hat x \hat v - \hat v \hat x) \cos \frac{\theta}{2} \sin \frac{\theta}{2} + \hat v \hat x \hat v \sin^2 \frac{\theta}{2}</math>

Recognizing that <math>\scriptstyle i (\hat x \hat v \,-\, \hat v \hat x) \;=\; 2i (\hat x \,\wedge\, \hat v)</math> and that <math>\scriptstyle -\hat v \hat x \hat v</math> is the reflection of <math>\scriptstyle \hat x</math> about the plane perpendicular to <math>\scriptstyle \hat v</math> gives a geometric interpretation to the rotation operation: the rotation preserves the components that are parallel to <math>\scriptstyle \hat v</math> and changes only those that are perpendicular. The terms are then computed:
:<math>\begin{align}
\hat v \hat x \hat v &= \frac{1}{3} (-\hat x + 2 \hat y + 2 \hat z) \\
2i \hat x \wedge \hat v &= 2i \frac{1}{\sqrt{3}} (\hat x \hat y + \hat x \hat z) = \frac{2}{\sqrt{3}} (\hat y - \hat z)
\end{align}</math>

The result of the rotation is then
:<math>\hat x' = \hat x \left(\cos^2 \frac{\theta}{2} - \frac{1}{3} \sin^2 \frac{\theta}{2}\right) + \frac{2}{3} \hat y \sin \frac{\theta}{2} \left(\sin \frac{\theta}{2} + \sqrt{3} \cos \frac{\theta}{2}\right) + \frac{2}{3} \hat z \sin \frac{\theta}{2} \left(\sin \frac{\theta}{2} - \sqrt{3} \cos \frac{\theta}{2}\right) </math>

A simple check on this result is the angle <math>\scriptstyle \theta \;=\; \frac{2}{3}\pi</math>. Such a rotation should map the <math>\scriptstyle \hat x</math> to <math>\scriptstyle \hat y</math>. Indeed, the rotation reduces to
:<math>\begin{align}
\hat x' &= \hat x\left(\frac{1}{4} - \frac{1}{3} \frac{3}{4}\right) + \frac{2}{3} \hat y \frac{\sqrt{3}}{2} \left(\frac{\sqrt{3}}{2} + \sqrt{3}\frac{1}{2}\right) + \frac{2}{3} \hat z \frac{\sqrt{3}}{2} \left(\frac{\sqrt{3}}{2} - \sqrt{3}\frac{1}{2}\right) \\
&= 0 \hat x + \hat y + 0 \hat z = \hat y
\end{align}</math>

exactly as expected. This rotation formula is valid not only for vectors but for any [[multivector]]. In addition, when Euler angles are used, the complexity of the operation is much reduced. Compounded rotations come from multiplying the rotors, so the total rotor from Euler angles is
:<math>R = R_{\gamma'} R_{\beta'} R_\alpha = \exp\left(\frac{-i \hat z' \gamma}{2}\right) \exp\left(\frac{-i \hat x' \beta}{2}\right) \exp\left(\frac{-i \hat z \alpha}{2}\right)</math>

but <math>\scriptstyle \hat x' \;=\; R_\alpha \hat x R_\alpha^\dagger</math> and <math>\scriptstyle \hat z' \;=\; R_{\beta'} \hat z R_{\beta'}^\dagger</math>. These rotors come back out of the exponentials like so:
:<math>R_{\beta'} = \cos \frac{\beta}{2} - i R_\alpha \hat x R_\alpha^\dagger \sin \frac{\beta}{2} = R_\alpha R_\beta R_\alpha^\dagger</math>

where <math>\scriptstyle R_\beta</math> refers to rotation in the original coordinates. Similarly for the <math>\scriptstyle \gamma</math> rotation, <math>\scriptstyle R_{\gamma'} \;=\; R_{\beta'} R_\gamma R_{\beta'}^\dagger \;=\; R_\alpha R_\beta R_\alpha^\dagger R_\gamma R_\alpha R_\beta^\dagger R_\alpha^\dagger</math>. Noting that <math>\scriptstyle R_\gamma</math> and <math>\scriptstyle R_\alpha</math> commute (rotations in the same plane must commute), and the total rotor becomes
:<math>R = R_\alpha R_\beta R_\gamma</math>

Thus, the compounded rotations of Euler angles become a series of equivalent rotations in the original fixed frame.

While rotors in geometric algebra work almost identically to quaternions in three dimensions, the power of this formalism is its generality: this method is appropriate and valid in spaces with any number of dimensions. In 3D, rotations have three degrees of freedom, a degree for each linearly independent plane (bivector) the rotation can take place in. It has been known that pairs of quaternions can be used to generate rotations in 4D, yielding six degrees of freedom, and the geometric algebra approach verifies this result: in 4D, there are six linearly independent bivectors that can be used as the generators of rotations.

==See also==
*[[Charts on SO(3)]]
*[[Euler filter]]
*[[Orientation (geometry)]]
*[[Rotation around a fixed axis]]
*[[Rotation (mathematics)]]
*[[Rotation operator (vector space)]]

==References==
{{Reflist}}
*Evangelos A. Coutsias and Louis Romero, (1999) ''The Quaternions with an application to Rigid Body Dynamics'', Department of Mathematics and Statistics, [[University of New Mexico]].
*F. Landis Markley, (2003) ''Attitude Error Representations for Kalman Filtering'', Journal of Guidance, Control and Dynamics.
*H. Goldstein, (1980) ''Classical Mechanics'', 2nd. ed., Addison–Wesley. ISBN 0-201-02918-9
*James R. Wertz, (1980) ''Spacecraft Attitude Determination and Control'', [[D. Reidel]] Publishing Company. ISBN 90-277-1204-2
*J. Schmidt and H. Niemann, (2001) ''Using Quaternions for Parametrizing 3-D Rotations in Unconstrained Nonlinear Optimization'', Vision, Modeling and Visualization (VMV01).
*Lev D. Landau and E. M. Lifshitz, (1976) ''Mechanics'', 3rd. ed., [[Pergamon Press]]. ISBN 0-08-021022-8 (hardcover) and ISBN 0-08-029141-4 (softcover).
*Klumpp, A. R., ''Singularity-Free Extraction of a Quaternion from a Direction-Cosine Matrix'', Journal of Spacecraft and Rockets, vol. 13, Dec. 1976, p. 754, 755.
*C. Doran and A. Lasenby, (2003) ''Geometric Algebra for Physicists'', Cambridge University Press. ISBN 978-0-521-71595-9

==External links==
*[http://www.euclideanspace.com/maths/geometry/rotations/index.htm EuclideanSpace] has a wealth of information on rotation representation
* [http://www.j3d.org/matrix_faq/matrfaq_latest.html#Q36 Q36. How do I generate a rotation matrix from Euler angles?] and [http://www.j3d.org/matrix_faq/matrfaq_latest.html#Q37 Q37. How do I convert a rotation matrix to Euler angles?] — The Matrix and Quaternions FAQ
* [http://www.mrao.cam.ac.uk/~clifford/introduction/intro/node9.html#SECTION00030000000000000000 Imaginary numbers are not Real – the Geometric Algebra of Spacetime] – Section "Rotations and Geometric Algebra" derives and applies the rotor description of rotations
* [http://www.starlino.com/dcm_tutorial.html Starlino's DCM Tutorial] – Direction cosine matrix theory tutorial and applications. Space orientation estimation algorithm using accelerometer, gyroscope and magnetometer IMU devices. Using complimentary filter (popular alternative to Kalman filter) with DCM matrix.

{{DEFAULTSORT:Rotation Representation (Mathematics)}}
[[Category:Rotation]]
[[Category:Orientation]]
[[Category:Rotation in three dimensions| ]]
[[Category:Euclidean symmetries]]

formulasearchengine - User contributions [en]

Greedy algorithm for Egyptian fractions