Computing Concepts with C++ Essentials
Laboratory Notebook
Chapter 11 - Modules

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.

/* snowflake.cpp */

#define CCC_WIN
#include "ccc.h"

/* PURPOSE: Program to display a Koch curve
 */

int main()
{  string path = "F--F--F--"; 
   string replacement_rule = "F+F--F+F"; /* replaces each F in path */

   Point location = Point(0, 0);
   float direction = M_PI / 2;
   
   float step_length = 0.5;
   float turn_angle = M_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 new_path = "";
      for (i = 0; i < path.length(); i++)
      {  sub = path.substr(i, 1);
         if (sub == "F") /* replace F with the rule */
            new_path = new_path + replacement_rule;
         else 
            new_path = new_path + sub; 
      }
      path = new_path;
   }

   /* draw the curve */
   
   for (i = 0; i < path.length(); i++)
   {  sub = path.substr(i, 1);
      if (sub == "F") /* move turtle forward */
      {  Point new_location = location;
         new_location.move(cos(direction) * step_length, 
            sin(direction) * step_length);
         cwin << Line(location, new_location);
         location = new_location;
      }
      else if (sub == "-")
         direction += turn_angle;
      else if (sub == "+")
         direction -= turn_angle;
   }

   return EXIT_SUCCESS;
}

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 extensible.

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 header file turtle.h that defines a class Turtle with member functions forward, turn_left and turn_right. Supply a declaration of a constructor with four parameters: the initial position and direction, the length of each move and the turn angle.

Now implement the Turtle operations in a file turtle.cpp. Note that this file does not have a main function. You can copy the code for moving the turtle from the initial snowflake program.

We will test the Turtle class with the following program:

/* square.cpp */
#define CCC_WIN
#include "ccc.h"
#include "turtle.h"
int main()
{  Turtle leonardo(Point(0, 0), 0, 1, M_PI / 2);
   leonardo.forward();
   leonardo.turn_left();   
   leonardo.forward();
   leonardo.turn_left();   
   leonardo.forward();
   leonardo.turn_left();   
   leonardo.forward();
   return EXIT_SUCCESS;
}

Now build a program out of square.cpp, turtle.cpp and turtle.h.

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

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 header file koch.h that defines a class KochCurve with member functions void grow() and void draw(Turtle& t). Supply a declaration of a constructor with two parameters: the initial path and the replacement rule.

Before implementing the KochCurve class, let's see if it has enough operations to put it to use. Write a program snowflake.cpp (which will be combined with turtle.cpp and koch.cpp) 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 main function that constructs a KochCurve and a Turtle object and puts them to use.

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

Build the program out of the three source files and two header files.

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 another source file newcurv.cpp and combine it with the turtle and Koch curve source.


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 newcurve.cpp file to prompt the user for two replacement rules.

Carry out these changes and supply your new files. 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.