Article directory
- Algorithm Description
- Algorithm implementation
- Case Analysis
IFS is the abbreviation of Iterated Function System. It is a mathematical tool often used in computer graphics to generate fractal images. In IFS, a set of iterative functions is defined, and starting from a simple initial value, By repeatedly applying these functions, complex structures can be generated. These iterative functions usually have some similarity or transformation properties, such as translation, scaling, rotation, etc. In computer graphics, IFS is used to create fractal images, where each pixel Or pixel blocks are processed by an iterative function to generate the final image. This method can generate images with complex structures of natural phenomena (such as mountains, clouds, trees, etc.). In addition, random IFS is a special kind of IFS in which iterative Both the function and the initial values are chosen randomly. This method is often used to create abstract art and computer-generated artwork.
In this article, only linear random IFS iterations are considered on the plane.
Algorithm description
On a two-dimensional plane, we have the following affine transformation:
(
x
‘
y
‘
)
=
(
a
b
c
d
)
(
x
y
)
+
(
e
f
)
\begin{pmatrix} x^\prime\y^\prime \end{pmatrix} =\begin{pmatrix} a & amp;b\\c & amp;d \end {pmatrix} \begin{pmatrix} x\y \end{pmatrix} + \begin{pmatrix} e\f \end{pmatrix}
(x′y′?)=(ac?bd?)(xy?) + (ef?)
For a more complex graphic, multiple different affine transformations may be needed to achieve it. The affine transformation family
{
ω
n
}
\{\omega_n\}
{ωn?} controls the structure and shape of the graph. Since the form of affine transformation is the same, different shapes depend on the coefficients of affine transformation. In addition, the affine transformation family
{
ω
n
}
\{\omega_n\}
In {ωn?}, the probability of each affine transformation being called is not necessarily the same. That is to say, the number of points falling into each part of the graph is not necessarily the same. This requires the introduction of a New quantity, namely affine transformation
ω
\omega
The probability that ω is called
P
P
P. Thus, 6 affine transformation coefficients
{
a
,
b
,
c
,
d
,
e
,
f
}
\{a,b,c,d,e,f\}
{a,b,c,d,e,f} and a probability
P
P
P constitutes the most critical part of the linear random IFS iteration – the IFS code.
Given an IFS code, we can perform multiple iterations to finally generate the required graphics.
The linear stochastic IFS iteration method can be described as follows:
- Input: IFS code
A
\bm A
A, number of iterations
n
n
n, iteration initial value
x
0
\bm x_0
x0?
- Output: iterative path
p
p
p
- initialization
P
P
P is
A
A
The last column of A is accumulated element by element.
- for
i
i
i from
1
1
1 to
n
n
n Follow these steps:
- generate
[
0
,
1
)
[0,1)
[0,1) Uniformly distributed random numbers
r
r
r
- exist
P
P
Find the first one in P greater than
r
r
subscript of r
d
d
d
- take advantage of
A
A
A’s
d
d
Line d performs an affine transformation and adds to
p
p
within p
- generate
- return
p
p
p
Algorithm implementation
First preprocess as follows:
#include <armadillo> #include <stdio.h> #include <random> #include <ctime> using namespace arma; using namespace std;
Then implement linear random IFS iteration:
/*
* Linear random IFS iteration
* ifs: IFS code
* n: number of iterations
* x0: initial value of iteration
* path: iteration process saving path
* e: Real number comparison accuracy
*
* Return (bool):
* true : iteration failed
* false: iteration successful
*/
bool IFS_iteration(const mat & amp;ifs, unsigned n, const char *path, vec x0 = randu(2), const double & amp;e = 1e-6)
{<!-- -->
if (ifs.n_cols != 7 || x0.n_elem != 2)
return true;
if (!n)
return true;
vec p = cumsum(ifs.col(6));
if (abs(p.at(p.n_elem - 1) - 1.) > e)
return true;
FILE *file;
if (fopen_s( & amp;file, path, "w"))
return true;
fprintf(file, "x,y\\
%f,%f", x0.at(0), x0.at(1));
static default_random_engine engine(time(nullptr));
static uniform_real_distribution<double> distribution;
do
{<!-- -->
double d(distribution(engine));
unsigned i(0);
while (p.at(i) <= d)
if ( + + i == p.n_elem)
{<!-- -->
--i;
break;
}
d = ifs.at(i, 0) * x0.at(0) + ifs.at(i, 1) * x0.at(1) + ifs.at(i, 4);
x0.at(1) = ifs.at(i, 2) * x0.at(0) + ifs.at(i, 3) * x0.at(1) + ifs.at(i, 5);
x0.at(0) = d;
fprintf(file, "\\
%f,%f", x0.at(0), x0.at(1));
} while (--n);
fclose(file);
return false;
}
Example analysis
It is known that the IFS code of a certain tree is as follows:
A
=
(
0.06
0
0
0.6
0
0
0.1
0.04
0
0
?
0.5
0
1
0.1
0.46
0.32
?
0.34
0.38
0
0.6
0.1
0.48
?
0.15
0.17
0.42
0
1
0.23
0.43
0.37
?
0.26
0.48
0
1
0.23
0.42
?
0.36
0.35
0.31
0
0.8
0.24
)
A=\begin{pmatrix} 0.06 & amp;0 & amp;0 & amp;0.6 & amp;0 & amp;0 & amp;0.1\ 0.04 & amp;0 & amp;0 & amp;- 0.5 & amp;0 & amp;1 & amp;0.1\ 0.46 & amp;0.32 & amp;-0.34 & amp;0.38 & amp;0 & amp;0.6 & amp;0.1\ 0.48 & amp ;-0.15 & amp;0.17 & amp;0.42 & amp;0 & amp;1 & amp;0.23\ 0.43 & amp;0.37 & amp;-0.26 & amp;0.48 & amp;0 & amp;1 & amp;0.23\ 0.42 & amp;-0.36 & amp;0.35 & amp;0.31 & amp;0 & amp;0.8 & amp;0.24 \end{pmatrix}
A=?0.060.040.460.480.430.42?000.32?0.150.37?0.36?00?0.340.17?0.260.35?0.6?0.50.380.420.480.31?000000?010.6110.8 ?0.10.10.10.230.230.24
Substitute into the program and use Origin to draw the following tree iterative phase diagram:
