Advanced Programming II, Spring 2003

Programming Assignment 1 - An Example Solution

Table of Contents

Introduction

I scribbled down the origins of this problem while I was playing with a Java applet that let you freehand sketch box and arrow diagrams. The applet would recognize what you were sketching and tidy it up: boxes would be two pairs of parallel lines of each of the same size and arrows would be straight with uniform heads.

As you read this code, you might be wondering why it doesn't use the STL. There are two reasons:

  1. Knowing the STL isn't a prerequisite for the course, and it hasn't been covered yet in the course.

  2. A good way to appreciate the value of something (or to discover if it's still valuable) is to go without it for a while.

Design

The problem statement outlines the five things that a solution needs to do:

  1. Read the strokes from std-in.

  2. Classify the strokes as nodes or edges.

  3. Organize the nodes and edges into a tree.

  4. Lay-out the tree so it's tidy.

  5. Write the nodes and edges to std-out.

Reading and writing are simple enough to handle in a straightforward way. Classifying the strokes seems difficult, because all it has to work with is a sequence of points, and the points could vary from the ideal edges or nodes by quite a lot.

Starting with the obvious, edges are (mostly) straight, and nodes are (mostly) not. In technical terms, you would expect the x and y point coordinates in an edge to be highly correlated (that is, linear) and the x and y point coordinates in nodes to be anti-correlated. Computing the correlation coefficient between x and y for a stroke should provide a reasonably forgiving indication if the stroke's a node or an edge. Unfortunately, computing correlation coefficients is complicated (that is, I have to look up the formula).

Another obvious difference between nodes and edges is that the distance between node endpoints is small while the distance between edge endpoints is large when compared against the size of the whole stroke. Finding the stroke endpoints is easy. Finding the stroke size is harder than finding the endpoints, but finding the stroke's bounding box is easy and the bounding-box diagonal represents a good approximation for the stroke's size. As a first cut if the ratio of end-point distance over bounding-box diagonal is small, the stroke is assumed to be a node. If the ratio is large, the stroke is assumed to be an edge. If the ratio is between small and large the node's unclassifiable.

Once the nodes and edges have been recovered, they have to be assembled into a tree. This problem breaks down into two sub-problems: 1) establishing the connectivity between nodes and edges to form a graph and 2) checking that the graph forms a tree. The (undirected) graph can be assembled with a simple, brute-force search that examines each edge to determine its adjacent nodes. Once the graph is assembled, a depth-first traversal from the root marks out the tree.

There are several other aspects involved when assembling the tree. First, the left-to-right child order has to be preserved so that the output looks like the input. Second, the graph or tree could be malformed; every part requires error checking to make sure the data being worked on are valid. These aspects complicate tree assembly, but don't change it significantly.

Finally, the tree has to be laid-out so that it's tidy. Given the tree's regular recursive structure and the simple tidiness rules, there's a straightforward recursive algorithm for tidy tree lay-out, described below in the section on Tree Layout.

Files

This main() combines the first two steps of reading and classifying the strokes into one routine, largely to simplify things.

Main

<main.cc>=

#include <iostream>
#include <cstdlib>
#include "graph.h"
#include "read-strokes.h"
#include "tidy-tree.h"
#include "output-tree.h"


int main() {

  const stroke_list strokes = read_strokes(std::cin);

  if (strokes.node_cnt() + strokes.edge_cnt() == 0)
    return EXIT_SUCCESS;

  if (strokes.node_cnt() != strokes.edge_cnt() + 1) {
    std::cerr << "Improper tree: the node count (" << strokes.node_cnt()
              << ") should be one more than the edge count (" 
              << strokes.edge_cnt() << ").\n";
    return EXIT_FAILURE;
    }

  const graph g(strokes);

  output_tree(std::cout, g, tidy_tree(g));
  }
Defines main.cc (links are to index).

Strokes

It turns out that using a single bounding box to determine edge adjacency doesn't work too well when the edges are close together; the bounding boxes tend to intersect the same nodes, making it hard to distinguish edges. Also, while it's easy to tell when two bounding boxes overlap or not, it's harder to figure out how close they are when they don't overlap. This capability is needed when edges don't quite abut their adjacent nodes.

The solution to both these problems is to use two smaller bounding boxes, one around each edge endpoint. The smaller bounding box makes the adjacency testing more selective and resistant to interference from near-by edges. The end bounding boxes extend past the stroke bounding box, which lets them intersect with node bounding boxes even when the edge doesn't reach the node. The size of the endpoint bounding box is the key parameter; larger endpoint bounding boxes can cover larger gaps, but increase the likelihood of interference from near-by edges.

Because edge strokes use two bounding boxes and node strokes only use one, they should each have their own data structure. However, due to laziness (the non-Haskell kind), there is only one data structure used by both and the node bounding box is repeated. 

<stroke.h>=

#ifndef _stroke_h_defined_
#define _stroke_h_defined_

#include <string>
#include "bounding-box.h"

class stroke {

  public:

    // The many kinds of strokes.

       enum stroke_types {
         edge,
         error,
         node
         };


    // Create a stroke with no points.

       stroke();


    // Create a stroke from the given the coordinate sequence.

       stroke(const std::string &);


    // Return true iff this stroke is higher than the given stroke.

       bool higher(const stroke &) const;


    // Return true iff the given stroke overlaps with this stroke.

       bool overlaps(const stroke &) const;


    // What kind of stroke is this?

       stroke_types stroke_type;


    // An arbitrary index for this stroke.

       unsigned index;

  private:

    // The stroke's bounding boxes.

       bounding_box bb1, bb2;


    void read_points(const std::string &);
    void classify_stroke(point, point, const point &, const point &);
  };

#endif
Defines stroke.h (links are to index).

 * 
<stroke.cc>=

#include <sstream>
#include <cmath>
#include <iostream>
#include "point.h"
#include "stroke.h"


// Deja vu, c++ style.

   static bool read_point(std::istream &, point &, std::string &);
   static point max(const point &, const point &);
   static point min(const point &, const point &);
   static int snap_to(int, int, int);
   static point snap_to(const point &, const point &, const point &);


void stroke::
classify_stroke(point p1, point p2, const point & minp, const point & maxp) {

  // Classify a stroke given the first (p1) and last (p2) points in the stroke
  // and the diagonal (minp, maxp) of the bounding box containing the stroke.

  const double 
    length = p1.distance(p2)/minp.distance(maxp),
    nearness = 0.25;

  if (length >= 1 - nearness) {
    stroke_type = edge;
    p1 = snap_to(minp, maxp, p1);
    p2 = snap_to(minp, maxp, p2);
    bb1.set(p1.shift(-10), p1.shift(10));
    bb2.set(p2.shift(-10), p2.shift(10));
    }
  else if (length <= nearness) {
    stroke_type = node;
    bb1.set(minp, maxp);
    bb2.set(minp, maxp);
    }
  else {
    std::cerr << "Input contains an unclassifiable stroke, endpoint/diagonal = "
              << length << "\n";
    exit(EXIT_FAILURE);
    }
  }


bool stroke::
higher(const stroke & s) const {
  return (bb1.higher(s.bb2) and bb1.higher(s.bb1)) or
         (bb2.higher(s.bb2) and bb2.higher(s.bb1));
  }


static point
max(const point & p1, const point & p2) {

  // Return the point (max(p1.x, p2.x), max(p1.y, p2.y)).

  return point(std::max(p1.x, p2.x), std::max(p1.y, p2.y));
  }


static point
min(const point & p1, const point & p2) {

  // Return the point (min(p1.x, p2.x), min(p1.y, p2.y)).

  return point(std::min(p1.x, p2.x), std::min(p1.y, p2.y));
  }


bool stroke::
overlaps(const stroke & s) const {
  return bb1.overlaps(s.bb2) or bb1.overlaps(s.bb1) or
         bb2.overlaps(s.bb2) or bb2.overlaps(s.bb1);
  }


static bool
read_point(std::istream & is, point & pt, std::string & emsg) {

  // Read and store into pt the next point from the input stream is.  Return
  // the read status.

  if (!(is >> pt.x)) {
    if (!is.eof()) 
      emsg = "error during point read";
    return false;
    }

  if (is >> pt.y)
    return true;
  
  emsg = is.eof() ? "unexpected eof during point read" : "error during point read";
  
  return false;
  }


void stroke::
read_points(const std::string & l) {

  std::istringstream iss(l);
  point p1, p2;
  point maxp, minp;
  std::string emsg;

  if (!read_point(iss, p1, emsg) and emsg.empty()) 
    assert(!"unexpected eof from read-point()");

  if (!emsg.empty()) {
    std::cerr << "Error during stroke read:  " << emsg << ".\n";
    exit(EXIT_FAILURE);
    }

  minp = maxp = p1;

  while (read_point(iss, p2, emsg)) {
    minp = min(minp, p2);
    maxp = max(maxp, p2);
    }

  if (!emsg.empty()) {
    std::cerr << "Error during stroke read:  " << emsg << ".\n";
    exit(EXIT_FAILURE);
    }

  classify_stroke(p1, p2, minp, maxp);
  }


static int
snap_to(int min, int max, int v) {

  // Given the interval defined by the endpoints min and max, return the
  // endpoint that's closest to the given value v.

  assert(min <= max);
  assert((min <= v) and (v <= max));

  const unsigned
    d1 = v - min,
    d2 = max - v;

  return (d1 < d2) ? min : max;
  }


static point
snap_to(const point & minp, const point & maxp, const point & p) {

  // Given the bounding box defined by minp and maxp, return the box corner
  // that's closest to p.

  return point(snap_to(minp.x, maxp.x, p.x), snap_to(minp.y, maxp.y, p.y));
  }


stroke::
stroke() {
  stroke_type = error;
  }


stroke::
stroke(const std::string & l) {
  read_points(l);
  }
Defines stroke.cc (links are to index).

The Stroke List

<stroke-list.h>=

#ifndef _stroke_list_h_defined_
#define _stroke_list_h_defined_

#include "stroke.h"

class stroke_list {

  public:

    // Create a stroke list from the given stroke array, which contains the
    // given number of strokes.

       stroke_list(const stroke *, unsigned);

    // Get rid of this stroke list.

      ~stroke_list();

    // Return an array of indices for the children of the node with the given
    // index.  The children are stored in left-to-right order; the end of the
    // list is marked by -1.  The array should be freed by the caller.

       int * get_children(unsigned) const;

    // Return the index of the root node.

       unsigned get_root(void) const;

    // Return the number of strokes that are nodes.

       unsigned node_cnt(void) const { return ncnt; }

    // Return the number of strokes that are edges.

       unsigned edge_cnt(void) const { return ecnt; }

  private:

    unsigned ecnt, ncnt;
    stroke * edges, * nodes;

    bool find_adjacent(unsigned, unsigned, unsigned &) const;
  };

#endif
Defines stroke-list.h (links are to index).

 * 
<stroke-list.cc>=

#include <cstdlib>
#include <iostream>
#include "stroke-list.h"


int * stroke_list::
get_children(unsigned pindx) const {

  assert(pindx < ncnt);

  int * const children = new int[ncnt];
  unsigned ccnt = 0;

  for (unsigned i = 0; i < ecnt; i++) {
    unsigned cindx;
    if (find_adjacent(pindx, i, cindx))
      children[ccnt++] = cindx;
    }

  assert(ccnt < ncnt);
  children[ccnt] = -1;

  return children;
  }


bool stroke_list::
find_adjacent(unsigned pindx, unsigned eindx, unsigned & cindx) const {

  // Return true iff the edge with the given index overlaps the node with the
  // given index and a second node too.  If it does, set the given reference to
  // the index of the second node.

  assert(pindx < ncnt);
  assert(eindx < ecnt);

  if (!edges[eindx].overlaps(nodes[pindx]))
    return false;

  for (cindx = 0; cindx < ncnt; cindx++)
    if ((cindx != pindx) and edges[eindx].overlaps(nodes[cindx]))
      return true;
      
  return false;
  }


unsigned stroke_list::
get_root() const {

  assert(ncnt > 0);

  unsigned root = 0;

  for (unsigned i = 1; i < ncnt; i++)
    if (nodes[i].higher(nodes[root]))
      root = i;

  return nodes[root].index;
  }


static stroke *
make_list(unsigned cnt, const stroke * strokes, unsigned scnt, stroke::stroke_types stype) {

  // Return an array of size cnt containing strokes of type stype 
  // from the list of strokes strokes, which contains scnt strokes.  
  // returned array should be freed by the caller.

  assert((stype == stroke::node) or (stype == stroke::edge));

  if (cnt == 0)
    return 0;

  stroke * slist = new stroke[cnt];

  for (unsigned i = 0; i < scnt; i++)
    if (strokes[i].stroke_type == stype) {
      slist[--cnt] = strokes[i];
      slist[cnt].index = cnt;
      }

  assert(cnt == 0);

  return slist;
  }


stroke_list::
stroke_list(const stroke * strokes, unsigned cnt) {

  ecnt = ncnt = 0;
  for (unsigned i = 0; i < cnt; i++)
    if (strokes[i].stroke_type == stroke::node)
      ncnt++;
    else if (strokes[i].stroke_type == stroke::edge)
      ecnt++;
    else
      assert(!"unknown stroke type in stroke_list()");

  edges = make_list(ecnt, strokes, cnt, stroke::edge);
  nodes = make_list(ncnt, strokes, cnt, stroke::node);
  }


stroke_list::
~stroke_list() {
  delete [] edges;
  delete [] nodes;
  }
Defines stroke-list.cc (links are to index).

The Graph

To avoid having to deal too much with dynamic storage, the graph uses an adjacency matrix representation for the tree. The parent indices run down the matrix (are row indices), the child indices run across the matrix (are column indices). A non-negative value in an element indicates the parent and child are related; the value itself gives the child's position in the left-to-right ording of its sibling (0 is leftmost). 
<graph.h>=

#ifndef _graph_h_defined_
#define _graph_h_defined_

#include "stroke-list.h"

class graph {

  public:

    // Build the tree from the given set of strokes.

       graph(const stroke_list &);

    // Get rid of this tree.

      ~graph();

    // Return the number of children for the node with the given index.

       unsigned child_cnt(unsigned) const;

    // Return the index of the cno-th child (in left-to-right order) of the
    // node with the given index.

       unsigned get_child(unsigned nindx, unsigned cno) const;

    // Return the root of this tree.

       unsigned get_root() const { return root; }

    // Return true iff the node with the given index is a leaf.

       bool is_leaf(unsigned) const;

    // Return the number of nodes in this tree.

       unsigned node_cnt() const { return ncnt; }

  private:

    const unsigned ncnt;
    const unsigned root;
    int ** adjacency_matrix;

    void find_children(const stroke_list &, unsigned);
    void find_children(const stroke_list &, unsigned, bool *);
    void initialize_adjacency_matrix();
    void verify_tree(void) const;
  };

#endif
Defines graph.h (links are to index).

 * 
<graph.cc>=
#include <cstring>
#include <iostream>
#include "graph.h"


unsigned graph::
child_cnt(unsigned nindx) const {

  assert(nindx < ncnt);

  unsigned ccnt = 0;

  for (unsigned i = 0; i < ncnt; i++)
    if (adjacency_matrix[nindx][i] != -1)
      ccnt++;

  return ccnt;
  }


void graph::
find_children(const stroke_list & strokes, unsigned root) {

  // Find the children of all the nodes in the graph.

  bool * marked = new bool[ncnt];

  for (unsigned i = 0; i < ncnt; i++)
    marked[i] = false;
  marked[root] = true;

  find_children(strokes, root, marked);

  delete [] marked;
  }


void graph::
find_children(const stroke_list & strokes, unsigned root, bool * marked) {

  // Find the children of the given node.

  const int * const children = strokes.get_children(root);
  unsigned ccnt = 0;

  for (unsigned i = 0; children[i] > -1; i++) {
    assert(i < ncnt);
    const unsigned cindx = static_cast<unsigned>(children[i]);
    assert(cindx < ncnt);

    if (!marked[cindx]) {
      marked[cindx] = true;
      adjacency_matrix[root][cindx] = ccnt++;
      find_children(strokes, cindx, marked);
      }

    verify_tree();
    }

  delete [] children;
  }


unsigned graph::
get_child(unsigned p, unsigned cno) const {

  for (unsigned i = 0; i < ncnt; i++)
    if (adjacency_matrix[p][i] == static_cast<int>(cno))
      return i;

  assert(!"invalid child number in graph::get_child()");

  return 0;
  }


graph::
graph(const stroke_list & strokes) 

  : ncnt(strokes.node_cnt()), 
    root(strokes.get_root()) {

  initialize_adjacency_matrix();
  find_children(strokes, root);

  /*
  for (unsigned i = 0; i < ncnt; i++) {
    for (unsigned j = 0; j < ncnt; j++)
      fprintf(stderr, "%3d ", adjacency_matrix[i][j]);
    std::cerr << "\n";
    }
  */
  }


graph::
~graph() {
 for (unsigned i = 0; i < ncnt; i++)
   delete [] adjacency_matrix[i];
 delete [] adjacency_matrix;
 }


void graph::
initialize_adjacency_matrix() {

  // Create the adjacency matrix and initialize it so that no nodes are
  // adjacent.

  unsigned i;

  adjacency_matrix = new int *[ncnt];

  for (i = 0; i < ncnt; i++)
    adjacency_matrix[i] = new int [ncnt];

  for (i = 0; i < ncnt; i++)
    for (unsigned j = 0; j < ncnt; j++)
      adjacency_matrix[i][j] = -1;
  }


bool graph::
is_leaf(unsigned nindx) const {
  return 0 == child_cnt(nindx);
  }


void graph::
verify_tree(void) const {

  // Make sure all the nodes have been accounted for in the tree.

  unsigned edges = 0;

  for (unsigned i = 0; i < ncnt; i++)
    for (unsigned j = 0; j < ncnt; j++)
      if (adjacency_matrix[i][j] != -1) 
        edges++;

  if (edges != ncnt - 1) {
    std::cerr << "The input contained edges that could not be associated with any nodes.\n";
    exit(EXIT_FAILURE);
    }
  }
Defines graph.cc (links are to index).

Reading the Strokes

Because stroke-list has done most of the heavy lifting , the code to read strokes is relatively simple. The only tricky bit is that this code reads all the strokes before making the stroke list because the stroke list needs to know how much space to allocate to hold the strokes. Unfortunately, read_strokes() has the same problem: it needs to know how much space to allocate to hold the stokes as they're being read in.

Fortunately, the problem's easier to solve here than in stroke list. By recursing for each line of input, the strokes read can be held on the run-time stack. On end of input, all stokes have been read and the proper sized array can be created to hold the strokes. 

<read-strokes.h>=
#ifndef _read_strokes_h_defined_
#define _read_strokes_h_defined_

#include <istream>
#include "stroke-list.h"

// Return a stroke list containing the stokes read from the given input stream.

   stroke_list read_strokes(std::istream &);

#endif
Defines read-strokes.h (links are to index).

 * 
<read-strokes.cc>=
#include "read-strokes.h"


static bool is_blank_line(const std::string & l) {

  // Return true iff l is a line containing only space characters.

  return l.find_first_not_of(" \t\n\v") == std::string::npos;
  }


static bool
read_nonblank_line(std::istream & is, std::string & l) {

  // Read and store into l the next non-blank line read from the input stream
  // is.  Return true iff a non-blank line was read.

  while (true) {
    if (!getline(is, l))
      return false;
    if (!is_blank_line(l))
      return true;
    }
  }


static bool
read_stroke(std::istream & is, stroke & s) {

  // Read and store into s the next stroke read from the input stream is.
  // Return true iff a stroke was read.

  std::string l;
  if (!read_nonblank_line(is, l))
    return false;
  else {
    s = stroke(l);
    return true;
    }
  }


static stroke * 
read_strokes(std::istream & is, unsigned & total) {

  stroke s, * slist;
  
  if (read_stroke(is, s)) {
    const unsigned cnt = total++;
    slist = read_strokes(is, total);
    slist[cnt] = s;
    }
  else
    slist = new stroke[total];

  return slist;
  }


stroke_list 
read_strokes(std::istream & is) {

  unsigned total = 0;
  stroke * strokes = read_strokes(is, total);
  stroke_list slist(strokes, total);

  delete [] strokes;

  return slist;
  }
Defines read-strokes.cc (links are to index).

Making the Tree Tidy

This is a straightforward recursive algorithm for tidying a tree: tidy each of the tree's subchildren in (for example) left-to-right order, then position the root correctly over the tidy subtrees. 
<tidy-tree.h>=
#ifndef _tidy_tree_h_defined_
#define _tidy_tree_h_defined_

#include "node-info.h"
#include "graph.h"

// Return node lay-out information for a tidy version of the given graph.

   extern node_info tidy_tree(const graph &);

#endif
Defines tidy-tree.h (links are to index).

 * 
<tidy-tree.cc>=
#include "tidy-tree.h"

static const unsigned node_radius = 100;
static const unsigned inter_level_gap = 300;
static const unsigned sibling_gap = std::max(static_cast<unsigned>(1), node_radius/20);

static unsigned
tidy_tree(const graph & g, node_info & nodes, unsigned root, unsigned x, unsigned y) {

  // Locate the center of the root of tree t, assuming the current point is (x,
  // y).  Return the right-most x coordinate of the bounding box for tree t.

  assert(root < g.node_cnt());

  if (g.is_leaf(root)) {
    nodes.set_center(root, x + node_radius, y);
    return x + 2*(node_radius + sibling_gap);
    }

  unsigned right = x;
  for (unsigned i = 0; i < g.child_cnt(root); i++)
    right = tidy_tree(g, nodes, g.get_child(root, i), right, y + inter_level_gap);
  nodes.set_center(root, (x + right)/2, y);

  return right;
  }


node_info
tidy_tree(const graph & g) {

  node_info nodes(g.node_cnt(), node_radius);

  tidy_tree(g, nodes, g.get_root(), 0, 0);

  return nodes;
  }
Defines tidy-tree.cc (links are to index).

Outputting the Tree

<output-tree.h>=
#ifndef _output_tree_h_defined_
#define _output_tree_h_defined_

#include <ostream>
#include "graph.h"
#include "node-info.h"

// Write to the given output stream the given node information, extracted from
// the given graph.

   extern void output_tree(std::ostream &, const graph &, const node_info &);

#endif
Defines output-tree.h (links are to index).

 * 
<output-tree.cc>=
#include "point.h"
#include "output-tree.h"


static void 
output_edge(std::ostream & os, const node_info & nodes, unsigned pindx, unsigned cindx) {

  // Write to the given output stream the edge connecting the nodes with the
  // given indices.

  const point
    & c1 = nodes.get_center(pindx),
    & c2 = nodes.get_center(cindx);

  const double gap = nodes.radius/c1.distance(c2);

  os << " " << c1.interpolate(c2, gap)
     << " " << c1.interpolate(c2, 1.0 - gap);
  }


static void 
output_edges(
  std::ostream & os, const graph & g, const node_info & nodes, unsigned root) {

  // Write to the given output stream the edges in the given graph, starting
  // from the node with the given index.

  for (unsigned i = 0; i < g.child_cnt(root); i++) {
    const unsigned cindx = g.get_child(root, i);
    output_edge(os, nodes, root, cindx);
    output_edges(os, g, nodes, cindx);
    }
  }


static void 
output_nodes(std::ostream & os, const node_info & nodes) {

  // Write to the given output stream the given node set.

  for (unsigned i = 0; i < nodes.node_cnt; i++)
    os << " " << nodes.get_center(i);
  }


void 
output_tree(std::ostream & os, const graph & g, const node_info & nodes) {

  os << "nodes";
  output_nodes(os, nodes);
  os << "\n";

  os << "edges";
  output_edges(os, g, nodes, g.get_root());
  os << "\n";
  }
Defines output-tree.cc (links are to index).

Node Lay-Out Information

<node-info.h>=
#ifndef _node_info_h_defined_
#define _node_info_h_defined_

#include <cstring>
#include "point.h"

// The information needed to place nodes on the plain.

struct node_info {

  // The node centers.

     point * const centers;

  // The radius of every node.

     const unsigned radius;

  // The number of nodes.

     const unsigned node_cnt;


  // Create node information for ncnt nodes, each having radius r.

     node_info(unsigned ncnt, unsigned r) 
       : centers(new point[ncnt]),
         radius(r),     
         node_cnt(ncnt) {

       assert(ncnt > 0);
       assert(radius > 0);
       }


  // Create a copy of the given node information.

     node_info(const node_info & ni) 
       : centers(new point[ni.node_cnt]),
         radius(ni.radius),     
         node_cnt(ni.node_cnt) {

       std::memcpy(centers, ni.centers, node_cnt*sizeof(point));
       }


  // Get rid of this node information.

    ~node_info() {
       std::memset(centers, 0, node_cnt*sizeof(point));
       delete [] centers;
       }


  // Return the center for the node with the given index.

     point & get_center(unsigned nindx) const { 
       assert(nindx < node_cnt);
       return centers[nindx];
       }


  // Set the center coordinates for the node with the given index.

     void set_center(unsigned nindx, int x, int y) { 
       assert(nindx < node_cnt);
       centers[nindx].x = x;
       centers[nindx].y = y;
       }

  private:

    // No assignment.

       node_info & operator = (const node_info &) {
         assert(!"trying to assign one node-info to another");
         return *this;
         }
  };

#endif
Defines node-info.h (links are to index).

Bounding Boxes

<bounding-box.h>=

#ifndef _bounding_box_h_defined_
#define _bounding_box_h_defined_

#include "point.h"

class bounding_box {

  public:

    // Create the minimal bounding box.

       bounding_box();

    // Create a bounding box having a diagonal defined by the given points.

       bounding_box(const point &, const point &);

    // Return true iff this bounding box is higher than the given one.

       bool higher(const bounding_box &) const;

    // Return true iff this bounding box overlaps the given one.

       bool overlaps(const bounding_box &) const;

    // Reset the bounding box to have the diagonal defined by the given points.

    void set(const point &, const point &);

  private:

    int minx, miny, maxx, maxy;

    bool overlaps(int, int, int, int) const;
  };

#endif
Defines bounding-box.h (links are to index).

 * 
<bounding-box.cc>=

#include "bounding-box.h"


bounding_box::
bounding_box() : minx(0), miny(0), maxx(0), maxy(0) { }


bounding_box::
bounding_box(const point & p1, const point & p2) {
  set(p1, p2);
  }


bool bounding_box::
overlaps(int l1, int r1, int l2, int r2) const {

  // Return true iff the interval defined by [l1, r1] overlaps the interval
  // defined by [l2, r2].

  assert((l1 <= r1) and (l2 <= r2));

  return !((r2 < l1) or (r1 < l2));
  }


bool bounding_box::
overlaps(const bounding_box & bb) const {
  return overlaps(minx, maxx, bb.minx, bb.maxx) and 
         overlaps(miny, maxy, bb.miny, bb.maxy);
  }


bool bounding_box::
higher(const bounding_box & bb) const {
  return miny < bb.miny;
  }


void bounding_box::
set(const point & p1, const point & p2) {
  minx = std::min(p1.x, p2.x);
  miny = std::min(p1.y, p2.y);
  maxx = std::max(p1.x, p2.x);
  maxy = std::max(p1.y, p2.y);
  }
Defines bounding-box.cc (links are to index).

Points

<point.h>=
#ifndef _point_h_defined_
#define _point_h_defined_

#include <ostream>

struct point {

  // The point coordinates.

     int x, y;


  // Create a point with the default coordinates.

     point() : x(0), y(0) { }


  // Create a point with the given coordinates.

     point(int x, int y) : x(x), y(y) { }


  // Return the distance between the given point and this point.

     double distance(const point &) const;


  // Return a point that's the given faction of the way between this point 
  // and the given point.

     point interpolate(const point &, double) const;


  // Return the point that's shifted in both coordinates by the given amount.

     point shift(int) const;


  private:

     int interpolate(int, int, double) const;
  };


// Write the given point to the given output stream; return the given
// output stream.

   extern std::ostream & operator << (std::ostream & os, const point &);

#endif
Defines point.h (links are to index).

 * 
<point.cc>=
#include <cmath>
#include "point.h"


double point::
distance(const point & p) const {

  const int 
    delta_x = x - p.x,
    delta_y = y - p.y;
  
  return std::sqrt(static_cast<double>(delta_x*delta_x + delta_y*delta_y));
  }


int point::
interpolate(int v1, int v2, double fraction) const {

  // Return the (rounded) integer that's the given faction of the way between v1 
  // and v2.

  return v1 + static_cast<int>((static_cast<double>(v2 - v1)*fraction) + 0.5);
  }


point point::
interpolate(const point & p, double fraction) const {

  assert((0.0 <= fraction) and (fraction <= 1.0));

  return point(interpolate(x, p.x, fraction), interpolate(y, p.y, fraction));
  }


point point::
shift(int delta) const {
  return point(x + delta, y + delta);
  }


std::ostream &
operator << (std::ostream & os, const point & p) {
  return os << " " << p.x << " " << p.y;
  }
Defines point.cc (links are to index).

Index

This page last modified on 23 February 2003.