This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 1.1+

The Chaos Game and the Sierpinski Triangle

The chaos game is a method for generating fractal images by plotting randomised points inside a polygon according to a simple set of rules. In this article we will use the chaos game to generate the Sierpinski triangle using C# and Windows Forms.

The Chaos Game

The chaos game is a mathematical term for a method of generating fractal imagery. The game provides a simple set of rules that can produce surprisingly complex figures. The algorithm specifies a starting condition with a set of defined points, or attractors. The set of attractors can be thought of as a series of vertices of a polygon. A starting point within the polygon is selected and plotted within the image.

Once the start condition is known, a repetitive process is followed to generate the fractal. Firstly a random vertex in the polygon is selected. Next, the current position, or starting position for the first iteration, is connected to the attractor's position with an imaginary, straight line. The current position is moved along this line by a fraction of the distance between the two points and the new position is plotted in the figure.

The Sierpinski Triangle

The Sierpinski triangle is a fractal that was first described by the Polish mathematician, Wacław Sierpiński. When displayed, it appears as a triangle divided into four sections, each a triangle half of the height and width of the original. The central triangle is inverted and can be thought of as a hole in the image. Each of the three outer triangles is a smaller version of the entire figure, with its own central hole. This pattern repeats infinitely to give a result similar to that in the image below:

Sierpinkski Triangle

There are various methods in which the Sierpinski triangle can be produced. One of these is using the chaos game with the three attractors positioned at the three vertices of an equilateral triangle. When moving the current position towards an attractor, the amount moved is always half of the distance between the current point and the selected vertex. The steps to create the fractal are therefore:

  1. Define the three points.
  2. Select a starting position.
  3. Randomly select one of the three attractors.
  4. Move the current position halfway towards the selected attractor position and plot a point.
  5. Return to step 3.

Drawing the Sierpinski Triangle

In the remainder of this article we will create a C# program to generate the Sierpinski triangle. The program we will develop is that one that was used to generate the image above.

Creating the Project

To begin, create a Windows Forms project. We will use the default form to display the triangle, drawing directly onto the form's surface. Open the default form and change its BackColor property to white. We will start the process of generating the fractal in response to a button click, so add a button to the form and apply a suitable label to it using the Text property.

Class-Level Scoped Variables

During the production of the image there are three items that will be used by various methods. The first is a pseudo-random number generator, which will be used to determine the direction of travel during each iteration of the chaos game. Secondly, we need to hold the positions of the three vertices of the equilateral triangle. We can hold these in a small array of Point structures. Finally, another Point structure will hold the current position.

To declare the variables for these items, add the following class-level scoped variables to the class:

Random _randomiser = new Random();
private Point[] _points;
private Point _currentLocation;

Determining the Triangle Size

The size of the triangle should be as large as possible to enable the maximum detail to be displayed. However, we do want to ensure that the triangle is equilateral and is positioned centrally within the form's client area. To determine the largest possible size, we must consider the ratio between the height and width of any equilateral triangle. Assuming the base of the triangle is aligned horizontally, the width will be the same as the length of one of the sides. The height will be the width multiplied by half of the square root of three.

We can add a method to the form to calculate the ratio by adding the following code:

private double HeightWidthRatio()
    return Math.Sqrt(3) / 2;

With the ratio readily available, we can determine the maximum size of the triangle by comparing the full width of the form's client area and the its height divided by the ratio. The smaller of these two values is the greatest size. The following method should be added to the form's class to calculate the triangle's size. Note that the height is reduced by two before being returned. This will allow for a small border around the edge of the fractal.

private int SideLength()
    int height = (int)Math.Min(
        (double)ClientSize.Width, ClientSize.Height / HeightWidthRatio());
    return (int)height - 2;
17 May 2009