MX-CIF Quadtree Demo

Recursively decompose the underlying space into four equal area blocks so that each rectangle is associated with its minimum enclosing quadtree block. Several rectangles can be associated with a particular quadtree blocks (which need not be a leaf node). They are further distinguished by the use of one-dimensional variants of the MX-CIF quadtree (termed MX-CIF bintrees). There is one such tree for each of the x and y coordinate axes that pass through the center of each quadtree block. Each rectangle is associated with the smallest MX-CIF bintree node whose width covers it. If a rectangle overlaps the center of its minimum enclosing quadtree block, then it is associated with MX-CIF bintree corresponding to the y coordinate axis. For more details, see pages 466-473 and 827-832 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 200-213 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. If you click in an area that is occupied by several rectangles, one of them will be chosen arbitrarily and deleted.

In Search mode, click and drag to specify a rectangle. All rectangles stored in the MX-CIF tree overlapped by the new rectangle will be drawn in blue.