ASSIGNMENT #5 - Recursive Graphics

In this assignment, you will make a program that draws a Sierpinski triangle. You will then develop a program that draws a recursive pattern of your own design. You will get practice in using recursion and drawing graphics. The library files you will need to do graphics can be downloaded here: Lab5.zip.

Part 1.   The Sierpinski triangle is another example of a fractal pattern like the H-tree pattern we covered in the lecture on recursion. The Polish mathematician Wacław Sierpiński described the pattern in 1915, but it has appeared in Italian art since the 13th century. Though the Sierpinski triangle looks complex, it can be generated with a short recursive program. Your task is to write a program Sierpinski.py with a recursive function sierpinski() and a main function that calls the recursive function once, and plots the result using standard drawing. Think recursively: sierpinski() should draw one filled equilateral triangle (pointed downwards) and then call itself recursively 3 times (with an appropriate stopping condition). When writing your program, exercise modular design: include a (non-recursive) function filledTriangle() that draws a filled equilateral triangle of a specified size at a specified location.

Your program shall take one integer command-line argument N, to control the depth of the recursion. All of the drawing should fit snugly inside the equilateral triangle with endpoints (0, 0), (1, 0), and (1/2, √3/2). Do NOT change the scale of the drawing window. First, make sure that your program draws a single filled equilateral triangle when N equals 1. Then, check that it draws four filled equilateral triangles when N equals 2. Your program will be nearly (or completely) debugged when you get to this point.

API specification. Your program Sierpinski.py must be organized as a library of functions with the following API:

--------------------------------------------------------------------------------
     filledTriangle(float x, float y, float s)        // draw shaded equilateral triangle with
                                                         bottom vertex (x, y), side length s

     sierpinski(int n, float x, float y, float s)     // draw one triangle, bottom vertex (x, y), side s;
                                                         recursively call itself three times to generate
                                                         the next order Sierpinski triangles above, left
                                                         and right of current triangle

     __main__                                         // read order of recursion N as a command-line
                                                         argument; draw gray outline triangle with endpoints
                                                         (0, 0), (1, 0), and (1/2, √3/2); generate an
                                                         N-order Sierpinski triangle inside the outline

Examples. Below are the target Sierpinski triangles for different values of N.

	% python Sierpinski.py 1	% python Sierpinski.py 2	% python Sierpinski.py 3
	% python Sierpinski.py 4	% python Sierpinski.py 5	% python Sierpinski.py 6

A diversion: fractal dimension.   In grade school, we learn that the dimension of a line segment is one, the dimension of a square is two, and the dimension of a cube is three. But you probably didn't learn what is really meant by dimension. How can we express what it means mathematically or computationally? Formally, we can define the Hausdorff dimension or similarity dimension of a self-similar figure by partitioning the figure into a number of self-similar pieces of smaller size. We define the dimension to be the log (# self similar pieces) / log (scaling factor in each spatial direction). For example, we can decompose the unit square into 4 smaller squares, each of side length 1/2; or we can decompose it into 25 squares, each of side length 1/5. Here, the number of self-similar pieces is 4 (or 25) and the scaling factor is 2 (or 5). Thus, the dimension of a square is 2 since log (4) / log(2) = log (25) / log (5) = 2. We can decompose the unit cube into 8 cubes, each of side length 1/2; or we can decompose it into 125 cubes, each of side length 1/5. Therefore, the dimension of a cube is log(8) / log (2) = log(125) / log(5) = 3.

We can also apply this definition directly to the (set of white points in) Sierpinski triangle. We can decompose the unit Sierpinski triangle into 3 Sierpinski triangles, each of side length 1/2. Thus, the dimension of a Sierpinski triangle is log (3) / log (2) ≈ 1.585. Its dimension is fractional—more than a line segment, but less than a square! With Euclidean geometry, the dimension is always an integer; with fractal geometry, it can be any fraction. Fractals are widely applicable for describing physical objects like the coastline of Britain.

Part 2.   In this part you will design and create your own recursive fractal. Your job is to write a program Art.py that takes one integer command-line argument N (to control the depth of recursion) and produces a recursive pattern of your own choosing. It should work and stay within the drawing window for values 1 through 7. You are free to choose a geometric pattern (like, but not too similar to, Htree or Sierpinski) or a random construction. Your design should not be easy to generate with iteration alone. Originality and creativity in the design will be a factor in your grade.

Your Art.py program must take one integer command-line argument N (expect it to be between 1 and 7).

---

I forget how to do geometry. Any hints? Everything you need is summed up by the Pythagorean theorem:
The sum of the squares of the two side lengths of a right triangle, a and b, equals the square of the length of the hypotenuse, c.

Here are the coordinates of the critical endpoints for the first few levels of the Sierpinski triangle. Click the image for a bigger version.

How do I draw an equilateral triangle? Use StdDraw.polygon() or StdDraw.filledPolygon() with appropriate parameters. Both methods take two parallel lists of floating point numbers, the first containing the x-coordinates of the vertices and the second containing the y-coordinates.

Should I be calling StdDraw.setCanvasSize(), StdDraw.setXscale(), StdDraw.setYscale(), or StdDraw.save()? No.

May I use a different color from black to fill in the triangles? Yes, you may use any color that contrasts with the white background.

How should I go about doing the artistic part of the assignment? This part is meant to be fun, but here are some guidelines in case you're not so artistic. A very good approach is to first choose a self-referential pattern as a target output. Check out the graphics exercises in Section 2.3, about halfway down the page. These are from a text on Java, but the concepts are the same for Python. Here are some good ones from a previous classes at Princeton: Spring '14. Here is a list of fractals, by Hausdorff dimension. Some pictures are harder to generate than others (and some require trig).

What will cause me to lose points on the artistic part? We will deduct points if your picture is too similar to Htree or Sierpinski. To be "different enough" from those algorithms, you need to change the recursive part of the program. For example, it is not sufficient to simply substitute squares for triangles in Sierpinski. You will also lose points if your artwork can be more easily created without recursion. This is indicated by a tail-recursive function, e.g., a recursive function that calls itself as its last action. For example, the recursive factorial method shown in lecture was tail-recursive.

May I use .gif, .jpg, or .png in my artistic creation? Yes. If so, be sure to submit the graphic files you use along with your other files.

My function for Art.py takes several parameters, but the assignment says that I can only read in one command-line argument N. What should I do? Choose a few of the best parameter values and do something like the following:

if N == 1:
     x = 0.55
     y = 0.75
     n = 3
elif N == 2:
    x = 0.55
    y = 0.75
    n = 5
elif N == 3:
    x = 0.32
    y = 0.71
    n = 8
elif ...

---

Grading. Once again, there is no Autograder.py program for this assignment since the output is graphic and the assignment is creative.

Grade Item	Points Possible	Points Earned
Programs Compiles and Runs	2
Appropriate Comments on All Classes and Methods	4
Sierpinski - filledTriangle Method	2
Sierpinski - sierpinski Recursive Method	8
Sierpinski - main	2
Art - Uses Recursion	8
Art - Dissimilar to H-Tree and Sierpinski	4
Total	30

---

Extra-credit. Create an interactive recursive graphics program. Find a way to use input such as the mouse and keyboard to create an exciting and visually engaging user experience.

---

Submission. Submit your programs Sierpinski.py, Art.py, and any supplementary files needed by Art.py using Moodle. Be sure each submitted source file has the required header with your name, and a description of the program. For extra-credit, please submit a single zip file containing all your programs/graphics/sounds via the extra-credit drop box at the top of the Moodle page.

---

Page last updated: February 09, 2022