On this page we will describe two methods to construct
a self-similar fractals or an attractor of IFS (Iterated Function Systems).
Method of Successive Approximations
|
Looking at this picture one can easily understand,
how to construct self-similar fractal (Sierpinski's tetrahedron in this case).
It is necessary to take ordinary pyramid (tetrahedron), then cut its middle (octahedron).
As a result we obtain four small pyramids.
With each of them we repeat the same operation, e.t.c.
Notice, that every such iteration appear to be
an attractor of recurrent iterated function system
(RIFS, also known as Digraph IFS or Graph-directed IFS)
and therefore their can be built by IFS Builder 3d.
|
Construction by Points or Probabilistic Method
This is the easiest method to implement on computer.
For simplicity let's consider the case of the plain self-affine set.
Let {S1,..,Sm} will be some system of affine contractive maps.
Maps Si can be represented as:
Si(x)=Ai( x-oi )+oi,
where Ai - some matrix of 2x2 size
and oi - a vector.
- As the starting point we will take the fixed point of the
first map S1:
x := o1;
Here we use that all fixed points of contractions
S1,..,Sm belong to the fractal.
As the starting point we can choose any point, and
the generated sequence of points will converge to the fractal anyway,
but some wrong points will appear on the screen.
- Draw the current point x=(x1,x2) on the screen:
putpixel(x1,x2,15);
- Select in a random way a number j from 1 to m and recalculate coordinates
of the x point:
j:=Random(m)+1;
x:=Sj(x);
- Go to step 2, or stop if we done sufficiently many number of iterations.
Remark. If the contraction coefficients of maps Si are different,
then the fractal will be filled with points irregularly.
In a case, when maps Si are similarities,
this can be avoided by small complication of algorithm.
On the 3-rd step of algorithm, number j from 1 to m should be
selected by probabilities p1=r1s,..,pm=rms,
where ri denotes similarity coefficient of the map Si,
and number s (known as similarity dimesion) is found from the equation
r1s+...+rms=1.
This equation can be solved, for example, by Newton method.
Such method is used by Fractracer program and many others.
|