Rectangle Quadtree Demo

Recursively decompose the underlying space into four equal area blocks until we obtain blocks which do not contain more than one rectangle. For more details, see pages 480-483 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 240-257 of Samet, Design and Analysis of Spatial Data Structures.


In Insert mode, click and drag to specify a new rectangle, in Delete mode click inside an existing rectangle to remove it from the quadtree. In Search mode click and drag to specify a rectangle. Rectangles in the quadtree that overlap the specified rectangle will be shown.