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
Insert data into the selected region

Delete
Delete data from the selected region

Move
Move the selected region to a new destination.

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

X: The region being moved.
Y: The region which lies beneath the region X.
Z: The region that will be displayed as the result of an operation ("Move", "U Move", or "Copy").

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

Select
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:

Select an arbitrary rectangular region by clicking and dragging the mouse, the selection will be shown on the screen
Select one of the operations ("Insert", "Move", "Copy", "Delete", or "U Move")
Click inside the region that is selected at the first step