Click here to Skip to main content
15,119,285 members
Articles / Programming Languages / C#
Article
Posted 22 Jan 2017

Stats

9.3K views
300 downloads
11 bookmarked

Iterated Function Systems and self similar fractals

Rate me:
Please Sign up or sign in to vote.
5.00/5 (14 votes)
22 Jan 2017CPOL6 min read
A simple way to build a wide family of fractals

Introduction

In this article I will show how to use a set of a few contractive affine transformations to generate fractals that can aproximate real world objects. The Iterated Function Systems (IFS) is a method developed in 1985 by M.F. Barnsley, and is one of the basis of some image compression methods.

I have developed a simple desktop application to illustrate the two basic algorithms to build fractals using this method. The IFSDrawer solution is written in c# using Visual Studio 2015.

Background

An affine transformation of a point in the plane is an application of the form:

Affine Transformation

Off course, this can be extended to spaces with more than two dimensions, but we will work with two-dimensional points.

With the e and f coefficients, we can displace the point in the horizontal and vertical directions.

When the b and c coefficients have a value of zero, the x and y coordinates are multiplied by the coefficients a and d. This can be used to enlarge or shrink a figure, and to create a symmetry horizontal and/or vertical by giving negative values to these coefficients.

On the other hand, you can use the b and c coefficients to interchange the x and y coordinates, if you leave a and d with a value of zero.

Yo can rotate the points of a figure an angle ϕ giving to the coefficients the values a=cosϕ, b=-sinϕ, c=sinϕ and d=cosϕ.

You can combine various transformations in one calculating the product of their matrices.

The IFS are simply a set of n affine transformations, which you apply iteratively to a given point or set of points, creating a series that converges to a fractal set which is the attractor of the system. The transformations must be contractive, which means that the coefficients must be between 0 and 1.

There are two basic algorithms. With the deterministic algorithm, you start applying the n transformations to an arbitrary set of points, obtaining n transformed sets. You apply iteratively the n transformations again and again to all the sets obtained in the previous step. In the step k you have nk transformed sets. When you draw these sets, you can see how the union of all of them converges to the attractor of the system, a self-similar fractal. Normally you won't need more than 10 iterations.

In the random algorithm, you apply only one of the functions of the system to a single point. All the functions have a probability assigned, being the sum of all of them 1. In each iteration, you take a random number between 0 and 1, then, you go suming the probabilities of each function until the result is greater than this random number, the corresponding function is selected and applied to the point, and so on, normally a big number of times, about 10000 or more.

Using the application

Once started the IFSDrawer application, you can use the second button in the toolbar to open a sample file, located in the Samples folder of the application. Open the Sierpinski.ifs file to see an example of the determinsitic algorithm:

The IFSDrawer application

Before you can start the process, you have to use the last button in the toolbar to check the values of the different transformations defined by their coefficients in each row of the grid. The last column, P, is used to define the probabilities in the random version of the algorithm. Leave it blank to use the deterministic version of the algorithm.

In the right side, you have a list box where you can select a shape to which apply the deterministic algorithm. Then you can use the button with the green arrow, in the middle of the toolbar, to iterate the system step by step.

The grid allows define formulas in their cells, so you don't have to use a calculator. Look in this article for the syntax of the formulas (here in spanish). In this project I have added the constants _pi, _e, for the pi and e numbers, _rand, to give a random number between 0 and 1, and _width and _height, with the values of the width and height of the current drawing.

You can add a new transformation, or remove the selected rows, by using the other two buttons at the right of the toolbar. The buttons at the left of the toolbar are for clear all, open a file, save the transformations to a file, save the image to a file and copy the image to the clipboard, respectively.

The control is slightly different for the random algorithm. Open, by example, the Leaf.ifs file and click the check button:

Random algorithm controls

Now, in the middle of the toolbar, there are two text boxes where you can set the number of iterations of the algorithm and a scale factor for the final drawing. Instead of going step by step, as the number of iterations is high, all the iterations will be made when you press the buton with two green arrows.

Using the code

The code of the application is divided into four projects. The BNFUP project is the expression compiler. You can read more on it in this article (here in spanish). The GridFormulas project is the implementation of the math formulas for the grid, and FormulaDataGridView is the implementation of the DataGridView control.

The application itself is in the IFSDrawer project. This is the Transformation class, used to store each affine transformation.

C#
[Serializable]
public class Transformation
{
    public Transformation()
    {
    }
    public object A { get; set; }
    public object B { get; set; }
    public object C { get; set; }
    public object D { get; set; }
    public object E { get; set; }
    public object F { get; set; }
    public object P { get; set; }
    public double AValue
    {
        get
        {
            if (A == null)
            {
                return double.NaN;
            }
            if (A is FormulaBase)
            {
                return (A as FormulaBase).Value;
            }
            return (double)A;
        }
    }
    public double BValue
    {
        get
        {
            if (B == null)
            {
                return double.NaN;
            }
            if (B is FormulaBase)
            {
                return (B as FormulaBase).Value;
            }
            return (double)B;
        }
    }
    public double CValue
    {
        get
        {
            if (C == null)
            {
                return double.NaN;
            }
            if (C is FormulaBase)
            {
                return (C as FormulaBase).Value;
            }
            return (double)C;
        }
    }
    public double DValue
    {
        get
        {
            if (D == null)
            {
                return double.NaN;
            }
            if (D is FormulaBase)
            {
                return (D as FormulaBase).Value;
            }
            return (double)D;
        }
    }
    public double EValue
    {
        get
        {
            if (E == null)
            {
                return double.NaN;
            }
            if (E is FormulaBase)
            {
                return (E as FormulaBase).Value;
            }
            return (double)E;
        }
    }
    public double FValue
    {
        get
        {
            if (F == null)
            {
                return double.NaN;
            }
            if (F is FormulaBase)
            {
                return (F as FormulaBase).Value;
            }
            return (double)F;
        }
    }
    public double PValue
    {
        get
        {
            if (P == null)
            {
                return double.NaN;
            }
            if (P is FormulaBase)
            {
                return (P as FormulaBase).Value;
            }
            return (double)P;
        }
    }
}

The A, B, etc. properties are of type object as they can contain double values or FormulaBase objects. You can obtain their values converted to double with the AValue, BValue, etc. properties. This class is only used to store the data, and it doesn't have functionality.

All the shape classes are descendant of the ShapeBase abstract class:

C#
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 constructor with parameters is used to create a copy of the given shape and apply to it the given transformation.

The figure is stored in a GraphicsPath object, in the variable _path, and it is created in the method SetInitialSize, which all the shapes must override and implement.

The public Draw method, applies a transformationto the shape and draws it in the given Graphics object. It returns a transformed copy of itself.

This is, for example, the implementation of a triangular shape:

C#
public class EquilateralTriangle : ShapeBase
{
    public EquilateralTriangle() : base()
    {
    }
    public EquilateralTriangle(ShapeBase clon, Transformation tr) : base(clon, tr)
    {
    }
    public override void SetInitialSize(SizeF sz)
    {
        float szm = Math.Min(sz.Width, sz.Height);
        PointF p1 = new PointF(0f, 0f);
        PointF p2 = new PointF(-szm * (float)Math.Cos(2 * Math.PI / 3), szm * (float)Math.Sin(2 * Math.PI / 3));
        PointF p3 = new PointF(szm, 0f);
        _path = new GraphicsPath();
        _path.AddLine(p1, p2);
        _path.AddLine(p2, p3);
        _path.AddLine(p3, p1);
    }
    public override string ToString()
    {
        return "Equilateral Triangle";
    }
}
public class FilledEquilateralTriangle : EquilateralTriangle
{
    public FilledEquilateralTriangle() : base()
    {
        _fill = true;
    }
    public FilledEquilateralTriangle(ShapeBase clon, Transformation tr) : base(clon, tr)
    {
        _fill = true;
    }
    public override string ToString()
    {
        return "Filled " + base.ToString();
    }
}

The only method you have to implement is SetInitialSize, to create the figure, and override ToString to show their name in the shape list box.

The deterministic algorithm is implemented in the click event handler of the bStep button:

C#
private void bStep_Click(object sender, EventArgs e)
{
    try
    {
        // New generation of shapes
        List<ShapeBase> lnw = new List<ShapeBase>();
        // Create the bitmap
        int hv = Math.Min(pbDraw.Size.Width, pbDraw.Size.Height);
        Bitmap bmp = new Bitmap(hv + 1, hv + 1);
        Graphics gr = Graphics.FromImage(bmp);
        gr.FillRectangle(Brushes.White, new Rectangle(0, 0, hv + 1, hv + 1));
        // Process all shapes
        foreach (ShapeBase sh in _lShapes)
        {
            // Apply every function to each shape
            foreach (Transformation t in _ifs)
            {
                // Add new generated shape
                lnw.Add(sh.Draw(gr, t));
            }
        }
        _lShapes = lnw;
        Bitmap oldimg = pbDraw.Image as Bitmap;
        bmp.RotateFlip(RotateFlipType.RotateNoneFlipY);
        pbDraw.Image = bmp;
        if (oldimg != null)
        {
            oldimg.Dispose();
        }
        _step++;
        lStep.Text = "Step " + _step.ToString();
    }
    catch (Exception ex)
    {
        MessageBox.Show(ex.Message);
        lStep.Text = "";
        bStep.Enabled = false;
    }
}

As you can see, it is very simple. Process the list of shapes and apply to each one all the transformations and draw them on the bitmap. In each step, a new generation of shapes is created and substitutes the previous one.

The random algorithm is implemented in the click event handler of the bRandom button:

C#
private void bRandom_Click(object sender, EventArgs e)
{
    try
    {
        // Get parameter values
        int iterations = 5000;
        if (!int.TryParse(txtIterations.Text, out iterations))
        {
            MessageBox.Show("Integer no valid");
            txtIterations.SelectAll();
            txtIterations.Focus();
        }
        if (iterations < 100)
        {
            iterations = 100;
        }
        else if (iterations > 50000)
        {
            iterations = 50000;
        }
        txtIterations.Text = iterations.ToString();
        float scale = 0f;
        if (!float.TryParse(txtZoom.Text, out scale))
        {
            MessageBox.Show("Number not valid");
            txtZoom.SelectAll();
            txtZoom.Focus();
        }
        if (scale <= 0f)
        {
            scale = 1f;
        }
        txtZoom.Text = scale.ToString();
        // Create the Bitmap
        int hv = Math.Min(pbDraw.Size.Width, pbDraw.Size.Height);
        Bitmap bmp = new Bitmap(hv + 1, hv + 1);
        Graphics gr = Graphics.FromImage(bmp);
        gr.FillRectangle(Brushes.White, new Rectangle(0, 0, hv + 1, hv + 1));
        pbDraw.Image = bmp;
        Random rnd = new Random();
        // Point to iterate
        PointF pt = new PointF(0f, 0f);
        // Center of the image
        Point pc = new Point(bmp.Width / 2, bmp.Height);
        for (int ix = 0; ix < iterations; ix++)
        {
            double vr = rnd.NextDouble();
            // Select a function according with the probabilities
            Transformation t = _ifs[_ifs.Count - 1];
            double p = _ifs[0].PValue;
            for (int it = 0; it < _ifs.Count - 1; it++)
            {
                if (vr <= p)
                {
                    t = _ifs[it];
                    break;
                }
                p += _ifs[it + 1].PValue;
            }
            // Transform the current point
            float x = (float)(pt.X * t.AValue + pt.Y * t.BValue + t.EValue);
            float y = (float)(pt.X * t.CValue + pt.Y * t.DValue + t.FValue);
            pt = new PointF(x, y);
            // Scale result
            Point pp = new Point((int)(pt.X * scale), (int)(pt.Y * scale));
            // Discard the first 10 iterations and points beyond the image
            if ((ix > 10) && (pp.X + pc.X >= 0f) && (pc.Y - pp.Y >= 0f) && (pp.X + pc.X < bmp.Width) && (pc.Y - pp.Y < bmp.Height))
            {
                bmp.SetPixel(pp.X + pc.X, pc.Y - pp.Y, Color.Black);
            }
        }
    }
    catch (Exception ex)
    {
        MessageBox.Show(ex.Message);
        bRandom.Enabled = false;
    }
}

In this case, the same point is used each time, and only a function is selected to apply the transformation to the point. The probabilities are used to select the application. The first 10 points are discarded, as they have a great probability to are too far from the attractor.

And that's all, thanks for read!!!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Miguel Diaz Kusztrich
Software Developer (Senior) Free lance
Spain Spain
I'm working with computers since the 80's of the past century, when I received as a present a 48K Spectrum which changed all my life plans, from a scientific career to a technical one. I started working in assembler language, in low lewel systems, mainly in the electromedical field. Today I work as a freelance, mainly in .NET Framework / database solutions, using the C# language.

I'm interested in scientific computer applications, and I,m learning AI and data analytics technics. I also own a technical blog, http://software-tecnico-libre.es/en/stl-index, where I publish some of the practice works of this learning process.

Comments and Discussions

 
QuestionWell Done! Pin
Bassam Abdul-Baki3-Feb-17 5:40
professionalBassam Abdul-Baki3-Feb-17 5:40 
SuggestionContraction Pin
Stefan_Lang27-Jan-17 0:51
mveStefan_Lang27-Jan-17 0:51 
PraiseIt is amazing... Pin
James Hunter Ross24-Jan-17 14:32
MemberJames Hunter Ross24-Jan-17 14:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.