Implement a representation for a collection of (two dimensional) rectangles using a quadtree based on regular decomposition.
Question:
Implement a representation for a collection of (two dimensional) rectangles using a quadtree based on regular decomposition. Assume that the space being represented is a square whose width and height are some power of two. Rectangles are assumed to have integer coordinates and integer width and height. Pick some value c, and use as a decomposition rule that a region is subdivided into four equal-sized regions whenever it contains more that c rectangles. A special case occurs if all of these rectangles intersect at some point within the current region (because decomposing such a node would never reach termination). In this situation, the node simply stores pointers to more than c rectangles. Try your representation on data sets of rectangles with varying values of c.
Step by Step Answer:
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer