Case Study: Drawing Shapes with Turtle Graphics

Graphics programming is a very satisfying activity, because you get immediate visual feedback. Most introductory C++ books don't do graphics for the simple reason that there are no standard graphics calls, unlike with Java. However, the principles are usually the same. Doing some graphics is (a) enjoyable and (b) better than doing no graphics at all.

This case study shows how structures can be used to store information about shapes, and how then these shape objects can be drawn using turtle graphics in more detail. At the end, there is some more advanced but optional material.

The Specification

You need to write a program that takes a file describing shapes and draws the shapes on a window. Initially, these shapes are squares, rectangles, circles, ellipses, and lines; color can be specified for both lines (foreground) and shapes (background). Here is an example of the proposed format:

RECT    10 10 30 40
SQUARE  40 20 10
CIRCLE  80 20 10
FCOLOR  255 0 0
BCOLOR  0 0 255
ELLIPSE 80 40 120 60
INC STARS 200 200

General shapes such as rectangles and ellipses are specified by their bounding rectangle, whereas squares and circles are specified by an origin followed by a size. Colors are specified by three numbers—red, blue, and green—each of which varies from 0 to 255. This gives you 3 bytes, or 24 bits, per color. There is also an include command that brings in other plot files; this can be (optionally) drawn in a specified location.

The Representation

Your first design decision is to read the file into a data structure, which is then used for doing the actual plotting. There are a number of good reasons for this. First, it is efficient because the file will be read only once, and the shapes will have to be drawn whenever the window repaints itself. Second, you need to find the minimum and maximum bounds of the shapes, which would not only require another reading of the file but would be awkward.

Third, it allows you to split the problem neatly into two parts—reading in and plotting out—and this will simplify development.

A struct would be the best way to represent each shape. You could use unstructured arrays of numbers, but as many a FORTRAN programmer has discovered, this ends up confusing both the guilty and the innocent. Shapes naturally can be specified by their bounding rectangles (that is, the smallest rectangle than encloses the shape); as far as the representation goes, a circle is merely an ellipse with a square bounding rectangle. If it is later important to know the difference between circles and ellipses, it is easy to compare the dimensions of the rectangle.

The first struct you need to create is Rect, which consists of left, bottom, top, and right (with the typedef real defined as the chosen floating-point number):

typedef unsigned char byte;
typedef double real;
typedef unsigned long Color;

struct Rect {
  real top,left;
  real bottom,right;
};

enum Type { ELLIPSE,RECTANGLE,LINE};

struct Shape {
   Type type;
   Rect rect;
   Color fcolor,bcolor;
};

typedef std::list<Shape> ShapeList;

The struct Shape then consists of a Type, a Rect, and two colors. The shape type can be expressed as a named enumeration because any value of type Type can have only one of three values: ELLIPSE, RECTANGLE, or LINE. (The integer values are not important.) Color is just a typedef name for an unsigned long integer. (Using a typedef here aids documentation and leaves the design open to later modification.)

For the collection of Shape objects, the best solution is probably a list, given that you don't need random access (that is, you will not need to access any shape quickly by position alone.) Lists are easy to append to and economical with memory, and they can be rearranged easily. (That might be crucial later because drawing order is often important.) In any case, you can use a typedef to define ShapeList as being the same as std::list<Shape>. ShapeList is easier to type, and it gives you more freedom to change your mind later. You rarely know all the relevant factors early on in a project, and it's wise to keep options open.

There is also a supporting cast of functions and operators to read (and write) rectangles, squares, and other shapes. These are pretty straightforward and exist to make your job easier later. Not only is it easier to type in >> pt than in >> pt.x >> pt.y, but it means that you can redefine the format for reading in points and know that the rest of the code will be fine. A little more effort up front saves you both time and lines of code later.

Please look at these functions in chap6input.cpp. As in the reverse-Polish program discussed in Chapter 4, you define a fail() function that lets you bail out if you hit a problem:

void fail(string msg)
{
 throw msg;
}

Point point(double x=0.0, double y=0.0)
{
 Point pt;
 pt.x = x;  pt.y = y;
 return pt;
}

Rect& operator+= (Rect& rt, Point p)
{
  rt.top += p.y;
  rt.right += p.x;
  rt.bottom += p.y;
  rt.left += p.x;
  return rt;
}

void read_color(istream& in, Color& cl)
{
 int r,g,b;
 in >> r >> g >> b;
 cl = TG::rgb(r,g,b);
}

void read_square(istream& in, Rect& rt)
{
    double x,y,rr;
    in >> x >> y >> rr;
    rt.bottom  = y-rr;
    rt.left = x-rr;
    rt.right = x+rr;
    rt.top = y+rr;
}

ostream& operator<<(ostream& out, const Rect& rt)
{
 out << rt.left << ' ' << rt.bottom << ' '
     << rt.right << ' ' << rt.top << endl;
 return out;
}

The main input routine is called read_shapes(), and it is responsible for reading each line from the file, setting the current foreground and background colors, and including specified plot files.

bool contains_numbers(const string& s)
{
 string::iterator p1 = s.begin(), p2 = s.end();
 while (p1 != p2) {
   if (isdigit(*p1)) return true;
   ++p1;
 }
 return false;
}

// forward declaration of read_any_shape
void read_any_shape(istream& in, string obj, Shape& shp);

bool read_shapes(string file, ShapeList& sl, real xp, real yp)
{
  Shape shp;
  Color current_bcolor = default_bcolor,
        current_fcolor = default_fcolor;
  string obj;
  Color ival;
 // if there's no file extension, then assume it's .plt   [note 1]
  if (file.find(".")==string::npos) file += ".plt";
  ifstream in;
  if (!in.open(file.c_str())) fail("cannot open " + file);
  while (in >> obj) {
   switch(obj[0]) {
   case 'F': // foreground color
    read_color(in,ival); current_fcolor = ival;
    break;
   case 'B': // background color
    read_color(in,ival); current_bcolor = ival;
    break;
   case 'I': {  // insert file!  [note 2]
     string file,rest;
     real xm=xp,ym=yp;
     in >> file;
     // MAY be followed by some (x,y) offset
     getline(in,rest);
     if (contains_numbers(rest)) {
       istringstream ins(rest);
       ins >> xm >> ym;
     }
     // a recursive call!
     read_shapes(file,sl,xm,ym);
  }  break;
  default: {  // read a shape...[note 3]
    Shape shp;
    read_any_shape(in,obj,shp);
  // shape properties effected by current color and offset
    shp.fcolor = current_fcolor;
    shp.bcolor = current_bcolor;
    shp.rect += point(xp,yp);
    sl.push_back(shp);
  }
 }  // switch...
}  // while...
   return true;
}

The code for the 'I' command (see code marked note 2) calls read_shapes() again. This is a classic application of recursion: Plot files can include other plot files, which can themselves include plot files, like Russian dolls or Chinese boxes. The only complication is that you have to check the line after the filename for the optional (x,y) offset. The idea is that sometimes the user wishes to bring in a shape file starting at a specific (x,y). The problem is that just saying in >> file >> xm >> ym will always try to skip to the next line if there are no numbers on the line. So the rest of the input line is read into a string, and contains_numbers() is used to check whether it does indeed contain an (x,y) offset. If so, then istringstream is used to read that offset in.

If a command is not recognized by read_shapes(), then it falls through to the default case of the switch statement (see code marked note 3). It assumes that the command is a shape and asks read_a_shape() to do the specific reading. The resulting Shape object is modified by the current color and also by any specified offset. The object is then put into the list of Shape objects.

The function read_a_shape() reads each shape from the file. Because it will be defined later on in the file, it is declared (or prototyped) before read_shapes(). It is like a promise that the bill will be paid within 30 days. You can use a simple switch statement here, only looking at the first character of each shape. It would not be difficult to use the whole string, but it might be tedious to have to type the full name of each shape. You can regard squares as degenerate rectangles, and the code of read_a_shape() is straightforward because the detailed work has been done by the input routines such as read_square(). If the command is still not recognized, then fail() is called and an exception is thrown.

Now I could have put the shape-reading code into read_shapes(), but then that function would be a large ugly switch statement, which will only get worse when more commands are added. Plus, putting all the shape commands into their own function makes it easier to see them at a glance.

void read_any_shape(istream& in, string obj, Shape& shp)
{
         switch(obj[0]) {
         case 'C': // circle
           shp.type = ELLIPSE;
           read_square(in,shp.rect);
           break;
         case 'E': // ellipse
           shp.type = ELLIPSE;
           in >> shp.rect;
           break;
         case 'S': // square
           shp.type = RECTANGLE;
           read_square(in,shp.rect);
           break;
         case 'R': // rectangle
           shp.type = RECTANGLE;
           in >> shp.rect;
           break;
         case 'L': // line
           shp.type = LINE;
           in >> shp.rect;
           break;
         default:
           fail("Not recognized " + obj);
        }
}

The task after reading the shapes is to calculate the bounding rectangle of each of the shapes. You use the standard algorithm for_each() to call a function that compares the bounding rectangles (note the initialization of the bounding rectangle because it's easy to get it the wrong way around). Notice that a problem with using for_each() here is that you need a global variable to store the overall bounding rectangle because the function is called only with each individual bounding rectangle. You call this gBnd to make it obvious that this is a global, and you put it inside a nameless namespace to make gBnd (together with update_bounds() and reset_bounds()) private to this module. Here is the code that calculates the bounding rectangle for all the shapes:

const double MAX = 1.0e30;
namespace {
  Rect gBnd;

 void update_bounds(const Shape& sh)
 {
  Rect rt = sh.rect;
  gBnd.top    = max((double)gBnd.top,rt.top);
  gBnd.right  = max((double)gBnd.right,rt.right);
  gBnd.bottom = min((double)gBnd.bottom,rt.bottom);
  gBnd.left   = min((double)gBnd.left,rt.left);
 }

void reset_bounds()
{
  gBnd.top = -MAX;
  gBnd.left = MAX;
  gBnd.bottom = MAX;
  gBnd.right = -MAX;
}

}  // namespace

void max_rect(const ShapeList& sl, Rect& bounds)
{
  reset_bounds();
  for_each (sl.begin(),sl.end(),update_bounds);
  bounds = gBnd;
}

I have included a write_shapes() function in chap6input.cpp, which is not necessary for the purpose of drawing shapes. But experience shows that a little extra effort in writing debugging code is always rewarded. Debugging code doesn't have to be polished; it just needs to give a recognizable text form of the program's internal data structures. The write_shapes() function, in particular, doesn't write the same format for colors. Instead, it forces the system to output colors as hexadecimal. It is then easy to see the three significant bytes (0xFF is 255, so red is 0xFF0000, blue is 0x00FF00, and green is 0x0000FF). Here is write_shapes(), which certainly helped me in constructing this program:

void write_shapes(ostream& os, const ShapeList& sl)
{
  ShapeList::iterator sli;
  for (sli =  sl.begin();  sli != sl.end(); ++sli) {
    if (sli->fcolor != default_fcolor)
      os << "F " << (void *)sli->fcolor << endl;
    if (sli->bcolor != default_bcolor)
      os << "B " << (void *)sli->bcolor << endl;
    char ch;
    switch (sli->type) {
    case RECTANGLE: ch = 'R';  break;
    case ELLIPSE:   ch = 'E';  break;
    case LINE:      ch = 'L';  break;
    default:        ch = '?';  break;
    }
    os << ch << ' ' << sli->rect << endl;
  }
}

When you finally get to drawing the shapes, you don't need much code at all. With turtle graphics, you use methods for drawing ellipses (ellipse()) and rectangles (rectangle()) that use the foreground color for the outline, and the background color for the fill color. For instance, to draw a red rectangle with a black border you would set background to red, foreground to black, and then call rectangle(). You draw lines by calling plot() twice. Here is draw():

void draw(TG& tg, const ShapeList& sl)
{
  ShapeList::iterator sli;
  for (sli =  sl.begin();  sli != sl.end(); ++sli) {
    tg.set_color(sli->fcolor,true);       // set foreground color
    tg.set_color(sli->bcolor,false);      // set background color
    Rect rt = sli->rect;
    switch(sli->type) {
    case RECTANGLE:
        tg.rectangle(rt.left,rt.bottom,rt.right,rt.top);
        break;
    case ELLIPSE:
        tg.ellipse(rt.left,rt.bottom,rt.right,rt.top);
        break;
    case LINE:
        tg.penup();
        tg.plot(rt.left,rt.top);
        tg.plot(rt.right,rt.bottom);
        break;
    }  // switch(...)
   }  // for(...)
}

This function is the only part of the program where the graphics system and the data come together; to make this program use a different graphics library would be straightforward, because you would only have to rewrite draw().

Extensions

Specifying the coordinates of shapes explicitly is not fun. If you had a graphics processor embedded in your head, perhaps it would seem more natural, but most programmers have to sketch on pieces of paper and then experiment with various numbers. The beauty of true turtle graphics is that everything is done relative to the last position and orientation. For instance, having specified a square, it would be cool to then specify subsequent squares as clones of that square, relative to its position. Here is one possible notation:

S 10 20 40
S +w+3
S +w+3
S +h+3 -w-3

This is intended to produce three squares in a row, separated by three units. +w would mean “add width to the x position” and +3 would give the extra spacing (which would be optional). The last line will then add a square below the middle square; “+h+3” would mean “add height to y position, plus 3”, and so on. I will call these 'relative expressions' since they specify coordinates relative to the current position.

To add this feature, you can modify the code responsible for reading in rectangles (operator>>.) First, the code must save the last rectangle read in as a static variable old_rect. This variable will keep its value between calls to the operator. Second, operator>> now scans for 'w' and 'h' in the line that has been read in, and if the line contains these characters, then it must contain relative expressions . The relative expressions are evaluated with get_inc_expr(), which will give us an offset to add to old_rect. Otherwise, rect is read in as before from the line.

real get_inc_expr(string s, int idx, int real); // forward

istream& operator>>(istream& in, Rect& rt)
{
 string line;
 static Rect old_rect;
 Point p = point(0,0);
 getline(in,line);
 //------- look for width expr
 int idx = line.find("w");
 if (idx != string::npos)
   p.x = get_inc_expr(line, idx, width(old_rect));
 //------- look for height expr
 idx = line.find("h");
 if (idx != string::npos)
   p.y = get_inc_expr(line, idx, height(old_rect));
 if (p.x != 0 || p.y != 0) {  // at least one was specified!
   old_rect += p;            // modify and use last rect...
   rt = old_rect;
   return in;
 }
 // otherwise, we have to read the full rect in
 istringstream ins(line);
 ins >> rt.left >> rt.bottom >> rt.right >> rt.top;
 old_rect = rt;   // save the rectangle for possible future use...
 return in;
}

real get_inc_expr(string s, int idx, real dim)
{
  s += ' ';
  char p_m = s[idx-1];
  if (p_m != '+' && p_m != '-') fail("{ +|-} ...");
  if (p_m == '-') dim = -dim;
  p_m = s[idx+1];
  if (p_m == '+' || p_m == '-') {  // pick up number
    int is = idx+2;
    while (s[is] != ' ') is++;
    string tmp = s.substr(idx+2,is-idx-2);
    real val = atof(tmp.c_str());
    if (p_m == '+') dim += val;  else dim -= val;
  }
  return dim;
}