CPSC 170 Lab 7: Recursion and Fractals
As usual, create a lab7 subdirectory for today's lab, open this
document in Mozilla, and start emacs.
A fractal is a geometric figure that is
self-similar in that any piece of the figure contains a miniature of
the entire figure.
are lots of fractals that have interesting mathematical properties (and
make pretty pictures); in this
lab you will draw two of them, Sierpinski triangles and Koch snowflakes.
A Sierpinski triangle is a fractal that may be constructed as follows:
- Draw a triangle.
- Draw a new triangle by connecting the midpoints of the three sides
of your original triangle. This should split your triangle into
four smaller triangles, one in the center and three around the outside.
- Repeat (2) for each of the outside triangles (not the center one). Each
of them will split into four yet smaller triangles. Repeat for each of
their outside triangles.. and for each of the new ones.. and so on,
forever. Draw a few
rounds of this on paper to see how it
works, then check out the demo to see it
on screen. Reload to get another triangle.
Your job is to write a Java program that draws a Sierpinski triangle.
When this works,
modify it so that when the user clicks, a new, random Sierpinski triangle
is drawn. (The demo does this too.)
You'll need the usual private inner class to implement the MouseListener
interface, and in the mouseClicked method you will
need to choose three random points and a random color
If you followed the guidelines above, nothing will change in your
paintComponent or sierpinski methods.
(But be sure that paintComponent calls super.paintComponent as
its first statement or
it won't erase the previous triangle.)
- A Sierpinski triangle is a recursively defined structure -- each of
the three outer triangles formed by joining the midpoints is itself a
- In practice you don't want to go on with the process "forever"
as suggested above, so we'll limit how deep it goes. Define the depth
of a Sierpinski triangle as the number of directly nested triangles at the deepest
point. So a Sierpinski triangle consisting of a single triangle has
depth 0; when a triangle is drawn inside of it, the resulting Sierpinski
triangle has depth 1; when the three outside triangles have triangles drawn inside
of them, the resulting triangle is depth 2, and so on. A depth of 10 or
11 gives a nice looking triangle in a reasonable amount of time. (The
demo uses depth 10.)
Smaller depths are interesting in that you can see more of the construction;
higher depths generally take too long for casual viewing.
- A triangle is a polygon, so you'll use the drawPolygon method.
Remember that it takes an array containing the x coordinates, an
array containing the y coordinates, and an integer indicating how many
points should be drawn (3 for a triangle).
- As usual, you'll need two
files: 1) a driver that sets up a JFrame, adds an interesting JPanel to it, and
displays it, and 2) the class that defines the JPanel.
You can model the driver after ones you've done before, with one modification:
instead of calling the
pack method of the JFrame, use its setSize method to set the
JFrame to slightly larger than the JPanel you will add to it. For example,
if your JPanel is 600x400, you might make your JFrame 650x450.
- Most of the work goes on
in the class that defines the JPanel:
Use instance variables to hold the vertices of the initial triangle and the
triangle's color. Initialize these appropriately (choose a random color)
in the constructor. For the vertices, I strongly recommend using the
Point class (p. 877 in the text), one Point for each vertex.
You may be tempted to use an array of
x coordinates and an array of y coordinates, since you'll need these to
draw the triangle anyway, but it's much cleaner later if you go with Points.
- Use constants to hold the desired depth and the height and width of
- The paintComponent method should draw the initial triangle, then
call a recursive sierpinski method, passing it the Graphics object,
points of the initial triangle, and the initial depth (0). It will
have to construct arrays of x and y coordinates from the points it was
passed to do the drawing, but it should pass the points themselves to
The initial triangle should look like the one in the demo -- one
point at the top center of the window and one point near each lower corner.
- The sierpinski method should assume that the triangle whose points
passed in has already been drawn. Its job is to
check to see if the desired depth
has been achieved; if not, it should draw the triangle formed by the midpoints
of the given points (yes, you'll need to form arrays again), then call itself
recursively on each of the three new outer triangles.
Note that it will have to figure out what points to
pass to each of these calls, and that each recursive call increases the depth
- Your triangles may look a
little different from the demo's as they draw, because the demo is an
applet and you are using a JFrame.
Print your Sierpinski program.
The Koch snowflake is a fractal generated by starting with 3
line sements forming an equilateral triangle (a Koch fractal of order
1). The algorithm for generating higher order Koch fractals involves
splitting each line segment
into three equal segments then replacing the middle segment by two
line segments that protrude outward.
The same algorithm is then recursively applied
to each of the 4 new line segments.
In the basic Koch snowflake the two protruding
line segments meet at a 60 degree angle. These line segments form an
equilateral triangle with the middle segment that is removed.
(See the discussion in Chapter 11 for more details.)
Files KochSnowflake.java and
KochPanel.java contain the program from
the text that generates Koch snowflakes (Listings 11.6 and 11.7).
Note that this is written as an applet.
Copy these files to your directory, compile them, and run the program in
the appletviewer to see how it works
(you may use the file Koch.html to run the program).
In this exercise you will generalize the pattern to allow for
triangles other than equilateral ones to be built on the middle
third segment. In the drawFractal method this involves changing the
calculation of x3 and y3, the coordinates of the protrusion point.
The following calculations are equivalent to those currently in the
x3 = (int) (x2 + (cosine * deltaX - sine * deltaY)/3);
y3 = (int) (y2 + (cosine * deltaY + sine * deltaX)/3);
where cosine is the cosine of 60 degrees (which is 1/2) and sine
is the sine of 60 degrees (which is the square root of 3 over 2).
These equations are generalizable to angles other than 60. In this
exercise you will generalize the program to work for angles other
than 60. The angle will be controlled by increase and decrease buttons
in the same way that the order is currently controlled.
Do the following:
- In KochPanel.java,
- Add instance variables angle, sine,
and cosine. Angle will be an integer and sine and cosine type
- In the constructor, set angle to 60 (this will be the default),
and set sine to Math.sin (Math.PI / 3) and cosine to Math.cos (Math.PI / 3).
- In drawFractal, replace the current calculations for x3 and y3
with those given above.
- Compile and run the program. It should behave just as before.
- To add controls to allow the angle to change, do the following:
- Compile and run the program. Play with the angles and order to
see what fractal patterns are generated.
Print KochSnowflake.java and KochPanel.java to turn in.
Hand in hardcopy of your Sierpinski classes, KochSnowflake.java and KochPanel.java.
Tar the files in your lab7 directory and email the .tgz file
to me with cpsc170 lab7 in the Subject line.