Homework 3: Recursive Graphics

Goals

Learn about iterated fractal systems.
Use functions and recursion.

Submission

Submit Sierpinski.java, Art.java, and, if desired, a zip file containing any supplementary image files needed by Art.java. Finally, submit a completed readme_sierpinski.txt file.

Background

The Sierpinski triangle is another example of a fractal pattern like the H-tree pattern from Section 2.3 of the textbook. 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 tasks are to write a recursive program that draws the Sierpinski triangle and a second program that draws another design of your choosing using recursion.

Here's a fractal in polymer clay or a fractal cookie.

Here is a Hall-of-Fame Art Gallery from past semesters for the second part of this assignment.

Here's a Sierpinski candy corn video. Check out her other videos while you're at it!

Part I: The Sierpinski Triangle

Write a program Sierpinski.java with a recursive function sierpinski() and a main() function that calls the recursive function once, and plots the result using standard drawing.

Review the H-Tree example from the textbook and lecture.
Drawing a triangle. Write a function singleTriangle() that uses StdDraw.filledPolygon() to draw a filled, equilateral triangle (see the booksite for help with StdDraw.) The side length and triangle location should be arguments to the function. It is up to you whether to specify the location of the triangle center, a particular vertex, or something else (we recommend using the bottom vertex). Compile. Use the figure below to work out the coordinates of the triangle's vertices:
Write a main() function that calls singleTriangle() to draw a triangle with sides of length 0.5 with the bottom vertex located at (0.5, 0). Later you will modify main to draw the full Sierpinski triangle. Compile and run. The triangle should be in the bottom center of your window.
The recursive structure. Write a function sierpinski() that takes two arguments n and size. Your function should print n and size, then recursively call itself three times with the arguments n - 1 and size / 2. The recursion should stop when n is 0. After this recursion is tested, you will add in a call to the triangle-drawing function. Compile.

Modify main() to take one integer, command-line argument N and have it call sierpinski(N, 0.5). Your program should produce the following output:

% java Sierpinski 0
[ No output. ]

% java Sierpinski 1
1 0.5

% java Sierpinski 2
2 0.5
1 0.25
1 0.25
1 0.25

% java Sierpinski 3
3 0.5
2 0.25
1 0.125
1 0.125
1 0.125
2 0.25
1 0.125
1 0.125
1 0.125
2 0.25
1 0.125
1 0.125
1 0.125

Note: You should remove these print statements before submitting. The final output of your program will be just the graphical representation.
Drawing the Sierpinski triangle. Modify sierpinski() to take two additional arguments, x and y, and draw a Sierpinski triangle of order n of size size with the bottom vertex at (x, y). Think recursively: a Sierpinski triangle of order n is just a solid triangle surround by three smaller Sierpinski triangle (half the size) of order n - 1 to the left and right and above it. You already have written the code to draw the triangle and to do the recursion from the previous steps - you just need to make the appropriate function calls. (The triangular outline in the figures below is for illustration. You do not need to draw it in your own program.)

   % java Sierpinski 1 % java Sierpinski 2 % java Sierpinski 3



   % java Sierpinski 4 % java Sierpinski 5 % java Sierpinski 6
Warning: Do not call StdDraw.save(). It will break our test scripts and you will receive a large point deduction.
Warning: Do not call StdDraw.setXscale(), StdDraw.setXscale(), or StdDraw.setCanvasSize(). They will break our test scripts and you will receive a large point deduction.

Part II: Have Fun

In this part you will create your own recursive pattern. Write a program Art.java that takes one integer command-line argument N to control the depth of the recursion and produces a recursive pattern of your own choosing.

It's up to you what to write, as long as it follows the rules below. Check out the Art Gallery from past semesters for ideas, as well as the Famous Fractals in Fractals Unleashed, and Wikipedia's list of fractals by Hausdorff dimension. Some pictures are harder to generate than others (and some require trig); consult a TA for advice if you're unsure.

Some examples from the lists above that fulfill the requirements for Art.java are shown below:


Cantor Set	Sierpinski Carpet

Dragon Curve	Moore Curve

Rules:

The pattern can be based on recursively drawing a pattern, like Sierpinski, on recursive subdivision, like the dragon curve or fractal Brownian motion, or on any combination of the two. But it must be recursive (sorry, no Mandelbrot fractals).
The recursive structure of your program must be different from Sierpinski, H-Tree, and Brownian — just changing the triangle in Sierpinski to a square, for example, is not enough. If the number of recursive calls is different, or the order in which the calls are made is different, you should be fine.
Your program must not be tail-recursive. Tail recursive functions make a single recursive call at the very beginning or end of the function.
Your drawing must stay with the unit square (the area between 0 and 1 in both x- and y-coordinates). The window shows a bit more than this, so if you draw the square in your program, you will be able to see if your drawing goes outside it.
The background of your drawing should be white, to save toner, unless you use a background image. If you use a background image, it may extend outisde the unit square. Please crop it as best you can to the correct size however, because it makes grading easier.
Warnings: All the same warnings apply to Art.java as Sierpinski.java.
You may optionally submit a zip file containing any additional images, sound or other data required for your program. Your program can rely on animation for effect if you wish, as long as it is recursive.
Be creative and have fun (but see the extra credit note below).

Extra Credit

You will receive up to two points of extra credit for espeically creative submissions. Extra credit will be rewarded for espeically cool recursions, but also for especially cool designs, even if the recursion is fairly simple. As long as your Art.java meets the minimum recursion required (not tail-recursive, and different from our examples), it will be eligible for extra credit.

Since this assignment is on a compressed schedule before the midterm, we will allow extra credit submissions up to one week late. You must still submit an Art.java with your assignment for grading so you get the practice writing recursive functions. But you can submit something basic for the grade, and something more creative for extra credit later.

After the regular deadline, we will open a separate assignment for submitting the extra credit. If you receive extra credit, it will still be entered on your original homework. If your original Art.java is worthy of extra credit, that is fine. You do not have to make a separate submission to receive extra credit.

Frequently Asked Questions and Common Problems

What preparation do I need before beginning this assignment? Read Sections 2.1-2.3 of the textbook.
Do I need to do any error checking? No. In particular, you may assume your programs will be run with exactly one argument which will be a positive integer (possible 0).
I see a blank window, even though I am drawing a triangle. Make sure all your coordinates are between 0 and 1. Otherwise, the figure you are drawing is outside the window and will not be visible.
Can I use color? Yes! You can use StdDraw.setPenColor() to set the drawing color in both Sierpinski.java and Art.java. StdDraw defines names for standard colors, like StdDraw.RED.
Can I use colors not defined in StdDraw? Yes, but it requires some syntax that we will not cover until later in the semester. For now you will need to accept the instructions below as magic, or look up the meaning on your own. You can create a color like this:
```
    java.awt.Color c = new Color(r, g, b);
```
where r, g, and b are integers between 0 and 255 (inclusive). c is a variable, just like any other variable, except that it contains a color rather than a number or a string. You can call StdDraw.setColor(c) to draw in the color you just created.
My function for Art.java 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; }
else if (N == 2) { x = 0.55; y = 0.75; n = 5; }
else if (N == 3) { x = 0.32; y = 0.71; n = 8; }
else if ...
```
Is my Art.java good enough to get full credit? See the directions for Part II. This is the most common question we get in office hours for this assignment, but you need to decide for yourself. We do not grade homework before it is submitted, and we can never promise in advance that something is correct.
Is my Art.java cool enough to get extra credit? See above.

Enrichment: 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.

`% java Sierpinski 1`	`% java Sierpinski 2`	`% java Sierpinski 3`



`% java Sierpinski 4`	`% java Sierpinski 5`	`% java Sierpinski 6`

CIS 110 Spring 2013 - Introduction to Computer Programming