Insanity is doing the same thing
over and over again
and expecting different results.
— Anonymous1
Modern computers are remarkably powerful devices, capable of storing millions of pages of text and executing tens of billions of instructions per second, all while being small enough to fit in the palm of your hand.
The key to harnessing all this power is repetition, the seemingly simple idea of performing a sequence of operations multiple times. As a simple example, suppose we want to print a million integers starting from zero. Every programmer knows how to do this: Use a loop to count from 1
to 1 000 000 and output the successive values of the loop variable i:
for (int i = 1; i <= 1_000_000; i++) {
System.out.println(i);
}
This form of repetition is known as iteration, and the example demonstrates its two main ingredients: Every iterative procedure repeatedly performs a sequence of operations (here the instructions inside the loop) while updating a set of variables with each repetition (here the loop
variable i). It’s the ability to update variables that distinguishes iteration from mindless repetition and allows us to do slightly different things over and over again.
Iteration is so commonplace that we rarely give it the recognition it deserves — what could be more ordinary than a loop that iterates over a sequence of integers or the elements of a list? But it’s not hard to find examples of simple iterative processes that show startlingly complex behavior. One such
algorithm is the chaos game, a simple procedure for constructing a sequence of points in the plane.
The chaos game simulates the movement of a point in the plane. We start with a point somewhere inside an equilateral triangle, for example in its center, and then repeatedly move it halfway toward a randomly chosen corner. The trajectory of the point depends on the order in which the corners are
chosen. Figure 1.1 shows the first steps from one particular run of the chaos game. In the left part of the image, the point starts its journey by moving alternately towards the lower-left and upper corners and then takes a final step
towards the lower-right corner. Afterward, as shown in the right part of the image, the point continues to move erratically inside the triangle.
Figure 1.1 The first steps of the chaos game. The game starts with a single point in the center of the triangle and then repeatedly moves it halfway towards one of the corners chosen at random. The image on the left shows the first six points generated in one particular
run of this game, and the image on the right the first 50 steps.
You might expect that the points generated by the chaos game will eventually cover the entire triangle more or less evenly. This is not what happens, however. Figure 1.2 shows the point distributions after 50 000 and
200 000 iterations. As you can see, the points produced by the chaos game are distributed unevenly and converge toward a shape that looks like a triangle from which a number of successively smaller triangles have been cut out. There is a single large empty triangle in the center, which is
surrounded by three smaller ones. Each of these smaller triangles is again surrounded by three smaller triangles, and the pattern continues indefinitely. The longer we let the chaos game run, the more closely the resulting set of points approximates this unexpected limiting shape.
Figure 1.2 Visualization of the first 50 000 and 200 000 points computed by the chaos game. As the number of iteration increases, the point set slowly converges toward a fractal called the Sierpiński triangle.
This curious shape — known as the Sierpiński triangle — is an example of a fractal. Fractals are geometric objects that share two main properties: They have a “fractured” appearance that is irregular but not random, and they can be magnified indefinitely, revealing new details at every level of magnification. In addition,
fractals are often self-similar, which means that their parts resemble the shape as a whole. The Sierpiński triangle clearly has all three properties: Its geometric structure isn’t random but it’s also not as regular as a simple polygon or circle, and it can be magnified
indefinitely, with new copies of the Sierpiński triangle appearing at every level of magnification.
The chaos game we used to construct the Sierpiński triangle is a simple example of an algorithm, a formal description of how to break down a computation into a sequence of elementary steps. To describe algorithms, we will use the format shown in Algorithm 1.1. In this case, the
algorithm consists of a single function named ChaosGame that takes two inputs \(\vec {s}\) and \(n\), the starting point and the number of iterations to perform. The numbered lines that follow explain
the computational steps performed by the algorithm.
Algorithm 1.1
Given a starting point \(\vec {s}\), produce a sequence of \(n\) points in the plane.
Let’s take a closer look at the steps of Algorithm 1.1. Line 1 defines three variables \(\vec {c}_1\) to \(\vec {c}_3\) that represent the corners of an
equilateral triangle; we assume that these corners are already known or that they are computed using a method not specified in the algorithm. We use the let keyword to define read-only variables that don’t change over the course of the algorithm. Line 2 defines a new variable \(\vec {p}\) for the current position and initializes it to the starting point \(\vec {s}\). This variable is defined using the var keyword, which indicates that the value of \(\vec {p}\) is
modified as the algorithm progresses. The repeat loop on the following line repeats the indented lines in its body \(n\) times. It starts with an output statement that outputs the current value of \(\vec {p}\). Line 5 then sets the constant \(k\) to a random integer between 1 and 3, and line 6 moves \(\vec {p}\)
toward the \(k\)th corner. The loop is then repeated \(n-1\) more times. Since output is executed \(n\) times, the algorithm produces \(n\) points.
Mathematicians usually distinguish between points and vectors: Points represent locations in space, whereas a vectors represent directions. However, for simple geometric problems in the plane, the two concepts are closely related: Every point \(P\) with
coordinates \((x,y)\) can be represented by the position vector \(\vec {p}=\left (\begin {smallmatrix}x\\y\end {smallmatrix}\right )\) that points from the origin to \(P\), and vice versa.
For the geometric problems discussed in this book, we will keep things simple and use points and positions vectors interchangeably. Boldface symbols like \(\vec {p}\) and \(\vec {q}\) are always vectors, and if we say something like “the
point \(\vec {s}\),” what we really mean is “the position vector \(\vec {s}\).”
Implementing the Chaos Game
We can now turn to the fun part: implementing the chaos game so that it runs on a real computer and produces real images. In most cases, turning an algorithm into a working program is more complicated than translating it step by step. For instance, we may have to make changes based on the chosen
programming language, flesh out details that weren’t specified precisely, or integrate the algorithm with other parts of a larger program. Here are some of the technical details we have to consider when implementing the ChaosGame algorithm:
1. How do we store points and move them?
2. How do we compute the three corners of the outer triangle?
3. How do we create random numbers between 1 and 3?
4. What does it mean to output a point?
Let’s address these questions one by one.
We start by defining a custom data type called Point that allows us to store and compute with points in the plane. What kinds of operations do we require in Point? Obviously, we need a way to construct points at certain
positions in the plane, so that we can specify the starting point of the chaos game and the three corners that enclose the fractal. To store a point’s position we use Cartesian coordinates \((x,y)\), which measure the point’s position along the horizontal and vertical axis. The Point type defined in Listing 1.1 stores these coordinates in two fields x and y.
Listing 1.1ch1 / Point
// A point in 2D.
public record Point(double x, double y) {
// ...
}
To implement the chaos game, we also need a way to move the current point halfway toward one of the triangle’s corners, that is, we need to compute the midpoint of two points. The easiest way to do this is to average their coordinates, as shown here for the points p and q:
Point midPoint = new Point(
0.5 * (p.x() + q.x()), 0.5 * (p.y() + q.y()));
This is a special case of a more general operation that computes points along the line segment between two arbitrary points \(\vec {p}\) and \(\vec {q}\). In computer graphics, the point that lies some fraction \(t\) between \(\vec {p}\) and \(\vec {q}\) is commonly denoted
by \(\lerp (\vec {p}, \vec {q}, t)\).2 Three special cases of this lerp function are worth noting: For \(t=0\) we obtain the first end point \(\vec {p}\), for \(t=1\) the second end point \(\vec {q}\), and for \(t=1/2\) their midpoint. The function is illustrated in
Fig. 1.3.
Figure 1.3 The lerp function computes a point that lies on the line segment between two end points.
There are two equivalent formulas for defining the lerp function. The first is obtained by starting at the first point \(\vec {p}\) and then advancing along the line to \(\vec {q}\) by adding the difference vector \(\vec {q}-\vec {p}\) scaled by \(t\):
Both definitions can be transformed into each other by reorganizing the terms on the right-hand side. Even though the first definition is slightly more intuitive, we will use the second one since it is more symmetrical and slightly easier to generalize to other forms of interpolation; the implementation is
shown in Listing 1.2.
Listing 1.2ch1 / Point
// Compute the linear interpolation of two points.
public static Point lerp(Point p, Point q, double fraction) {
return new Point((1 - fraction) * p.x + fraction * q.x,
(1 - fraction) * p.y + fraction * q.y);
}
It’s now easy to implement the chaos game itself. The chaosGame() function in Listing 1.3 takes three arguments — a list of
corners, a starting point, and the number of iterations that should be performed — and returns the sequence of points it visits as a list of Points. The function first creates a random number generatorrng that is used to
select one of the corners in each iteration and then allocates a data structure for the return value, in this case an ArrayList of Points.3 The actual algorithm is
implemented by the for loop that follows, which stores the current point in points and then moves it towards a randomly chosen corner.
Listing 1.3ch1 / ChaosGame
public static List<Point> chaosGame(List<Point> corners,
Point start, int iterations) {
var rng = new Random();
var points = new ArrayList<Point>(iterations);
Point p = start;
for (int i = 0; i < iterations; i++) {
points.add(p);
Point c = corners.get(rng.nextInt(corners.size()));
p = Point.lerp(p, c, 0.5);
}
return points;
}
If we want to create an image of the Sierpiński triangle like the one in Fig. 1.2, we have to simulate a few thousand iterations of the chaos game and then draw the resulting points. One way to do this is
shown in Listing 1.4. We first construct a large equilateral triangle with a side length of 1000 and then call chaosGame() to compute 50 000 points inside this triangle, using the center of the triangle as the starting point. Finally, we draw each of the resulting points as a small, filled circle. The Graphics2D type used in this
listing is the standard interface provided by Java for producing 2D graphics; Exercise 1.7 asks you to complete this program by setting up a suitable instance of Graphics2D.
Listing 1.4ch1 / ChaosGame
public static void drawSierpinski(Graphics2D g) {
double sideLength = 1000;
var corners = List.of(
new Point(0, 0),
new Point(sideLength, 0),
new Point(sideLength / 2, sideLength * Math.sqrt(3) / 2));
Point start = new Point(
sideLength / 2, sideLength / Math.sqrt(3) / 2);
List<Point> points = chaosGame(corners, start, 50_000);
float radius = 0.01f;
for (Point p : points.subList(50, points.size()))
g.fill(new Ellipse2D.Double(p.x(), p.y(), radius, radius));
}
You may be wondering why drawSierpinski() removes the first 50 elements of points before drawing them. The reason is that for some starting points the chaos game may require a
few iterations to “warm up” and produce points that are sufficiently close to the actual fractal. In the present example, for instance, we start at the center of the triangle, which isn’t part of the Sierpiński triangle. But with every iteration, the point moves closer to the final fractal until it is imperceptibly
close. Discarding the first few points produced by the chaos game is enough to get rid of the obvious outliers and obtain clean-looking images.
2 The name “lerp” is a contraction of “linear interpolation.”
3 In Java, an ArrayList is a special type of List, so the code is correct even though the return type of chaosGame() doesn’t match the type of points exactly.
Exercises
Exercise 1.1.Given two points \(\vec {p}\) and \(\vec {q}\), what is the geometric interpretation of \(\lerp (\vec {p}, \vec {q}, -1)\)?
Exercise 1.2.Extend the Point class with a method distance() that computes the distance between two points.
Exercise 1.3.What happens if you place the starting point of the chaos game outside of the triangle defined by the three corners? What happens if you
move the corners of the triangle so that it is no longer equilateral?
