CPSC 170 Lab 8: Recursion and Fractals
As usual, create a lab8 subdirectory for today's lab, open this
document in FireFox, 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.
Naturally, fractals fit nicely with the concept of
recursion. There 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
A Sierpinski triangle (aka a Sierpinkski Gasket) is a fractal that may
be constructed as follows:
- Draw a triangle.
- Draw a new triangle by connecting the midpoints of the three
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
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.
Think about the following:
- A Sierpinski triangle is a recursively defined structure -- each
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
point. So a Sierpinski triangle consisting of a single triangle has
depth 0; when a triangle is drawn inside of it, the resulting
triangle has depth 1; when the three outside triangles have triangles
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
higher depths generally take too long for casual viewing.
- A triangle is a polygon, so you'll use the drawPolygon method of a
graphics object (p 409-410). Note: this method 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 (Sierpinski.java) that sets up a JFrame, adds
an interesting JPanel to it, and
displays it, and 2) the class that defines the JPanel
(SierpinskiPanel.java). You can model the driver after ones you've done
before: for example look at the Circle.java and CirclePanel.java
When this works,
modify it so that when the user clicks, a new, random Sierpinski
is drawn. (The demo does this too.)
You'll need the usual private inner class to implement the
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.
- Most of the work goes on
in the class that defines the JPanel:
- Use instance variables to hold the vertices of the initial
triangle's color. Initialize these appropriately (choose a random
in the constructor. For the vertices, I strongly recommend using the
Point class (see JavaDoc), one Point for each vertex.
- Use constants to hold the desired depth of the fractal and
the height and width of
- The paintComponent method should clear the screen (by
calling super.paintComponent), set the drawing color and then
call a method called drawGasket passing
it the Graphics object, the
points of the initial triangle, and the initial depth (0).
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
- The sierpinski method should draw the triangle whose
points were passed in, and then check to see if the desired depth has
been achieved; if not, it should draw the triangle formed by the
of the given points, 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
- 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
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);
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
y3 = (int) (y2 + (cosine * deltaY + sine * deltaX)/3);
- 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
and set sine to Math.sin (Math.PI / 3) and cosine to Math.cos (Math.PI
- In drawFractal, replace the current calculations for x3 and
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:
- In KochPanel.java, add two public methods getAngle()
the angle (type int), and setAngle (int newAngle) that sets
the angle to be the value of newAngle and sets sine and
cosine of that angle. Remember that the sin and cos
the Math class must have arguments that are in radians not degrees
so you need to multiply the angle (which is in degrees) by Math.PI
divided by 180 (pi/180 is the degree to radian conversion factor).
- In KochSnowflake.java, add a new panel for the buttons
to increase and decrease the angle. This panel will contain two buttons
and a label giving the current angle, and will be very
similar to the tools panel that holds the buttons that increase
the order. Note that the tools panel uses a horizontal box
layout; you should do the same for your panel. You can read more about
layout managers on p. 341, and about the box
layout on p. 351.
- The new tools panel should be added to the appletPanel. To
accomodate it change APPLET_HEIGHT to 480.
- This applet deals with listeners in a slightly different way.
The applet itself implements ActionListener. This means that the
"actionPerformed" method required for the implementation is just part of the
KochSnowFlake class. When it comes time to add the actionListener to the
buttons - what is the instance that needs to be passed? It needs to pass
a reference to itself... this Make your buttons respond to events
the same way.
- The method actionPerformed must be modified to take action if
event source was one of the new buttons. If the source was the
button to increase the angle, increase the angle by 10 degrees
(you can get the current angle using the method you added to
if the source was the button to decrease the angle, decrease it by 10
degrees. The new angle should be between 10 and 170 (inclusive) --
you should add constants (similar to MIN and MAX) for the minimum and
- 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 Stapled hardcopies
of your Sierpinski classes, KochSnowflake.java and
Tar the files in your lab8 directory and email the .tgz file
to me with cpsc170 lab8 in the Subject line.
If you Finish early:
Start looking at Assignment 2