Sierpinski Gasket "Chaos Games"
The Sierpinski Gasket (SG) Chaos Game is one of the most popular programming methods for approximating the image of the Sierpinski gasket. The rules for the game are quite simple. Let $V_1$, $V_2$, and $V_3$ be the three vertices of the initial equilateral triangle. These are the "fixed points" for the game. Start with any point $x_0$ inside (or outside) the triangle. This point is the seed. Choose one of the three vertices at random and move the point half the distance to that vertex to get $x_1$. Keep choosing a vertex at random and plotting the point half the distance between the current point and that vertex to generate a sequence $(x_n)$ of points called the orbit of the seed. The figure below shows the first 5 steps of the orbit when selecting vertices 2,1,1,3,2 in that order. The fixed points are depicted by the three colored squares, and the orbit points are colored according to which fixed point had been randomly chosen.
As more and more points are plotted, an approximate image of the Sierpinski gasket will begin to emerge. It can be shown that with probability 1, the sequence $(x_n)$ is dense in the Sierpinski gasket and thus will form a good approximation to the gasket after a sufficient number of points have been plotted (see references below).
Play the SG chaos game here! The small black dot is the initial seed. Click the "Next 1" button to randomly select a vertex. A line segment connecting that vertex and the seed will be drawn, and a new point will be plotted at the midpoint of the line segment in the same color as the corresponding vertex. Keep clicking "Next 1" to plot one point at a time. To see the points generated more quickly (without the line!), click either the "Next 10" or "Next 1000" buttons to plot the next 10 or 1000 points, respectively. Click "Clear" to start over with a new initial seed.
You might notice a few spurious points that are clearly not in the Sierpinski gasket, especially if the seed point starts outside the equilateral triangle or is in one of the "middle" triangles not in the Sierpinski gasket. These are points from the beginning of the orbit. It is the reason that many chaos game programs will compute the first 10 or 20 points in the orbit before starting to plot the subsequent orbit points. By that time the orbit will consist of points very close to the Sierpinski gasket.
Chaos Game
with
Rotations
The SG chaos game is based on moving half way towards one of the three fixed points. We can modify the rules to incorporate rotations of 180° around one or more of the fixed points. The figure below show the chaos game rules on the left using the same fixed points for each game, and the corresponding fractal generated by those rules on the right. Click the buttons to see the effect if the rules are changed for one, two, or three rotations around the fixed points. As an example, click the button for one rotation. For this chaos game, when the red or blue fixed point is randomly chosen, the point will move half the distance towards that fixed point. But when the green fixed point is chosen, you first move half the distance to the green fixed point and then rotate about the fixed point by 180°. That is, you flip around the point to the exact opposite side. Playing this one rotation chaos game produces a different fractal than the Sierpinski gasket. Now try the buttons for two and three rotations.
Click the button to play the Chaos Games with one, two, or three rotations.
Iterated
Function
Systems
The iterated function systems for these rotation chaos games will depend on the chaos game rules and the coordinates of the three fixed points. For rule (1)—move a point $P$ half the distance to a fixed point $F$—the function is $$f(P) = P + \frac{1}{2}\left(F - P\right) = \frac{1}{2}P + \frac{1}{2}F= \left[ {\begin{array}{cc} { 1/2} & {0} \\ { 0} & { 1/2} \\ \end{array}} \right]\left[ {\begin{array}{c} P_x \\ P_y \\ \end{array}}\right] + \left[ {\begin{array}{c} F_x /2 \\ F_y /2 \\ \end{array}} \right]$$ For rule (2)—move a point $P$ half the distance to a fixed point $F$, then rotate by 180°—the function is $$f(P) = P + \frac{3}{2}\left(F - P\right) = -\frac{1}{2}P + \frac{3}{2}F= \left[ {\begin{array}{cc} { -1/2} & {0} \\ { 0} & { -1/2} \\ \end{array}} \right]\left[ {\begin{array}{c} P_x \\ P_y \\ \end{array}}\right] + \left[ {\begin{array}{c} 3 F_x /2 \\ 3 F_y /2 \\ \end{array}} \right]$$
Notice that the fixed point $F$ satisfies $f(F) = F$ for the function $f$ associated with either rule above.
IFS
Animation
One Rotation SG Chaos Game Example
Let the fixed points for rule (1) be $(0,0)$, $(1,0)$, and the fixed point for rule (2) be $(1/2, \sqrt{3}/2)$. The iterated function system corresponding to the three fixed points is
Click the button to view an animation of the IFS starting with an equilateral triangle whose vertices are the fixed points.
IFS
Animation
Two Rotations SG Chaos Game Example
Let the fixed point for rule (1) be $(1/2,\sqrt{3}/2)$, and the two fixed points for rule (2) be $(0,0)$, $(1,0)$. The iterated function system corresponding to the three fixed points is
Click the button to view an animation of the IFS starting with an equilateral triangle whose vertices are the fixed points.
IFS
Animation
Three Rotations SG Chaos Game Example
Let the three fixed points for rule (2) be $(0,0)$, $(1,0)$, and $(1/2, \sqrt{3}/2)$. The iterated function system corresponding to the three fixed points is
Click the button to view an animation of the IFS starting with an equilateral triangle whose vertices are the fixed points.
Trema Construction Trema construction, a term coined by Benoit Mandelbrot, builds fractals by exhaustively removing pieces—called "tremas" (Latin for "holes")—from a solid shape (the initiator) in successive, recursive iterations. The process defines how gaps are created, reducing the solid mass while preserving self-similar patterns.
An alternative construction mimics the trema construction of the Sierpinski gasket (subdivide an equilateral triangle into four smaller equilateral triangles and remove the middle triangle). These are special cases of the SG chaos games with rotations using trapezoids, pentagons, and hexagons of specified shapes.
One Rotation
For the SG chaos game with one rotation, start with an isosceles trapezoid A trapezoid with congruent non-parallel sides (legs), making it a symmetric quadrilateral. It is symmetric with respect to a line perpendicular to the base. with the top edge being half the length of the bottom edge. The height can be whatever is desired. Subdivide the trapezoid into 6 regions by drawing lines from the midpoint of the bottom edge to the top vertices and a horizontal line between the midpoints of the side edges. This forms three copies of the isosceles trapezoid scaled by 1/2, and three congruent isosceles triangles [Construction Details]. Remove the three isosceles triangles. Here is an example of an isosceles trapezoid with base of length 1 on the $x$-axis and height $\sqrt3/2$, along with the first iteration after the isosceles triangles are removed.
Construction
Animation
GeoGebra
Animation
Now recursively iterate the trema construction on the remaining isosceles trapezoids. The iterated function system for this example would be $$\begin{aligned} {\text{green: }f_1}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 3/4 \\ \sqrt3/2 \end{array} \right] \\ {\text{red: }f_2}(\mathbf{x}) &= \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 0 \\ 0 \end{array} \right] \\ {\text{blue: }f_3}(\mathbf{x}) &= \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1/2 \\ 0 \end{array} \right] \end{aligned}$$
The fixed points for this iterated function system are the points ${F_i}$ satisfying $f_i({F_i})={F_i}$ for $i=1,2,3$. These turn out to be ${{F_1}=(1/2,\sqrt3/3)}$, ${{F_2}=(0,0)}$, and ${{F_3}=(1,0)}$ for these functions as shown in the image of the first iteration. If the SG chaos game with one rotation is played with these three fixed points, then according to the results above in the IFS section, the iterated function function system for the chaos game would be $$\begin{aligned} \text{rule 2:} \quad {g_1}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} 3 (F_1)_x /2 \\ 3 (F_1)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 3/4 \\ \sqrt3/2 \end{array} \right] = {f_1}(\mathbf{x})\\ \text{rule 1:} \quad {g_2}(\mathbf{x}) &= \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} (F_2)_x /2 \\ (F_2)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 0 \\ 0 \end{array} \right] ={f_2}(\mathbf{x})\\ \text{rule 1:} \quad {g_3}(\mathbf{x}) &= \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} (F_3)_x /2 \\ (F_3)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1/2 \\ 0 \end{array} \right] = {f_3}(\mathbf{x}) \end{aligned}$$
So both the trapezoid trema construction and the SG chaos game with one rotation will result in the same fractal image since they have the same iterated function system.
This particular trapezoid example was used to construct the game board for the Sierpinski Gasket Chaos Game Challenge with one rotation.
Two Rotations
For the SG chaos game with two rotations, start with an isosceles pentagon A pentagon that has a single axis of symmetry that passes through one vertex and the midpoint of the opposite side. whose width is twice the length of the base and for which the height is three times the distance from the base to the width.
Subdivide the pentagon into 7 regions by drawing lines from the vertices of the bottom edge to the midpoint of the opposite side, and a horizontal line at half the height (so it bisects the axis of symmetry). This forms three copies of the isosceles pentagon scaled by 1/2, and four similar isosceles triangles [Construction Details]. Remove the four triangles.
Here is an example of an isosceles pentagon with base of length 1 on the $x$-axis and width 2 at a height of 0.5, along with the first iteration after the isosceles triangles are removed.
Construction
Animation
Now recursively iterate the trema construction on the remaining isosceles pentagons. The iterated function system for this example would be $$\begin{aligned} {\text{green: }f_1}(\mathbf{x}) &= \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1/4 \\ 3/4 \end{array} \right] \\ {\text{red: }f_2}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1/4 \\ 3/4 \end{array} \right] \\ {\text{blue: }f_3}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 5/4 \\ 3/4 \end{array} \right] \end{aligned}$$
The fixed points are at ${F_1 =(1/2,3/2)}$, ${F_2=(1/6,1/2)}$, and ${F_3=(5/6,1/2)}$ as shown in the image above of the first iteration. If the SG chaos game with two rotations is played with these three fixed points, then according to the results above in the IFS section, the iterated function function system for the chaos game would be $$\begin{aligned} \text{rule 1:} \quad {g_1}(\mathbf{x}) &= \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} (F_1)_x /2 \\ (F_1)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} 1/2 & 0 \\ 0 & 1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1/4 \\ 3/4 \end{array} \right] = {f_1}(\mathbf{x})\\ \text{rule 2:}\quad g_2(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} 3 (F_2)_x /2 \\ 3 (F_2)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1/4 \\ 3/4 \end{array} \right] = {f_2}(\mathbf{x})\\ \text{rule 2:}\quad g_3(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} 3 (F_2)_x /2 \\ 3 (F_2)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 5/4 \\ 3/4 \end{array} \right] = {f_3}(\mathbf{x}) \end{aligned}$$
So both the pentagon trema construction and the SG chaos game with two rotations will result in the same fractal image since they have the same iterated function system.
This pentagon example was used to construct the game board for the Sierpinski Gasket Chaos Game Challenge with two rotations.
Three Rotations
For the chaos game with three rotations, start with an isosceles hexagon A hexagon that has a line of reflection symmetry, so that corresponding sides and angles occur in equal pairs. for which the width is 3/2 the length of the base, the top is half the length of the base, and the height is three times the distance from the base to the width.
Subdivide the hexagon into 7 regions by drawing lines from the quarter points of the bottom edge to the quarter point from the top of the opposite side, and a horizontal line at half the height (so it bisects the axis of symmetry). This forms three copies of the isosceles hexagon scaled by 1/2, and four similar isosceles triangles [Construction Details]. Remove the four triangles.
Here is an example of an isosceles hexagon with base of length 1 on the $x$-axis and width 1.2 at a height of 0.4, along with the first iteration after the isosceles triangles are removed.
Construction
Animation
Now recursively iterate the trema construction on the remaining isosceles hexagons. The iterated function system for this example would be $$\begin{aligned} {\text{green: }f_1}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 3/4 \\ 6/5 \end{array} \right] \\ {\text{red: }f_2}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 3/8 \\ 3/5 \end{array} \right] \\ {\text{blue: }f_3}(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 9/8 \\ 3/5 \end{array} \right] \end{aligned}$$
The fixed points are at $F_1=(1/2,4/5)$, $F_2=(1/4,2/5)$, and $F_3=(3/4,2/5)$. Click the first iteration image above to see the fixed points. If the SG chaos game with three rotations is played with these three fixed points, then according to the results above in the IFS section, the iterated function function system for the chaos game would be $$ \begin{aligned} \text{rule 2:}\quad g_1(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} 3 (F_1)_x /2 \\ 3 (F_1)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 3/4 \\ 6/5 \end{array} \right] = {f_1}(\mathbf{x}) \\ \text{rule 2:}\quad g_2(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} 3 (F_2)_x /2 \\ 3 (F_2)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 3/8 \\ 3/5 \end{array} \right] ={f_2}(\mathbf{x}) \\ \text{rule 2:}\quad g_3(\mathbf{x}) &= \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ {\begin{array}{c} 3 (F_3)_x /2 \\ 3 (F_3)_y /2 \\ \end{array}} \right] = \left[ \begin{array}{cc} -1/2 & 0 \\ 0 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 9/8 \\ 3/5 \end{array} \right] = {f_3}(\mathbf{x}) \end{aligned} $$
So both the hexagon trema construction and the SG chaos game with three rotations will result in the same fractal image since they have the same iterated function system.
This hexagon example was used to construct the game board for the Sierpinski Gasket Chaos Game Challenge with three rotations.
