.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 an image similar to that shown below:
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:
- Define the three points.
- Select a starting position.
- Randomly select one of the three attractors.
- Move the current position halfway towards the selected attractor position and plot a point.
- 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;
}
Setting the Vertex Locations
The next method will calculate the positions of each of the three attractors, each being located at a vertex of the triangle. These values will be based upon the size of the triangle and the midpoint of the form's client area. The midpoint is calculated first by using half of the height and width of the form. We then add the top vertex, which will be point zero, whose X co-ordinate is vertically aligned with the midpoint and whose Y co-ordinate is half of the height of the triangle above the midpoint.
The two lower vertices are positioned at half of the triangle's height below the centre of the form and half of its width to either side of this point. These are points one and two within the array.
private void SetPointLocations(int sideLength)
{
Point midPoint = new Point(ClientSize.Width / 2, ClientSize.Height / 2);
_points = new Point[3];
_points[0] = new Point(midPoint.X
, midPoint.Y - (int)(sideLength * HeightWidthRatio() / 2));
_points[1] = new Point(midPoint.X - sideLength / 2
, midPoint.Y + (int)(sideLength * HeightWidthRatio() / 2));
_points[2] = new Point(midPoint.X + sideLength / 2
, midPoint.Y + (int)(sideLength * HeightWidthRatio() / 2));
}Plotting the Vertices
The next task is to create a method to plot the positions of the vertices. This is achieved by using a for-each loop to plot the positions of each point in turn. The actual drawing will be done by another method, in this case named "PlotPoint", as this will be reused for the plotting of the points during the production of the fractal. Note that these two methods both accept a parameter containing the graphics surface to be drawn upon. This will be created when the user clicks the button.
private void PlotPointLocations(Graphics g)
{
foreach (Point p in _points)
{
PlotPoint(p, g);
}
}
private void PlotPoint(Point p, Graphics g)
{
Brush b = new SolidBrush(Color.Black);
g.FillRectangle(b, p.X, p.Y, 1, 1);
}Plotting a Random Point
The previous methods control the initialisation of the triangle. Now we can create the methods that are used within the algorithm's loop to draw the fractal. The DrawNextPoint method will control this process by calling a new method named "MoveTowardsRandomPoint", followed by a call to PlotPoint to place a dot at the current position. Finally, it calls Application.DoEvents so that the updated drawing is visible.
MoveTowardsRandomPoint selects one of the three vertices using the randomiser object. It then calculates the position that is half way between the current position and the selected attractor and moves to that point. Add the two methods below to the form's class:
private void DrawNextPoint(Graphics g)
{
MoveTowardsRandomPoint();
PlotPoint(_currentLocation, g);
Application.DoEvents();
}
private void MoveTowardsRandomPoint()
{
int moveTowards = _randomiser.Next(0,3);
_currentLocation.X = (_currentLocation.X + _points[moveTowards].X) / 2;
_currentLocation.Y = (_currentLocation.Y + _points[moveTowards].Y) / 2;
}Creating the Loop
The final job is to bring all of the methods together within the Click event of the form's button. Add the code below to the button's event. This starts by obtaining the form's graphics area and the size of the triangle. The size is used to calculate the positions of the three vertices and store them in the array. Once the three points have been plotted, the initial location is set. In this case I have used the position of the top vertex as the starting point.
An infinite loop is created with a while loop with a condition that will always be true. In this loop, the DrawNextPoint method is repeatedly called. Ideally, you would create a loop that could be stopped by the user. This is demonstrated in the sample that can be downloaded from the link at the top of the page.
Graphics g = CreateGraphics();
int sideLength = SideLength();
SetPointLocations(sideLength);
PlotPointLocations(g);
_currentLocation = new Point(_points[0].X, _points[0].Y);
while (true)
{
DrawNextPoint(g);
} |