Description
In this assignment you will build a custom data structure named QuadTree. The data structure you will build for this homework is similar to the classic quad tree, octree, k-d tree, and binary space partition data structures from computational geometry. These structures are used to improve the performance of applications that use large spatial data sets including: ray tracing in computer graphics, collision detection for simulation and gaming, motion planning for robotics, nearest neighbor calculation, image processing, and many, many others. Our QuadTree implementation will share some of the framework of the ds_set implementation we have seen in lecture and lab. You are encouraged to carefully study that implementation as you work on this homework. The diagrams below illustrate the incremental construction of the QuadTree data structure. In this example, we add the 21 two-dimensional points shown in the first image to the tree structure. We will add them in the alphabetical order of their labels. Each time a point is added we locate the rectangular region containing that point and subdivide that region into 4 smaller rectangles using the x,y coordinates of that point as the vertical and horizontal dividing lines. Each 2D coordinate (x,y) is stored in the Point class. In these plots (0,0) is in the upper left corner. The x axis runs horizontally, with increasing values to the right. The y axis runs vertically with increasing values in the downward direction. input points after adding the 1st point after adding the 2nd point +—————————————–+ | | | J | | G K | | F | | C | | B | | M | | H L | | I | | | | A | | | | O | | N R | | S | | D | | E | | P | | Q U | | T | | | +—————————————–+ +—————————————–+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |——————–A——————–| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +—————————————–+ +—————————————–+ | | | | | | | | | | | | | | | | | | | | |———-B———| | | | | | | | | | | | | | | | | | |——————–A——————–| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +—————————————–+ after adding the 3rd point after adding 9 points after adding all 21 points +—————————————–+ | | | | | | | | | | | | | | | | | | | | | | |———C———-| |———-B———| | | | | | | | | | | | | | | | | | | | | | | |——————–A——————–| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +—————————————–+ +—————————————–+ | | | | | | | | | | | | | | | | |—-G—-| | | |—–F—-| | | | | | | | | |———C———-| |———-B———| | | | | | | | | | |—-H—–| | | | | | | |—I—–| | | | | | | | | | |——————–A——————–| | | | | | | | | | | | | | | | | | | | | |———–D——–| | | | | |———-E———| | | | | | | | | | | | | | | | | | | | | +—————————————–+ +—————————————–+ | | | | | | | | | | | | | |—-J—-| | | | | |—-G—-| | |—-K—–| |—–F—-| | | | | | | | | | | |———C———-| |———-B———| | | | | | | | | | | |—–M—-| |—-H—–| | |—–L—| | | | | |—I—–| | | | | | | | | | | | | | |——————–A——————–| | | | | | | | | | | | |—-O—| | | | | |—N——-| | |—-R—–| | | | | | | | | |—–S—| |———–D——–| | | | | | | | | |———-E———| |—-P——| | | | | | | | | |—Q—-| | |—-U—-| | | | | |—T——| | | | | | | | | | | | +—————————————–+ Like an STL map and STL set, inserting a new Point into the QuadTree or querying (using find) whether a Point is already in the structure is fast, and can be completed in O(log n), where n is the number of Points in the tree. However, unlike the set and map structures which are based on a binary tree, having two subtrees per node, the QuadTree has 4 children at each node! The data in our QuadTree can be visualized using two different output routines, plot and print_sideways. You will also implement two different methods for iterating over the tree: depth-first or breadth-first. To do this, you will write two helper classes DepthIterator and BreadthIterator which will be typedef-ed within the QuadTree class. Here is a diagram showing the relationships between the different classes you will implement for this assignment. Be sure to draw plenty of your own diagrams as you work, and be prepared to show these diagrams when you come to office hours or ALAC tutoring to ask for help on the assignment. 3 Point
