Tuesday, January 3, 2012

2D Linear Transformation as Action on a Line Segment

Okay, this post is about 2D linear transformations as a stepping stone to 3D affine transformations for geodesic dome programs. I think a lot of people miss a useful bit of understanding about affine transformations: that they are just linear transformations in a higher-dimensional space. Some familiarity with the properties and "feel" of linear transformations first is helpful, and there is less bookkeeping and it is easier to see what is going on in 2D.

We are going to be working with linear transformations (maps) from the 2D real plane (\(\mathbb{R}^2\) viewed as a vector space) to itself. Given a transformation \(\mathbf{T}\), vectors \(\mathbf{a}\), \(\mathbf{b}\) and scalar \(\alpha\), we have the usual general linearity conditions:

  • \(\mathbf{T(a} + \mathbf{b)} = \mathbf{T(a)} + \mathbf{T(b)}\)
  • \(\mathbf{T(}\alpha\mathbf{a)} = \alpha\mathbf{T(a)}\)

From these, we can derive in particular over \(\mathbb{R}^2\) (though these also generalize to higher dimensional spaces):

  • The origin (0,0) is a fixed point.
  • Compositions of linear transformations are also linear.
  • Inverses of linear transformations (if they exist) are also linear.
  • Linear transformations on \(\mathbb{R}^2\) are representable as 2x2 matrices with real coefficients (and any such 2x2 matrix implements a linear transformation), operating on column vectors in \(\mathbb{R}^2\).
  • Linear transformations preserve co-linearity (lines map to lines) and proportional distance between colinear points.
  • A linear transformation on \(\mathbb{R}^2\) is completely specified by its action on two points, or, equivalently, its action on a single line segment.

This last property will be of interest to us -- it will turn out to generalize nicely to affine transformations and higher dimensional spaces. This, and the co-linearity property, will be directly useful for geodesic dome programs.

The big pain/limitation/disappointment with linear transformations is that they leave the origin fixed. This is what will be overcome by moving to affine transformations.

Here is a web toy for playing around with 2D linear transformations. You can click in the image to specify endpoints for a couple of line segments, then repeatedly apply the transformation whose action maps the first line segment to the second one, operating on one of several synthetic images. Click the "+" to go offsite and investigate the code (computation explanation follows). Some patience required; depending on your browser it can be a bit slow (it's all client side JavaScript).

So, if you play around with this a bit, most of the qualities of linear transformations are noticeable. Note particularly the "inconvenience" of having the origin fixed. Transformations defined by segments that are co-linear or close to co-linear with the origin are singular or nearly so.

You can also get a feel here for that fact that linear transformations have a pretty simple taxonomy/decomposition -- there are only reflections, rotations, scales, stretches (unequal scale in x and y) shears (flattening of squares to parallelograms), and combinations of these.

The above toy works computationally by representing transformations as 2x2 real matrices. The matrix operations are "unrolled" into primitive algebraic operations in the code in lieu of using a prefab linear algebra JavaScript package, mostly for performance reasons. A matrix is generated for the inverse of the transformation that we want; then each desired point in the output image is transformed back through that matrix to find its corresponding point in the synthetic test subject.

The most interesting calculation here is the one that yields the matrix of a transform, given the endpoints for the source and transformed line segments. This is a useful computational trick if you haven't seen it before. It works like this:

Suppose we are looking for the transformation that maps vectors \(\mathbf{a},\mathbf{b}\) to vectors \(\mathbf{c},\mathbf{d}\), that is:\[\begin{align*}(a_x,a_y) &\mapsto (c_x,c_y)\\(b_x,b_y) &\mapsto (d_x,d_y)\end{align*}\]
First, consider the matrix formed from adjoining the two source points \(\mathbf{a},\mathbf{b}\), and it's inverse. We have:\[\left(\begin{array}{cc}a_x&b_x\\a_y&b_y\end{array}\right)^{-1}\left(\begin{array}{cc}a_x&b_x\\a_y&b_y\end{array}\right) = \left(\begin{array}{cc}1&0\\0&1\end{array}\right)\]
Since a column of the result matrix on right is the result of the leftmost matrix operating on the corresponding column of the middle matrix (definition of matrix multiplication), we can see the the leftmost matrix here sends each of our source points to an orthonormal basis vector. That is:\[\begin{align*}\mathbf{a}&\mapsto(1,0)\\\mathbf{b}&\mapsto(0,1)\end{align*}\]
Likewise, we have:\[\left(\begin{array}{cc}c_x&d_x\\c_y&d_y\end{array}\right)\left(\begin{array}{cc}1&0\\0&1\end{array}\right) = \left(\begin{array}{cc}c_x&d_x\\c_y&d_y\end{array}\right)\]
so the leftmost matrix here sends each basis vector on to one of our destination points:\[\begin{align*}(1,0)&\mapsto\mathbf{c}\\(0,1)&\mapsto\mathbf{d}\end{align*}\]
Composing these two matrices (destination point matrix multiplied by the inverse of source point matrix) gives the matrix result which will carry the source points to the destination points and all other points along for the ride, obeying the constraints/behaviors of linear transformations. This same method is perfectly generalizable to higher dimensional spaces, and will be one of the principal techniques used in the upcoming geodesic dome programs.