CSE 326 Data Structures
Project 3
Quad Trees: Spatial Data Structures
due: Wednesday May 21, 1997, 11:30pm
Overview
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:
Rectangular Range Search Problem: Given a collection of points
S and an input rectangle R, find the points in S that are in the interior
of R. A spatial data structure can be very useful here: we traverse
the tree, but we need only consider the sub-regions of a node that intersect
the rectangular query region.
Circular Range Deletion Problem: Given a collection of points
S and a circular region C, compute a set of points S' = S-C , that is,
the set of points in S that are not in C. This is similar to the
above, except now we consider only sub-regions that intersect the circular
region. The intersection test for this is trickier: you essentially
need to determine whether any of the region's points are within a certain
distance of C's center. In addition, this problem involves deletion
of the query region: you can solve this as a circular range query followed
by a series of quad tree deletions, or perhaps do both the search in the
delete in tandem. Both of these solutions have elegant features.
Assignment
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:
quad.C - this is the main driver code for quad
that we've partially implemented. Mostly, this will just make calls to
the Quadtree ADT and display their results. You are welcome to use
our partial implementation, or devise your own main driver that behaves
similarly.
Quadtree.{h,C} - contains a skeleton of the specification
of the quad tree ADT. Choose any implementation of the quad tree
data structure you like. You must implement:
Quadtree(pts,LL,UR) - the constructor for the ADT which takes
a set of points and the lower left and upper right corners of the bounding
box of the points.
Insert(pt) - inserts a point into the tree
RangeFind(LL,UR,pts) - returns a set of points pts
in the rectangular range given by the points LL and UR
CircleDelete(c,r,pts) - removes the points in the circular
range centered at c with radius r
Display() - display the quad tree
You can stick to our object interface, or devise a reasonable one of your
own.
Point.{h,C}, PointSet.{h,C}- contains the class Point
which abstracts operations on two dimensional points, and the class PointSet
for storing a collection of points.
display.{h,C}, GPKernel.{h,C} - these contain graphics
routines. The routines in display.{h,C} are provided for
your convenience, allowing you to draw rectangles, lines, circles, and
points, using point coordinates rather than screen coordinates. There
are also routines here to open a display, get a mouse click, and clear
the screen. Should you want any more drawing routines, you should
add them here and base them on the lower level routines in GPKernel.{h,C}.
Makefile - make quad will use this
to build your program.
All provided files can be found in the project directory:
/cse/courses/cse326/97sp/project3
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:
% quad inputs/exp.100 Building quadtree... Enter a command: [R]ange query, [I]nsert, [C]ircular delete, [Q]uit >> c
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:
Quadtree.h, Quadtree.C, quad.C
README - This is a text file describing your project
implementation. It should describe your implementation of the quad tree
and give a high level description of your algorithms.
any additional files that you added/changed.
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).