Random iterated function system algorithm
The random iterated function system (IFS) is a very simple algorithm that can easily produce a large variety of fractals including but not exclusively cantor's set, serpinskis, dragon curves, koches and many others.
The algorithm is based around the use of transformations, namely axis rotation, translation and scaling. These transformations are used to draw the attractor pointwise (one point at a time). The generalisation resulting from using transformations means that these fractals can be drawn in an arbitrary number of dimensions.
The transformations are usually expressed as matrices, either as a single homogeneous matrix or a matrix for scaling and rotation and one for translation.
The algorithm also uses a weight for each of the transformations. The weight for each is either proportional to the determinant of the matrix or a small value for cases where the determinant is zero. The total of all the weights should add up to one. These weights can then be used a probabilities for picking a particular transformation. This weight is not strictly necessary but it does improve the performance of the algorithm a great deal.
Each IFS fractal is described as a weighted list of transformations. Amazingly only two transformations are necessary to produce a wealth of nice fractals but the more complex ones will require more. The ubiquitous fern requires four: the stem, left leaflet, right leaflet and the overall shape.
The probability of a given transformation being picked is found using the determinate of the transformation. The determinates are totalled up and each of the individual determinates are divided by this total. This results in a probability out of one for each of the transformations and a total probability of one for all the transformations. If a transformation has a determinate of zero (a pure rotation for example) it should be given a low but non-zero probability e.g. 0.01.
As previously stated the algorithm is very simple:
Start with a
point at the
origin P = (0,0)
FOR however many points you want DO
Pick a transformation, T, from the list with probability p(T)
Apply it to the point P = T*P
Draw the point p
END
Some of the literature suggests that you discard the first hundred or so points to give the algorithm a chance to converge to the attractor. I, personally, have never found this necessary as often the origin lies on the attractor anyway and if it doesn't who's going to notice a few stray points in the maelstrom this algorithm produces. I've never been able to spot more than three but I guess it depends on the application.