Iterated Transformations

In some geometric constructions one needs to iterate (or carry out) a specific  transformation multiple times. Geometry Explorer has a built-in capability to automate the iterations of a compound transformation.  We will illustrate this capability by playing the "Chaos Game.'' This is an example of constructing a fractal used by Michael Barnsley in his book Fractals Everywhere.

To play the chaos game we need to define a compound transformation that is built from a set of three dilations, but will be applied in such a way that only one of these dilations (chosen at random) will be applied.

We start by constructing a triangle ABC and a point D inside the triangle.

iterated 11

Next, we define a custom dilation of 1/2 by choosing "Dilation'' under the Custom menu in the Transform Panel and typing in "1'' for the numerator and "2'' for the denominator. We will now dilate point D towards the vertices A, B, and C. To dilate D towards A, select A and choose "Center'' from the "Mark'' menu. Then, select D and hit the dilate button. To dilate D towards B, select B and choose "Center'' from the "Mark'' menu. Then, select D and hit the dilate button. Finally, set C as a center and dilate D towards C. We get three new (dilated) points E,F, and G as shown.

iterated 2

At this point, we will define a random compound transformation consisting of these three dilations. Open up the Compound Transformation Dialog Box by choosing "Compound..." from the "Custom"" menu. Select the three dilations in the list on the left side of this dialog box, name the new transformation "chaosGame'' and select the "Random Transform:'' checkbox.

Once we hit the Okay button in the Compound Transformation Dialog Box, a new dialog box will pop up asking us to set the probabilities for each of the three dilations.  There are two lists on the top of this dialog box: one for the transformations in the compound transform and one for the probability that each transformation will be applied. We assign probabilities as follows. First, we click on a transformation in the list at the left. Then, in the text field labeled "Probability='' we type in the numerical value for the probability that the transformation will have. Once we hit the return key, that probability will appear in the list on the right.  In the figure shown we have assigned probabilities of .33, .33, and .34 to the three dilations.

stats transform panel

The checkboxes in the lower right corner of the probability dialog box control how the new random compound transformation will be applied each time the Canvas is re-drawn.  If we wish one of the three dilations to be chosen at random a single time and then left fixed forever we would select "Fixed update:'' However, if we want the dilation to be chosen at random every time we redraw objects in the Canvas, then we would select "Random update:'' For this example, select the fixed update option. Then, hit the Okay button to finish the definition of the new random compound transformation.

We have now defined a compound transformation that will be random in effect. Every time we apply the compound transformation, one of its three dilations will be chosen at random, with the assigned probability, and applied.  To see how this works, hide points E,F,and G, and select point D. Under the Custom menu you will see a new transformation listed -- "chaosGame.'' Upon choosing this menu item, point D will be dilated by a factor of 1/2 towards one of the three vertices A, B, or C,  creating a new dilated point H.

iterated 3

The choice of dilation will be random with a .33 chance of each dilation being chosen. The new dilated point will be created in a selected state. If we choose "chaosGame'' again we will dilate this new point randomly towards one of the vertices. We can continue using "chaosGame'' repeatedly to get a sequence of points that are randomly dilated by a factor of 1/2 towards the three vertices. In the figure at the right we have carried out about twenty iterations of this random transformation, beginning with the single point D.

iterated 4

What will happen as we iterate this random transformation again and again? Select one of the points inside the triangle.  Geometry Explorer has a built-in capability to automate the iterations of a compound transformation on the selected point. To access this capability drag down in the "Custom'' menu until you hit the "Iterated...'' entry. A dialog box shown below will pop up with a list of the currently defined compound transforms and a text field for the iteration level desired. Click on the list item labeled "chaosGame" and then type in 300 in the "Iteration Number" field. Click the Okay button to start the iteration. At this point the Okay button will switch to a "Stop" button. We can stop the iteration process at any point by clicking the "Stop" button.

iteration panel

Geometry Explorer will now carry out 300 iterations of the "chaosGame" random transformation. One possible result of this is shown below. Notice that the pattern of points is not entirely random, as one might expect. There are discernible triangular gaps within the image that are very reminiscent of a famous figure called the Sierpinski triangle.

iterated 5

The Sierpinski triangle is produced by starting with a solid triangle. We then find the midpoints of each of the three sides of the triangle and connect these, forming four sub-triangles. Next we remove the middle triangle, leaving three solid triangles near the three vertices. The process continues by applying what we just did (i.e. remove a middle sub-triangle) to each of the three solid little triangles. We then would have nine quite small solid triangles remaining. For each of these we again remove a middle triangle, and so on. In the figure below we have carried out this process two more times, yielding 81 small triangles.

Note how similar the randomly iterated transformation process looks when compared to Sierpinski's triangle. In Barnsley's book he shows that the random process above actually converges to Sierpinski's triangle. That is, if we could iterate our random transformation an infinite number of times, and if our points could be represented as ever smaller dots, then the random collection of points we would get would exactly match Sierpinski's triangle. This is quite an amazing result -- that one can get an ordered geometric figure out of an apparently random process. This is one of the great mysteries and delights of the theory of chaos and fractals.