Fractal Images

Fractals are an amazing visual representation of recursion because they are composed of repeating patterns. In this section of the lab, you will write a program called fractal.py that generates two classic fractal patterns. In a main() function, your program should prompt the user to pick a pattern, pick a size, and pick a depth of recursion. The patterns available to the user should be Carpet and Snowflake (more details below). Loops may not be used. To summarize, your program should do the following:

1. Print a numbered list of available patterns, and ask the user to select one.
2. Get a size and depth from the user.
3. Draw the selected pattern on a size-by-size canvas.

In the sections below, you will find more information about the different fractal patterns that you will need to generate. We begin with an example of a “Bubble” fractal to demonstrate the concept. We then move on to the two patterns, Carpert and Snowflake, that you need to implement for this lab.

Bubble Example

Consider the following sequence of fractal patterns. (This pattern is implemented for you already in bubbles.py as an example—you do not need to implement it again in your program.)

Each pattern is built entirely out of filled circles. Notice how the pattern changes as the depth increases. The pattern can be described recursively as a single filled circle, with four patterns of one less depth and half the size, offset to the northwest, northeast, southwest, and southeast.

Design

For this fractal, the repeating function is drawing a circle, then repeating four times around the just-drawn circle. This implies that the design of the recursion is to draw a circle at a given center (x,y) and with a given radius r, then make four recursive calls with:

• new centers (one recursive call for each of the northwest, northeast, southwest, and southeast),
• half the radius of the just-drawn circle,
• one less depth (so we count down to depth == 0).

This process continues depth times. So a simple base case is to check the value of depth: if it is greater than 0, keep drawing, else stop (by returning from the function).

Implementation

The code used to implement this fractal is provided for you in bubbles.py. Run the program and try to understand how it works. Please feel free to use this example to help you with the following fractals.

Carpet

The Carpet pattern, also known as Sierpinski’s Carpet, is built entirely out of filled squares. The pattern can be described recursively as a single filled square (whose sides are one third the width of the region containing the square), with eight patterns of one lesser depth and one third the size, offset to the north, northeast, east, southeast, south, southwest, west, and northwest. See the examples below.

Design

At this point we’re ready to define our recurrence more precisely. When designing recursive algorithms, it’s critical that you think about how your recurrence works not just at the top level, but also at subsequent levels. It’s easy to define a recurrence that does what you intend on the first step, or even the first few steps, but then breaks down on deeper iterations.

In this case, it’s tempting to simply say that the largest square is drawn centered halfway from top to bottom and side to side, and the next recursive calls are made centered at 1/6 width by 1/6 height (for the northwest repeat), 1/2 width and 1/6 height (for the north repeat), etc. Unfortunately, that description doesn’t lend itself to a useful recurrence. What happens now when the lower-right subproblem is solved recursively?

To deal with this, we need a more general description. In particular, try to figure out what it would mean to draw this pattern with depth depth in a square area with sides of length size, and a center point with coordinates x, y. Note that you shouldn’t assume that x and y corresponds to the middle of the canvas, because in many recursive calls they won’t. It might be helpful to work through the details of this recurrence on paper.

Implementation

Now create a function called carpet() in your fractal.py program that generates this pattern. You’ll need to decide upon a few things. In particular, what parameters will this function take in? And what will the initial call to this function look like? If something goes wrong, find the smallest depth at which things break down and trace through what your program is doing. You may find you’ve implemented your design incorrectly, or you may need to revisit the algorithm itself. Along the way, make sure to comment your code.

Snowflake

The Snowflake, also known as Koch’s Snowflake, is a fractal made from line segments.

Design

To understand the Snowflake design, let’s think about drawing only one of the three sides of the Snowflake (for example, focus on the bottom side of the Depth 1 Snowflake above). When depth == 1, the side is just a line. For higher depths, the side is made up of several lines. What does this hint about the base case of the recursion?

For depth == 2, the side is no longer a single line, but four line segments—each with one third the length of the line at depth == 1 and some angles between those lines. Altogether, these four line segments replace one edge of the triangle from depth == 1. For depth == 3, each line in depth == 2 is replaced with the same pattern, just as the line from depth == 1 was replaced to create depth == 2. This hints that the recursion involves drawing four lines with angle rotations between them.

Once we understand the recursion for each side of the snowflake, then the only thing left to do is to draw all three sides of the fractal. Unlike the other fractal patterns, the recursive function doesn’t draw the entire snowflake, but only one side. So instead we need three total calls to the snowflake() function in our main function (one call for each side). Remember that you’ll have to rotate the pen after each call to snowflake() in order to draw each side.

Implementation

Now create a function called snowflake() that generates one edge of the Snowflake pattern. What parameters does it require? Below are some picture functions you may find useful for this pattern.

• picture.rotate(theta) - rotate pen theta degrees clockwise (note that theta can be positive or negative)
• picture.draw_forward(d) - draw a length-d line from the current position in the current direction
• picture.set_position(x,y) - move the pen to position (x,y)

You are required to draw your snowflake such that, for any depth d, it is fully visible (i.e. nothing drawn outside the canvas!). You are welcome to center your snowflake, but that is not a requirement.