A: Why does the chaos game generate fractals?

Why does the chaos game generate fractals?

My answer fill focus on Sierpiński triangle case, but I think some general conclusions can be drawn from it as well. By no means I'm an expert in the subject, so there will be no mathematical proofs.

Rules of chaos game

The rules of the chaos game (as written by @irelandscape), are very simple:

1. Imagine an area of the screen corresponding to a polygon, such as a triangle, square, pentagon, etc.
2. Select a fraction number f between 0 and 1 (e.g 1/2).
3. Pick a random point within that polygon and plot a pixel at that location
4. Select any vertex (corner) of the polygon at random.
5. Calculate the distance d between the last plotted pixel and the selected vertex.
6. Plot a pixel on the imaginary line between the last plotted pixel and the selected vertex at a distance fd from the previously plotted pixel.
7. Repeat from step 4.

Below, I will assume f=0.5

Restricted regions

First let's consider we have already chosen a vertex of triangle.

Let it be vertex C on the image above. Now if we pick completely random point, anywhere in the triangle, where would next point need to be drawn?

In an area marked with yellow. That's because whatever point we choose, we must cut it's distance in half. So for the farthest points located at the line between A and B vertices, resulting points will land on the line between D and E. The closer we get to C with initial point, the closer will be the resulting one.

Now let's see what happens if we mark achievable regions for all vertices:

You can clearly see what I call a "restricted region" - an area that will be occupied only by a first, completely random point. Points drawn in all subsequent iterations will have to be located in the areas marked with yellow.

Now, if you think about it, you will notice that to get to some regions of the areas that are currently yellow, you would need to start in the restricted area. So those points will also be restricted.

This of course scales down for as long as you wish. Now, why do only certain values of f generate such a nice fractals? In case of triangle it works well for values bigger then 0.5, which result in the same pattern but spaced apart. For smaller values, triangles start to overlap until empty regions vanish completely, and you get only chaos.

For shapes other then triangle, I think a general rule will be similar: You need to have a set of points that is not achievable in the first iteration. Shape of that area will be replicated over the whole polygon.

StemQ Notice: This post was originally submitted on StemQ.io, a Q&A application for STEM subjects powered by the Steem blockchain.