A. Goals
The purpose of the Recursive Graphics assignment is to gain practice with recursion.
- Learn about iterated fractal systems
- Use recursion
B. Background
Read sections 2.1–2.3 of Sedgewick & Wayne. Review the H-Tree example from the textbook and lecture.
The Sierpinski carpet is an 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 1916. Though the Sierpinski carpet looks complex, it can be generated with a short recursive program. Your tasks are to write a recursive program that draws the Sierpinski carpet and a second program that draws another design of your choosing using recursion.
This is a Sierpinski carpet:
Here's a fractal in polymer clay and a Sierpinski valentine. Have a fractal cookie, a Sierpinski hamentashen, or a Sierpinski candy corn video (check out her other videos while you're at it!):
In this assignment, you will write a program Sierpinski.java that recursively draws a Sierpinski carpet
using PennDraw. These instructions will walk you through the process step by step.You are not allowed to use PennDraw.setXScale(), setYScale(), or any scale changing in this assignment. Doing so will only make the assignment harder.
A. The main() function
Write a main() function that
calls the PennDraw.filledSquare() function to draw a square with sides of
length 1.0 / 3.0 with the center vertex located at (0.5, 0.5)
Later
you will modify main() to draw the full Sierpinski
carpet.
When you compile and run your program, you should see a square in the center of your window.
B. Setting up the recursive structure of sierpinski()
Write a static function sierpinski() that takes two parameters,
numLevels and halfSideLength. Your function should
print both parameters, before recursively calling itself
eight times with the arguments numLevels - 1 and halfSideLength / 3. The recursion should stop when numLevels is less than 1. Later, you will replace the print statements with
a call to PennDraw.filledSquare().
Modify main() to interpret its first command-line
argument as numLevels. Have it
call sierpinski(numLevels, 1.0 / 6.0). You may assume that your program
will be run with exactly one command-line argument that is a positive integer.
Make sure that your code compiles.
C. Checkpoint
Running your program with the following command-line arguments should produce the following output:
> java Sierpinski 0
(no output)
> java Sierpinski 1 1 0.16666666666666666
> java Sierpinski 2 2 0.16666666666666666 1 0.05555555555555555 1 0.05555555555555555 1 0.05555555555555555 1 0.05555555555555555 1 0.05555555555555555 1 0.05555555555555555 1 0.05555555555555555 1 0.05555555555555555
> java Sierpinski 3 3 0.16666666666666666 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 2 0.05555555555555555 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517 1 0.018518518518518517
D. Drawing the Sierpinski carpet in sierpinski()
Comment out the print statements from sierpinski().
Modify sierpinski() to take two additional
arguments, x and y, and draw a Sierpinski carpet
of order numLevels of size 2 * halfSideLength centered at
(x, y). Remember that if you have more than 80 characters
on a single line, you need to break the line up. This can be done by putting a linebreak between
arguments.
Think recursively. A Sierpinski
carpet of order numLevels comprises just a solid square and
eight smaller Sierpinski carpets, each one third the size of the original, each of
order numLevels - 1, to the four cardinal directions plus the four diagonals
relative to the center square. The distance between the center of the original square and the
center of the smaller squares should be 2 * halfSideLength of the original.
You have already written the function to draw the square and the
recursion code from the previous steps – now, you only need to make the correct
function calls.
Warning Do not
call, PennDraw.setCanvasSize(),
or PennDraw.save(). These functions will break
our test scripts, and you will receive a large point
deduction.
E. Checkpoint
Running your program with the command-line arguments below should produce the following output. (The figures below have a light outline around the carpet for illustration. You do not need to draw this outline in your own program.)
| 
| 
|
| > java Sierpinski 1 | > java Sierpinski 2 | > java Sierpinski 3 |
|
| 
| 
|
| > java Sierpinski 4 | > java Sierpinski 5 | > java Sierpinski 6 |
F. Animating
Once you have your Sierpinski carpet working, add calls
to PennDraw.enableAnimation()
and PennDraw.advance() into
your sierpinski() function. (You are not
required to animate your Sierpinski carpet, and it is not
worth any points, but it is fun and will help you visualize
the recursion. If you do add animation, leave it in your
code: it will not affect our grading scripts.)
Experiment with different arrangements of the recursive calls to sierpinski().
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.
- 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 – they're very cool, but they aren't recursive).
- The recursive structures of your program must be different from Sierpinski, H-Tree, Cantor set, and L-Systems; just changing the carpet in Sierpinski to a triangle, 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 take one command-line argument. If your recursive function
takes multiple parameters, you can choose some of the values that have the best effect, and
do something like the following:
if (commandLineArgument == 1) { x = 0.55; y = 0.75; n = 3; } else if (commandLineArgument == 2) { x = 0.55; y = 0.75; n = 5; } else if (commandLineArgument == 3) { x = 0.32; y = 0.71; n = 8; } else if ...
Your recursive function should work reasonably well up to at least a command line value of 6 or 7, but it must work at least somewhat (even if extremely slowly) with any number n. - Your program must not be tail-recursive. Tail recursive functions make only a single recursive call at the very beginning or end of the function. These are cases that are very easy to rewrite as a loop with no recursion. (There are plenty of cases where a tail-recursive function may be more elegant than a loop, but we want you to do something that really requires recursion.)"
- Your drawing must stay within the unit square (the area
between 0 and 1 in both x-
and y-coordinates). You drawing must not go
past the border of the canvas that PennDraw adds to the canvas. If
you use the
PennDraw.setXscale()andPennDraw.setYscale()functions, your drawing must stay withing the bounds you pass to those functions (i.e. the same are the unit square occupies by default). - Your
Art.javacannot have interactive features that depend upon keyboard or mouse input: you may not callPennDraw.hasNextKeyTyped(),PennDraw.nextKeyTyped(),PennDraw.mouseX(),PennDraw.mouseY(), orPennDraw.mousePressed(). - The same warning as
for
Sierpinski.javaapplies: do not call,PennDraw.setCanvasSize(), orPennDraw.save(). These functions will break our test scripts, and you will receive a large point deduction. - 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.
Extra credit You will receive up to two points of
extra credit for especially creative submissions, as judged
by the graders. Extra credit will be rewarded not only for
especially cool recursion, but also for especially cool
designs, even if the recursion is fairly simple. As long as
your Art.java meets the minimum requirements
(takes one command-line argument, is not tail-recursive,
stays within the unit square, and is fundamentally different
from our examples), it will be eligible for extra
credit.
Be creative and have fun!
Warning Teaching staff are unable to answer questions such as "Is my Art.java
good enough to get full credit?" or "Is my Art.java cool enough to get extra credit?"
You will need to decide for yourself. We do not grade homework before it is submitted,
and we will not promise in advance that something is correct.
Examples
Check out 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.
|
|
| Dragon Curve | Moore Curve |
Submit a
completed readme_sierpinski.txt,
Sierpinski.java, Art.java,
and if desired, an extra.zip file containing any
supplementary files needed by Art.java.