The point quadtree and the kd-tree are two data structures that generalize the binary search tree and are used to store multi-dimensional keys, such as points in k-dimensional space. For this assignment, however, we will limit our implementations to points in two-dimensional space though the extension to higher dimensions is quite straightforward Requirements 1. Implement the class Point for two-dimensional points. Include appropriate getters and setters (or properties). 2. Implement classes PointQuadtree and KDTree. a. Select an appropriate data structure b. // Insert point p // Assume that duplicate points are not inserted // Return true if successful; false otherwise public bool Insert(Point p) Note: Unlike the handout, assume that all points are not known beforehand. Therefore, no pre-processing is done to help balance the tree. c. // Delete point p // Returns true if successful; false otherwise public bool Delete(Point p) c. // Return true if point p is found; false otherwise public bool Contains(Point p d. // Return the list of points that are contained in the rectangle // bounded by the top left corner point p and the bottom right point q public List<Point> RangeSearch(Point p, Point q) Additional notes: Insert and delete points at a leaf node. Use internal nodes to define areas. For the PointQuadTree class only, initially set each dimension of the 2-D space to a power to 2. Implement additional support methods as required. 3. Test all classes and include your test cases 4. In a separate document, comment on how the implementations for Point, PointQuadTree and KDTree can be modified for points in k dimensions where k > 2. Consider for instance how a branch is determined for a PointerQuadTree and how a splitting line/plane is determined for a KDTree
The point quadtree and the kd-tree are two data structures that generalize the binary search tree and are used to
store multi-dimensional keys, such as points in k-dimensional space. For this assignment, however, we will
limit our implementations to points in two-dimensional space though the extension to higher dimensions is quite
straightforward
Requirements
1. Implement the class Point for two-dimensional points. Include appropriate getters and setters (or properties).
2. Implement classes PointQuadtree and KDTree.
a. Select an appropriate data structure
b. // Insert point p
// Assume that duplicate points are not inserted
// Return true if successful; false otherwise
public bool Insert(Point p)
Note:
Unlike the handout, assume that all points are not known beforehand.
Therefore, no pre-processing is done to help balance the tree.
c. // Delete point p
// Returns true if successful; false otherwise
public bool Delete(Point p)
c. // Return true if point p is found; false otherwise
public bool Contains(Point p
d. // Return the list of points that are contained in the rectangle
// bounded by the top left corner point p and the bottom right point q
public List<Point> RangeSearch(Point p, Point q)
Additional notes:
Insert and delete points at a leaf node. Use internal nodes to define areas.
For the PointQuadTree class only, initially set each dimension of the 2-D space to a power to 2.
Implement additional support methods as required.
3. Test all classes and include your test cases
4. In a separate document, comment on how the implementations for Point, PointQuadTree and KDTree
can be modified for points in k dimensions where k > 2. Consider for instance how a branch is
determined for a PointerQuadTree and how a splitting line/plane is determined for a KDTree
Step by step
Solved in 2 steps with 1 images
