An IFS Fern

The examples on the Logistic Map and the Mandelbrot Set have shown surprisingly complex behaviour from simple quadratic equations. Here something simpler is considered: a set of linear equations.

Consider the following four linear transformations of a point in 2D space:

1. x= 0;y= 0.16y
2. x= 0.849x+0.037y; y=-0.037x+0.849y+1.6
3. x= 0.197x-0.226y; y= 0.226x+0.197y+1.6
4. x=-0.150x+0.283y; y= 0.260x+0.238y+0.44

What would happen if one started at a random point, say (0.5,0.5), picked one of the above four transformations at random and applied it, and then repeatedly selected one of the above transformations at random and applied it? It sounds like a recipe for a random scatter of dots.

Not a random scatter at all!

#!/usr/bin/python3
from random import randint
import numpy as np
import matplotlib.pyplot as plt

def ifs(x,y):
    r=randint(1,4)
    if (r==1):
        x=0
        y=0.16*y
    if (r==2):
        nx=0.849*x+0.037*y
        y=-0.037*x+0.849*y+1.6
        x=nx
    if (r==3):
        nx=0.197*x-0.226*y
        y=0.226*x+0.197*y+1.6
        x=nx
    if (r==4):
        nx=-0.15*x+0.283*y
        y=0.26*x+0.238*y+0.44
        x=nx
    return(x,y)
    
x=.5
y=.5

for i in range (1,100):
    (x,y)=ifs(x,y)

plt.axes().set_aspect('equal')
plt.xlim(-3,3)
plt.ylim(0,10)
plt.ion()
plt.show()
    
for i in range (200):
    vx=[]
    vy=[]
    for j in range (100):
        (x,y)=ifs(x,y)
        vx=vx+[x]
        vy=vy+[y]
    plt.plot(vx,vy,'k,')
    plt.pause(0.0001)

print("Done")
plt.ioff()
plt.show()    

The above code bundles points into collections of one hundred for efficiency before calling the plot routine. It plots 20,000 points, after discarding an initial 100 iterations. It should run in a little under half a minute.

The result is similar to the picture on this page, but distinctly sparser. The trick for making a better quality image reasonably quickly is to change the random selection of the four possible transformations. Whilst almost any scheme will ultimately produce the same result, if one biases in favour of the second transform then a well filled in fern is produced much faster.

The function ifs was modified as below. The probabilities used here are not optimal, but are a lot better than the previous uniform distribution.

def ifs(x,y):
    r=randint(1,10)
    if (r==1):
        x=0
        y=0.16*y
    elif (r<=8):
        nx=0.849*x+0.037*y
        y=-0.037*x+0.849*y+1.6
        x=nx
    elif (r==9):
        nx=0.197*x-0.226*y
        y=0.226*x+0.197*y+1.6
        x=nx
    elif (r==10):
        nx=-0.15*x+0.283*y
        y=0.26*x+0.238*y+0.44
        x=nx
    return(x,y)

IFS?

Iterated Function System.

The fern given above was found by Michael Barnsley, and looks remarkably natural. Other 2D and 3D geometric patterns can also be produced from a small number of transformations. In the book The Science of Fractal Images (Springer-Verlag, 1988), Barnsley descibes the above 2D fern as being reduced from a 3D fern, again using just four linear transformations, and states that "on a 68020 based workstation a single view of the 3D fern required one minute of computation." The Motorola 68020 was released in 1984 and used in some Apple Macintoshes and the Sun 3. His code must have been better optimsed than the code here.