CSCE 441 Lecture 10

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

Fractals and Iterated Affine Transformations

A transformation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(X)} is contractive if, for all compact sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1 \ne X_2} ,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_H(X_1, X_2) = D_H(X_2, X_1)}

Hausdorff Distance

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}

Iterated Affine Transformations

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_0} , inductively define Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{i+1} = \bigcup_{j} F_j(X_j)}

Attractor is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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?

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

Fractal Tennis

Start with any point on the fractal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} by applying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = M_{rand} \, x} several times.
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;
}