Sierpiński Triangles
I discovered Sierpiński triangles as a kid and have had a low-key fascination with them ever since.
I remember reading an article giving a simple algorithm to generate them which didn't need to be either recursive (which at the time I probably wouldn't have understood), or to keep track of where in the process you are.
The algorithm is simple:
- Given three points for the corners of the triangle, lets say \(a\), \(b\) and \(c\),
- and a current point, which we'll call \(p_n\).
- To find the next point \(p_{n+1}\)
- let \(r\) be one of \(a\), \(b\), or \(c\) chosen at random,
- The next point is the midpoint of \(p_n\) and \(r\), \(p_{n+1} = \frac{1}{2}\left(p_n + r\right)\)
- Repeat
While this isn't a perfect method, it's usually a good idea to discard the first few points, it does converge on points that are in the set.
But why?
Hopefully it is easy to see that if \(p_n\) is within the triangle, that \(p_{n+1}\) must also be within the triangle.
We can either set-up so that the first point is chosen to be within the triangle, i.e. we could define \(p_0\ = \frac{1}{3} \left( a + b + c \right) \). Alternatively, given that we are going to discard the first few points anyway, just pick a point at random and rely on the fact that the iterative process will bring it into the triangle at some point, and that once it is there it will stay there.
From there the next step is to ask why this doesn't just fill the triangle.
If we consider the recursive definition of a Sierpiński triangle,
Draw a triangle
Create the inner triangle, formed from the midpoints of the three sides, and remove it.
Repeat steps 2 & 3 for each of the three triangles left.
Considering step 2 (the on the first iteration)
If the randomly selected point is \(a\) and \(p_n\) is in the blue triangle
Then the mid-point between that and \(a\) will be in the red triangle (i.e. \(a\)'s triangle)
You can also see that it will be in the portion of the red triangle that would be blue on the next iteration
The triangle within triangle within triangle... is encoded in the sequence of choices of random points, the level of detail is a function of the number of points that we draw