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.
Instructions
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.