Tuesday, June 23, 2009

The Fern as an Iterated Function System

From Curran Kelleher, "Recursive Structures and Processes," MIT Open Courseware (24 Aug. 2007) 10-12.

1.2.7 Iterated Function Systems [= "a method of constructing fractals; the resulting constructions are always self-similar" (wikipedia)]

Iterated Function Systems (IFS) take a single point and move it around re­peatedly, plotting a point on the screen for each move. The point is moved according to a mapping function, which is chosen probabalistically from several possible mapping functions.

["The fractal is made up of the union ['collage'] of several copies of itself, each copy being transformed by a function (hence 'function system'). . . . The functions are normally contractive. . . . Hence the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself" (wikipedia).]

[Barnsley's fern, cf. Michael Barnsley, Fractals Everywhere (Academic P, 1988)]

The fern IFS is a system of four mapping functions. Each of these functions is a mapping from the outermost rectangle to another, smaller rectangle. The system is comprised of the following four functions, which map from any point inside the outermost black rectangle . . .

1. to a point on the green part of the stem (1% of the time)
2. to a point in the red rectangle, the lowest left branch (7% of the time)
3. to a point in the dark blue rectangle, the lowest right branch (7% of the time)
4. to a point in the light blue rectangle, which spirals everything upwards and smaller (85% of the time)

Figure 1.1: The rectangles used in the coordinate transformations (approx­imately), and the image generated by our program.

Here is Java code which implements this IFS:

Is this algorithm recursive? The code itself is not recursive, it is just repetitive. However, the mappings are recursive, because they are applied to themselves eventually. The ļ¬lling in of the fractal object happens because of the randomness introduced by selecting probabilistically which of the four mappings to apply.

See wikipedia.

No comments: