Personal tools


From HaskellWiki

< Diagrams | Dev(Difference between revisions)
Jump to: navigation, search
(Inverse and transpose transformations: clean up, wiki formatting etc.)
(Notes on an intensional representation for angle-preserving transformations)
(2 intermediate revisions by one user not shown)

Revision as of 02:54, 1 December 2013


1 Linear and affine transformations


  • f(kv) = kf(v)


  • rotation
  • reflection
  • scaling
  • shear



  • translation


2 Matrices, inverse and transpose transformations


4 & 5 \\
6 & 2



The transpose of a matrix (denoted M^\top) is the matrix you get when you reflect all the entries about the main diagonal. For example,

4 & 5 \\
6 & 2
4 & 6 \\
5 & 2


What we really want to think about is the inverse transpose, that is, the inverse of the transpose of a matrix, denoted M^{-\top}. Suppose we have a vector v, and another vector p which is perpendicular to v. Now suppose we apply a linear map (represented by a matrix M) to the vector v, giving us a new vector v' = Mv. In general, Mp may not be perpendicular to Mv, since linear transformations do not preserve angles. Some linear maps such as rotations and uniform scales do preserve perpendicularity (if that's a word), but not all linear maps do: for example, the 2D linear map that scales all x-coordinates by 2 but leaves y-coordinates unchanged. But what if we want to obtain another vector perpendicular to v'? In fact, the thing to do is to multiply p not by M, but by the inverse transpose of M. That is: if v and p are perpendicular vectors, then so are Mv and (M^{-\top})p. This can be proved by noting that the dot product of two vectors v_1 \bullet v_2 can equivalently be written v_1^\top v_2 (treating vectors as n \times 1 column matrices), and that two vectors are perpendicular iff their dot product is zero. Hence

(Mv) \bullet (M^{-\top}p) = (Mv)^\top(M^{-\top}p) = v^\top M^\top M^{-\top}p = v^\top p = 0


It's easy to see that (M^{-1})^{-1} = M = (M^\top)^\top (i.e. the inverse and transpose operations are involutions). It's not quite as obvious, but not too hard to show, that the inverse of the transpose is the same as the transpose of the inverse. Combining these facts, we see that for a given matrix M there are really only four matrices of interest: M, M − 1, M^\top, and M^{-\top}. We can arrange them conceptually in a square, thus:

M   &   M^{-1} \\
M^\top &  M^{-\top}




3 Representation




Then an (affine) Transformation is defined as follows:




4 Specifying transformations as matrices



1 & 2 \\
3 & 4



5 Angle-preserving transformations

An angle-preserving transformation is one which preserves angles between all pairs of lines. It is possible to prove the following:

  • A linear transformation L is angle-preserving iff there exists a constant λ such that \|L(v)\| = \lambda \|v\| for all vectors v. (See
  • Intuitively, the previous result means that any angle-preserving linear transformation (other than the constantly zero transformation) can be uniquely decomposed as a uniform scale followed by a rotation.
  • An affine transformation is angle-preserving iff it can be expressed as an angle-preserving linear transformation followed by a translation.
  • Angle-preserving affine transformations are closed under composition.

The last two points in particular imply that we can uniquely represent angle-preserving affine transformations by a triple A = (θ,s,w) where A(v) = Rθ(sv) + w (Rθ indicates a rotation by θ), and given this representation we may compute

(\theta_1, s_1, w_1) \circ (\theta_2, s_2, w_2) = (\theta_1 + \theta_2, s_1 s_2, R_{\theta_1}(s_1 w_2) + w_1)

It is also easy to compute the inverse

(θ,s,w) − 1 = ( − θ,1 / s, − R − θ(w / s))

and the transpose of the linear part:

(θ,s)T = ( − θ,s)

(The above calculations are simplified by the observation that rotations and uniform scales commute, though of course transformations do not commute in general.)

As a concrete proposal, we can change T2 from a synonym for Transformation R2 to a sum type

 data T2
   = Ortho Angle Double R2
   | GenT2 (Transformation R2)

and change things like rotate to construct an Ortho instead of a Transformation R2. There is a bit of trickiness to be worked out with the function scaling, which currently has type Scalar v -> Transformation v, i.e. it is supposed to work over any vector space, but we want it to do something special for R2. I am not sure what the right solution is.

In any case, some benefits of such a scheme would be:

  • Angle-preserving transformations are precisely those which preserve circular arcs. If we add a new primitive type of arc segment, we can look at the final transformation applied to the segment to determine whether we can simply issue a primitive arc command (if the transformation is an Ortho) or if we must issue an arc command wrapped in a transform (or approximate the arc with Beziers).
  • For typical applications, Ortho transformations make up the vast majority of transformations actually used. Intuitively, it seems this should lead to a performance boost, since Ortho values consist of simple first-order data, making it easier for GHC to optimize e.g. chains of repeated transformations. General Transformation values, on the other hand, are functions, which can be tricky for GHC to optimize e.g. when deeply nested.