Transcript HWS Robot Festival

Iterated Function Systems (IFS) and
Fractals
Math 204
Linear Algebra
November 16, 2007
Affine Transformations
Affine transformations F: R2 => R2 are mappings made by
2 x 2 matrix multiplication then translation.
An affine map is defined by four numbers: a b c d e f
Affine maps combine four possible actions on a triangle.
Facts about affine maps

The composition of two affine maps is an affine map.
 Affine maps can be defined by triangle mappings. That is,
if we describe how to map the vertices of a triangle ABC
to triangle DEF, this defines an affine mapping.
 An affine map F: R2 => R2, is called a contraction if for
any two points p, q in the plane, the distance between
F(p) and F(q) is less than the original distance between p
and q.
 Given a geometric figure S in the plane, we can ask what
“collages” we can make by applying several contraction
mappings to S and plotting all these contracted versions
of S together.
Example of a Fractal Collage:
Sierpinski Triangle
Affine Contractions Create Collages

Collage Theorem: Given any finite collection of
contractions F1, F2, … , Fn, there is a unique
geometric object S such that
S = F1(S) U F2(S) U … U Fn(S)

That is, S is the unique collage defined by these
contractions.
 FDESIGN is a old DOS program which allows us
to easily design collages by drawing triangle
mappings then showing us the resulting unique
figure that is defined by the mappings.
Barnsley Fern
showing the
four
contractions
which define
this figure
Random Iteration Algorithm: How
FDESIGN draws pictures

FDESIGN works by keeping track of your affine
mappings and assigning a probability p to each
one. FractInt IFS format: a b c d e f p
 Starting with a random point (x,y) FDESIGN
picks one of your affine maps according to its
probability, applies it to the point (x,y) to get a
new point and repeats (iterates) this action
endlessly. Recall this is same as picking a
random value 1-3 then shrinking 1/2 way to
toward the vertex of our Sierpinski triangle.
 Fact: This random iteration algorithm will draw
as much of our collage as we wish if we wait
long enough.