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