Iterated function system 505225 226049176 2008-07-16T16:30:54Z Spot 152229 add construction diagram [[Image:Sierpinski1.png|thumb|right|250px|[[Sierpinski gasket]] created using IFS]] [[Image:Chris_Ursitti_fractal_0000.png|thumb|right|250px|Colored IFS designed by Chris Ursitti using [[Apophysis (software)|Apophysis]] software and rendered by the [[Electric Sheep]].]] In [[mathematics]], '''iterated function systems''' or '''IFS'''s are a method of constructing [[fractal]]s; the resulting constructions are always [[self-similar]]. '''IFS''' fractals as they are normally called can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the [[Sierpinski gasket]]. The functions are normally [[contraction mapping |contractive]] which means they bring points closer together and make shapes smaller. 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, [[ad infinitum]]. This is the source of its self-similar fractal nature. ==Definition== Formally, :<math>S = \bigcup_i^N f_i(S),\,</math> where :<math>S \subset \mathbb{R}^n\,</math> and :<math>f_i:\mathbb{R}^n\to\mathbb{R}^n.</math> are the [[iterated function|functions to be iterated]]. ''S'' is the fixed point of a [[Hutchinson operator]], which is the union of the functions <math>f_i</math>. ==Properties== The collection of functions <math>f_i</math> together with composition form a [[monoid]]. If there are only two such functions, the monoid can be visualized as a [[binary tree]], where, at each node of the tree, one may compose with the one or the other function (''i.e'' take the left or the right branch). In general, if there are ''k'' functions, then one may visualize the monoid as a full [[k-ary tree]], also known as a [[Cayley tree]]. ==Examples== [[Image:Chaosgame.gif|thumb|right|250px|Construction of an IFS by the [[chaos game]]]] Sometimes each function <math>f_i</math> is required to be [[linear]], or more accurately an [[affine transformation]] and hence can be represented by a [[matrix (mathematics)|matrix]]. However, IFSs may also be built from non-linear functions, including [[projective transformation]]s and [[Möbius transformation]]s. The [[Fractal flame]] is an example of an IFS with nonlinear functions The most common algorithm to compute IFS fractals is called the [[chaos game]]. It consists of picking a random point in the plane, then iteratively applying one of the functions chosen at random from the function system and drawing the point. An alternative algorithm is to generate each possible sequence of functions up to a given maximum length, and then to plot the results of applying each of these sequences of functions to an initial point or shape. 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. This makes zooming into an IFS construction normally impractical. Where a high degree of detail is required in a small area of the fractal, local construction methods based on calculating forward orbits and the fate of individual points may be more efficient (although no software for solving IFS does this). ===Example: a fractal "fern"=== [[Image:Fractal_fern_explained.png|thumb|right|150px|Fractal fern using IFS]] Here is an example of a fern-like image computed using an [[iterated function system]]. The first point drawn is at the origin (''x''<sub>0</sub> = 0, ''y''<sub>0</sub> = 0) and then the new points are iteratively computed by randomly applying one of the following four coordinate transformations: :''x''<sub>''n'' + 1</sub> = 0 :''y''<sub>''n'' + 1</sub> = 0.16 ''y''<sub>''n''</sub>. This coordinate transformation is chosen 1% of the time and maps any point to a point in the line segment shown in green in the figure. :''x''<sub>''n'' + 1</sub> = 0.2 ''x''<sub>''n''</sub>&nbsp;&minus;&nbsp;0.26&nbsp;''y''<sub>''n''</sub> :''y''<sub>''n'' + 1</sub> = 0.23 ''x''<sub>''n''</sub>&nbsp;+&nbsp;0.22 ''y''<sub>''n''</sub>&nbsp;+&nbsp;1.6. This coordinate transformation is chosen 7% of the time and maps any point inside the black rectangle to a point inside the red rectangle in the figure. :''x''<sub>''n'' + 1</sub> = &minus;0.15 ''x''<sub>''n''</sub> + 0.28 ''y''<sub>''n''</sub> :''y''<sub>''n'' + 1</sub> = 0.26 ''x''<sub>''n''</sub> + 0.24 ''y''<sub>''n''</sub> + 0.44. This coordinate transformation is chosen 7% of the time and maps any point inside the black rectangle to a point inside the dark blue rectangle in the figure. :''x''<sub>''n'' + 1</sub> = 0.85 ''x''<sub>''n''</sub> + 0.04 ''y''<sub>''n''</sub> :''y''<sub>''n'' + 1</sub> = &minus;0.04 ''x''<sub>''n''</sub> + 0.85 ''y''<sub>''n''</sub> + 1.6. This coordinate transformation is chosen 85% of the time and maps any point inside the black rectangle to a point inside the light blue rectangle in the figure. The first coordinate transformation draws the stem. The second draws the bottom frond on the left. The third draws the bottom frond on the right. The fourth generates successive copies of the stem and bottom fronds to make the complete fern. The recursive nature of the IFS guarantees that the whole is a larger replica of each frond. Note: The fern is within the range -5 <= x <= 5 and 0 <= y <= 10. ==Example== [[Image:Ifs-construction.png|thumb|right|400px|[[Ifs Construction]] IFS being made with two functions.]] The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the Hutchinson operator. Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal. ==History== Iterated function systems are a generalisation of the [[Cantor set]], first described in 1884, and of [[de Rham curve]]s, a type of self-similar curve described by [[Georges de Rham]] in 1957. IFS were conceived in their present form by [[John Hutchinson]] in 1981 and popularized by [[Michael Barnsley]]'s book ''Fractals Everywhere''. In 1992 [[Scott Draves]] developed the [[Fractal flame]] algorithm. ==See also== [[Image:Menger sponge (IFS).jpg|thumb|200px|[[Menger sponge]], a 3-Dimensional IFS.]] * [[L-system]] * [[Fractal compression]] * [[Fractal flame]] * [[Complex base systems]] ==External links== <!--===========================({{NoMoreLinks}})===============================--> <!--| DO NOT ADD MORE LINKS TO THIS ARTICLE. WIKIPEDIA IS NOT A COLLECTION OF |--> <!--| LINKS. If you think that your link might be useful, do not add it here, |--> <!--| but put it on this article's discussion page first or submit your link |--> <!--| to the appropriate category at the Open Directory Project (www.dmoz.org)|--> <!--| and link back to that category using the {{dmoz}} template. |--> <!--| |--> <!--| Links that have not been verified WILL BE DELETED. |--> <!--| See [[Wikipedia:External links]] and [[Wikipedia:Spam]] for details |--> <!--===========================({{NoMoreLinks}})===============================--> *[http://www.cut-the-knot.org/ctk/ifs.shtml A definition of IFS and a Java illustration with several built-in examples] at [[cut-the-knot]] *Scott Draves' [http://flam3.com/flame.pdf The Fractal Flame Algorithm] [[Category:Fractals]] [[de:Iteriertes Funktionensystem]] [[es:Sistema de funciones iteradas]] [[eo:Iteraciitaj sistemoj de funkcioj]] [[fr:Système de fonctions itérées]] [[hr:Sustav iterirane funkcije]] [[ja:反復関数系]] [[pl:IFS (geometria fraktalna)]] [[pt:Sistemas de funções iterativas]] [[sv:Itererande funktionssystem]]