Lab 8: Creating fractals with recursion

Due 11:59pm Tuesday, April 5, 2011

The goal of this program is to learn about recursion by designing fractal patterns. A fractal is a seemingly complex pattern that is built up from many copies of some rather simple base pattern. We will again be using the graphics library that we used in earlier labs.

To start, run update21b to create the cs21b/labs/08 directory containing two initial files called triangle.py and tree.py. Edit these files to create your solutions for this lab.


1. Draw a triangle fractal pattern

In triangle.py, write a recursive function:

  fracTriangle(window, top, left, right, color, n)
that takes as parameters a GraphWin window, three Points (top, left, and right), a color that will be "black" or "white", and an integer n which is the recursive depth. The fracTriangle function should draw a triangle of color color in the graphics window and then, depending on the depth n, either return or recursively use the fracTriangle function to draw smaller triangles as described below.



The base case: n = 0

Recall that every recursive function needs a base case where the recursion ends. For your fracTriangle function, the base case should occur when n is zero; your fracTriangle function should use top, left, and right to draw a single triangle of the given color, and then return. For example, with color="black" and n=0, your function should produce something like the single triangle below. (Your image should not contain the text labels "top", "left", and "right". We just put them in the image here to clarify how the triangle is drawn.)


The recursive case: n > 0

If n is greater than zero, your function should use top, left, and right to draw a triangle of the appropriate color and then use three recursive calls (with depth n-1) to draw smaller triangles inside the given triangle. The three recursive calls should draw triangles of the opposite color defined by the points illustrated below:

  1. top, midLeft, and midRight
  2. midLeft, left, and midBottom
  3. midRight, midBottom, and right
For reference, the diagram below was produced with depth n=1 and color="white". Your program should not produce any text labels; we just put the labels here to clarify the various points you should use when recursively calling the fracTriangle function. Also note that the center area (marked here in French) was not drawn using the fracTriangle function; it is just the white area that was left when the other three black triangles were drawn.


The left image below was drawn with n = 2 and color = "black", and the right image was drawn with n = 3 and color = "white":


Using larger depths can lead to attractive patterns, but can take a long time! The following diagram was drawn with color="white" and n=7:



The main function

In main(), your program should read in a recursive depth n and initial color (which must be "black" or "white") and draw the pattern of the appropriate recursive depth.

To summarize, here are some hints for the recursion:



2. Fractal trees

In tree.py, you will write a program that draws a fractal tree using recursion. Your tree will be drawn using a recursive function:

  drawBranch(window, n, start, length, angle, scale, splitAngle)
that takes the following parameters:


The base case: n = 0

If the recursive depth n is 0, drawBranch should draw a small green circle -- a leaf -- at the Point start and then return; this is the base case. The following image was created using some start Point and n=0:



The recursive case: n > 0

If the recursive depth n is not 0, drawBranch first draws a single branch, and then recursively uses two calls to the drawBranch function to draw more branches or leaves.

A branch is just a brown Line drawn between the given start Point and some end Point that you must compute. The position of the end Point is specified by the length and angle parameters using polar coordinates. You can compute the x and y coordinates of the end Point using the following equations:

  endX = startX + length*cos(angle)
  endY = startY + length*sin(angle)
where angle is in radians and startX and startY are the x and y coordinates of the start Point.

For some start Point, length, a vertical angle, and n = 1, drawBranch produces the image below. Note that the initial call to drawBranch draws just the brown branch, and the green leaf is produced by recursive calls with a smaller n.


For n = 2, drawBranch produces:


Carefully consider the above image for n = 2. In this image, the bottom (thicker, vertical) branch is drawn by the initial call to the drawBranch function. Each of the thinner, non-vertical branches is drawn using a recursive call from the drawBranch function -- one call for the left branch and one call for the right branch -- using a different start Point, length, and angle.

For those thinner, non-vertical branches:

Using a larger recursive depth can lead to very pretty trees. For instance, here are images produced for n = 3 and n = 8:



The main function
Your main function should get three pieces of information from the user:
  1. n: recursive depth of tree (e.g., the number of branches between the trunk and a leaf.)
  2. splitAngle: the angle between two branches in each level of the tree (e.g., 15.0 degrees)
  3. scale: the relative length of a smaller branch relative to a bigger branch at each level in the tree. (e.g., 0.7 is a good scale factor).

Some hints:




3. Koch curves (Optional)

Note: This is not required and should only be attempted once the previous two parts are working correctly. This problem is more difficult.

Below are examples of six Koch curves that have recursion depths from 0 (a straight line) at the top to 5 at the bottom.

A Koch curve is created by breaking a line segment into thirds and replacing the middle segment by two segments that are equal in length. This creates a two-sided equilateral triangle in the middle (e.g., all angles are 60 degrees).

You should start by creating a program called koch.py. You will write a function:

drawKochCurve(win, n, start, end, angle)
which draws a Koch curve from point start to a point end with recursion depth n where angle specfies the angle of the line that connects start to end.

A Koch curve of recursion depth n is formed by four Koch curves as follows:

  1. drawing a Koch curve of length length/3 with degree n-1 and angle
  2. drawing a Koch curve of length length/3 with degree n-1 and angle-radians(60)
  3. drawing a Koch curve of length length/3 with degree n-1 and angle+radians(60)
  4. drawing a Koch curve of length length/3 with degree n-1 and angle

Hint: Each one of these recursive calls is starting from a different starting point.

Once you have successfully create a single Koch curve, you can put three Koch curves to create a Koch snowflake. The snowflake shown below is an example of a Koch snowflake made with 3 Koch curves.


Submit

Once you are satisfied with your programs you can hand them in by typing handin21b in a terminal window.