The Sierpinski Gasket by Affine

So, in my last post, I promised to explain how the chaos game is is an attractor for the Sierpinski triangle. It's actually pretty simple. First, though, we'll introduce the idea of an affine transformation. Affine transformations aren't strictly necessary for understanding the Chaos game, but by understanding the Chaos game in terms of affines, it makes it easier to understand
other attractors.

An affine transformation is a simple set of linear equations which has the effect of doing a simple
scaling of any geometric figure put through it.

So, for a two-dimensional affine transformation, there are two linear equations - one for each
dimension. Each does a scaling in a different direction - the X equation scales a figure horizontally; the Y equation scales vertically. What it means to apply a transformation T to a figure F is to take each point p=(x,y)∈F, and use the transform to compute a new point p'=(x',y')=T(x,y). The transform F' of F is the set of points p'. p' is called the image of p under T; F' is the image of F under T.

An affine transformation in a plane is a pair of linear equations - one for computing the new X value after the transformation; the other for computing the new Y value. For example, here's an affine transformation A:

• x' = 1/2x + 0y + 0
• y' = 0x + y + 0

If we take a square, and apply A to it, here's what happens: it scales it in half horizontally, and leaves it unchanged vertically.

Affine transformations, in general, can do any combination of dilation (scaling),
rotation, shear, or translation (moving). The chaos game is basically three
different affine scaling transformations. The translation of points to the midpoint of the line between a point and a vertex of the triangle essentially select points near corner points
of triangles. The triangles that attract points are triangles 1/2, 1/4, 1/8, ..., the size of the original triangle because the affine transformations do a 1/2 scaling.

So - you start at a random point within your triangle. Then you pick an affine which scales and translates towards one vertex. That moves your point towards a corner vertex of some triangle. That first translated point may not be very close to an actual member of the Sierpinski set - for example, if the initial point was in the middle of the white space in the center of the triangle. But each iteration, each application of one of the three affines, will move it closer.

So imagine you've got an initial point, and you apply the affine towards one vertex of the triangle. You'll get points along the red lines in this figure. If you use the affine towards a different vertex,
you'll get points on the green colored lines. Looking at those two, you can see the beginnings of
where the gasket is going to come from - those two are sets of lines are starting to draw triangles within larger triangles. But using those two affines, you'll just keep getting smaller, and closer to the
bottom edge of the enclosing triangle - the smallest triangles will only be in the bottom row.

There's one more bit left. The third vertex.

If you alternate between any two vertices, you'll get the edge-approaching scenario we saw above. To get beyond that, we use the third vertex. Basically, at any moment, you're defining points of line parallel to the edge of the triangle connecting the vertices used for the new point, and the point before it; and you're shifting the line closer to that edge - and that's the same thing as moving it away from
the third vertex. So doing A,B,A,B,A,B gives you smaller triangles close to the A/B edge of the triangle. Then doing A,C pulls the points away from C, and close to the center - drawing the points to form edges of smaller triangles parallel to the A,C edge of the triangle. So there's a constant motion in and out towards the vertices - closer to any pair of vertices means farther away from the third. And since the three are being selected randomnly, over time, we expect to fill in points in every region.

The key to understanding it are to know what the affine transformations are doing; and to understand
the pattern of their invocation and how that will cause them to interact. If you switch gears, and look at the affines for the Fern, you can see what they're doing - variations
on translations and rotations in the different directions of the branches of the ferns. You can trace out lines like the ones I used for the gasket, except that they'll be more complicated, because of the combination of translations and rotations in the affine transformations of the Fern attractor. The Fern is a lot harder - but it still just comes down to understanding the effects of the individual affines, and then putting it together with the invocation pattern.