User:Snietfeld

ToDo List

• Splay tree remove - DONE
• Towels
• Lost Lake, NM
• Attitude Dynamics and Control
  • Include Magnetometer in Sensors section
  • Create page on Magnetic Torquers?
• Gyroscopic Phase Advancement
• Burnet, Tx
• NSROC
• /TRIAD Algorithm

TRIAD Algorithm

The TRIAD algorithm is a well-known method for generating a rotation matrix between two frames of reference using two reference vectors common to both frames. It is perhaps most commonly used for generating an attitude solution for satellites and suborbital payloads. In this context, sources of reference vectors may include:

• Solar sensors
• Magnetometers
• Horizon sensors
• Star Trackers

Knowing a single reference vector in both frames is not enough to generate a full attitude solution, and in general generates a cone solution, with the reference vector serving as the axis of the cone. A three-axis magnetometer, for example, will not provide a full attitude solution, and a supplementary source of attitude information is needed.

The TRIAD algorithm works by using the two reference vectors to create a third reference frame that can be related to from each frame independently. This reference frame is common to both frames because the orientation of the reference vectors relative to each other is expected to be the same regardless of what frame they are being observed in.

The goal is to find a rotation matrix $R_{ip}$ that can be used to rotate an arbitrary vector between two reference frames $i$ and $p$. For both reference frames $i$ and $p$ we will generate rotation matrice ($R_{ic}$ and $R_{pc}$, respectively) that perform a coordinate transformation from each reference frame into a third common reference frame $c$.

1. Of the two reference vectors, choose the one expected to be more accurate as v1. Take the remaining reference vector as v2. Normalize both vectors.
2. For the first frame, create a rotation matrix to the common reference frame
   1. Take v1_i as the first vector.
   2. Take the cross product of the two reference vectors and normalize. This gives us our second vector. ${\frac {{\hat {v}}1_{i}\times {\hat {v}}2_{i}}{\left|{\hat {v}}1_{i}\times {\hat {v}}2_{i}\right|}}$
   3. Take the norm of the cross product of the first two vectors to complete the triad. $c_{3}$

Operations

Splaying

When a node x is accessed, a splay operation is performed on x to move it to the root. To perform a splay operation we carry out a sequence of splay steps, each of which moves x closer to the root. By performing a splay operation on the node of interest after every access, the recently accessed nodes are kept near the root and the tree remains roughly balanced, so that we achieve the desired amortized time bounds.

Each particular step depends on three factors:

• Whether x is the left or right child of its parent node, p,
• whether p is the root or not, and if not
• whether p is the left or right child of its parent, g (the grandparent of x).

The three types of splay steps are:

Zig Step: This step is done when p is the root. The tree is rotated on the edge between x and p. Zig steps exist to deal with the parity issue and will be done only as the last step in a splay operation and only when x has odd depth at the beginning of the operation.

Zig-zig Step: This step is done when p is not the root and x and p are either both right children or are both left children. The picture below shows the case where x and p are both left children. The tree is rotated on the edge joining p with its parent g, then rotated on the edge joining x with p. Note that zig-zig steps are the only thing that differentiate splay trees from the rotate to root method introduced by Allen and Munro prior to the introduction of splay trees.

Zig-zag Step: This step is done when p is not the root and x is a right child and p is a left child or vice versa. The tree is rotated on the edge between x and p, then rotated on the edge between x and its new parent g.

Insertion

The process of inserting a node into a splay tree is identical to inserting a node into a binary tree.

Deletion

The deletion operation for splay trees is somewhat different than for binary or AVL trees. To delete an arbitrary node x from a splay tree, the following steps can be followed:

1. Splay node x, sending it to the root of the tree.

2. Perform a right tree rotation on the first left child of x until the first left child of x has no right children.

3. Delete x from the tree & replace the root with the first left child of x.