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:
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:
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:
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.
[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:
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:
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:
private void bStep_Click(object sender, EventArgs e)
{
try
{
List<ShapeBase> lnw = new List<ShapeBase>();
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));
foreach (ShapeBase sh in _lShapes)
{
foreach (Transformation t in _ifs)
{
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:
private void bRandom_Click(object sender, EventArgs e)
{
try
{
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();
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();
PointF pt = new PointF(0f, 0f);
Point pc = new Point(bmp.Width / 2, bmp.Height);
for (int ix = 0; ix < iterations; ix++)
{
double vr = rnd.NextDouble();
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;
}
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);
Point pp = new Point((int)(pt.X * scale), (int)(pt.Y * scale));
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!!!
