Tuesday, Thursday
9:05 (ILR 315)
11:15 (Call Aud)

CS 1110: Introduction to Computing Using Python

Fall 2018

Assignment 4:
Turtles

Due to CMS by Thursday, October 25th at 11:59 pm.

Computer graphics can be tricky, and you often need a lot of experience with programming before you can get started. However, for over fifty years, the LOGO Turtle has allowed elementary-school students to draw cool and interesting shapes on their computer. And if they can do it, so can you.

The Turtle is a cursor on the screen that uses a Turtle for its icon. To draw a line, you push the Turtle forward. The screen draws a line of the same color as the Turtle (which can be changed at any time) along its path of movement. To draw more interesting shapes, you simply change the direction of the Turtle. With a few more commands you can even draw solid shapes.

While programming languages have come a long way since the early days of LOGO, the graphics Turtle lives on. Every major programming language, from C/C++ to Java to Python, has a version of the Turtle. For today's assignment you get to participate in this 50 year tradition, and hopefully have some fun in the process.

This assignment is a little harder than the previous one, but you have two full weeks to work on it. In the past we have found this to be more than enough time for this assignment. But get started early! If you do not know where to start, or if you are completely lost, please see someone immediately: either the instructor, a TA, or a consultant. A little in-person help can do wonders.

Again, please remember to fill out the survey telling us how long you worked on this assignment.

IMPORTANT

We discovered a last minute bug in the Turtle class when were finishing this assignment. We originally thought that the bug is minor, but problems on Windows demonstrated that it was worse that we thought. You will all need to upgrade your version of introcs to complete this assignment.

Open the command shell and type

  pip install --upgrade introcs

You may see a warning that you do not have permission to do this. If that is the case, you will need to run this command in administrator mode. In Windows, right-click on the PowerShell icon to run it in Adminstrator mode. On MacOS, you will need to use the sudo command. Type

  sudo pip install --upgrade introcs

This will ask you for your password before continuing. If this does not work, talk to a consultant to help you upgrade.

Learning Objectives

This assignment serves several important roles.

  • It introduces you to the famous Turtle, which is a great way to learn a new language.
  • It gives you experience with writing simple for-loops.
  • It gives you experience with recursion.
  • It gives you experience with complex objects that have both attributes and methods.
  • It gives you experience with using asserts to enforce your preconditions.

Table of Contents

Authors: D. Gries, W. White, L. Lee, S. Marschner.


Academic Integrity and Collaboration

Academic Integrity

This is a classic assignment that is continuing because students really like it. But when we say classic, we mean really, really old. While we did mix it up a bit this year, there are guaranteed to be solutions to many of these problems in the wild. Please avoid looking at solutions online, or looking code from other students this semester, or semesters previous.

In this assignment, it is highly unlikely that your code for this assignment will look exactly like someone else's. We will be using Moss to check for instances of plagiarism. We also ask that you do not enable violations of academic policy. Do not post your code to Pastebin, GitHub, or any other publicly accessible site.

Collaboration Policy

You may do this assignment with one other person. If you are going to work together, then form your group on CMS as soon as possible. If you do this assignment with another person, you must work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping.

With the exception of your CMS-registered partner, we ask that you do not look at anyone else's code or show your code to anyone else (except a CS1110 staff member) in any form whatsoever. This includes posting your code on Piazza to ask for help. It is okay to post error messages on Piazza, but not code. If we need to see your code, we will ask for it.


Turtle Graphics

Python actually has a built-in Turtle provided by the turtle module. However, we find this module a bit confusing to use, particularly for a beginner. In addition, we discovered last year that Python 3 broke the Turtle on Windows. Instead, we provide an alternative Turtle, which we call the Introcs Turtle. This Turtle is provided by the module introcs, which you should be well familiar with right now.

However, you cannot access the Turtle by importing introcs. Why not? Because the Turtle uses a lot of memory and processing power and we did not want it to start up every time you import introcs. Instead, it is contained in a module inside of introcs (yes, modules can contain other modules) called introcs.turtle. So to use this module, you would instead type

  import introcs.turtle

This is a bit of a mouthful, because you will have to write introcs.turtle before all the functions in this module as well. That is why, for this assignment, we prefer the from syntax. You only need three things from this module: Window, Turtle, and Pen, which you can import as follows:

  from introcs.turtle import Window, Turtle, Pen

While we describe these in detail below, you can get even more information from the official documentation. We wrote this new Turtle from scratch and are quite proud of how powerful it is.


Assignment Source Code

This assignment is much more bare-bones than previous ones. There is only one file to download:

a4.py
This is file contains stubs for all the functions in this assignment, and is the file you will submit for a grade.

To save you time, we have given complete specifications of most of the functions you are to write. Study them carefully. Note how precise and thorough they are. You should aim for this level of quality when you start to write your own specifications.

You will not be creating a test script this time. Writing test cases for graphics is almost impossible. Therefore, you will be looking at the the drawings produced by your functions to determine correctness.

However you will notice that you can actually run a4.py as a script. Run it as a script by typing

  python a4.py

You will see that it asks you yes/no questions. Answer 'y' to this first question. The turtle will draw two lines for you. In general, answering 'y' will call the specific drawing function so that you can test it. Any other answer will skip over that drawing function. Since drawing can take a long time, this gives you a nice way to test only the specific drawing function that you are working on. However, right now it does not do much. That is because you have not started on the assignment.

If you want more control over your testing, you will need to import the functions of a4.py manually. To do this, you need to understand the introcs.turtle module a bit more. This module provides three classes: Window, Turtle, and Pen.


Window

To create a window, you use the constructor Window() and assign the result to a variable. Try this command at the interactive prompt:

>>> from introcs.turtle import Window
>>> w = Window()

This will display a window on your screen. The window object has several attributes that you can change.

Attribute Meaning Invariant
w.x x-coordinate of top left corner Must be an int
w.y y-coordinate of top left corner Must be an int
w.width Width of the window in pixels Must be an int
w.height Height of the window in pixels Must be an int
w.title Title at top of window Must be a string

Try changing the values of these attributes (with assignment statements). For example, what happens when you type the following command:

>>> w.width = 100

In addition, there are two important methods:

w.clear()
This erases the contents of the Window. It also detaches any Turtles so that they no longer work.
w.dispose()
This closes the Window permanently.

Pixels inside of the window follow a rather intuitive coordinate system. The point (0,0) is the center of the window. The x-coordinates get larger to the east and the y-coordinates get larger going up.


Turtle

The Turtle class is used to draw on your Window. Each Turtle object t has the following important attributes:

Attribute Meaning Invariant
t.x x-coordinate of the Turtle Must be an int or float.
Cannot be altered directly
t.y y-coordinate of the Turtle Must be an int or float.
Cannot be altered directly
t.heading Turtle heading in degrees counter-clockwise from east. Must be an int or float.
t.color Current Turtle color Must be a string, an RGB object, or an HSV object.
t.speed The drawing speed of this Turtle. Must be an int 1 (slowest) to 10 (fastest), or 0 (special)
t.visible Whether the Turtle icon is visible. Must be a bool
t.drawmode Whether the Turtle should draw anything when it moves; if False, nothing is drawn. Must be a bool

To create a Turtle, you use the constructor Turtle() which takes a single argument: the Window that you want to draw on. Assuming that you made a Window object w in the previous section, try the following at the interactive prompt:

>>> from introcs.turtle import Turtle
>>> t = Turtle(w)

Assuming that you upgraded introcs, you should now see a (red) Turtle on your Window. The Turtle will always start at coordinate (0,0), which means it is centered in the window. It will also face east.

The fact that Turtle and Window are separate allows you to have as many Turtles as you like so that you can draw different things with them. If at any time you have too many Turtles, use the method w.clear(). This removes all Turtles from the Window (which means that attempts to do anything with any old Turtles will fail), so you will need to add a brand new Turtle to start drawing again.

Position and Orientation

The position and heading of the Turtle are maintained using floating point numbers. This is needed for accuracy. If integers were used, errors would be introduced after only a few calculations. However, whenever a point is to be drawn in the window, its x- and y-coordinates are rounded to the nearest integer because the pixel coordinates are represented as integers.

The direction of the Turtle is called its heading. It is a number representing the angle in degrees counterclockwise from east (to the right). Thus east is 0 degrees, north is 90 degrees, west is 180 degrees, and south is 270 degrees. Negative angles and angles greater than 360 are allowed; the remainder modulo 360 is used.

While the heading attribute can be modified, the x and y attributes cannot. You can only control the Turtle's position via the methods listed below.

Important Methods

In addition to its attributes, a Turtle object t has several important methods:

t.forward(dist)
Moves the Turtle dist pixels in the direction of its current heading. If the drawmode is True, a line is drawn; otherwise, no line is drawn.
t.backward(dist)
Moves the Turtle dist pixels in the opposite direction of its current heading. If the drawmode is True, a line is drawn; otherwise, no line is drawn.
t.left(a)
Rotates the Turtle in place a degrees counterclockwise.
t.right(a)
Rotates the Turtle in place a degrees clockwise.
t.move(x,y)
Moves the Turtle t to pixel (x,y) without drawing anything.

Note that most of these methods are used to move the Turtle about the screen. This is why the attributes x and y cannot be altered directly (e.g. you cannot assign values to them). You should use these methods instead. All of these methods autoflush when the speed is not 0 (see below), and so you will see the Turtle draw as soon as they are called.

Colors

To change the Turtle color, you assign a new value to the color attribute. You can use the RGB and HSV objects from the last assignment. You cannot use a CMYK object with a Turtle; that color model is designed for printing, and not for displaying on your screen.

The Turtle also supports strings as colors. Just put the name of the color that you want in quotes; make sure the name is all lower case. For example, to make your Turtle blue, try

>>> t.color = 'blue'

If you are familiar with web colors, those are also supported. Just remember to start the string with a hashtag (#), like this:

>>> t.color = '#0099CC'

Speed

As you will discover with this assignment, the turtle can be quite slow. You can control the speed of the Turtle by setting is speed attribute. It is a number in the range 1 ≤ speed ≤ 10, with 1 slowest and 10 fastest. But even speed 10 can be quite slow. Speed 10 will draw a single line instantaneously. However, if the Turtle is drawing multiple lines, it will draw each one separately. For the radial shapes, this can take a while.

If you really want to draw quickly, you should set the speed to 0. This speed is exactly what it sounds like: the Turtle does not draw at all. This seems counter-intuitive; of course you want the Turtle to draw. But you can always tell the Turtle to draw later by calling the flush method, like this:

>>> t.flush()

When you call flush on a Turtle with speed 0, it instantaneously draws all the lines that you asked the Turtle to draw. Hence, speed 0 remembers all the drawing commands, but draws them only when you ask it to finish. This is really handy for fast drawing (and we will rely on it for grading).

For this reason, you will need to remember to flush in many of your functions in this assignment. But you should be careful how you use flush. If you call it after each Turtle step, it will update the screen before you are ready. In this case, your Turtle will be no faster than speed 10. You should only call flush at the end of a function, and only in the main functions (i.e. not the helpers).

If the speed is 1 through 10, it is unnecessary to call flush. All of the drawing methods above will autoflush (meaning they call flush for you). But it is still safe to call flush for these speeds anyway.


Drawing with the Turtle

Throughout this assignment, you will be asked to draw shapes with a Turtle. There are three ways to do this. The first is to type Turtle commands directly in the Python interactive shell. You should do this right now to familiarize yourself with the Turtle class and its methods. For example, try these commands:

>>> from introcs.turtle import Window, Turtle
>>> w = Window()
>>> t = Turtle(w)
>>> t.color = 'green' # This will flush and show the turtle
>>> t.forward(100)
>>> t.color = 'red'
>>> t.right(90)
>>> t.forward(150)

As you type the lines up to and including t.color = 'green', you will see a window appear with a Turtle at the center facing east. As you type the other commands, the Turtle will change color, move, and draw lines.

The second way to draw is to add new procedures to the module a4.py and call them from the interactive prompt. If you look at the file, you will notice that it contains a procedure draw_two_lines. We gave you this procedure to show you how to write a graphics procedure. Note that it takes the Window object as an argument, so it does not create a new window. It also does not clear the Window, though we might want our other functions to do that. All it does is create a Turtle, and use that Turtle to draw two lines.

To try out this function, navigate to the directory containing the file a4.py and start up the interactive prompt. Then type:

>>> from introcs.turtle import Window
>>> w = Window()
>>> import a4
>>> a4.draw_two_lines(w,2)

This will draw two lines in the window w, at speed 2. Study the body of draw_two_lines, as it will help you with all of the tasks in this assignment.

For the remainder of this assignment, you will be writing procedures that draw shapes, much like draw_two_lines. As you write a procedure, refer constantly to the specification. Follow it carefully. If you have to call another procedure, look at its specification and make sure you follow it. A huge number of programming errors arise from not following specifications carefully.


Pen

Objects of type Pen are very similar to Turtle objects, except that they draw a bit differently. You create a Pen just as you would a Turtle. At the interactive prompt try

>>> from introcs.turtle import Pen
>>> w = Window()
>>> p = Pen(w)

The pen icon does not look like a turtle. Instead, it looks like a diamond on its side with two different colors. With that said, this Pen object has a lot of attributes in common with a Turtle object. It draws from the tip on the left, and the left-side color is the drawing color.

However, the Pen does not have a heading attribute. Instead, for a Pen object p, you draw with the following methods.

p.drawLine(dx,dy)
Draws a line starting from the current Pen position with distance dx pixels along the x-axis and dy pixels along the y-axis.
p.drawTo(x,y)
Draws a line starting from the current Pen position to the pixel (x, y).
p.drawOval(xrad,yrad)
Draws a oval of x-axis radius xrad (in pixels) and y-axis radius yrad centered at the current Pen position.
p.move(x,y)
Moves the Pen p to pixel (x,y) without drawing anything.

Solid Shapes

The Pen also does not have a drawmode attribute. The four methods listed above either always draw (drawLine, drawTo, drawOval) or never draw (move). What the Pen has is a solid attribute. When this attribute is True, the Pen will enter into a "solid mode". Anything that is drawn between now and when the attribute becomes False (or when a call to move is made) will result in a solid shape.

For example, to draw a solid square, try the following sequence of commands with your Pen.

>>> p.fillcolor = 'blue'
>>> p.solid = True
>>> p.drawLine(0,50)
>>> p.drawLine(50,0)
>>> p.drawLine(0,-50)
>>> p.drawLine(-50,0)
>>> p.solid = False

When you finish, the pen will fill the insides of the square with the color blue.

Because the pen can draw solid shapes, it actually has two color attributes: fillcolor and edgecolor (there is no simple color attribute in Pen). The fillcolor is the color it uses inside a solid shape, and edgecolor is the color for hollow shapes as well as the border of solid shapes. When you look at the pen icon, the edge color is the color on the left and the fill color is the color on the right.


Assignment Instructions

This assignment is broken up into five tasks. Each task corresponds to a procedure stub (or collection of stubs) in a4.py. You will find this assignment to be a lot easier if you complete and fully test one task before moving on to the next.

We do not require that you make a test module this time. We have provided the test procedure main() which calls the various drawing functions. It is the procedure called when you run the module as a script. Feel free to make any changes that you wish to this function. We will not look a the body of this function when we grade your assignment.


Asserting Preconditions

As we saw in class, it is very helpful to assert your preconditions when you are using recursion or iteration. This keeps you from being caught in an (effectively) infinite loop.

Through out the code in a4.py, we have placed assert statements in the various function stubs. However, we do not guarantee that they are enough. When you complete a function, we expect that you fully check your precondition with assert statements. If the provided assert statements do not fully check your precondition, then you must add more.

To help you with this process, we have provided you with several helper functions at the very top of a4.py. All of these helper functions return a boolean value: True or False. These helper functions are to be used inside of an assert to check part of a precondition, as shown throughout the code.

As we saw in class, it is quite common to use helper functions to check preconditions. Some of the preconditions in this assignment can be quite complex. In particular, look at the function for is_valid_color(). This allows us to simplify our assert statements a lot.

You will also notice that we have a helper function called report_error. In the past, we discovered that students are quite prone to make coding mistakes in their assert error messages (particularly adding a non-string to a string). This function is a nice way to make error messages that is fairly foolproof.


Task 1. Triangles

Complete the procedure draw_triangle(t,s,c). This procedure is given a Turtle as a parameter. You do not need to make a new Turtle, nor a new Window.

This procedure should draw an equilateral triangle of side length s and color c using Turtle t. It should draw the triangle using t's current position, orientation, and speed. The Turtle should end its drawing at the same position and orientation as when it started. Do not save the Turtle's position and orientation at the beginning and then restore them at the end. If you draw the triangle correctly, following the instructions in the procedure specification, then this should happen automatically.

Remember to flush the Turtle at the very end of the procedure. If you do not do this, your Turtle will not draw anything when the speed is 0. However, only flush once. Do not flush after each line drawn.

To try out the procedure, type the following in interactive mode.

       
>>> from introcs.turtle import Window, Turtle
>>> import a4
>>> w = Window()
>>> t = Turtle(w)
>>> a4.draw_triangle(t,200,'green')

Task 2. Hexagons

Complete the procedure draw_hex(t,s). This method should draw six equilateral triangles using color 'cyan' with side lengths s. This triangles should form a hexagon, as illustrated to the right. Follow the specification and hints carefully. In particular, be sure to use the helper function suggested. Do not try to repeat code already written. However, you should still remember to flush in this procedure after you restore the Turtle attributes, even though you already flushed in draw_triangle.

For both draw_triangle and draw_hex, it is very important that you follow the specifications. If you do not follow the specifications exactly, we will deduct points. In particular, pay close attention what we say about the state of the Turtle. Did you make any changes to Turtle attributes that need to be changed back to what they were orginally?


Task 3. Radial Shapes

Choose two (and only two!) from the following three activities: spirals, polygons, or radiating lines. Once you have done two of these, you are free (but not required) to do the remaining one. These are pretty fun assignments. If you decide to do all three, we will grade you on the best two (though there is no extra credit beyond that).

Each of these tasks involves creating a helper procedure. In each case, the main procedure does not have a Turtle as parameter, but its helper procedure does. The main procedure clears the Window, creates a Turtle, calls the helper procedure to do the work, then hides the Turtle. Note that some of these procedures are very particular about which way that the newly created Turtle should start out facing. Remember that you can control the facing of your Turtle via the heading attribute.

When one of these procedures completes, you should flush the Turtle to handle speed 0 properly. However, you should only flush in the main procedure, and at the end. Never flush in the helper functions.

When writing these procedures, write the main procedure first, then the helper, and finally test both by calling the first one in python. If the main procedure is foo, its associated helper is called foo_helper. We have created stubs for all of these procedures in a4.py. Do not change the headers (either the names or the parameters), as our grading software will be calling them by those names. Just fill in the bodies.

Once again, it is very important that you follow the specifications for all three procedures below. If you do not follow the specifications exactly, we will deduct points. Pay close attention what we say about the state of the Turtle. Did you make any changes to Turtle attributes that need to be changed back to what they were orginally?

Spirals

The first picture to the right is done by drawing 10 lines. The lines have length 10, 20, 30, ... . After each line, the Turtle turns left 90 degrees. The second diagram to the right shows a similar spiral but with the Turtle turning left 75 degrees after each line.

Complete the procedures draw_spiral and draw_spiral_helper. Pay close attention to how the lines grow at each step. Also pay close attention to how these change color. These are all import parts of the specification.

When you first test these function, use 10 for the initial side length. Try different angles, like 90 degrees, 92 degrees, 88 degrees, and so on. You will be amazed at what these procedures do. Find out by trying these calls (after creating the Window w):

  draw_spiral(w,  8,  90, 300, 10)
  draw_spiral(w,  8, 135, 400, 10)
  draw_spiral(w,  9,  60, 100, 10)
  draw_spiral(w,  9, 121, 500, 10)
  draw_spiral(w, 10,  89, 400, 10)
  draw_spiral(w, 10, 150, 300, 10)
  draw_spiral(w, 10,-144, 500, 10)

Polygons

The first image to the right is a 10-sided polygon. The second image to the right is a series of 100 10-sided polygons, the first started at angle 90, the second at an angle of 90 + 360.0/100, the third at an angle of 90 + 2*360.0/100, and so on. This demonstrates the kind of cool pictures you can draw just with polygons (for those of a certain age, this is very reminiscent of a Spirograph).

Complete the procedures multi_polygons and multi_polygons_helper so that your program can draw such designs. You should use the procedure draw_polygon, which we have provided, as a helper function (do not modify this procedure).

You should also pay attention to the color alternation. As you can see in the 100 polygon picture, we alternate the color blue and red. When your are finished, experiment to see what neat designs come out. For example, try the following (after creating the Window w):

  multi_polygons(w, 45,  3, 100, 10)
  multi_polygons(w, 60, 30,  20, 10)

Radiating Lines

The picture on the left consists of 16 lines of the same length radiating out from the initial Turtle position. The angle between the lines is the same. The second picture has 300 lines. If n lines are drawn, the angle between them is 360.0/n. Furthermore, the color of each line depends on the angle (i.e. the direction) of each line.

Note that the Turtle color attribute will accept HSV objects. A line drawn at angle ang uses the color HSV(ang, 1.0, 1.0). Just assign the object to the attribute and start drawing. This should make this part of the assignment fairly straightforward. Remember the invariants for an HSV object when you are drawing.

Complete the procedures radiate and radiate_helper. When finished, test them with small values of n, like 4 or 8. After the procedures are completely tested, try them with 360 lines of length 200. Also, try 2000 lines and Turtle speed 0 (which should be instantaneous if you wrote the procedure correctly), and notice how much more filled in the disk becomes.


Task 4. Recursive Solids

In this next two tasks you will draw some fractals. A fractal is a shape that has parts which (when you zoom in) look like the whole shape. This suggests that you will need to use recursion to draw them. The number of recursive steps (or depth) determines the resolution of the fractal drawn. Wikipedia has a wealth of information about these and other fractals.

This time you are to choose one (and only one) from the following two shapes: the Cantor stool or the T-Square. Once again you are free (but not required) to complete them both. If you do both of them, we will grade the best one.

Throughout both of these tasks, we ask that you use a Pen instead of a Turtle because (1) there is no need to maintain the direction and (2) Pen methods can draw solid shapes. See the overview of the Pen above for more information.

As with the radial shapes, for each of these recursive tasks, you will implement two procedures, a main procedure and a helper. The main procedure clears the Window and creates a new Pen. It also calls the helper to do the drawing, then cleans up afterward. The main procedure does not have a Pen as a parameter (though it does have the Window as a parameter), while the helper does. You should flush at the end of the main procedure, but not in the helper.

The helper is the function that does all the real drawing. It is the function that is supposed to call itself recursively. The main procedure is not recursive.

Once again, it is very important that you follow the specifications for all three procedures below. If you do not follow the specifications exactly, we will deduct points. Pay attention to when the Pen should and should not be visible.

Cantor Stools

The Cantor stool is a 2-dimensional version of the Cantor set. The legs of the stool are formed by the recursive calls beyond the base case. Below are the Cantor stools for depths 0, 1, 2, and 3 respectively. The width of each stool stool is side and the height of the stool is hght. In depth 0, there is no recursive call and so the stool is a simple rectangle. In depth 1, there is a single recursive call, and the stool was cut in half vertically. The horizontally, the legs take up the first and last third of the width. In depth 2, the legs of the stool are themselves stools.

Cantor Depth 0 Cantor Depth 1 Cantor Depth 2 Cantor Depth 3
Depth 0 Depth 1 Depth 2 Depth 3

In general, we construct a Cantor stool as shown below. In the base case, we draw a simple rectangle. For later depths, divide the rectangle in half vertically, drawing a rectangle with width size and height hght/2. For the legs, draw stools of one less depth whose width is size/3. You will need to reposition the stools so that they line up with the edges of the top rectangle.

Cantor Stools

We have stubbed in the procedures cantor and cantor_helper for you to complete. We have provided a procedure fill_rectangle, which you can use to draw a solid triangle. You should not modify fill_rectangle (even though it is missing asserts).

T-Squares

The T-Square is an interesting shape because it is a smaller square that is growing into a bigger square. Each additional depth fills in more of the bigger square. If you were to continue your recursive calls infinitely, it would just look like a solid (bigger) square.

Below are the T-squares for depths 0, 1, 2, and 3 respectively. In depth 0, there is no recursive call and so it is just a square of width and height side. In depth 1, there is a single recursive call and so we center smaller squares (of width side/2) on the corners of the original square. In depth 2, the corners are themselves T-squares.

T-Square 0 T-Square 1 T-Square 2 T-Square 3
Depth 0 Depth 1 Depth 2 Depth 3

In general, we construct a T-Square as shown below. In the base case, we draw a simple square. For later depths, we draw four T-Squares of half the size on each corner. You will need to reposition the T-Square so that they centered properly.

T-Squares

We have stubbed in the procedures tsquare and tsquare_helper for you to complete. As with the Cantor stool shape, you will want to use fill_rectangle as a helper.


Task 5. Koch Snowflake

For the last task, you will implement one of the most famous fractals of all time: the Koch Snowflake. This is different from the shapes in Part 4 in that it is a line drawing and not a solid shape. The basic shape is an equilateral triangle, just like the procedure draw_triangle. Later shapes embellish the edges to add cool crystalline effects.

Snowflake Depth 0   Snowflake Depth 1   Snowflake Depth 2   Snowflake Depth 3
Depth 0   Depth 1   Depth 2   Depth 3

The important thing to understand about the Koch Snowflake is that the recursion is not applied to the triangle. It is applied to the edges. The basic edge is a straight line. Later shapes break the edge into three parts and put an equilateral "bump" in the middle third (using four edges instead of three). These four edges are themselves snowflake edges of one less depth.

Edge Depth 0   Edge Depth 1   Edge Depth 2   Edge Depth 3
Depth 0   Depth 1   Depth 2   Depth 3

Because this is a line drawing, you will be using the Turtle once again. Using the Turtle to draw a recursive shape can be quite tricky because you have to handle the orientation correctly. In the diagram below, we assume that the Turtle is drawing the edge west-to-east. However, if you code the turns correctly, it will work no matter what the initial orientation of the turtle is.

At each step, the Turtle draws an edge of one less depth. The Turtle first draws an edge for one third of the side length (Step 1). Once it reaches a third of the way, it turns 60 degrees left to start the bump and draws another edge of one third the side length (Step 2). It turns back to the right 120 degrees and draws another edge of one third the side length (Step 3). Finally, it straightens out and draws a final edge of one third the side length (Step 4).

Edges

Finally, you have to put the edges together to form a Koch Snowflake. The code is very similar to draw_triangle in that you draw an equilateral triangle, but you draw the edges, as shown below.

Snowflake

This composition step is not recursive, so it belongs in the main procedure and not the helper function. In addition, the main procedure needs to position the "triangle" correctly. The snowflake should be centered at (0,0) and not have the bottom left corner at (0,0). The center of a snowflake is the center of the circle that can be drawn inside (inscribed) the snowflake. Looking at the diagram below, you can see that an equilateral triangle of side length s contains a circle of diameter s/sqrt(3) anchored at the bottom edge centered horizontally. Use this information to pick the starting location of your turtle.

We have stubbed in the procedures snowflake and snowflake_edge for you to complete. You will notice that, while snowflake places the Turtle in the lower left corner oriented 60 degrees, snowflake_edge makes no assumption about the orientation. That is because snowflake_edge must be able to draw the edge in several different orientations.

Equilateral

If you are unsure of how to approach this function, look at the Hilbert curve example from class. This example uses a Turtle to recursively draw a shape in much the same way.

Koch Snowflakes are particularly spectacular for large recursion depths. For example, the picture below is for depth 6. Note that it can take a long time to draw this shape, however. Each depth that you add effectively doubles the drawing time for the Turtle. That is why you need to be able to support speed 0 and make sure that you flush in the main procedure.

Snowflake Depth 6
Koch Snowflake (Depth 6)


Finishing the Assignment

Before you submit this assignment, you should be sure that everything is working and polished. Unlike the first assignment, you only get one submission for this assignment. If you make a mistake, you will not get an opportunity to correct it. With that said, you may submit multiple times before the due date. We will grade the most recent version submitted.

Once you have everything working you should go back and make sure that your program meets the class coding conventions. In particular, you should check that the following are all true:

  1. There are no tabs in the file, only spaces (this is not an issue if you used Atom Editor).
  2. Functions are each separated by two blank lines.
  3. Lines are short enough (80 chars) that horizontal scrolling is not necessary.
  4. The specifications for all of the functions are complete and are docstrings.
  5. Specifications are immediately after the function header and indented.

Upload this file to CMS by the due date: Thursday, October 25th at 11:59 pm.


Survey

In addition to turning in the assignment, we ask that you complete the survey posted in CMS. Once again, the surveys will ask about things such as how long you spent on the assignment, your impression of the difficulty, and what could be done to improve it. Please try to complete the survey within a day of turning in this assignment. Remember that participation in surveys comprise 1% of your final grade.


Course Material Authors: D. Gries, L. Lee, S. Marschner, & W. White (over the years)