CS 261 Homework 6 - Fractal Drawing

Due Fri Mar 28 at 11:59pm

Overview

A fractal image is an image in which every small subsection is the same as the larger image it is a part of--if you keep zooming in on the image, you just keep seeing the same thing. These images are defined recursively--each piece of the image contains a copy of itself, and so on.

For example, consider the simple sideways H (It's an H, not an I!) shape labeled Step 1. If you draw similar, but smaller, H shapes at the end of each leg, you get the second shape (Step 2). Continuing that process until the line segments are too small to draw gives you the final shape (Step N).

Step 1

Step 2

Step N

Although this is just a simple example (less than a dozen lines of code), more complicated images can be just as easy. Indeed, simple recursive rules like this can produce all kinds of amazing artwork.

In this assignment, you will be writing methods to draw some simple fractal images. You will be drawing 4 different fractals:

an H-Tree
the Sierpinski Triangle
a line version of the Pythagoras Tree
the Koch Snowflake

Note that this assignment is not complex--it is intended to be a "warm-up" exercise your ability to write recursive methods (and review some other concepts, like inheritance and drawing).

This assignment should be completed individually. You are welcome to ask for help from me, or from your classmates (but remember to follow the Gilligan's Island rule)!

Objectives

To practice with recursion
To review working with abstract classes and inheritance
To practice with drawing pretty pictures

Necessary Files

You will need a copy of the Hwk6.zip file. This file contains two classes you will need to import into Eclipse. DrawableFrame is a JFrame that you can draw on (by passing an image to). FractalDrawing is an abstract class that you should use as the basis for your own drawings. This class provides functionality to initialize the frame, and provides you with a Graphics2D object that you can draw on. Do not modify either of these classes, simply use their methods! If you find that you're modifying them to make your code work, then you're doing it wrong!

The FractalDrawing class also has a couple of helpful methods you will want to use. Calling showFractal() will make your drawing so far appear in the frame, so you can use it as a kind of "refresh" method while you're drawing. Calling wait() will make your program "pause" for a moment. You can use this to slow down the drawing so that you can see what's happening. On my computer, a pause time of 0 milliseconds is instantaneous, and pause time of 5-10 milliseconds looked good. Use whatever time is needed

Note: if you include pause times, use a CONSTANT defined at the top of your class to specify how long your drawing pauses for. That way I can set the constant to be 0 to test your code without waiting. Do not make me alter your code or wait for a slow drawing.

Finally, the zip file also contains the short README.txt for this assignment, which you will need to fill out.

Assignment Details

You will need to make a separate class for each of your fractals. These classes should extend FractalDrawing. You will also need to make a Tester that can be used to start drawing all of your fractals.
Each of your classes will need to override the drawFractal() method. This abstract method is effectively the "launcher" for your fractal drawing--that's why it's part of the public interface!
None of the fractal methods require more than a dozen or so lines of code (depending on how fancy you get want to get with color, etc.). If you find your method is getting much longer than that, take a moment to convince yourself you are on the right track!
- Your helper methods should all be private; let the launcher be the only part of the public interface.
- Think about what parameters you will need: what information is required for each "step" of the drawing (or for each "run" through the recursive loop?)
- Hint 1: Write the "base case" draw function first (e.g., draw a single iteration of your recursion). Test that, then add in the recursive loop. Doing the base first will let you confirm that your drawing is correct.
- Hint 2: Remember, it is an excellent debugging strategy to print out the arguments given at the start of each call to the recurive method (e.g., make the first line of the method a printout that says "I am X method called with args A B C"). This can help you follow what is going on.
Include a full JavaDoc comment for each of your methods. I highly recommend you write this comment first, so that you know what your parameters represent and what you should be returning (if anything)

The Fractals

This section details the 4 fractals you will need to implement.

The H-Tree

The H-Tree is one of the simplest fractals to understand and program. You begin by drawing a vertical line with two (shorter) horizontal 'legs' like a sideways H (Figure H1). Then, at the ends of each 'leg', draw the same shape, rescaled (Figure H2). The process continues until the line segments are too small to draw (e.g., a single pixel or less). The result is a grid-like image (Figure H3).

Figure H1

Figure H2

Figure H3

To draw the H-Tree, you will need the horizontal coordinate of the central segment and the y coordinates of the two endpoints (though you can even get away with just having the center of the H and the length of the different segments!). You will also need a ratio to specify the lengths of the 'legs' relative to the length of the central segment. The above images were generated with a ratio of 0.5; you should experiment with different ratios to see the effects.

The Sierpinski Triangle

The Sierpinski Triangle Fractal is a class simple fractal. You begin by drawing a triangle (Figure S1). Then, by connecting the midpoints of the triangle's sides, you construct three triangles (Figure S2). Note the triangles are at the corners. The 'upside down' one in the middle is not a triangle, but is formed as a result of the other three. The process continues: in the next step, you connect the midpoints of the three smaller triangles to create three triangles in each one (Figure S3). Continuing this process, the resulting fractal image looks like Figure S4.

Figure S1

Figure S2

Figure S3

Figure S4

The only things you need to get started drawing a Sierpinski Triangle are the coordinates of the three vertices of the first triangle. Note that these vertices can be anywhere. That is, the triangle does not have to be equilateral or isosceles. Try drawing out Sierpinski Triangle that is neither!

The Pythagoras Tree

You will be drawing a version of The Pythagoras Tree (or "tree fractal"), using lines instead of cubes. This fractal is a bit more complicated than the previous two. You begin by drawing a 'trunk' for the tree. In the next step, you draw 'branches'--each of which is another Pythagoras tree with a shorter trunk! That is, the 'branches' become the 'trunks' in the next recursion (see Figure P1).

Figure P1

Figure P2

Figure P3

You will need an initial spot (the base of the trunk) to draw each recursive tree. You should also use some passed in ratio (similar to with the H-Tree) to determine how much to shrink think next trunk; 0.8 is a good number.

In order to have your tree grow out, you will need to have each branch (recursive tree) spread out at an angle. This can be measured as the angle off the the horizontal axis (angle1 in Figure P2). In addition, your branches will be splitting by a particular angle each time (angle2 in Figure P2)--so you can figure out the new angle for a branch by adding the split angle to the current angle.

Because Java math functions use them, your angles should be in radians measured counterclockwise from the x-axis. So a vertical trunk has an angle of 𝜋/2 (that is: 90 degrees).
If you use 𝜋/2 as your "splitting angle", your branches will angle away at 90 degrees, forming a T. This is not a bad way to test that your recursion is working. Smaller angles will give the traditional Y-shape.
Math Hint! If you have some angle from the horizontal axis, you can figure out the location of a point some length distance away by using the equations from polar coordinates:
```
newX = oldX + length * cos(angle)
newY = oldY - length * sin(angle) //subtracted because of inverted y!
```

The Koch Snowflake

The Koch Snowflake is the most complicated fractal (but is still not too bad)--mostly because it doesn't use tail recursion (where you recurse at the end of the method). To draw the Kock Snowflake, think about drawing line segments, where a segment is the side of a triangle. Each time you draw a segment, you actually break that segment up into three smaller pieces (that are themselves segments): you draw a segment over the "first" 1/3 of the edge and a segment over the "third" 1/3 of the edge. But instead of drawing the middle segment, you draw a pair of shorter segments that would form a kind of new triangle. See the below figures (from Wikipedia) for an example.

Drawing each segment is a recursive call--instead of drawing that segment, you actually break it up into the three pieces, and so forth. Keep going until you hit a maximum number of steps (an iteration count, similar to with the Pythagoras tree), in which case you can stop dividing the segment and just draw the straight line alreadt!

Figure P1

Figure P2

Figure P3

Figure P4

Note that the greens lines are for illustration purposes; you do not need to draw them!

The only things you'll need to draw the Koch snowflake are the starting x and y coordinates of the side of each triangle. Note that you'll need to keep your points in "order," so that you build your fractal out instead of in. You will also want to keep track of how many iterations you have gone through, so that you can stop (4 or 5 ended up being a good number for me--though again, you can stop when your segments are too short to subdivide).

Find the points that are 1/3 and 2/3 of the way through the segment easily; simply take the distance between the start and end coordinates (x2 - x1) and divide it by 3.
Math Hint! Finding the new, outside point to draw the growing triangle is a lot trickier; but some simple trigonometry can show that:
```
newX = x1 + 0.5 * (x2 - x1) + sqrt(3)*(y2 - y1)/6.0 
newY = y1 + 0.5 * (y2 - y1) - sqrt(3)*(x2 - x1)/6.0
```
Again, make sure that you keep your points in order so you build out instead of in!

Timeline

This assignment is not intended to be difficult, but there are a number of pieces to work on. Try to complete one fractal each day, and you can easily get it done in time!

Extensions

You can have lots of fun with using different colors for different parts of the recursive drawings, to make really neat images!

You are welcome to implement more than one of these fractals if you have time. There are lots of other amazing fractals out there, including the infamous Mandelbrot Set

You might also have fun creating a new FractalFrame that has different buttons used to draw the different fractals. Note that you would need to adjust the FractalDrawing class to not create its own frame.

Submitting

BEFORE YOU SUBMIT: make sure your code is fully documented and functional! If your code doesn't run, I can't give you credit! Your name should be in the class comment at the top of each class.

Submit your programs to the Hwk6 submission folder on hedwig. Make sure you upload your work to the correct folder!. You should upload your entire src folder with all your classes. Be sure to complete the provided README.txt file with details about your program.

The homework is due at midnight on Friday, Mar 28.

Grading

This assignment will be graded on approximately the following criteria:

You have implemented your fractal classes by extending the abstract FractalDrawer [5%]
You have implemeneted the H-Tree fractal [15%]
You have implemented the Sierpinski Triangle [15%]
You have implemented the Pythagoras Tree [25%]
You have implemented the Koch Snowflake [25%]
Program demonstrates good recursive and object-oriented style [5%]
Program is fully documented with complete Javadoc comments [5%]
You have completed the included README.txt file [5%]