Cover Fieldtree or Loose Quadtree

The cover fieldtree and the equivalent loose quadtree (loose octree in three dimensions), is obtained by expanding the size of the space that is spanned by each quadtree block c of width w by a block expansion factor p (p>0) so that the expanded block is of width w.(1+p). Thus instead of associating (inserting) objects with (into) their minimum enclosing quadtree blocks as in MX-CIF quadtrees, they are associated with (inserted into) their minimum expanded quadtree block. For more details, see pages 257-259, 466-473 and 827-832 of Samet, Foundations of Multidimensional and Metric Data Structures and, 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 Move mode, you can click and drag to specify a rectangle. The yellow rectangle corresponds to the rectangle that is being operated upon. The blue square is the minimum enclosing quadtree block containing the yellow rectangle. The green square corresponds to the expanded blue quadtree block, containing the yellow rectangle. The yellow rectangle is reinserted in to the loose quadtree as soon as the centroid of the yellow rectangle extends past the blue quadtree block.

In Motion Insensitivity mode, you can click and drag to specify a rectangle. The yellow rectangle corresponds to the rectangle that is being operated upon. The blue square is the minimum enclosing quadtree block containing the yellow rectangle. The green square corresponds to the expanded blue quadtree block, containing the yellow rectangle. The yellow rectangle is reinserted in to the loose quadtree as soon as it touches the green square. The difference between Motion Insensitivity and the Move operation is that in the case of the Motion Insensitivity the centroid of the yellow rectangle can lie outside the blue quadtree block.

In Show Quadtree mode, the yellow rectangle corresponds to the rectangle that is being operated upon. The blue square is the minimum enclosing quadtree block containing the yellow rectangle. The green square corresponds to the expanded blue quadtree block, containing the yellow rectangle.