CMSC 341 Spring 2009
Project 3

Assigned Friday, March 20, 2009
Due 11:59pm Friday April 3, 2009
Updates: Sample command line arguments:
"file1.txt 5 5 file2.txt"
Deadline extended until Sunday April 5th, 11:59 pm


  1. To gain experience implementing a Binary Tree ADT from scratch
  2. To gain experience using inheritance with generic classes
  3. To gain experience using Tree Iterators
  4. To gain experience using a Binary Tree in a real application
  5. To gain experience implementing the Adapter Design Pattern


A Binary Search Tree is most commonly used for maintaining information in a manner such that any node's left child is less than that of its value and a right child is greater than it. This definition is recursive and visually creates a partitioning of data held within the structure. A Binary Space Partition Tree is an implementation upon this which is commonly used in graphics to divide a scene up about a specific polygon into all polygons that are either behind or infront of that specific polygon. For a polygon, or anything (an object), to be in view (visible to us) we commonly say you are facing it. For an object to be infront of you, we commonly refer to objects that are in view from our left shoulder to the right. In this project you will implement a variation upon both of these data structures creating a Space Tree which will be used to partition objects in a scene based upon a viewing location and view direction vector.

We will implement a variation of a binary search tree using inheritance called a Space Tree. This will require you to implement your own Binary Search Tree ADT and create the derived Space Tree implementation. This Space Tree has a couple of properties (some recursive) that must be upheld at all times given the following information:

The viewer is located at an object in Cartesian space. The point at which the viewer resides is indicated (x,y) The view vector consists of (dx,dy) which represents the run and rise of the direction in which the viewer is facing/directed.

Space Tree Properties:

Figure 1: All letters are objects in the scene. X is the object where viewer resides at that specific time. v is the view vector of the viewer. If we look at the children of Y, we can see the effect of applying v to Y. Note that E is infront of Y thus its right child, and D is behind Y making it its left child.

Distance and View Vectors

Computing distance between any two points P1 and P2 can be computed by the following calculation (

Calculates the distance between any two points

Given the view vector of the Space Tree v knowing if an object is in view (infront or behind) is a simple comparison.

Figure 2

First, we apply the viewer's view vector v to a node(object) and call this vector v' at P0. Then given any point P1, not currently present in our tree, we calculate another vector v1
P1(x) - P0(x)
P1(y) - P0(y)
If v1 is not within a 90o rotation of v' then it is out of view and behind P0. Seen in Figure 2. To find the Θ for the difference in rotation (90o from v') lets look at how to rotate a vector v by &Theta degrees to create v'':
vx*cos(&Theta) - vy*sin(&Theta)
vy *cos(&Theta) + vx*sin(&Theta)

Using v' and v1 you can solve for &Theta . where v1 and v' are normalized.
&Theta = cos-1(v1 dot v')
v1 dot v' = v1(x)*v'(x)+v1(y)*v'(y)

Project 3 will be invoked with multiple command line arguments.

  1. The first argument is the name of the text file which will contain the objects in the scene. These are to be inserted into the Space Tree in the order read from the file based on the 2nd and 3rd command line arguments. The first object in this file is to be inital viewer location.
  2. The second argument is the view vector. Note this view vector may divide your scene any way you can draw a straight line. (Two integers)
  3. The third argument is the name of a text file containing a series of commands.

The Commands

Every command defined below triggers the resulting response in the application. Please note that the commands are case sensitive and illegal commands should be dealt with such that the program does not abort execution.

The ADTs

The Scene Object ADT

The Scene Object ADT is a Binary Node with a few changes to the methodology. The left child is a node that is behind the parent and the right child is a node that is infront. Scene objects also have a name(string) and x and y coordinates (The object file will contain these fields in this order). These coordinates will be integer values.

The Space Tree ADT

This ADT will implement the properties of the Space Tree, manage the viewer location, and manage the view vector. The Space Tree also has the following functionality:

Basic Project Requirements

  1. ALL TREES used in this project must be created from scratch. This includes tree iterators if you choose to use one. This means NO JAVA TREES or ITERATORS are permitted.
  2. You create/modify your own tree, tree node, and tree iterator.
  3. The Space Tree must be implemented using inheritance from the Binary Tree you create.
  4. All possible exceptions discussed pertaining to Trees must be caught and dealt with appropriately. Your program should continue processing after an exception if at all possible.
  5. Only the Space Tree class is instantiated in main( ) or in functions called from main( ).
  6. You may include any private data and private functions to any class.
  7. Be prepared for your code to work on large data sets.
  8. The move function must result in a splay operation. You can use either top-down or bottom-up splay methods.
  9. You must bulletproof your code as much as possible, e.g. making sure that the command line parameters are all valid, that the files named in it all exist, and that there is at least one report command. In case of invalid report parameters, your program should print them and a message indicating that the command is in error.

Project Notes and Hints

  1. You may not use the java tree classes and will recieve 0 points in this event. However, you may use the material presented in class as a guide. This does not mean you can copy any code from the slides.
  2. For this project you are to consider closest as an object in the Space Tree which is nearest to the partition line created by a node view vector.
  3. One or more objects may neither be infront nor behind a node. In this event, we will always treat these nodes as behind based on their distance.
  4. Only implement methodolgy you NEED in your base classes.
  5. Trees are generic in type.
  6. The move operation should not trigger a recreation (or a new tree construction) of your entire tree about the new viewer position.
  7. To answer the questions with this project, you may need to implement code that is not required by the output of the project.
  8. There are many ways to implement your tree ADT. Choose the most appropriate given the requirements of the Space Tree.
  9. Adhere to and live by the K.I.S.S. principle.
  10. This is not an easy project. Start early!!!
  11. Good Luck!

Files To Be Submitted

You must use CVS to check out your module in the Proj3 repository and to check in your code. That must include an ant build.xml file with targets for creating javadoc (named "doc"), for running your program (named "run" and that allows the command line arguments to be specified with -Dargs, like this ant -Dargs="arg1 arg2 ..." run), and for compiling your code (this must be the default target). The build.xml file that comes with your module in the Proj3 repository has all of this. Do not submit or put under CVS control your javadoc output. We will build it with the "ant doc" command. See the projects page for more information on all of these topics. If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Grading and Academic Integrity

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.