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.

About Fractals

A fractal is a geometric figure that is self-similar in that any piece of the figure contains a miniature of the entire figure. 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 snowflakes.

Sierpinski Triangles

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. Think about the following:

A Sierpinski triangle is a recursively defined structure -- each of the three outer triangles formed by joining the midpoints is itself a Sierpinski triangle.
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 panel.
- The paintComponent method should draw the initial triangle, then call a recursive sierpinski method, passing it the Graphics object, the 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 sierpinski. 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 were 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 by one.
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.

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 and repaint. 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.)

Print your Sierpinski program.

Koch Snowflakes

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

      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 double.
- 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:
- In KochPanel.java, add two public methods getAngle() that returns 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 methods in 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 and decrease 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. 510, and about the box layout on p. 523.
  The applet itself should be added as a listener for your new buttons -- this is the same as for the buttons that increase/decrease the order.
- The new tools panel should be added to the appletPanel. To accomodate it change APPLET_HEIGHT to 480.
- The method actionPerformed must be modified to take action if the 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 KochPanel); 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 maximum angles.
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:

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.