GS 2003/Math - Collins
Lab 10
Fractals: MRCM and IFS

Preliminaries

MRCM = Multiple Reduction Copy Machine
IFS = Iterated Function System

Finish Your Homework

If you haven't finished finding the transformations for your
homework, you need to finish it now.  You can use MATLAB to
help.  (If you did it already, you can follow along to check
or jump on down to the next section).

Here's what you should have: 1 Unit Square, 4+ Parallelograms
You should know the vertices of all the figures.

To find the transformation from the Unit Square to a Pgram:
   Consider the vertices of the square: A,B,C where A(0,0), B(1,0), C(0,1)
   And the corresponding vertices on the Pgram: A',B',C' where
       A'(x1,y1), B'(x2,y2), C'(x3,y3)

   We want to find values a, b, c, d, e, f so that
       nx = a x + b y + c    and   ny = d x + e y + f
   transforms the Unit Square to the Pgram, in particular A to A', etc.
   We get the following equations for a-f:
      a 0 + b 0 + c = x1     d 0 + e 0 + f = y1
      a 1 + b 0 + c = x2     d 1 + e 0 + f = y2
      a 0 + b 1 + c = x3     d 0 + e 1 + f = y3

   Note: you will have values for x1,x2,x3,y1,..

   Solve by hand or use MATLAB to solve these systems:
      M = [0 0 1; 1 0 1; 0 1 1];
      b1 = [x1;x2;x3];    % use the values not the symbols
      b2 = [y1;y2;y3];
      M\b1   % these are the values for a, b, c
      M\b2   % these are the values for d, e, f
   For the rest of the Pgrams, you only need to change
   the matrices  b1  and   b2  to find the new values for a-f.

Make a Cool Image I

If you have your transformations, we need to save them so
MATLAB can use them.  Make a file mytrans.m that
has your transformations (as 3x3 matrices) in it.  Label
the transformations T1, T2, etc.

As an example, it might look like this:
   
   T1 = [1/2 0 0;0 1/2 0;0 0 1];
   T2 = [1/2 0 1/2;0 1/2 0;0 0 1];
   T3 = [1/2 0 1/4;0 1/2 sqrt(3)/4;0 0 1];
   

If you need, you can build them from transformation primatives, like
scalings, rotations, etc.

Our first function/script will be the MRCM.  The idea is simple:
   1. Take an image (in our case a collection of points)
   2. Apply each transformation to the image creating a new image 
      (in our case a new, bigger, set of points)
   3. Repeat the application, but now to the new figure, again and again
   4. Draw the results

You also need a simple figure drawn in the unit square to start with.

(Details)
You'll need the function transform.m from the previous two
labs (make sure you have a clean copy if you made any changes to it).

The key step is #2 and it is executed in MATLAB as follows (if pts
  contains the points of our figure)

   p1 = transform(pts,T1);
   p2 = transform(pts,T2);
   p3 = transform(pts,T3);    % do for each transform you have
   np = [p1; NaN NaN; p2; NaN NaN; p3];   % combine the points into one figure


To repeat this you'll need to apply the transformations to np
or change pts to np, or do something else to put it
in a for loop (you only need to repeat about 7-9 times)

To graph the results, we do it just like in Lab 8:
   plot(np(:,1),np(:,2))

Make a Cool Image II

Our second function/script will be the IFS.  The idea is even simpler:
   1. Take a point somewhere in the square.
   2. Pick a random number r from 1 to k (k = number of transf)
   3. Apply transformation r to the point, creating a new point.
   4. Repeat #2,#3 to the new point, again and again
   5. Plot all the points you produced

(Details)

For the random number use r = floor(k*rand(1)) + 1;
Use either switch/case or if/then/else to select between
    the various transformations
Use transform.m to do the transformation or do it yourself
You'll want to loop through this 10000 times or more
If x is a column vector with your point in it after i iterations, 
    save it to a variable z by z(:,i) = x;
Speed hint: if you pre-allocate space for z your function/script will
    run faster; if you'll store N points: z = zeros(2,N); 
Plot the final result using plot(z(1,:),z(2,:),'.')

I put a general version of this program down below as ifs.m, call
it by z = ifs(10000,T1,T2,T3,T4) or with however many points
you want to use and with however many transformations you have.

Assignment

1. Get all your programs working for Cool Image I and Cool Image II
2. Using the transformations you created, use both methods to
   generate fractal images and print out the results.
   (Use the title command to put a label on your graph)
3. Below I've listed several other transformation sets, pick 2
   and create images by both methods for them
4. (Challenge) In the IFS, it is better for the probability of picking
   a certain transformation to be relative to the size of the Pgram
   you are mapping into relative to the other Pgrams.  In math,
      Prob using Ti =  Ai/sum(Ak, k=1,..,M)
   where Ak is the area of Pgram k.

   Modify ifs.m to ifs2.m that computes and uses these
   new probabilities.  Hint: The area of the Pgram produced by the
   transformation T is det(T); if det(T) is 0,
   replace it by some small value (like 0.01).


--------------------------OTHER TRANSFORMATIONS------------------------------

Fern
T1 = [0 0 0; 0 0.16 0; 0 0 1];
T2 = [0.85 0.04 0; -0.04 0.85 1.6; 0 0 1];
T3 = [0.2 -0.26 0; 0.23 0.22 1.6; 0 0 1];
T4 = [-0.15 0.28 0; 0.26 0.24 0.44; 0 0 1]; 

Fractal Tree
T1 = [0 0 0; 0 0.5 0;0 0 1];
T2 = [0.42 -0.42 0; 0.42 0.42 0.2;0 0 1];
T3 = [0.42 0.42 0; -0.42 0.42 0.2; 0 0 1];
T4 = [0.1 0 0; 0 0.1 0.2; 0 0 1];


Koch curve
T1 = [1/3 0 0; 0 1/3 0; 0 0 1];
T2 = [1/3*cos(pi/3) -1/3*sin(pi/3) 1/3; 1/3*sin(pi/3) 1/3*cos(pi/3) 0; 0 0 1];
T3 = [1/3*cos(pi/3)  1/3*sin(pi/3) 1/2; -1/3*sin(pi/3) 1/3*cos(pi/3) sqrt(3)/6; 0 0 1];
T4 = [1/3 0 2/3; 0 1/3 0; 0 0 1];


Sierpinski Triangle
T1 = [1/2 0 0;0 1/2 0;0 0 1];
T2 = [1/2 0 1/2;0 1/2 1/2; 0 0 1];
T3 = [1/2 0 1/2; 0 1/2 0; 0 0 1];


Sierpinski Square
T1 = [1/3 0 0; 0 1/3 0; 0 0 1];
T2 = [1/3 0 2/3; 0 1/3 0; 0 0 1];
T3 = [1/3 0 1/3; 0 1/3 1/3; 0 0 1];
T4 = [1/3 0 0; 0 1/3 2/3; 0 0 1];
T5 = [1/3 0 2/3; 0 1/3 2/3; 0 0 1];


Sierpinski Carpet
T1 = [1/3 0 0;0 1/3 0;0 0 1];
T2 = [1/3 0 1/3;0 1/3 0; 0 0 1];
T3 = [1/3 0 2/3;0 1/3 0; 0 0 1];
T4 = [1/3 0 0;0 1/3 1/3; 0 0 1];
T5 = [1/3 0 2/3;0 1/3 1/3; 0 0 1];
T6 = [1/3 0 0;0 1/3 2/3;0 0 1];
T7 = [1/3 0 1/3;0 1/3 2/3;0 0 1];
T8 = [1/3 0 2/3;0 1/3 2/3;0 0 1];


Twin Christmas Tree
R = [0 -1 0;1 0 0; 0 0 1];   % 90 degree rot
T1 = [1/2 0 1/2; 0 1/2 0;0 0 1]*R;
T2 = [1/2 0 1/2;0 1/2 1/2;0 0 1]*inv(R);
T3 = [1/2 0 1/4;0 1/2 sqrt(3)/4;0 0 1];


3-fold Dragon
R = [0 1 0;-1 0 0; 0 0 1];   % 270 degree rot
T1 = [2/3 0 0;0 2/3 2/3;0 0 1]*R;
T2 = [2/3 0 0;0 2/3 1;0 0 1]*R;
T3 = [2/3 0 1/3;0 2/3 5/6;0 0 1]*R;


Cantor Maze
R = [0 -1 0;1 0 0;0 0 1];  % 90 degree rot
T1 = [1/3 0 1/3;0 1 0;0 0 1]*R;
T2 = [1/3 0 1/3;0 1/3 2/3;0 0 1];
T3 = [1/3 0 2/3;0 1 0;0 0 1]*[-1 0 0;0 1 0;0 0 1]*R;



----------------------------PROGRAMS------------------------------

ifs.m

function z = ifs(N,varargin)
% does N iterations of the IFS defined
% by the transformations passed in

T = varargin;      % get the transformations
k = size(T,2);     % number of transformations
x = [1/2 1/2 1]';  % starting point
z = zeros(2,N);    % save space for the output
i = 0;

while (i<N)
    r = floor(k*rand(1))+1;    % pick a random transformation
    x = T{r}*x;                % apply it to the point
    i = i + 1;
    z(:,i) = x(1:2);           % save the point
end




Mail: ccollins@math.utk.edu