A fractal is a geometric figure that is self-similar in that any piece of the figure contains a miniature of the entire figure. Naturally, fractals fit nicely with the concept of recursion. There are lots of fractals that have interesting mathematical properties (and make pretty pictures); in this lab you will draw two of them, Sierpinski triangles and Koch snowflakes.
If you recall from last semester, the PPM file format is a very simple file format for displaying images. It simply specifies the red, green, and blue components of each pixel within the image. For this lab (and for the coming assignment on Friday), we will be writing PPM images instead of dealing with the intricacies of turtle.
The file ppm.pyc is a "compiled" module file containing a class called PPM. This file behaves exactly as a typical module. You can import it as if it were a .py file. However, you cannot view the actual implementation. Save the .pyc file inside your lab7 directory. To understand the module, you can view documentation for this module here. This class contains all of the information you need to maintain a PPM image within your code. The key pieces to understand are that the ppm module defines 8 color constants you can use, and implements methods for drawing dots (with the size of a single pixel), and drawing lines (with the width of a single pixel).
Also note that the axis and origin of the ppm file is now different than the turtle axis. The origin of the ppm objects is the upper left corner of the image. As you progress to the right, the x coordinate is increasing. As you progress down, y is increasing.
A Sierpinski triangle (aka a Sierpinski Gasket) is a fractal that may be constructed as follows:
Draw a triangle.
Draw a new triangle by connecting the midpoints of the three sides of your original triangle. This should split your triangle into four smaller triangles, one in the center and three around the outside.
Repeat step 2 for each of the outside triangles (not the center one). Each of them will split into four yet smaller triangles. Repeat for each of their outside triangles.. and for each of the new ones.. and so on, forever. Draw a few rounds of this on paper to see how it works.
Your job is to write a program that draws a Sierpinski triangle. Think about the following:
A Sierpinski triangle is a recursively defined structure -- each of the three outer triangles formed by joining the midpoints is itself a Sierpinski triangle.
In practice you don't want to go on with the process "forever" as suggested above, so we'll limit how deep it goes. Define the depth of a Sierpinski triangle as the number of directly nested triangles at the deepest point. So a Sierpinski triangle consisting of a single triangle has depth 0; when a triangle is drawn inside of it, the resulting Sierpinski triangle has depth 1; when the three outside triangles have triangles drawn inside of them, the resulting triangle is depth 2, and so on. A depth of 8 or 9 gives a nice looking triangle in a reasonable amount of time. Smaller depths are interesting in that you can see more of the construction; higher depths generally take too long for casual viewing.
A triangle can be draw by drawing three lines between the three
vertices, corners, of a triangle using the draw_line
method of the PPM class.
The midpoint of a line segment can be calculated using interpolation. In order to find a point that is some fraction between the two points (x1, y1) and (x2, y2) the following equations can be used:
xi = i * x2 + (1 - i) * x1
yi = i * y2 + (1 - i) * y1
where i is a value between 0 and 1 that is the fraction of the distance between the two points that the point (xi, yi) is located. So, in order to find a point that is 1/2 between two points a value of i = 0.5 could be used.
The file sierpinski_triangle.py
contains the skeleton of a program to draw a Sierpinski triangle.
Your code for the recursive definition of the sierpinski triangle
should be contained within the draw_sierpinski method.
The method should draw the triangle whose verticies were passed in,
then check to see if the desired depth as been achieved; if not, it
should draw the triangle formed by the midpoints of the given verticies,
then call itself recursively on each of the outer triangles.
Try changing the color of the triangles and the location of the vertices, to create a more interesting fractal. When you are happy with your fractal, make sure it is named appropirately and saved within your lab 7 directory.
The Koch (pronounced coke) snowflake is a fractal generated by starting with 3 line segments forming a triangle (a Koch fractal of order 0). The algorithm for generating higher order Koch fractals involves splitting each line segment into three equal segments then replacing the middle segment by two line segments that protrude outward. The same algorithm is then recursively applied to each of the 4 new line segments. The diagram below illustrates the transformation of a segment.
x3 = x1 + x / 2 - y * p
y3 = y1 + y / 2 + x * p
where
x = x5 - x1
y = y5 - y1
and p is a value between -1 and 1 that is the percent length of the original segment that the protrusion will be. That is, if p is 0.5 then the protrusion would be half the size of the segment from (x1, y1) to (x5, y5). If p is -0.5 then it would also be half the size of the segment, but protrude off of the other side of the segment. A value of one third of a segment length produces a nice looking fractal.
The file koch_snowflake.py
contains the skeleton of a program to draw a Koch snowflake.
Your code for the recursive definition of the snowflake should be
written in the draw_koch method. The method should
check to see if the desired order has
been achieved. If it has, it should draw the line of the given
points. If it has not, then it should compute the four line segments
that make up the next order and call itself recursively on each.
Try changing the color of the triangles and the location and number of the initial lines. When you are happy with your fractal, make sure it is named appropirately and saved within your lab 7 directory.
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.