CSCE 441 Lecture 10

« previous | Wednesday, February 5, 2014 | next »

Fractals and Iterated Affine Transformations

A transformation $F(X)$ is contractive if, for all compact sets $X_{1}\neq X_{2}$,

$D_{H}(F(X_{1}),F(X_{2}))<D_{H}(X_{1},X_{2})$

compact set

a finite set

transformations on sets

A set is a collection of points

Apply point-wise transformation to all point within the set

distance

distance between identical sets should be 0

$D_{H}(X_{1},X_{2})=D_{H}(X_{2},X_{1})$

Hausdorff Distance

${\begin{aligned}d_{X_{1}\to X_{2}}&=\max _{x_{1}\in X_{1}}\left(\min _{x_{2}\in X_{2}}\left|x_{1}-x_{2}\right|\right)\\D_{H}&=\max {\left(d_{X_{1}\to X_{2}},d_{X_{2}\to X_{1}}\right)}\end{aligned}}$

Iterated Affine Transformations

Special class of fractals where each transformation is an affine transformation:

$F_{1}(x)=\left\{M_{1}\,x,F_{2}(x)=M_{2}\,x,\ldots \right\}$

Rotations, translation, and scaling by themselves are not contractive

Rendering Fractals

Given starting set $X_{0}$, inductively define $X_{i+1}=\bigcup _{j}F_{j}(X_{j})$

Attractor is $X_{\infty }$.

Serpinski's triangle: Scale by factor of 0.5 about each vertex of the large triangle

Apply transformations on previous shape again, and again, and again, etc.

Starting shape does not matter.

Perform BFS of "transformation tree"

Finding Transformations

Given a fractal built by iterated affine transformations, how do you determine the original transformation?

1. Locate a shape that covers the entire fractal
2. Find copies of that shape within the fractal
3. Use the three-point strategy to find the transformation of each copy.

Fractal Tennis

1. Start with any point on the fractal $x$ by applying $x=M_{rand}\,x$ several times.
2. Apply random transformations to that point to get corresponding points on the fractal:

for (int i = 0; i < 100; ++i)
    x = m[rand] * x;

for (int i = 0; i < 100000; ++i) {
    draw(x);
    x = m[rand] * x;
}