Homework 5: Recursive Graphics

GOALS OF THE ASSIGNMENT

The purpose of this assignment is to gain practice with recursion via creating interesting graphical patterns using the recursive concept.

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 and transformations.

To get an idea of what your final recursive graphics visualization is supposed to look like

Sierpinski triangle of order 9
Here's a fractal in polymer clay or a fractal cookie.

Since Halloween is only a few weeks away, here's a Sierpinski candy corn video. Check out her other videos while you're at it!

And while we are still a few months away from this,

Here's a Sierpinski valentine!, courtesy that great web-comic, xkcd!

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.

Write a function triangle() 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:
Sierpinski triangle geometry
Write a main() function that calls triangle() 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.
  • 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 comment out these print statements before submitting. The final output of your program will be just the graphical representation.
    • 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
       Sierpinski triangle of order 1 Sierpinski triangle of order 2 Sierpinski triangle of order 3
     
     
       % java Sierpinski 4 % java Sierpinski 5 % java Sierpinski 6
       Sierpinski triangle of order 4 Sierpinski triangle of order 5 Sierpinski triangle of order 6
    Once you have your Sierpinski triangle working, add a StdDraw.show(n) into your sierpinski function. Experiment with different values of n until you get an animation where you can clearly see how the triangle is being built up. This step is simply to gain a better understanding of the order in which recursive calls get executed.
    • 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.
         Please submit you Sierpinksi.java file. Also, submit a completed readme_sierpinski.txt file. For extra credit 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.


    You are not allowed to use any of the examples in the book or the booksite. One good resource for ideas is wikipedia's list of fractals. If you find a recursive image that you base your art off of, please cite it in your readme.