The Chaos Game

A number of years ago, Michael Barnsley introduced viewers of public television to the Chaos Game. Michael instructed his viewers to plot three arbitrary points A, B, and C on a piece of paper. In addition, he asked his viewers to plot an arbitrary initial point X1, as shown in Figure 1.

Michael then explained the rules of the game, as follows:

• Roll a three-sided die whose sides are imprinted with the letters A, B, and C.
• If A comes up, plot the midpoint of the segment joining X1 to A. If the point B comes up, plot the midpoint of the segment joining X1 to B. If the point C comes up, plot the midpoint of the segment joining X1 to C. Call the newly plotted point X2 (as shown in Figure 2).
• Roll the die again. Plot the midpoint of the segment joining X2 with either A, B, or C, depending on the outcome of the die toss. Call this new point X3.
• Roll the die again. Plot the midpoint of the segment joining X3 with either A, B, or C, depending on the outcome of the die toss. Call this new point X4.
• Repeat this process indefinitely.

The chaos game produces an infinite sequence of points X1, X2, X3,.... Barnsley then posed the following question to his viewers: What will the final image look like after you have plotted the infinite collection of points X1, X2, X3, ... generated by the chaos game?

For example, if your first few die tosses are A, B, B, and C, your image would look similar to that in Figure 3. Note: I have included the segments of which X2, X3, X4, and X5 are midpoints for reference. When playing the chaos game you do not plot the segments, you just plot the sequence of points X1, X2, X3, X4, ....

To Infinity and Beyond

Can you imagine what the image would look like if you plotted the infinite set of points generated by Barnsley's rules? Of course, if you used only pencil and paper, you would have to be very patient to plot even a finite number of points. But an infinite set of points? Even computers and calculators cannot accomplish that feat. You are going to have to settle for plotting a lot of points and use the resulting image to approximate what might happen if you plotted all of the points resulting from Barnsley's method.

The Chaos Game on the TI83

Here is a program that you can enter on a TI83 graphing calculator which will execute the rules of the chaos game.

ClrDraw
0->Xmin
1->Xmax
0->Xscl
0->Ymin
1->Ymax
0->Yscl
.5->X
.5->Y
For(I,1,1000,1)
rand->R
If R<1/3
Then
.5*X->X
.5*Y->Y
Pt-On(X,Y)
End
If R>1/3 and R<2/3
Then
.5*X+1/2->X
.5*Y->Y
Pt-On(X,Y)
End
If R>2/3
Then
.5*X->X
.5*Y+1/2üY
Pt-On(X,Y)
End
End

If you have a graph-link for the TI-83, you can download the program chaos.83p . This will help avoid some typing. If you run the program on a TI83, it will produce the image shown in Figure 4. This fractal in Figure 4 is called a Sierpinski triangle.

HP48 users can download chaos.hp, a program donated by Jonathan duSaint.

Matlab 5

The following Matlab 5 code will automate the chaos game. You can obtain a copy of the Matlab 5 M-file at chaos.m.. I have liberally sprinkled the Matlab 5 code with comments (lines beginning with % are comments) with the hopes that they will aid in translating the code into a language of your choice.

function chaos(N)

% The input variable represents the number of iterations
% made by the chaos game.

% Close all open figure windows. Delete this line if you
% don't want to do this.
close all;

% Create a new figure window, axes, and scale the axes.
fig1=figure;
ax1=axes;
axis([0,1,0,1])

% Place a message on the screen for the user.
txt1=text(.1,.5,'Select three points vertices with the mouse.');

% This command allows user to select vertices with the mouse.
[x,y]=ginput(3);
A=[x(1);y(1)];
B=[x(2);y(2)];
C=[x(3);y(3)];

% Delete the text message.
delete(txt1)

% Plot and label vertices selected by user.
text(A(1),A(2),'A')
text(B(1),B(2),'B')
text(C(1),C(2),'C')

% Place a text message on the screen for the user.
txt2=text(.1,.5,'Select initial point.');

% This command allows user to select initial point with the mouse.
x=ginput(1);
x=x(:);   % Makes x a column vector

% Delete the text message
delete(txt2);

% Main algorithm begins. The idea is this: Roll a 3-sided
% die with the letters A, B, and C on the faces. If A comes
% up, plot the midpoint of the segment joining the current
% point with the point A. Similar comments apply if B or C 
% are rolled.

% Reserve space for the N points (2 by 1 column vectors) 
% produced by the following iteration.
X=zeros(2,N);

% Main loop begins
for i=1:N

% The function rand produces a random number between 0 and 1.
        r=rand;  % Roll the die
        if r<1/3
                x=mid(x,A);  % A was rolled. Find midpoint of current point and A.
                X(:,i)=x;  % store the result for later plotting
        elseif r<2/3
                x=mid(x,B); % B was rolled. Find midpoint of current point and B.
                X(:,i)=x;  % store the result for later plotting
        else
                x=mid(x,C);  % C was rolled. Find midpoint of current point and C.
                X(:,i)=x;  % store the result for later plotting
        end  % end if
end  % end for loop

line(X(1,:),X(2,:),...
        'linestyle','none',...
        'marker','.');

function u = mid(x,vert)
% Find the midpoint of the segment joining current point and vert.
u=0.5*(x+vert);

If you wish to plot 10,000 points generated by the algorithm of the chaos game, simply enter chaos(10000) at the Matlab prompt. This should generate an image similar to that in Figure 5.

Affine Transformations in the Plane

An affine transformation maps a point (x,y) in the plane to a point (x',y') and has the form

where a, b, e, c, d, and f are coefficients. The point (x',y') is called the image of the point (x,y) under the affine transformation. The point (x,y) is called the preimage.

Example 1.

Consider the following affine transformation:

Find the image of each of the points ( 0,0) and (1,0) under the affine transformation (1).

Solution.

To find the image of (0,0), substitute the point (0,0) into equations (1) as follows:

Therefore, the image of the point (0,0) under affine transformation (1) is the point (0,0) . Sometimes we say that the transformation "sends" the point (0,0) to the point (0,0). Substitute the point (1,0) into equations (1) as follows:

The image of the point (1,0) under affine transformation (1) is the point (1/2,0) .

Exercise 1.

Show that the image of the point (1,1) under affine transformation (1) is (1/2,1/2) .

What Do They Transform?

Let's examine how affine transformations behave geometrically. For example, consider the triangle pictured in Figure 6.

In Example 1 and Exercise 1, you saw that the affine tranformation (1) sent

The affine transformation (1) "sends" (or "maps") each vertex of triangle ABC to the corresponding vertex of triangle A'B'C', as shown in Figure 7. In essence, the affine transformation (1) scales triangle ABC toward the origin by a factor of 1/2.

Example 2.

Let's consider a second affine transformation.

Check that affine transformation (2) "sends"

Consequently, affine transformation (2) "sends" each vertex of triangle ABC to the corresponding vertex of triangle A'B'C', as shown in Figure 8. In essence, the affine transformation (2) scales triangle ABC toward the origin by a factor of 1/2, then translates the resulting triangle to the right 1/2 unit and upward 1/2 unit.

Exercise 2.

Show that the affine transformation

sends triangle ABC to triangle A'B'C', as shown in Figure 9.

Iterated Function Systems

In the "Chaos Game," you started the game by randomly selecting an intial point X1. You then randomly applied one of three transformations to find the image of point X1, which you then labeled X2. You then repeated this process indefinitely.

The chaos game is actually a particular example of a more general class of processes called iterated functions systems. Iterated functions systems follow the same basic rules as the chaos game, but allow you more freedom in selecting and applying your transformations. You may select more than three transformations and it is not required that each transformation have an equal probability of being selected.

Here are the rules of the game for iterated function systems:

• First create two or more affine transformations.
• Assign probabilities to each transformation. That is, assign a number between 0 and 1 to each transformation that determines the likelihood that the transformation will be selected at any given iteration.
• Plot an arbitrary point X1 in the plane.
• Select a transformation at random (according to the probabilites assigned) and plot the image of the point X1 under the selected transformation. Label this point X2.
• Repeat this process indefinitely to produce a sequence of plotted points X1, X2, X3,....

Example 3.

In the section "What Do They Transform," you saw that each of the following transformations mapped triangle ABC to a scaled and translated image A'B'C', as shown in Figure 10.

Suppose that you assign each of the transformations T1, T2, and T3 probability 1/3. That is, each transformation has a one in three chance of being selected at any particular iteration. Select any point X1 in the plane. Randomly select one of the transformations T1, T2, or T3 (remember, each has probability 1/3 of being selected) and plot the image X2 under the selected transformation. If you repeat this process indefinitely, it should come as no surprise that you arrive at the image shown in Figure 11. The Matlab 5 M-file that created this image is called siepin.m .

Exercise 3.

The following set of transformations maps the unit square (with vertices (0,0), (1,0), (1,1), and (0,1)) to scaled and translated copies of itself.

If each transformation is equally likely to be selected at any iteration (each transformation has probability 1/5, or 0.2, of being selected), write a program that produces the image generated by this iterated function system.

Pretty Boring Stuff?

Why all the fuss and bother about iterated function systems? Why do so many people find them so fascinating? After all, not everyone is going to be equally excited by the Sierpinski triangles.

Example 4.

Michael Barnsley's famous example, the "Fern," can be recreated with the following transformations. The probability that a particular transformation is selected is listed in the third column of the following table.

The Matlab 5 M-file fern.m uses the transformations and probabilities in Table 3 to create the image in Figure 12.

Exercise 4

Write a program on your calculator that will draw the fern shown in Figure 12. Use the transformations and probabilities given in Table 3.

How Did They Do That?

As you can see from the image in Figure 12, you can create spectacular images using iterated function systems. But how does one discover the appropriate tranformations and probabilities required to build the object? How were the transformations in Table 3 created?

Michael Barnsley described a technique in his presentation called the Collage Theorem. The idea of the Collage Theorem is simple: cover the object with a collection of objects that are scaled, reflected, rotated, or translated copies of the original. In Figure 13, note that I have drawn a red triangle similar in size and shape to the fern. I then loosely covered the fern (and the red triangle) with four green transformed copies of the red triangle (the green stem is a very narrow copy of the red triangle).

Each of the tranformations in Table 3 maps the red triangle to one of the four transformed green triangles. But a question still remains: how do you find the transformations that map the red triangle to each of the green triangles?

Finding Affine Transformations

Recall that an affine transformation has the following form:

Example 5.

Suppose that you wish to find the transformation that maps triangle ABC to triangle A'B'C' in Figure 14.

You need to find the tranformation that sends

The affine transformation (3) has to send A(0,0) to A'(1/2,0). Substitute the coordinates of point A(0,0) (the preimage) into x and y and susbstitute the coordinates of the point A'(1/2,0) (the image) into x' and y'.

Because B(1,0) gets "sent" to B'(1,0), substitute the coordinates of the point B(1,0) into x and y of equation (3) and the coordinates of the point B'(1,0) into x' and y'.

Finally, substitute the coordinates of the point C(1,1) into x and y of equation (3) and the coordinates of the point C'(1,1/2) into x' and y'.

The substitutions made in (4), (5), and (6) lead to six equations in six unknowns. There are a variety of techniques available that will allow you to solve the six equations in (4), (5), and (6) for the unknowns a, b, c, d, e, and f. Ask your teacher for the technique most appropriate for your level. The solution of the equations in (4), (5), and (6) is

Substitute these values into the affine tranformation (3) to get the following result.

Project

Draw the triangles shown in Figure 13 on a sheet of graph paper. Estimate the coordinates of each of the vertices of the four triangles. Use the technique of Example 5 to find each of the four affine transformations that map the large red triangle to a corresponding green triangle. Note: Don't be disappointed if the transformations found in this project do not match exactly with those given in Table 3. Write a program to produce the image generated by the transformations found in this exercise. How closely does it match the fern given in Figure 12?

Computer Programs Simplify the Work

There are a number of excellent computer programs that simplify the work involved in finding the linear transformations required to generate an image. One program in particular very nearly matches the technique presented in this paper. Visit the Math Archives at http://archives.math.utk.edu/ and download the file fdesi313.zip at http://archives.math.utk.edu/software/msdos/dynamics/fdesign/.html . You will also need a program to unzip the file. Most modern day operating systems come with an unzip utility, but if you don't have one, you might look at Winzip at http://www.winzip.com .

The program is designed to be used with a mouse. You begin by drawing a large triangle (the large brown triangle in Figure 15), then you use the mouse to draw transformed copies of your original triangle. Each time you draw a transformed triangle the program automatically computes the transformation that maps your original triangle to the one just drawn. The image generated by your transformations is shown in the upper right corner of the screen and is updated each time you add a triangle.

World Wide Web Resources

Finally, there are all kinds of web pages dedicated to iterated functions systems. Use your favorite search engine to look for iterated functions systems. Good luck. I hope you enjoy working with iterated functions systems as much as I have.