CPSC 170 Lab 8: Recursion and 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. 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 snowflakes.

Sierpinski Triangles

A Sierpinski triangle (aka a Sierpinski Gasket) is a fractal that may be constructed as follows:

1. Draw a triangle.
2. 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.
3. Repeat step 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.

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. 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 can use the drawPolygon method of the Graphics class. 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).

The midpoint of a line segment can be calculated using interpolation. In order to find a point that is some fraction between the two points (x₁, y₁) and (x₂, y₂) the following equations can be used:

x_i = i * x₂ + (1 - i) * x₁ y_i = i * y₂ + (1 - i) * y₁

where i is a value between 0 and 1 that is the fraction of the distance between the two points that the point (x_i, y_i) is located. So, in order to find a point that is 1/2 between two points a value of i = 0.5 could be used. Include the following in your program:

• Use constants to hold the desired depth of the fractal and the height and width of the panel.
• The paintComponent method should clear the screen (by calling super.paintComponent), set the drawing color and then call a method called sierpinskipassing it the Graphics object, the points of the initial triangle, and the initial depth (0).
• The color and the corners of the triangle can be selected by you or chosen randomly.
• 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 midpoints 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 depth by one.

Koch Snowflakes

The Koch snowflake is a fractal generated by starting with 3 line segments forming a 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. The diagram below illustrates the transformation of a segment.

In order to calculate the four line segments that represent the transformation of the segment defined by the points (x₁, y₁) and (x₅, y₅) the points that divide the segment into thirds, (x₂, y₂) and (x₄, y₄), must be calculated. These can be calculated using interpolation and the equations from the previous section of this lab.

The point that is the apex of the protrusion, (x₃, y₃), can be calculated with the following equations:

x3 = x1 + Δx / 2 - Δy * p
y3 = y1 + Δy / 2 + Δx * p

where

Δx = x5 - x1
Δy = y5 - y1

and p is a value between -1 and 1 that is the percent length of the original segment that the protrusion will be. That is, if p is 0.5 then the protrusion would be half the size of the segment from (x₁, y₁) to (x₅, y₅). If p is -0.5 then it would also be half the size of the segment, but protrude off of the other side of the segment. A value of one third of a segment length produces a nice looking fractal.

Create a program that when run displays a Koch fractal. To do this you should create a recursive method that takes as a parameter the endpoints of a line segment, the order of the segment, and a Graphics object. The method should calculate the four segments that represent the next highest order and recursively call the same method to generate the next order of each of the segments. The recursion should terminate, and the method should draw, when the order reaches the order of the fractal being drawn.

You should begin by testing your recursive method on very simple fractals. For instance, on one segment of order 1. It should look like the diagram above. Once you are sure that your method is working test it on higher orders, and on multiple line segments. Add a slider that controls the order of the fractal as well as a slider that controls the size of the protrusion.

Lastly, add a slider to your program that adjusts the size of the protrusion, the size is determined by the value p in the equations for x₃ and y₃. Use the controls to create fractal that you like. Use the Applications>Accessories>Take Screenshot application to create an image of the fractal and put it in your lab8 directory.

Hand In: Tar your lab directory and e-mail it to your instructor with cpsc170 lab8 in the subject.