# Drawing Fractals with Iterated Function Systems (IFS)

The **Iterated Function Systems** (**IFS**) are a simple mathematical tool for constructing **fractal** sets through a series of contractive affine applications. This method was developed by **M.F. Barnsley** in 1985. In particular, it is useful to obtain a self-similar **fractal** based on iteratively applying the system of functions to any set, until arriving at a good approximation of the **fractal** set that constitutes the **attractor** of the system.

The **IFS** also serve as a basis for some data compression methods, especially images, since they allow obtain good approximations of objects of the real world. Instead of storing all the data of the images, what we store in its place are the coefficients of the applications of the different systems used to approximate the image, which is then reconstructed from them.

In this article I will use an application to show the operation of this method, with which you can define transformation systems and get images of the **fractals** generated by iterating them. In this link you can download the source code and executable of the IFSDrawer project, written in **CSharp** with **Visual Studio** **2015**.

## Contractive affine applications

I will explain a little what it is that of contractive affine applications. The examples I am going to use are for a space of two dimensions, a plane, but they can be extended to spaces of any dimension.

An affine application **F** on a point **(x, y)** of the plane can be represented as follows:

The **e** and **f** coefficients have an obvious function: that of displacing the **x** and **y** coordinates. With the other four coefficients, we can perform different operations, whose meaning is best seen if we imagine that we are dealing with the points of a given plane figure.

If we give the **b** and **c** coefficients a value of zero, the coordinates **x** and **y** of the points will be multiplied respectively by the value of the **a** and **d** coefficients, which will cause the figure to expand or contract in each of the two axes.

We can also create a symmetry with respect to the horizontal and/or vertical axes by making one or both **a** and **b** coefficients negative.

If we give a value of zero to the **a** and **d** coefficients, we can interchange, besides multiplying by the value of the coefficients **b** and **c**, the horizontal and vertical coordinates.

Also we can rotate the figure an angle **φ** giving the following value to the coefficients: **a=cosφ**, **b=-sinφ**, **c=sinφ** and **d=cosφ**.

We can compose several of these movements obtaining the product of the matrices corresponding to each one of them. Let us recall that the result of the product of two 2x2 matrices **A** and **A'** is another matrix **A''** whose coefficients are: **a''= aa' + bc'**, **b''= ab' + bd'**, **c'' = ca'+ dc'** and **d'' = cb'+ dd'**.

An affine application is **contractive** if the coefficients by which we multiply are less than one and greater than zero.

In **.NET framework** it is very easy to perform affine transformations using the **Matrix** class, in the **System.Drawing.Drawing2D** namespace.

## Iterated Function Systems

The **iterated function systems** are sets of **n** contractive affine transformations. Normally, two types of algorithms are used, the **deterministic** version or the **random** one.

The **deterministic** algorithm consists in taking a set of points, which can be any geometric figure, and applying to it each of the **n** affine transformations of the system, whereby we obtain **n** sets of transformed points. To each of them we re-apply each of the **n** functions, obtaining **n ^{2}** new sets of points.

We continue this way by iterating on the results, until the union of all the sets obtained in the last iteration is approaching sufficiently the figure that constitutes the **attractor** of the system. We will always arrive to this **attractor**, regardless of the starting selected set of points. Each **IFS** has a characteristic **attractor**, which will be a self-similar **fractal**, since it is built on copies of itself, smaller and smaller. Normally, it does not take many iterations to obtain such **fractal** set.

The **random** algorithm is similar, but instead of applying the functions to a set of points, we apply them to a single point again and again, drawing the result each time. We assign a probability value to each of the system transformations, taking into account that the total sum of the probability values of the functions must be 1. In each iteration of the algorithm, we select one of the transformations with probability **p**. This is very simple to do, simply get a random value between 0 and 1, for example with the class **Random**, and go adding the probabilities of each function one by one until the result is greater than the random number obtained. That will be the selected function.

The first points of the series are discarded. Because they are usually very far from the **attractor**, the rest are plotted until the corresponding **fractal** drawing is obtained, usually after a number of iterations between 1000 and 5000.

## IFSDrawer application

Let's now see the application that I have prepared to illustrate all this. It is a form that looks like this:

In the **Shapes** list on the right, you can select different starting polygons to iterate through the **deterministic** algorithm. At the bottom we will see how the **attractor** is drawn. The coefficients of the different transformations will be written in the **DataGridView** on the left, which is a DataGridView with formula support that I have already discussed in another article.

The formulas can be written in the text box above the grid and, with the button to the right, they can be compiled and assigned to the selected cells. These formulas can be useful in order to not having to use the calculator to calculate the values to write in each of the coefficients. You can consult the article on this control over the syntax of the formulas. In this application I have added to the language the following constants, which can also be used in the formulas:

**_pi**and**_e**: The values for the math constants pi and e.**_rand**: A random value between 0 and 1.**_width**and**_height**: The width and height of the drawing zone.

The first button, starting at the left of the toolbar, is to clear everything and start with a new empty system of functions. With the second you can open a file with a system of transformations that you have previously saved. The program works with two formats, **csv** and a proprietary binary format, **ifs**. The functions defined in the grid cells are also saved in these two file types along with the rest of the data.

In the Samples folder of the **IFSDrawer** project I have left some examples of systems. If you open, for example, the **Sierpinski.ifs** file, you will see the following:

There are three transformations, each one in a grid row, with their corresponding coefficients. Since the **P** column is empty, the **deterministic** algorithm will be used to process the system.

The third button on the toolbar allows you to save the transformation system to a file and the fourth and fifth are used to save the current image to a file or to the clipboard, respectively.

You can add more functions to the system with the third button, starting at the right, or delete one of them with the second, after having selected the corresponding row.

Before you can execute the algorithm, you have to process the values in the grid cells, to check that they are complete and correct. To do this you have to use the first button, starting from the right. You should also use this button if you have made any changes, before you can see the result.

Once this is done, one of the central buttons will be activated, with a green arrow, and you can begin to iterate the algorithm, one step at a time, each time you press the arrow.

The result, after 1, 3 and 8 iterations, is the following:

The well-known **Sierpinski triangle**. You can try with any of the other shapes, even with the circle, and you will always get this triangle, which is the **attractor** of this system of functions.

To see an example of a **random** algorithm, you can open the example file **Fern.ifs**, with which you can draw a fern leaf. First you have to press the same button as in the previous example to process the formulas. You can see that, in the middle, this time is activated a button with two green arrows, next to which two text boxes appear. The first is for the number of iterations. It should be noted that in this algorithm you cannot go step by step due to the large number of times it should be executed. You can also indicate a scale factor for the drawn figure. The result is something like this:

As for the program code, the **Transformation** class is used to store the data of each affine transformation in its **A**, **B**, **C**, **D**, **E**, **F** and **P** properties with generic **object** type, which can contain values of type **double** or formulas of the **FormulaBase** type. The value is retrieved in **double** format with the read-only properties **AValue**, **BValue**, etc:

`[Serializable]`

public class Transformation

{

public Transformation()

{

}

public object A { get; set; }

public object B { get; set; }

...

public double AValue

{

get

{

if (A == null)

{

return double.NaN;

}

if (A is FormulaBase)

{

return (A as FormulaBase).Value;

}

return (double)A;

}

}

...

}

The class is decorated with the **Serializable** attribute so that we can save it to a file.

The geometric shapes are all descendants of the abstract base class **ShapeBase**:

`public abstract class ShapeBase`

{

protected GraphicsPath _path;

protected bool _fill = false;

public ShapeBase()

{

}

public ShapeBase(ShapeBase clon, Transformation tr)

{

_path = clon._path.Clone() as GraphicsPath;

Transform(tr);

}

public abstract void SetInitialSize(SizeF sz);

public virtual ShapeBase Draw(Graphics gr, Transformation tr)

{

if (tr != null)

{

ShapeBase snw = GetType().GetConstructor(

new Type[] { typeof(ShapeBase),

tr.GetType() }).Invoke(new object[] { this,

tr }) as ShapeBase;

snw.Draw(gr);

return snw;

}

else

{

Draw(gr);

return this;

}

}

protected virtual void Transform(Transformation tr)

{

Matrix m = new Matrix((float)tr.AValue, (float)tr.BValue,

(float)tr.CValue, (float)tr.DValue,

(float)tr.EValue, (float)tr.FValue);

_path.Transform(m);

}

protected virtual void Draw(Graphics gr)

{

if (_path != null)

{

if (_fill)

{

gr.FillPath(Brushes.Black, _path);

}

else

{

gr.DrawPath(Pens.Black, _path);

}

}

}

}

The class has a **_path** variable of type **GraphicsPath**, where you define the lines and points with which you draw the shape. The **SetInitialSize** method is used to initialize the shape with a given initial size. This method is only called once, when creating the object, with the total size of the drawing area. Each shape must create and initialize the corresponding **GraphicsPath** object in this method.

The parameterized constructor is used to create a copy of another shape and apply a transformation to it. The transformation is applied with the **Transform** method, which simply creates a **Matrix** object and applies the transformation to the **GraphicsPath** with its **Transform** method.

The shape is drawn by calling their **Draw** method, to which is passed the **Graphics** object where it should be drawn and a **Transformation** that should be applied. If this second parameter is null, the shape is simply drawn on the **Graphics**, otherwise, a copy is created and the transformation is applied to it, then it is drawn and it is returned as a result of the method.

Defining any shape is very simple; just implement the **SetInitialSize** method and a version of **ToString** so that the shape name appears in the list of the main form. In the Load event, the **IFSForm** form is responsible for listing all the classes of the assembly that descend from **ShapeBase** and add them to the list, so there is no need to do anything else. This is, for example, the implementation of a square:

`public class Square : ShapeBase`

{

public Square()

: base()

{

}

public Square(ShapeBase clon, Transformation tr)

: base(clon, tr)

{

}

public override void SetInitialSize(SizeF sz)

{

_path = new GraphicsPath();

_path.AddRectangle(new RectangleF(0f, 0f,

Math.Min(sz.Width, sz.Height),

Math.Min(sz.Width, sz.Height)));

}

public override string ToString()

{

return "Square";

}

}

And that's all. To further explore the subject, I can recommend the book Fractals Everywhere, by **M.F. Barnsley**, where you can find a more rigorous mathematical development of the **IFS**, and the classic Fractal Geometry of Nature, by **Benoit Mandelbrot**.