Mathematically, the chaos game falls under the broader heading of an Iterated Function System (IFS)<\/a> where the ith point in the plane $q_i$ is given by<\/p>\n \\[ q_i = M^{(p)} q_{i-1} + f^{(p)} \\; \\]<\/p>\n or, in terms of arrays<\/p>\n \\[ \\left[ \\begin{array}{c} x_i \\\\ y_i \\end{array} \\right] = \\left[ \\begin{array}{cc} a^{(p)} & b^{(p)} \\\\ c^{(p)} & d^{(p)} \\end{array} \\right] \\left[ \\begin{array}{c} x_{i-1} \\\\ y_{i-1} \\end{array} \\right] + \\left[ \\begin{array}{c} f^{(p)} \\\\ g^{(p)} \\end{array} \\right] \\; .\\]<\/p>\n The index $p$ is an integer to label the various affine transformations available, and is chosen at random at each step according to some pre-defined probability distribution.<\/p>\n Before getting to the Python code, which is easy to implement, it is instructive to compare and contrast the traditional method and the chaos game in generating the well-known Sierpinski Triangle<\/a> fractal.<\/p>\n The traditional way to draw the Sierpinski Triangle starts with an equilateral triangle.<\/p>\n A similar triangle half in size (or a quarter in area) is removed from the middle of the larger triangle leaving an arrangement of three smaller triangles.<\/p>\n The process can then be applied to these smaller triangles yielding another stage of refinement.\u00a0 This in turn results in a larger set of smaller triangles to which the process can be applied yet again.<\/p>\n Continuing on indefinitely gives the Sierpinski Triangle in all its glory.<\/p>\n However, there is a fundamental limit on how much can be drawn by hand or by computer, and the amount of work to obtain a successively more exact approximation in level of detail becomes increasingly more immense.<\/p>\n In the chaos game, the programing is much simpler and, due to the random nature of the system, all levels of detail are present simultaneously.\u00a0 Central to the chaos game approach are the three affine transformations:<\/p>\n \\[ T1: \\left[ \\begin{array}{c} x_i \\\\ y_i \\end{array} \\right] = \\left[ \\begin{array}{cc} 0.5 & 0 \\\\ 0 & 0.5 \\end{array} \\right] \\left[ \\begin{array}{c} x_{i-1} \\\\ y_{i-1} \\end{array} \\right] + \\left[ \\begin{array}{c} 1 \\\\ 1 \\end{array} \\right] \\; ,\\]<\/p>\n \\[ T2: \\left[ \\begin{array}{c} x_i \\\\ y_i \\end{array} \\right] = \\left[ \\begin{array}{cc} 0.5 & 0 \\\\ 0 & 0.5 \\end{array} \\right] \\left[ \\begin{array}{c} x_{i-1} \\\\ y_{i-1} \\end{array} \\right] + \\left[ \\begin{array}{c} 1 \\\\ 50 \\end{array} \\right] \\; , \\]<\/p>\n and<\/p>\n \\[ T3: \\left[ \\begin{array}{c} x_i \\\\ y_i \\end{array} \\right] = \\left[ \\begin{array}{cc} 0.5 & 0 \\\\ 0 & 0.5 \\end{array} \\right] \\left[ \\begin{array}{c} x_{i-1} \\\\ y_{i-1} \\end{array} \\right] + \\left[ \\begin{array}{c} 50 \\\\ 50 \\end{array} \\right] \\; .\\]<\/p>\n At each stage of the iteration, one of these transformations is selected with probability 1\/3; that is to say that each is equally likely to be selected.<\/p>\n Four basic pieces of code are used in the implementation.<\/p>\n The first is a table that encodes the selection probability and the parameters for each affine transformation used in the game (i.e., each row of the table encodes the likelihood and the numbers associated with $T1$, $T2$, and so on).\u00a0 The table encoding for the Sierpinski Triangle is:<\/p>\n Second is the Transform iteration function that takes as input the current point, the table describing the game, and a random number simulating the probability at each step.<\/p>\n Third is looping code that carries out the chaos game through successive applications.\u00a0 The code, which, for convenience, wasn\u2019t encapsulated in a function, looks like<\/p>\n The parameter N sets the number of desired iterations; the numpy array shape pre-allocates the space for the resulting points from the iterations and initializes the starting point to the origin.\u00a0 The probabilities are also precomputed since a call to the numpy (np) random is more quickly performed when in bulk than at each step.\u00a0 The game object points at the particular table encoding the transformations, here the sierpinski_triangle table defined above.\u00a0 The for loop could be done faster using a list comprehension but at the loss of clarity.\u00a0 Since N = 100000 takes less than a second of computation there wasn\u2019t a compelling reason to lose the clarity.<\/p>\n The final step is a plot of the results.\u00a0 The code that performs this is given by<\/p>\n The parameter start sets the number of initial points to ignore.\u00a0 This is sometimes useful to suppress the initial stray n points until the game converges to the fractal attractor.<\/p>\n All of these pieces were put together in a Jupyter notebook.\u00a0 The resulting image is<\/p>\n Note that the Sierpinski Triangle is rotated 45 degrees from the more usual \u2018artistic\u2019 expression.\u00a0 That minor issue is easily rectified using a simple rotation matrix<\/p>\n where the parameters c45 and s45 are shorthand for $\\cos(45 {}^{\\circ}) = 1\/\\sqrt{2}$ and $\\sin(45 {}^{\\circ}) = 1\/\\sqrt{2}$, respectively.<\/p>\n The resulting image is now more aesthetically pleasing.<\/p>\n![\"\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2018\/11\/Sierpinski_Triangle_Stage0.jpg\")
<\/a><\/p>\n![\"\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2018\/11\/Sierpinski_Triangle_Stage1.jpg\")
<\/a><\/p>\n![\"\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2018\/11\/Sierpinski_Triangle_First_Five_Stages.jpg\")
<\/a><\/p>\nsierpinski_triangle = np.array([[0.33,0.5,0,0,0.5, 1, 1],\n [0.66,0.5,0,0,0.5, 1,50],\n [1.00,0.5,0,0,0.5,50,50]])<\/pre>\n<\/div>\n
def Transform(point,table,r):\n x0 = point[0]\n y0 = point[1]\n\n for i in range(len(table)):\n if r <= table[i,0]:\n N = i\n break\n\n x = table[N,1]*x0 + table[N,2]*y0 + table[N,5]\n y = table[N,3]*x0 + table[N,4]*y0 + table[N,6]\n\n return np.array([x,y])<\/pre>\n<\/div>\n
N\u00a0\u00a0\u00a0\u00a0 = 100000\nshape = np.zeros((N,2))\nprobs = np.random.random(N)\ngame\u00a0 = sierpinski_triangle\n\nfor i in range(1,N):\n shape[i,:] = Transform(shape[i-1,:],game,probs[i])<\/pre>\n<\/div>\n
start = 0\n\nfig_shape = plt.figure(figsize=(6,6))\nax_shape\u00a0 = fig_shape.add_subplot(1,1,1)\nax_shape.scatter(shape[start:,0],shape[start:,1],marker='.',color='k',s=0.01)\nax_shape.axes.set_frame_on(False)\nax_shape.xaxis.set_visible(False)\nax_shape.yaxis.set_visible(False)<\/pre>\n<\/div>\n
![\"\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2018\/11\/Sierpinski_Triangle_1.jpg\")
<\/a><\/p>\nc45 = 1.0\/np.sqrt(2.0)\ns45 = 1.0\/np.sqrt(2.0)\nA = np.array([[c45,s45],[-s45,c45]])\n\nnew_shape = np.array([A.dot(shape[i,:]) for i in range(len(shape))])<\/pre>\n<\/div>\n
![\"\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2018\/11\/Sierpinski_Triangle_2.jpg\")
<\/a><\/p>\n