Programming Exercise: Trees
Due 1 July 1999

CSC 172

The goal of this program is to allow you to construct and visualize (representations of) simple two-dimensional shapes. A general two-dimensional shape is made up of basic shapes combined with union, intersection, and difference set operations. Our basic shapes are rectangles with vertical and horizontal sides and disks. Your system will thus allow you to create such primitives, with sizes you control, in locations of a 2-D work area. You can then, using the combining set operations (Union, Intersection, and Difference), paste and cut the basic shapes to create more complex shapes. Thus by differencing a disk with another you could get an annular shape, by unioning two rectangles you can get an L shape (as you can by differencing two different rectangles).

You should have a Shape class that has derived classes for the various primitive shapes you support. I suggest a square shape and a circular disk shape. A shape is understood to have an origin point, which I like to think of as its center. It is understood to have a standard size. So the disk could be centered at (0,0) and have a radius of 1. The square could be centered at (0,0) and have a side length of 2, so its corners are at (1,1), (1, -1), (-1, 1) and (-1,-1).

Shapes also have parameters that describe scaling, orientation, and location. The idea is that a shape can be stretched in the x (horizontal) and y (vertical) direction, rotated counterclockwise around its center, and then moved to put its center at some (x,y) location. (This way to represent a shape is called template instancing, for obvious reasons. The type of shape expects certain arguments giving its location and the size of its variable parameters.) All shapes live in a 2-D space indexed by row and col: for definiteness let us say row and col are integers $0 \leq row, col \leq N$,where N is going to be some size supported by your screen, possibly 80. You'll be happier if you count rows upwards, with zero at the bottom. That will make them correspond to the normal y direction.

The shape parameters allow you to describe larger or smaller disks or squares, as well as possibly tilted ellipses and rectangles. Thus if you stretched the square by a factor of 3 in x and translated it by 20 in x and 30 in y, you would have a rectangle with corners at (17 ,31), (23,31), (23,29), and (17,29).

Building on your first two programs, it seems like an interactive program is possible here. It could first create shapes with names that are array indices in a shape array (as in the sparse array program). Basically you just run a command loop to create parameterized shape instances, as many as you'll need.

In the next stage, you combine the individual shapes into a set-theoretic combination. Just as in an arithmetic expression, you can specify a complex shape by an expression that uses the union intersection and difference set-combination functions operating on shape specifications. In infix, if you have defined the four shapes 0,1,2, and 3, an expression might be (0 U 1) I (2 - 3) (the intersection of (the union of 0 and 1) with (the difference of 2 and 3)). Thus you should have an operator class with derived classes for union, intersection, and difference. The operators have left and right operands, and some associated methods.

Now it turns out that the best way to represent this expression is not in infix, or postfix, but in prefix (which is how I described it in prose above). Infix is like postfix but backwards: each operator is followed by its two operands. Ultimately, you are to produce an expression tree (FCS, p. 228) from the expression. It is a binary tree, since the operators are binary, and its leaves contain the shapes. Its inner nodes contain operators. Thus the tree for the equivalent expressions above looks like this:

                     I
                    / \
                   /   \
                  /     \
                 U       D
                / \     / \             
               0   1   2   3
  

Now notice that a recursive parser can easily convert infix into one of these trees. The parser has cases for the various things it might see in the expression (operator symbols or operand integer indices). Each operator symbol causes creation of an operator instance of the correct class and two recursive calls to the parser to get its two (left and right) operands. For leaf nodes, the parser simply returns the shape instance pointer. If the infix expression is legal, everything works out neatly. This is called recursive descent parsing, and infix is a win since when you read each symbol you know just what to do at that point in building the tree and the recursion saves all the partial structure for you.

Now you have an expression tree, which is a representation of two-dimensional shape called Constructive Plane Geometry. Constructive solid geometry is an important tool in 3-D graphics packages.

It is now easy to visualize our shape graphically, at least approximately. Let us represent the desired image as a 2-D array of chars which we shall just print out in order to visualize it (if you want to do something fancier with graphics be my guest!). The indices on the array correspond to the range of x and y coordinates in the shape space. For each ``pixel'' (character position) in our array, we are going to compute whether it is in or out of the shape. If the point is in, we output an @ or other dark character at the corresponding position in our output array.

Thus the difference of two rectangles could appear something like this when the image array is printed:

             @@@@
             @@@@
             @@@@
             @@@@@@@@@@@@@
             @@@@@@@@@@@@@
             @@@@@@@@@@@@@
             @@@@@@@@@@@@@
             @@@@@@@@@@@@@
  

The simplest way to determine if a point is in the shape (for small problems) is recursively, through a postorder traversal of the expression tree, once for every point you wish to draw (every (x,y) position in the image matrix). For any non-leaf node of the tree, compute whether the point is in the left child and whether it is the right child. If a point is in either of the children of a union node it is in the union node, if it is in both the children of an intersection node it is in the intersection node, and if it is in the left and not in the right child of a difference node it is in the difference. If the point is in the root node of the tree, draw it in the image matrix, else don't.

The recursion ends at the leaves, where you must compute whether the point is inside or outside the geometric primitive. Now notice that we only implicitly know where these shapes are... explictly we only know their type and their parameters. This is OK, and in fact it should work out pretty well. I would treat all these calculations in floating point and then round to integers. The neat trick is that we only have to be able to calculate if a point is in the primitive (unrotated, unscaled, unmoved) primitive shape: to work with the parameterized shape we'll simply lie about what point we mean! For now we'll talk about ``the point'' and then figure out what point we need to specify.

First, it is easy to tell if the point (x,y) is in our primitive disk: The formula for the disk is $x^2 +y^2 <=1^2$, so if you sum up the squares of the point's x and y coordinates and the sum is less than or equal to 1, it's in. (Of course if your primitive disk has a different radius you'll need a different formula). Likewise for the square if $-1 <= x,y <=1$, the point is in the square.

OK, now the last issue. Suppose we have a grid point (row, col) and we have a shape that has been stretched (multiplied) by (xfac, yfac) in the x and y directions, rotated by $\theta$ degrees counterclockwise, and translated by (xt, yt) up into the grid. The idea is to perform the inverse shape-distortion operations (which would restore the shape to its primitive state) on the point. Then we can compare the new, transformed (by the ``un-distortion transform'') point with the undistorted shape as above. So that means you have to subtract the translation, un-do the rotation, and un-do the stretches, in that order. So the new point should be (remember that the row measures y and the column measures x, and that you are counting rows upwards from the lower left hand corner, not downwards from the upper left hand corner). If you work through the math (remember rotation of coordinate systems?) you'll see you need something like this:

  y1 = (row-yt); x1 = (col-xt);           //untranslate
  x2 = x1 * cos(theta) + y1 * sin(theta);
  y2 = x1 * sin(theta) - y1 * cos(theta); // unrotate
  x = x2/xfac;  y = y2/yfac;              // unscale
  
And this (x,y) is the one you test against the primitive shape. At least this should work: give it a try and see what happens: bug and thinko reports to CB please. You'll need the math library for this, so specify -lm in the appropriate compile or link command.

This is a two-dimensional version of``ray casting'' to produce an image. Ray-casting projects lines of sight at a 3-D representation to produce graphics. There have been VLSI chips made to do this job, and the POVRay software available for free off the web allows you to make zippy pictures like the one advertising Videre on Chris Brown's home page using Constructive Solid Geometry and ray-casting. For a POVRay tutorial, try http://tqd.advanced.org/3285/.

An alternative to the interactive version of this program would be to have an input (disk) file that was simply the infix for the tree, only in place of the shape indices you would have a letter (D or S, say) indicating the type of shape, and that would be followed by the parameters for the shape.

TURN-IN a directory with your code, a README file that is well-written and spell-checked file that tells the contents of the various files in the directory. It should document your approach, the functionality of the various subroutines, the semantics of the classes, any extra functionality you added, so that the code can be understood. Also the README should provide a user's manual: how to run the code. You should have sample data files, transcripts of sessions showing the code working, images it produced, whatever it takes to convince us it works. Do not include .o, outdated versions (.bak or tilde files) or binary executable files in the directory.