CSE 326 Data Structures
Project 3
Quad Trees: Spatial Data Structures

due: Wednesday May 21, 1997, 11:30pm


A spatial decomposition tree gives a hierarchical partitioning of a space. A region is associated with each node of the tree. If a node v corresponds to a region R, the children of v give a partition of R into disjoint subsets. In this assignment, we are interested in spatial decompositions of point sets. We decompose regions until each point is in a separate region. These regions form the leaves of the tree.

There are a zillion different schemes for spatial decomposition.  In this assignment, you are to design and implement a quad tree ADT-- one of the fundamental spatial data structures we've discussed in class.  With quad trees the region associated with a node is a square portion of two-dimensional space.  The children of a node correspond to an equal partitioning of the region into four equal-sized squares.

Spatial data structures are useful for applications where the data is multidimensional: where you might want to organize the data based on the values of multiple keys.  In these types of applications, the use of a spatial data structure allows you to efficiently answer questions about data points that are in certain regions of the multidimensional space-- they allow you to solve point location problems.

In this assignment we consider maintaining a set of two-dimensional points.  We consider the following two problems: 


You are required to implement a class Quadtree that performs some of the basic operations of a spatial ADT.  You are required to implement four methods: creation, point insertion, rectangular range query, and circular range deletion.  You will use your Quadtree class to build a program quad which allows you to test your operations, and solves the two problems defined above.  This test program has a graphical and command line user interface, so you will add methods to display or print your quad tree representation.  You may also find it useful to add graphics routines to the quad tree operations to animate your algorithms.

What we've provided 
As a starting point we've provided a few files: All provided files can be found in the project directory:
Running the program 
The program quad takes an input file containing a set of points, constructs a quad tree for those points, and displays it graphically.  We've provided a few interesting sample files in the directory project3/inputs. Once the quad builds the tree, it prompts the user for a command: The user can perform a rectangular range query to find points in a rectangular range, insert points into the set, and delete a set of points in a circular range.

What to hand in 
You are required to hand in your project3 directory with your implementation of the Quadtree data structure. Included in this directory should be at least these files: Turn your files in electronically using turnin:
% cd ~/326stuff/myproj3dir
% make clean
% cd ../
% turnin -c cse326=AA -p project3 myproj3dir

Sample solution

We've provided a sample executable quad.soln that you can use as a model for your solution.  Your program need not look the same, just perform similar functionality.  The solution executable is located in the directories project3/bin.alpha (for orcas & sanjuan executables) and project3/bin.RISC (for lynx, wolf, & grizzly).