#*****************************************************************************
# Copyright (C) 2008 Dean Moore < deanlorenmoore@gmail.com >
#
#
# Distributed under the terms of the GNU General Public License (GPL)
# http://www.gnu.org/licenses/
#*****************************************************************************
#################################################################################
# #
# Animated construction of Sierpinski Triangle. #
# #
# Source code written by Dean Moore, March, 2008, open source GPL (above), #
# source code open to the universe. #
# #
# Code animates construction of a Sierpinski Triangle. #
# #
# See any reference on the Sierpinski Triangle, e.g., Wikipedia at #
# < http://en.wikipedia.org/wiki/Sierpinski_triangle >; countless others are #
# out there. #
# #
# Other info: #
# #
# Written in sage mathematical package sage (http://www.sagemath.org/), hence #
# heavily using the computer language Python (http://www.python.org/). #
# #
# Important algorithm note: #
# #
# This code does not use recursion. #
# #
# #
# More topmatter & documentation probably irrelevant to most: #
# #
# Inspiration: I viewed it an interesting problem, to try to do an animated #
# construction of a Sierpinski Triangle in sage. Thought I'd be lazy & search #
# the 'Net for open-source versions of this I could simply convert to sage, but #
# the open-source code I found was poorly documented & I couldn't figure it #
# out, so I gave up & solved the problem from scratch. #
# #
# Also, I wanted to animate the construction, which I did not find in #
# open-source code on the 'Net. #
# #
# Comments on algorithm: #
# #
# The code I found on the 'Net was recursive. I do not much like recursion, #
# considering it way for programmers to say, "Look how smart I am! I'm using #
# recursion! Aren't I cool?!" I feel strongly recursion is often confusing, #
# can chew up too much memory, and should be avoided except when #
# #
# a) It's unavoidable, or #
# b) The code would be atrocious without it. #
# #
# Did some thinking & swearing, but concocted a non-recursive method, and by #
# doing the problem from scratch. Guess it avoids all charges of copyright #
# violation, plagiarism, whatever. #
# #
# More on algorithm via ASCII art. Below we have a given triangle, shaded via #
# x's. #
# #
# The next "generation" is the blank triangles. Sit down & start a Sierpinski #
# Triangle on scratch: the next generation is always two on each side of a #
# given triangle from the last generation, one on top. Algorithm takes the #
# given, shaded triangle (below), and makes the three of the next generation #
# arising from it. #
# #
# See code for more on how this works. #
# __________ #
# \ / #
# \ / #
# \ / #
# \ / #
# _________\/_________ #
# \ xxxxxxxxxxxxxxxx / #
# \ xxxxxxxxxxxxxx / #
# \ xxxxxxxxxxxx / #
# \ xxxxxxxxxx / #
# _________\ xxxxxxxx /_________ #
# \ /\ xxxxxx /\ / #
# \ / \ xxxx / \ / #
# \ / \ xx / \ / #
# \ / \ / \ / #
# \/ \/ \/ #
# #
#################################################################################
# #
# Begin program: #
# #
# First we need three functions; see the below code on how they are used. #
# #
# The three functions *right_side_triangle* , *left_side_triangle* & #
# *top_triangle* are here defined & not as "lambda" functions, as they need #
# documented. #
# #
# I don't care to replicate the poorly-documented code I found on the 'Net. #
# #
#################################################################################
# #
# First function, *right_side_triangle*. #
# #
# Function *right_side_triangle* gives coordinates of next triangle on right #
# side of a given triangle whose coordinates are passed in. #
# #
# Points *p*, *r*, *q*, *s* & *t* are labeled as passed in: #
# #
# (p, r)____________________(q, r) #
# \ / #
# \ / #
# \ / #
# \ / #
# \ (p1, r1)/_________ (q1, r1) #
# \ /\ / #
# \ / \ / #
# \ / \ / #
# \ / \ / #
# \/ \/ #
# (s, t) (s1, t1) #
# #
# p1 = (q + s)/2, a simple average. #
# q1 = q + (q - s)/2 = (3*q - s)/2 #
# r1 = (r + t)/2, a simple average. #
# s1 = q, easy. #
# t1 = t, easy. #
# #
#################################################################################
def right_side_triangle(p,q,r,s,t):
p1 = (q + s)/2
q1 = (3*q - s)/2
r1 = (r + t)/2
s1 = q # A placeholder, solely to make code clear.
t1 = t # Ditto, a placeholder.
return ((p1,r1),(q1, r1),(s1, t1))
# End of function *right_side_triangle*.
#################################################################################
# #
# Function *left_side_triangle*: #
# #
# (p, q) ____________________(q, r) #
# \ / #
# \ / #
# \ / #
# \ / #
# (p1, r1) _________\ (q1, r1) / #
# \ /\ / #
# \ / \ / #
# \ / \ / #
# \ / \ / #
# \/ \/ #
# (s1, t1) (s, t) #
# #
# p1 = p - (s - p)/2 = (2p-s+p)/2 = (3p - s)/2 #
# q1 = (p + s)/2, a simple average #
# r1 = (r + t)/2, a simple average. #
# s1 = p, easy. #
# t1 = t, easy. #
# #
#################################################################################
def left_side_triangle(p,q,r,s,t):
p1 = (3*p - s)/2
q1 = (p + s)/2
r1 = (r + t)/2
s1 = p # A placeholder, solely to make code clear.
t1 = t # Ditto, a placeholder.
return ((p1,r1),(q1, r1),(s1, t1))
# End of function *left_side_triangle*.
#################################################################################
# #
# Function *top_triangle*. #
# #
# (p1, r1) __________ (q1, r1) #
# \ / #
# \ / #
# \ / #
# \ / (s1, t1) #
# (p, r)_________\/_________ #
# \ xxxxxxxxxxxxxxxx / #
# \ xxxxxxxxxxxxxx / (q, r) #
# \ xxxxxxxxxxxx / #
# \ xxxxxxxxxx / #
# \ xxxxxxxx / #
# \ xxxxxx / #
# \ xxxx / #
# \ xx / #
# \ / #
# \/ #
# (s, t) #
# #
# p1 = (p + s)/2, a simple average. #
# q1 = (s + q)/2, a simple average #
# r1 = r + (r - t)/2 = (3r - t)/2 #
# s1 = s, easy. #
# t1 = r, easy. #
# #
#################################################################################
def top_triangle(p,q,r,s,t):
p1 = (p + s)/2
q1 = (s + q)/2
r1 = (3*r - t)/2
s1 = s # Again, both this & next are
t1 = r # placeholders, solely to make code clear.
return ((p1,r1),(q1, r1),(s1, t1))
# End of function *top_triangle*.
#################################################################################
# #
# Main program commences: #
# #
#################################################################################
# Top matter a user may wish to vary:
number_of_generations = 9 # How "deep" goes the animation after initial triangle.
first_triangle_color = (1,0,0) # First triangle's rgb color as red-green-blue tuple.
chopped_piece_color = (0,0,0) # Color of "chopped" pieces as rgb tuple.
delay_between_frames = 75 # Time between "frames" of final "movie."
figure_size = 8 # Regulates size of final image.
initial_edge_length = 3^7 # Initial edge length.
# End of material user may realistically vary. Rest should churn without user input.
number_of_triangles_in_final_generation = 3^(number_of_generations - 1) # Always a power of three.
# The "- 1" is because the
# first triangle is really the "zero" generation: go one generation and we draw 3^0 = 1 new triangles
# in final image, two and we draw 3^1 = 3 new triangles in final image, but user user doesn't need to
# know that.
images = [] # Holds images of final "movie."
p0 = (0,0) # Initial points to start iteration -- note
p1 = (initial_edge_length, 0) # y-values of *p0* & *p1* are the same -- an
p2 = ((p0[0] + p1[0])/2, # important book-keeping device.
((initial_edge_length/2)*sin(pi/3))) # Equilateral triangle; see any Internet
# reference on these.
# We make a polygon (triangle) of initial points:
this_generations_image = polygon((p0, p1, p2), rgbcolor=first_triangle_color)
images.append(this_generations_image) # Save image from last line.
coordinates = [( ( (p0[0] + p2[0])/2, (p0[1] + p2[1])/2 ), # Coordinates
( (p1[0] + p2[0])/2, (p1[1] + p2[1])/2 ), # of second
( (p0[0] + p1[0])/2, (p0[1] + p1[1])/2 ) )] # triangle.
# It is *supremely* important
# that the y-values of the first two points are equal -- check definitions
# above & code below.
this_generations_image = polygon(coordinates[0], # Image of second triangle.
rgbcolor=chopped_piece_color)
# Parameter *coordinates* isn't used again.
images.append(images[0] + this_generations_image) # Save second image, tacked on top of first.
# Now the loop that makes the images:
number_of_triangles_in_this_generation = 1 # We have made one "chopped" triangle, the second, above,
# also see above note on the "-1" in
# the code < number_of_triangles_in_final_generation = 3^(number_of_generations - 1) >.
while number_of_triangles_in_this_generation < number_of_triangles_in_final_generation:
this_generations_image = Graphics() # Holds next generation's image, initialize.
next_generations_coordinates = [] # Holds next generation's coordinates, set to null.
for i in range(0, len(coordinates)): # Loop on all triangles.
(p, r) = coordinates[i][0] # Right point; note y-value of this & next are equal.
(q, r1) = coordinates[i][1] # Left point; note r1 = r & thus *r1* is irrelevant;
# it's only there for book-keeping.
(s, t) = coordinates[i][2] # Bottom point.
# Now construct the three triangles & their three polygons of the next
# generation.
right_triangle = right_side_triangle(p,q,r,s,t) # Here use those
left_triangle = left_side_triangle (p,q,r,s,t) # utility functions
upper_triangle = top_triangle (p,q,r,s,t) # defined at top.
right = polygon(right_triangle, rgbcolor=(chopped_piece_color)) # Make next
left = polygon(left_triangle, rgbcolor=(chopped_piece_color)) # generation's
top = polygon(upper_triangle, rgbcolor=(chopped_piece_color)) # triangles.
this_generations_image = this_generations_image + (right + left + top) # Add image.
next_generations_coordinates.append(right_triangle) # Save the coordinates
next_generations_coordinates.append( left_triangle) # of triangles of the
next_generations_coordinates.append(upper_triangle) # next generation.
# End of "for i" loop.
coordinates = next_generations_coordinates # Save for next generation.
images.append(images[-1] + this_generations_image) # Make next image: all previous
# images plus latest on top.
number_of_triangles_in_this_generation *= 3 # Bump up.
# End of *while* loop.
final_image = animate(images, figsize=[figure_size, figure_size], axes=False) # Make image, and ...
final_image.show(delay = delay_between_frames) # Show image.
# End of program.