This is cool
Recently I bought and read Ian Stewart’s “How to Cut a Cake and Other Mathematical Conundrums” (OUP). It is a popular maths book consisting of a selection of Stewart’s columns in Scientific American and comes in nicely sized chunks about various topics such as envy free division, packing milk bottles into a crate and why phone cables get tangled.
One of the chapters is called “Sierpinski’s Ubiquitous Gasket” and surprisingly enough relates various things about the eponymous fractal. At the end, a random walk is mentioned which generates the fractal quite amazingly. The random walk is this:
- Take a random point P inside an equilateral triangle ABC
- Mark the midpoint of point P and a random one of A, B or C
- This midpoint is the new point P.
- Repeat 2 and 3
I implemented this random walk in PyGTK, so here is the source and a video of it in action (various video formats and source file available in http://joshh.co.uk/stuff/)
#!/usr/bin/env python
#
# Use a random walk to produce an approximation to the Sierpinski Gasket.
# Graphics rendered in Cairo/GTK
import pygtk
pygtk.require('2.0')
import gtk
import math
import random
# how many iterations to do on each click
iters = 10
# work out sqrt(3) now, as we'll be using it later
sqrt3 = math.sqrt(3)
tan30 = math.tan(math.pi/6)
# the points of the main triangle
top = 20
bottom = int(20+200*sqrt3)
left = 20
right = 420
triangle = [(left, bottom), ((left+right)/2, top), (right, bottom)]
def point_in_triangle(point):
if point[1] == bottom: # point is on bottom line, so
return True # guaranteed to be in triangle
if point[0] == (left+right)/2: # point is on middle line, so
return True # guaranteed to be in triangle
# calculate height up from bottom
dist_up = bottom - point[1]
# calculate how far in the sides are at the height relevant
dist_in = dist_up * tan30
if left+dist_in <= point[0] <= right-dist_in:
return True
# can't be in triangle
return False
def midpoint(point1, point2):
return ((point1[0]+point2[0])/2, (point1[1]+point2[1])/2)
class SierpinskiWin(object):
point_list = [] # the list of points added already
def __init__(self):
window = gtk.Window(gtk.WINDOW_TOPLEVEL)
window.set_title("Sierpinski's Gasket")
window.connect("destroy", lambda w: gtk.main_quit())
window.set_size_request(440, 400)
self.area = gtk.DrawingArea()
self.area.set_events(gtk.gdk.BUTTON_PRESS_MASK | gtk.gdk.EXPOSURE_MASK)
self.area.set_size_request(220, 200)
self.pangolayout = self.area.create_pango_layout("")
window.add(self.area)
self.area.connect("expose-event", self.area_expose_cb)
self.area.connect("button_press_event", self.clicked_cb)
self.area.show()
window.show()
def area_expose_cb(self, area, event):
self.style = self.area.get_style()
self.gc = self.style.fg_gc[gtk.STATE_NORMAL]
self.gc.line_width = 2
self.area.window.draw_polygon(self.gc, False, triangle)
for point in self.point_list:
self.area.window.draw_point(self.gc, *point)
return True
started = False # has the random walk started?
next = (0, 0)
def clicked_cb(self, area, event):
if not self.started:
self.next = int(event.x), int(event.y)
if point_in_triangle(self.next):
self.area.window.draw_point(self.gc, *self.next)
self.point_list.append(self.next)
self.started = True
else:
for i in range(10):
self.next = midpoint(self.next, random.choice(triangle))
self.point_list.append(self.next)
self.area.window.draw_point(self.gc, *self.next)
def main(self):
gtk.main()
return 0
if __name__ == "__main__":
sw = SierpinskiWin()
sw.main()
