Intuitively speaking, we can define a {\it geometric transformation} as a mapping from one space into another that takes geometric objects into other geometric objects. Such transformations have been studied quite extensively by generations of mathematicians, and F. Klein's school regarded them as the true foundation of geometry. Isometries of the plane (rotations, reflections and translations) were taken for granted by Euclid himself, and the concepts of scaling and shearing transformations were clearly familiar to him.

For lack of time and space, a satisfactory introduction to geometric transformations will be left to some future chapter; for now, we will restrict ourselves to the definitions and notation strictly necessary for the rest of this chapter.

The simplest transformation is the identity $I$, that maps every point into itself. A {\it translation} by a vector $v$, of course, is the map that takes every point $x$ of the plane to the point $x+v$. A translation is a special case of an {\it isometric transformation}, or {\it congruence}, a geometric map that preserves the distances between all pairs of points. Rotations and reflections around a line are also isometric transformations. It is easy to see that isometries must map straight lines into straight lines, and preserve the angles between them. Indeed, in classical geometry two figures related by a congruence are usually considered to be the same figure.

A slightly more general kind of geometrical mapping is a {\it similarity transformation} that is basically an isometry followed by a change of scale. A similarity will map straight lines into straight lines, angles into equal angles, and in general figures into similar figures (hence its name). Generalizing in a different way, we get a class of transformations that preserve straight lines and areas but not necessarily angles and distances; we may call them {\it unimodular transformations}. The ``vertical shearing'' that maps a point $(x, y)$ to the point $(x, y+\alpha x)$ (for some nonzero constant $\alpha$) is an element of this class.

The {\it affine transformations} constitute a more general class of mappings, including all of the above as proper subclasses. General affine maps take straight lines into straight lines, but do not in general preserve angles, distances or areas (they preserve {\it ratios} of areas, however). The affine maps that leave the origin fixed are the well-known {\it linear transformations} of $\reals^2$. A general affine transformation consists of a linear map followed by a translation.

An affine transformation $T$ is {\it degenerate} if it is not one-to-one; this happens if and only if two distinct points have the same image under $T$. Given a pair of non-degenerate triangles $abc$ and $a\pr b\pr c\pr$, there is exactly one (non-degenerate) affine transformation that maps $a$ to $a\pr$, $b$ to $b\pr$, and $c$ to $c\pr$.
\figspace 3cm
Conversely, any non-degenerate affine map of the plane will take the points $(0, 0)$, $(0, 1)$ and $(1, 0)$ to the vertices of a non-degenerate triangle. In this chapter, all affine maps will be assumed one-to-one unless stated otherwise.

We will denote by $p^T$ the image of a point $p$ by the affine transformation $T$. If $X$ is a set of points, $X^T$ is the set $\rset{p^T\relv p\in X}$. The image of a line $\lscr$ is written $\lscr^T$; its orientation is such that a point $p$ is on $\lscr$ (resp. to the left of $\lscr$) if and only if $p^T$ is on $\lscr^T$ (resp. to the left of $\lscr^T$).
\figspace 4cm

Note that if $\lscr$ is oriented from $a$ towards $b$, then depending on the map $T$ the image $\lscr^T$ may be oriented from from $a^T$ to $b^T$ or from $b^T$ to $a^T$. It can be shown that if this ``orientation reversal'' happens for one line, it happens for all of them. The mapping $T$ is said to be {\it odd} if that occurs, and {\it even} otherwise. An affine transformation is odd if and only if it maps a counterclockwise triangle into a clockwise one.

We define the image of a state $s$ under a mapping $T$ as the state $s^T$ with position $\po s^T$ and tangent line $(\ta s)^T$.
\figspace 4cm

The image of a turn of move $[r\to s]$ under an affine map $T$ will be precisely the turn or move $[r^T\to s^T]$. This is not entirely obvious at first sight; it follows from the fact that affine transformations preserve the ``betweeness'' properties of points and oriented lines, i.e. they map segments into segments and proper angles into proper angles. More precisely, a point $x$ belongs to the segment $(p\sp q)$ if and only if $x^T$ is in $(p^T\sp q^T)$. Similarly, if the three lines $r, s$ and $t$ are such that $\di t$ is in the proper arc $(\di r\sp \di s)$, then the same relationship holds for their images under $T$.
\figspace 3cm

The image $S^T$ of a tracing $S$ under an affine map is then defined quite naturally as the result of applying $T$ to every turn and move of $S$. For example, if $T$ is translation by a vector $v$, then $S^T$ will be what we would expect.
\figspace 3cm

Note that if $T$ is an odd affine map, then the move $[r\to s]^T$ will be backwards if $[r\to s]$ is forward, and vice-versa. In the same way, an odd map will change clockwise turns into counterclockwise ones, and conversely. (If you are beginning to feel confused, don't worry: all maps we will use in this chapter are even).

We will denote by $-I$ the {\it sign reversal} transformation that maps every point $(x, y)$ to its opposite $(-x, -y)$ across the origin. This transformation corresponds to a $180\deg$ turn around the origin, or to two successive reflections, one about each coordinate axis. In spite of the fact that it maps every line to one with opposite orientation, it is an even mapping (can you see why?). One of its properties is that any tracing which is centrally symmetric (e.g., a circle) is identical to its image under $-I$, up to orientations and directions of traversal.
\figspace 3cm

The affine maps are closed under composition, and the same is true of the other classes of transformations defined above. In other words, if $R$ and $S$ are arbitrary affine maps, then there is a third affine map $R S$ such that $x^{R S}=(x^{S})^R$ for all $x$ in the plane. We denote the translation through a vector $v$ by just $v$, so $x^{v\,-I}$ is what we obtain by applying the sign reversal transformation $-I$ to $x$, and then translating the result by $v$\foot\dag{Do not try to read $v\,-I$ as the difference between $v$ and $I$; the similarity of notation is just an unlucky coincidence.}. This particular transformation will play an important role in the next section.

It is interesting to consider the interaction between affine maps and convolution of polygonal tracings. If $T$ is a linear map, then $A^T\ast B^T=(A\ast B)^T$. This is not true for general affine maps, in particular for translations; however, it is the case that $A^v\ast B^w=(A\ast B)^{(v+w)}$, for any vectors $v$ and $w$. Since sign reversal is a linear map, we have $A^{v\,-I}\ast B^{w\,-I}=(A\ast B)^{(v+w)\,-I}$.
\figspace 4cm