Iterated function system
IFS fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D.
The functions are normally contractive, which means they bring points closer together and make shapes smaller.
Formally, an iterated function system is a finite set of contraction mappings on a complete metric space.
, such a system of functions has a unique nonempty compact (closed and bounded) fixed set S.[3] One way of constructing a fixed set is to start with an initial nonempty closed and bounded set S0 and iterate the actions of the fi, taking Sn+1 to be the union of the images of Sn under the fi; then taking S to be the closure of the limit
via The existence and uniqueness of S is a consequence of the contraction mapping principle, as is the fact that for any nonempty compact set
(For contractive IFS this convergence takes place even for any nonempty closed bounded set
Recently it was shown that the IFSs of non-contractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in X) can yield attractors.
These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.
The most common algorithm to compute IFS fractals is called the "chaos game".
Each of these algorithms provides a global construction which generates points distributed across the whole fractal.
If a small area of the fractal is being drawn, many of these points will fall outside of the screen boundaries.
[5] PIFS (partitioned iterated function systems), also called local iterated function systems,[6] give surprisingly good image compression, even for photographs that don't seem to have the kinds of self-similar structure shown by simple IFS fractals.
[7] Very fast algorithms exist to generate an image from a set of IFS or PIFS parameters.
It is faster and requires much less storage space to store a description of how it was created, transmit that description to a destination device, and regenerate that image anew on the destination device, than to store and transmit the color of each pixel in the image.
[6] The inverse problem is more difficult: given some original arbitrary digital image such as a digital photograph, try to find a set of IFS parameters which, when evaluated by iteration, produces another image visually similar to the original.
IFSs were conceived in their present form by John E. Hutchinson in 1981[3] and popularized by Michael Barnsley's book Fractals Everywhere.
IFSs provide models for certain plants, leaves, and ferns, by virtue of the self-similarity which often occurs in branching structures in nature.
