Computing Concepts with Java Essentials
Laboratory Notebook
Chapter 11 - Packages

Cay S. Horstmann
Geof Pawlicki


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


P1. The Koch snowflake

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 "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 string 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 degree 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 is a program to generate the Koch snowflake of degree 2. Run this program to verify that it indeed draws the correct shape.

import ccj.*;

public class Snowflake extends GraphicsApplet
{  /* program to display a Koch curve */
   public void run()
   {  String path = "F--F--F--"; 
      String replacementRule = "F+F--F+F"; /* replaces each F in path */

      Point location = new Point(0, 0);
      double direction = Math.PI / 2;

      double stepLength = 0.5;
      double turnAngle = Math.PI / 3;

      int degree = 2;
      int r; /* counts repetitions */

      int i; /* traverses the path */
      String sub;

      for (r = 1; r <= degree; r++)
      {  /* substitute each F in path */
         String newPath = "";
         for (i = 0; i < path.length(); i++)
         {  sub = path.substring(i, i + 1);
            if (sub.equals("F")) /* replace F with the rule */
               newPath = newPath + replacementRule;
            else 
               newPath = newPath + sub; 
         }
         path = newPath;
      }

      /* draw the curve */

      for (i = 0; i < path.length(); i++)
      {  sub = path.substring(i, i + 1);
         if (sub.equals("F")) /* move turtle forward */
         {  Point newLocation = (Point)location.clone();
            newLocation.move(Math.cos(direction) * stepLength, 
               Math.sin(direction) * stepLength);
            Line l = new Line(location, newLocation);
            l.draw();
            location = newLocation;
         }
         else if (sub.equals("-"))
            direction += turnAngle;
         else if (sub.equals("+"))
            direction -= turnAngle;
      }
   }
}

Of course, this is a very bad program. Everything has been crammed into the main function. You can't even recognize the turtle or the curve because these objects have been broken down into numbers and strings.

In this lab, you will improve this program and make it modular and reusable. And you will distribute your reusable classes into a package.

There are two important abstractions: the turtle and the Koch curve.

A turtle can turn left or right and it can move forward. When it moves, a line shows up on the graphics screen. The turn angle and the distance moved are fixed when the turtle is created. The initial position and direction of the turtle are also specifiied when the turtle is created, but they change as the turtle turns and moves.

Design a class Turtle with methods forward, turnLeft and turnRight. Supply a constructor with four parameters: the initial position and direction, the length of each move and the turn angle.

Place this class into a package com.yourname.fractal. Note that this file does not have a main function.

Into which directory did you place the Turtle.class file?

Test the Turtle class with the following program:

import ccj.*;
import com.yourname.fractal.*;
public class TurtleTest extends GraphicsApplet
{  public static void run()
   {  Turtle leonardo = new Turtle(new Point(0, 0), 0, 1, Math.PI / 2);
      leonardo.forward();
      leonardo.turnLeft();   
      leonardo.forward();
      leonardo.turnLeft();   
      leonardo.forward();
      leonardo.turnLeft();   
      leonardo.forward();
   }
}

Describe what you had to do with your compiler or development environment to build this program!

In this program, we used import com.yourname.fractal.* to include all classes from the com.yourname.fractal package. Actually, there is only one class that we needed to import, namely Turtle. Rewrite the TurtleTest.java file so that none of the import statements uses a .*.

The import statements are always a convenience to the programmer. If you are willing to prefix each class name with its package name, you can eliminate import statements. Rewrite the TurtleTest.java file so that no import statements are used at all.

Next, let us implement the Koch curve. A Koch curve has an initial path (such as "F--F--F--") and a replacement rule (such as "F+F--F+F"). Whenever you "grow" the curve, all F characters in the path are replaced with the replacement rule. You can draw the curve by having a turtle follow the path and execute the turn and move instructions.

Design a class KochCurve with methods void grow() and void draw(Turtle t). Supply a declaration of a constructor with twoString parameters: the initial path and the replacement rule.

Note that this file does not have a main function. You can take the code for rewriting the path from the initial snowflake program.

Place this class into the com.yourname.fractal package as well.

Let's see if the KochCurve class has enough operations to put it to use. Write a program Snowflake.java (which uses the classes from the com.yourname.fractal package) to draw a Koch snowflake with the following parameters:

                          angle: M_PI / 3
                    step length: 0.25
         number of replacements: 4
                 initial string: "F--F--F--"
             replacement string: "F+F--F+F"

This should be a short program, with a run method that constructs a KochCurve and a Turtle object and puts them to use.

Did it work as expected? Describe the result.


P2. Reusing the modules

There is a whole family of Koch curves, named after Helge von Koch, a Swedish mathematician who first described them in 1904. All can be described by a turtle traversing a string made up of the strings like "F", "-" and "+". A program that knows an angle to turn by, the number of generations to re-write, the initial string and its replacement rule(s) can draw the curve.

Here are some samples of different ages and rules.

                     turn angle: M_PI/2
                         degree: 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
                         degree: 3
                 initial string: F-F-F-F
             replacement string: FF-F+F-F-FF
Koch Curve No.2
                     turn angle: M_PI/2
                         degree: 4
                 initial string: F-F-F-F
             replacement string: FF-F--F-F
Koch Curve No.3

Write a program in which the user can specify these and other curves. Put the main function into a source file NewCurves.java and make use of the turtle and Koch curve classes.


P3. Extending the modules

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
                         degree: 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
                         degree: 6
                 initial string: "R"
              replacement rule1: "L" becomes "R+L+R"
              replacement rule2: "R" becomes "L-R-L"

The turtle class doesn't need to be modified to accommodate these new curves. However, you will need to design a new class LRCurve to handle these more complex curves. And you need to modify the NewCurves.java file to prompt the user for two replacement rules.

Carry out these changes and supply your new files. The LRCurve class should be in the com.yourname.fractal package; NewCurves should be in the default package. Test the new program to see that you can reproduce the dragon curve and the Sierpinski gasket.


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