Computing Concepts with Java Essentials
Laboratory Notebook
Chapter 14 - Object-Oriented Design


Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.


Lab Objectives

To gain experience with


R0. The Koch snowflake and other fractals

Suppose you want to instruct someone to draw a square. Here is how you could do it. Tell the person:

Or, in symbolic notation, if "forward steps" are denoted as "F" and 90 degree clockwise turns as"-", the instructions could be simply written as:

F-F-F-F

Try drawing this by hand or with a drawing utility to see that it works.

Many curves, or line drawings, can be described this way. Starting from some point, the next position is computed as an offset from the current position. This is called a Turtle algorithm. One way of thinking of it is that a turtle drags it's shell (and tail) along a beach one step at a time, leaving a trace of where it's been.

Now let's see how recursion fits into the picture. Start with an equilateral triangle given by the pattern "F--F--F--", (where now - denotes a 60 degree turn). That is, the turtle carries out the command

   Go Forward
   Turn Left
   Turn Left
   Go Forward
   Turn Left
   Turn Left
   Go Forward
   Turn Left
   Turn Left

It looks something like this:

0th degree Koch snowflake

Consider replacing each of the F's in the existing pattern with another sequence of steps and turns. Before drawing with a turtle, you replace every "F" with the string "F+F--F+F". (Here, "+" denotes a counterclockwise turn.) This yields: F+F--F+F -- F+F--F+F -- F+F--F+F -- . When drawn by a turtle, it looks like this:

1st degree Koch Snowflake

This is a Koch Snowflake of generation 1, meaning that each of the original edges have been rewritten once. Again, replacing each F with the string "F+F--F+F" yields a figure that looks like this:

2nd degree Koch Snowflake

Such a curve can be made increasingly complex by successive re-writings. The limit of these repetitions has an infinite parameter but a finite area. It is a geometric object called a fractal. Fractals have been studied both for their visual beauty and their interesting mathematical properties.

Here are some samples of different generations and rules.

                     turn angle: M_PI/2
                     generation: 2
                 initial string: F-F-F-F
             replacement string: F-F+F+FF-F-F+F
Koch Curve No.1
                     turn angle: M_PI/2
                     generation: 3
                 initial string: F-F-F-F
             replacement string: FF-F+F-F-FF
Koch Curve No.2
                     turn angle: M_PI/2
                     generation: 4
                 initial string: F-F-F-F
             replacement string: FF-F--F-F
Koch Curve No.3

Koch curves are related to other recursively defined drawings in 2 dimensions. These related curves rely upon successive re-writing of polygonal edges. For example, Dragon curves and the Sierpinski gasket are made up of pairs of edges at an angle to each other, facing either to the Left or to the Right, like this.

Dragon, Starting angle Dragon, Second angle

Here are the resulting curves, and settings to draw them.

Dragon Curve

Dragon Curve
                     turn angle: M_PI/2
                     generation: 4
                 initial string: "L"
              replacement rule1: "L" becomes "L+R+"
              replacement rule2: "R" becomes "-L-R"

Sierpinski Gasket

Sierpinski Gasket
                     turn angle: M_PI/3
                     generation: 6
                 initial string: "R"
              replacement rule1: "L" becomes "R+L+R"
              replacement rule2: "R" becomes "L-R-L"

The problem of this lab is to write programs that can draw these curves.

R1. Analysis

The preceding section describes the algorithm behind drawing fractal curves, which is very important. To complete the analysis of the program to be written, we need to specify how users provide input.

We will assume that it is satisfactory if the user can provide the input once, then see the graph. If the user desires to see another curve, it is acceptable if the user needs to exit the program and start over.

There are still a number of ways for providing the input, for example, in a text file, through a series of option dialogs, or through a group of text fields.

A complicating factor is that there may be multiple replacement rules.

Describe in precise detail (with a sketch of the user interface elements if you design a GUI) how a user will interact with the program.

R2. Discovering classes

Looking through the problem description, list all relevant concepts that could make a useful class. Turtle is one example; FractalCurve is another.

List the candidates for classes here:

Next, we will turn to CRC cards. In the CRC cards, pay particular attention which class is responsible for a certain action. For example, is the turtle responsible for drawing a pattern, or is it the responsibility of the pattern to guide the turtle along? Is it the responsibility of the replacement rule to rewrite a pattern, or is it the responsibility of the pattern to apply the replacement rule? There is no one right answer--what is important is to come up with a logically consistent design.

Give CRC cards for the following classes:

What relationships did you find in your classes? For example,

What attributes did you find? For example, the generation is an attribute of the FractalCurve.

You should draw an UML diagram that shows the relationships between the classes, and the key attributes and methods that you discovered so far.

R3. Method Documentation

Use Javadoc comments to document all methods of the Turtle class that you have discovered. Document the entire class as well.

Provide Javadoc comments for the following methods (or their equivalents if you divided up responsibilities differently):

P1. Classes and Unit Tests

Implement the Turtle class and test it with the following program. You may need to modify the program to match your own constructor parameters and method names.

public class TurtleTest extends JApplet
{  public static void paint(Graphics g)
   {  Graphics2D g2 = (Graphics2D)g;
      Turtle leonardo = new Turtle(200, 200 /* location */, Math.PI / 2 /* turn angle */);
      leonardo.forward(g2);
      leonardo.turnLeft();
      leonardo.forward(g2);
      leonardo.turnLeft();
      leonardo.forward(g2);
      leonardo.turnLeft();
      leonardo.forward(g2);
   }
}

Now test your Pattern and ReplacementRule classes. These classes should not require any graphics to test them. Here is a possible test program--again, you may need to rewrite it to match your design.

public static void main(String[] args)
{  ConsoleReader console = new ConsoleReader(System.in);
   System.out.println("Enter a pattern string, e.g. F--F:");
   String input1 = console.readLine();
   Pattern p = new Pattern(input1);
   System.out.println("Enter the character to be replaced, e.g F:");
   String input2 = console.readLine();
   System.out.println("Enter the replacement string, e.g. +F+F+:");
   String input3 = console.readLine();
   ReplacementRule r = new ReplacementRule(input2, input3);
   Pattern q = r.rewrite(p);
   System.out.println(q.toString());
}


P2. Putting everything together

Finally, the time has come to put the entire program together.

Give brief instructions how to test your program, e.g. a sample set of inputs or, if you process input from a file, a sample input file.


Don't forget to send your answers when you're finished.