Region QuadTree Demo

Region Quadtree

A quadtree representation of two-dimensional binary region data. The most studied quadtree approach to region representations, called a region quadtree, is based on the successive subdivision of a bounded image array into four equal-size quadrants. If the array does not consist entirely of 1s or entirely of 0s (i.e. the region does not cover the entire array), then it is subdivided into quadrants, subquadrants, etc., until blocks are obtained that consist entirely of 1s or entirely of 0s; i.e., each block is entirely contained in the region or entirely disjoint from it. The region quadtree can be characterized as a variable resolution data structure. For more details, see pages 211-220 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 2-9 of Samet, Design and Analysis of Spatial Data Structures.

Data insert/delete/update operations:

Insert data into the selected region

Delete data from the selected region

Move the selected region to a new destination.

The following definitions will be used to explain "Move", "U Move", and "Copy" operations:
"Move" operation performs the following:

      Y = 0
      Z = X & Y   // Bitwise "AND"

U Move
Move the selected to a new destination.

"U Move" operation performs the following:

      Z = X | Y   // Bitwise "OR"

Copy operation is same as the "Move" operation except that only a copy of the selected region is moved as opposed to moving the original selected region.

This operation facilitates the data insert/delete/update operations such as "Insert", "Delete", "Move", "U Move", and "Copy". "Select" makes it possible to apply these operations to an arbitrary region.

"Select" operation works as follows: