Compose Transformations

You’re composing several 2D transformations by multiplying their matrices into a single combined matrix. The key ideas are: (1) each geometric transform (rotation, translation, scaling, etc.) can be written as a matrix (usually in homogeneous coordinates), and (2) applying multiple transforms in sequence is equivalent to multiplying their matrices in the correct order.

---

1. Background Knowledge

In 2D computer vision and graphics, points are often represented in homogeneous coordinates as 3D vectors $[x, y, 1]^T$. This allows all common transforms—translation, rotation, scaling, shear—to be represented as $3 \times 3$ matrices. A transformation $T$ maps a point $p$ to $p' = T \cdot p$.

When you apply multiple transformations in sequence, say first $T_1$, then $T_2$, then $T_3$ to a point $p$, the result is:

$$p' = T_3 \cdot (T_2 \cdot (T_1 \cdot p)) = (T_3 \cdot T_2 \cdot T_1) \cdot p.$$

So you can precompute a combined transformation matrix T_{\text{combined}} = T_n \cdot \dots \cdot T_2 \cdot T_1, and then apply it once to all points. The important detail is that matrix multiplication is not commutative: $T_2 T_1 \neq T_1 T_2$ in general, so order matters.

---

2. Algorithm / General Approach

The general pattern for these problems:

1. Start from an identity matrix representing “do nothing”.
2. Iterate over the given transforms in the order they are applied (right-to-left in terms of application to points).
3. Multiply matrices to accumulate into a single combined matrix.
4. Use the combined matrix for any subsequent point transformations (if required by the problem).

Conceptually: “compose transformations by repeated matrix multiplication in the correct order”.

---

3. Step-by-Step Strategy

1. Choose matrix size For 2D transforms with translation, use homogeneous coordinates and $3 \times 3$ matrices.

2. Initialize the combined matrix

import numpy as np
T_combined = np.eye(3) # identity matrix

3. Multiply transforms in the correct order

• If the problem defines:

$$T_{\text{combined}} = T_n \cdot T_{n-1} \cdot \dots \cdot T_1$$

and you have a list Ts = [T1, T2,..., Tn], then:

T_combined = np.eye(3)
for T in Ts:
# apply T after current T_combined: T_combined = T * T_combined
T_combined = T @ T_combined

• This produces $T_n \dots T_2 T_1$ if Ts is in [T1, T2,..., Tn] order.

4. (If needed) Apply to points For a point $p = [x, y, 1]^T$:

p_prime = T_combined @ p

5. Return or output the final T_combined matrix as the solution.

---

4. Common Pitfalls

• Order of multiplication

• Applying transforms is right-to-left on vectors, but when accumulating you often loop left-to-right over the list and multiply as T_combined = T_i @ T_combined, not the other way around.

• Reversing the multiplication order will give the wrong combined transform.

• Using the wrong coordinate representation

• Trying to represent translation with a $2 \times 2$ matrix does not work; translations require homogeneous coordinates and $3 \times 3$ matrices.

• Mixing row-major vs column-major conventions

• Most math libraries use column vectors with transforms on the left: $p' = T p$.

• Some graphics APIs use row vectors with transforms on the right. Be consistent with the convention assumed by your problem.

• Floating-point inaccuracies

• Repeated multiplication may introduce small numerical errors. For this problem it’s usually fine, but be aware of tiny deviations from exact values.

---

5. Time & Space Complexity

Assume each transformation matrix is $k \times k$ (for 2D homogeneous transforms, $k = 3$) and there are $n$ transformations:

• Time complexity

• Each matrix multiplication is $O(k^3)$ with the standard algorithm.

• Doing this for $n-1$ compositions: $O(n \cdot k^3)$.

• For fixed $k = 3$, this is effectively $O(n)$.

• Space complexity

• You only need to keep the current combined matrix and the matrix you’re multiplying in: $O(k^2)$ space.

• For fixed $k = 3$, this is constant space relative to $n$.