English: Animated construction of Sierpinski Triangle

Self-made.

许可协议

I made this with SAGE, an open-source math package.The latest source code lives here, and has a few better variablenames & at least one small bug fix than the below.Others have requested source code for images I generated, below. Code is en:GPL; the exactcode used to generate this image follows:

#*****************************************************************************#       Copyright (C) 2008 Dean Moore  < dean dot moore at deanlm dot com >#                                      < [email protected] >           #                                        ##  Distributed under the terms of the GNU General Public License (GPL)#                  http://www.gnu.org/licenses/#*****************************************************************************##################################################################################                                                                               ## Animated 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 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   = 8       # 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    = 50      # Time between "frames" of final "movie."figure_size             = 12      # 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_last_generation = 3^number_of_generations # Always a power of three.images                                 = []                      # Holds images of final "movie."  coordinates                            = []                      # Holds coordinates. p0 = (0,0)                                # Initial points to start iteration -- notep1 = (initial_edge_length, 0)             # y-values of *p0* & *p1* are the same -- anp2 = ((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)

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.while number_of_triangles_in_this_generation < number_of_triangles_in_last_generation:    this_generations_image       = Graphics() # Holds next generation's image, initialize.    next_generations_coordinates = []         # Holds next generation's coordinates, set to null.     for a,b,c in coordinates: # Loop on all triangles.        (p, r)  = a      # Right point; note y-value of this & next are equal.        (q, r1) = b      # Left point; note r1 = r & thus *r1* is irrelevant;                         # it's only there for book-keeping.        (s, t)  = c      # 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 a,b,c" 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.a = animate(images, figsize=[figure_size, figure_size], axes=False) # Make image, ...a.show(delay = delay_between_frames)                                # Show image.  # End of program.

---

End of code.