Iterated Function Systems: The Barnsley Fern & Chaos Game

Contraction mappings and the attractor

The engine behind IFS is the Banach Fixed-Point Theorem: any contraction mapping has a unique fixed point, and repeated application converges to it from any starting position. An Iterated Function System is a finite set of contraction mappings {f₁, …, fₙ} on ℝⁿ, usually affine (fᵢ(x) = Aᵢx + bᵢ with all eigenvalues of Aᵢ under 1 in magnitude). The IFS attractor A is the unique compact set satisfying:

A = f₁(A) ∪ f₂(A) ∪ ... ∪ fₙ(A)

Starting from ANY compact set S₀:
S_{k+1} = f₁(Sₖ) ∪ ... ∪ fₙ(Sₖ)  →  A  (Hausdorff metric, exponentially fast)

Whether you start from a point, a filled square, or a random scribble, the orbit converges to the same fractal attractor — self-similarity by definition.

The chaos game

Tracking exponentially growing sets is impractical, so Michael Barnsley's chaos game (1988) traces a single random orbit instead: pick a transformation at random weighted by probability pᵢ, apply it, plot the point, repeat hundreds of thousands of times (skipping the first ~20 for warm-up). A natural probability choice is pᵢ ∝ |det(Aᵢ)|, proportional to the area each transformation covers, giving uniform density on the attractor. The whole algorithm runs in O(N) — any IFS fractal renders in milliseconds.

live demo · the chaos game painting a fractal attractor point by point● LIVE

The Barnsley fern: four transforms, one frond

Just four affine transformations produce a structure visually identical to a real fern: one (p=0.01) contracts the whole fern to a tiny stem, one (p=0.85) copies the fern at 85% scale for the main frond body, and two more (p=0.07 each) generate the left and right leaflets, rotated roughly 83° and 37°. The probabilities encode each transform's relative weight in the attractor's area — set them all equal instead, and the chaos game still converges to the same fern shape, but the stem and leaflets get oversampled while the main body is starved of points.

Fractal dimension and the collage theorem

For a self-similar IFS satisfying the open set condition (transformed copies don't overlap), the Hausdorff dimension d solves the Moran equation Σᵢ rᵢᵈ = 1, where rᵢ is each transform's contraction ratio — giving the Sierpiński triangle dimension log(3)/log(2) ≈ 1.585 and the Koch curve log(4)/log(3) ≈ 1.262. Running the problem backward is the Collage Theorem: if you can cover a target image with transformed copies of itself within error ε, the IFS attractor approximates the target with error bounded by ε/(1−c), where c is the maximum contraction ratio. This is the basis of fractal image compression — encoding an image as a small set of self-referential transformations rather than raw pixels.

Frequently asked questions

What is an Iterated Function System?

An Iterated Function System (IFS) is a finite set of contraction mappings, usually affine transformations, whose unique fixed point in the space of compact sets is a fractal attractor A satisfying A = f1(A) ∪ f2(A) ∪ ... ∪ fn(A). Starting from any shape and repeatedly applying the maps converges to the same attractor regardless of the starting point.

How does the chaos game render an IFS fractal?

Instead of tracking exponentially growing sets, the chaos game traces a single random orbit: starting from any point, repeatedly pick one transformation at random (weighted by probability) and apply it, plotting each new point after a short warm-up. After a few hundred thousand iterations the attractor becomes visible, and the algorithm runs in O(N) time.

What is the Collage Theorem?

The Collage Theorem is the inverse problem: given a target image, if you can cover it with transformed copies of itself (a collage) within error epsilon, the resulting IFS attractor will approximate the target with error bounded by epsilon divided by (1 minus the maximum contraction ratio). This is the mathematical basis of fractal image compression.

Try it live

Everything above runs in your browser — open IFS Fractals and watch the Barnsley fern, Sierpinski triangle, Dragon curve and custom affine transforms emerge from chaos, live.

▶ Open IFS Fractals simulation