Jump to content

File:Animated construction of Sierpinski Triangle.gif

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (950 × 980 pixels, file size: 375 KB, MIME type: image/gif, looped, 10 frames, 5.0 s)

Summary

 
This diagram was created with SageMath.
Description
English: Animated construction of Sierpinski Triangle

Self-made.

Licensing

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

#*****************************************************************************
#       Copyright (C) 2008 Dean Moore  < dean dot moore at deanlm dot com >
#                                      < deanlorenmoore@gmail.com >           
#                                        
#
#  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.wiki.x.io/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 -- 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)
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.
Date

23 March 2008 (original upload date)

(Original text: March 23, 2008)
Source Own work (Original text: self-made)
Author

Dino at English Wikipedia

(Original text: dino (talk))

Licensing

Dino at English Wikipedia, the copyright holder of this work, hereby publishes it under the following licenses:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
Attribution: Dino at English Wikipedia
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
GNU head Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License.
You may select the license of your choice.

Original upload log

The original description page was here. All following user names refer to en.wikipedia.
  • 2008-03-23 18:33 Dino 1200×1200×7 (344780 bytes) {{Information |Description=Animated construction of Sierpinski Triangle |Source=self-made |Date=March 23, 2008 |Location=Boulder, Colorado |Author=~~~ |other_versions= }} Self-made. Will post source code later.

Captions

Animation construction the Sierpinski Triangle.

Items portrayed in this file

depicts

23 March 2008

image/gif

5b78b6d9a0c951fd72acd22b4b236875f41679c2

384,183 byte

5 second

980 pixel

950 pixel

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current02:41, 10 February 2011Thumbnail for version as of 02:41, 10 February 2011950 × 980 (375 KB)DeanmooreSeemingly better version
20:34, 12 April 2008Thumbnail for version as of 20:34, 12 April 20081,200 × 1,200 (337 KB)יוסי{{Information |Description={{en|Animated construction of Sierpinski Triangle<br/> Self-made. == Licensing: == I made this with SAGE, an open-source math package. The latest source code lives [h

The following 2 pages use this file:

Global file usage

The following other wikis use this file: