Laboratory Notebook

Chapter 11 - Packages

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 gain experience with

- organizing code into packages
- using turtle graphics to draw recursively defined curves

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

- draw a line
- rotate drawing direction by a 90 degree turn
- draw a second line of the same length
- rotate again by 90 degrees
- draw another line of the same length
- rotate again by 90 degrees
- draw another line of the same length

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:

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:

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:

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

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 two`String` 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.

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

turn angle: M_PI/2 degree: 3 initial string: F-F-F-F replacement string: FF-F+F-F-FF

turn angle: M_PI/2 degree: 4 initial string: F-F-F-F replacement string: FF-F--F-F

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.

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.

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

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

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.