## 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

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:
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:
```% cd ~/326stuff/myproj3dir