Assignment 4: Functions Solution

Overview



For this assignment you will write a Python program that draws a Sierpinski Triangle using a method called a chaos game.




The chaos game is played as follows. The user chooses the window size (say 300 by 300 pixels). Denote the three corners of an isosceles triangle 1; 2; 3, where corner 1 is at the top center of the screen, corner 2 is in the lower left of the screen, and corner 3 is in the lower right of the screen. Here’s some pseudocode to help you understand how the chaos game works:




Let p
be a
random point in the window
loop 10000
times:
c
= a
random corner of the triangle
m
= the midpoint between p and c
choose
a color for m
color
the pixel at m
p
= m





This process will generate a Sierpinski Triangle like the one pictured below.




Details



One thing you might notice if you try this on paper (or if you carefully look at the image you generate once it’s complete) is that the rst few iterations of this game may produce points that are not actually part of the Sierpinski triangle. Thus, you should start the process of generating points, but don’t color the rst few points you calculate. To be safe you should start adding points to the image after 10 iterations.



You are provided with a skeleton code le called sierpinski.py. This le contains some code to help get you started, including a function that sets up the Turtle graphics window for our somewhat nontraditional turtle use case. In particular, take a look at the speci cation for the turtle_setup function: this takes care of creating a turtle, and resizing the window to the desired dimensions. Call this before beginning the chaos game iterations, and use the turtle it returns to do all your pixel coloring.



The setup function changes the window so its coordinate system now has (0,0) at the bot-tom left corner, with positive x going right and positive y going up, so the top left corner is at (0, canv_height),the bottom right corner is at (canv_width, 0), and the top right is at (canv_width, canv_height). This helps to simplify the math when locating corners of the tri-angle. The setup function also calls tracer(0, 0), which you may recall disables automatic re-drawing of the canvas. This means that to get your picture to show up, you need to call turtle.update() yourself. For the sake of speed, I recommend re-drawing the picture only every 100 or every 1000 iterations so the drawing doesn’t take too long.



In this program, we’re not really using turtles for what they were meant for. Instead of drawing lines as the turtle moves, we’ll use the turtle to color individual pixels on the canvas. Turtles draw as they move, but they can also draw shapes, such as circles and dots; we’ll make use of the aptly named dot method. To ll in a pixel, all you need to do is move the turtle to that pixel, then draw a dot of size 1.



When the turtle draws via movement with the pen down, or via other methods such as dot, the color it draws is determined by the turtle’s current color. You can change the turtle’s current color using the (again, aptly named) color method. One way to specify colors is using various standard color names ("red", "green", "purple", etc.). A more exible way is to specify how much red, green, and blue you want: some combination of these three primary colors can represent all colors that your screen can display. When storing images on computers, we typically store each R,G, and B value using a single byte (8 bits). That means a color is represented by three numbers from 0 to 255, which is the maximum number representable using 8 bits. For instance (255; 0; 0) is red, (0; 255; 0) is green and (0; 0; 255) is blue. Furthermore, (255; 255; 255) is white and (0; 0; 0) is black.



In the gure on the rst page, you can see that the colors of the pixels are related to their coordinates. If you simply followed the pseudocode at the top of this document, but chose black for the color every time, then you’d have a black and white version of the Sierpinski triangle. That’s a good rst step to make sure your chaos procedure is working correctly. Once you have that working, you should gure out how to make the triangle prettier. The color scheme used in the example above chooses each color value based on the distance from one of the corners. In particular, the red color scales from 255 to 0 based on distance from corner 1, the green scales with distance from corner 2, and blue scales with distance from corner 3. You may choose a di erent scheme, but your colors should appear in a smooth gradient across the triangle, and the corners should each be colored one of the \base" colors (red, green, and blue). This is not too di cult in a square window but you need to be a little more careful in a non-square window (when the width of the window is not equal to the height of the window).
Suggested Approach



This may seem like a big problem to solve all at once; in fact it is, so it is highly recommended that you write functions to solve small pieces of the problem, then put them together into a solution to the full program.




In class we wrote distance and midpoint functions. These will come in handy here, so copy those into your code, and feel free to modify them as needed.



I included the pseudocode for the chaos game in the skeleton le. This is a handy way to keep track of your overall program structure: start with pseudocode and piece-by-piece ll in code that accomplishes each of the steps. Because each step has some complexity to it, you should de ne functions that take care of the details of each step. That way, the code in your main program will end up corresponding fairly closely to the lines of the pseudocode, and it will be easy to understand.



Based on the pseudocode, decide what functions you’d like to have in order to make the algorithm easy to implement. In my solution, I have almost one-to-one correspondence between functions and lines in the pseudocode. To give one example, to choose a color for the point m, I have a choose_color function. It takes a point and the three corners and calculates the RGB color values based on distance of the point from each of the colors. This function in turn makes use of the distance function.



Instead of immediately starting to code each function you’ve decided to write, try this instead: write out the speci cation (docstring) for the function. This means deciding what the function takes as arguments and what it returns. Once you have this, try sketching out the code for the chaos game, using the functions (even though you haven’t written them yet!). In doing this, you may discover changes that you want to make to your function speci cations|make them now so you don’t have to rewrite the code.



Now, go implement each of your functions. Start with the ones that will be needed to draw the triangle in black. After nishing one function, test it. Use the interactive shell and/or put code in your main program that checks whether the code does what you expect it to. For example, to test my choose_color function, I rst tried passing in each corner: I made sure the top corner gave me (255; 0; 0) back, and so on for all three corners. Then I tried the bottom middle point on the canvas, because it’s easy for me to calculate that its blue and green values should be about 128 (it’s equidistant from the green corner and the blue corner). Then test the center point - its RGB values should all be equal because it’s equidistant from all three corners.



Finally, turn your sketch of the overall chaos game algorithm into real code that uses your functions to draw the Sierpinski triangle. Make sure it works with di erent square window sizes rst (e.g., 200 by 200, 300 by 300). Then try testing it with unequal width and height (e.g., 200 by 300).






Hints



I de ned three variables in my main program that hold the coordinates of the three corners, since the corner coordinates are needed in several places. The functions that do calculations involving corners need to take the relevant corners as parameters.



Drawing a black and white triangle is a great rst step. You may want to start out simply choosing black as the color for all pixels to ensure the geometry is all working correctly.
The distance and midpoint function used tuples to pack the coordinates of points together into a single argument / return value. This is a design decision, and you may choose to use this approach in your functions or not. For example, my function that colors a certain pixel a given color has the following header:



color_pixel(turt, point, color)







where point is expected to be a 2-tuple point = (x, y), and color = (r, g, b) is a 3-tuple of the RGB color values. I could also have written it




color_pixel(turt, px, py, r, g, b)







but I think it’s cleaner to pass points and colors to functions as tuples.




How solidly lled in your triangle is depends on how many iterations of the chaos game you run and how large your canvas is. A smaller canvas has fewer pixels to ll in, so fewer iterations will make a more solid picture, but it will have lower resolution. A large picture requires more iterations but has higher de nition. Feel free to experiment with running more iterations to get larger, higher-de nition triangles, but please turn in code that runs 10000 iterations and runs in less than 5 seconds. To keep things fast, remember that you can choose how often to call turtle.update(); for maximum speed, call it once after all your iterations are complete. The images below show what you can expect your drawing to look like with 10000 iterations for a few di erent canvas sizes.



Here’s a 200x200 output:























































Here’s a 100x300 output:




Here’s a 200x100 output:





































Guidelines



Please make sure your program follows these guidelines:




Your code should run 10000 iterations of the chaos game and run in under 5 seconds.




Your functions should not directly make use of (refer to) any global variables. Any information a function needs to do its job should be passed into the function as a parameter.




Your code should do all the drawing (i.e., color all pixels) with the Turtle object returned by the setup function. Don’t create any additional turtles.




Each of your functions, and the main program, should not be too long. Not counting comments, docstrings, and blank lines, my main program (the part in the if __name__ == "__main__": block) is just under 20 lines and each of my functions is less than 10 lines. If you nd yourself writing a continuous block of code that’s longer than about 30 lines (not counting comments and blank lines), think about how you could break it up into logical subtasks and write functions to accomplish each one.




Your functions and variable names should be descriptive but not overly long. For example, your corner 1 variable should probably not be called c1, nor should it be called the_top_middle_corner_of_the_triangle. Somewhere in between is best.







Submission




Take a screenshot of the drawing produced on a canvas with width = 300, height = 120, and name it triangle.png. Zip both les into a zip le called a4.zip and submit it to the A4 Code assignment on Canvas. As usual, please ll out the A4 Hours survey with an estimate of the hours you spent on this assignment.

Rubric




Submission Mechanics (10 points)


You submitted a zip le called a4.zip containing sierpinsky.py.
1




Your zip le also includes triangle.png, a screenshot of your program’s result on a
4
300x120 canvas.






Your sierpinski.py program runs in under 5 seconds.
4




sierpinski.py contains comments including your name, date, and description at the
1
top






Code Style and Clarity (36 points)


Your program de nes at least two additional functions beyond the provided setup, dis-
10
tance, and midpoint functions.






Each function you introduce has a docstring containing a clear function speci cation.
8




Your functions do not make use of any global variables.
6




The main program and each individual function is not excessively long.
6




The names of functions and variable names are descriptive but not too verbose.
6




Correctness (34 points)


The triangle is drawn correctly for a square window
10




The triangle is drawn correctly for a non-square window
10




The rst ten points generated are not added to the image.
4




Each corner is colored one of red, green and blue as described above
5




The colors gradually blend according to their distance from each corner
5








Total
80 points







6 Challenge Problem




Take a look at the following web page: http://mathworld.wolfram.com/ChaosGame.html. There you can see how what we’re doing here is just one speci c case of a general idea. The general idea is you can have triangles, squares, pentagons, hexagons, etc. And you when you choose a random corner and nd the midpoint you could instead nd the point that is 1=3 of the way to the corner, or 3=8 of the way to the corner, etc.Make a copy of your main assignment program in a le named chaos.py. In this le, implement the following function:




def chaos_game(canv_width, canv_height, poly_sides, ratio):




Run a chaos game on a canvas with size (canv_width, canv_height) with n = poly_sides (i.e., a poly_sides-sided polygon)



and r = ratio (i.e., fraction of distance from the corner)




"""




This challenge may require usage of material we haven’t covered in detail (for example, lists will likely come in handy to store the corners of the polygon). If you are trying to tackle this and encounter any problems, come talk to me and I’d be happy to help. Successful completion of the challenge problem is worth 5 points of extra credit. Submit chaos.py to the A4 Challenge assignment on Canvas.