quad tree

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".

The subdivided regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel
* Spatial indexing, point location queries, and range queries
* Efficient collision detection in two dimensions
* Hidden face removal#Viewing frustum culling, View frustum culling of terrain data
* Storing sparse data, such as a formatting information for a spreadsheet or for some matrix calculations
* Solution of multidimensional fields (computational fluid dynamics, electromagnetism)
* Conway's Game of Life simulation program.
* State estimation
* Quadtrees are also used in the area of fractal image analysis
* Maximum disjoint sets

Image processing using quadtrees

Quadtrees, particularly the region quadtree, have lent themselves well to image processing applications. We will limit our discussion to binary image data, though region quadtrees and the image processing operations performed on them are just as suitable for colour images.

Image union / intersection

One of the advantages of using quadtrees for image manipulation is that the set operations of union and intersection can be done simply and quickly.

Given two binary images, the image union (also called ''overlay'') produces an image wherein a pixel is black if either of the input images has a black pixel in the same location. That is, a pixel in the output image is white only when the corresponding pixel in ''both'' input images is white, otherwise the output pixel is black. Rather than do the operation pixel by pixel, we can compute the union more efficiently by leveraging the quadtree's ability to represent multiple pixels with a single node. For the purposes of discussion below, if a subtree contains both black and white pixels we will say that the root of that subtree is coloured grey.

The algorithm works by traversing the two input quadtrees ($T_1$ and $T_2$) while building the output quadtree $T$. Informally, the algorithm is as follows. Consider the nodes $v_1 \in T_1$ and $v_2 \in T_2$ corresponding to the same region in the images.
* If $v_1$ or $v_2$ is black, the corresponding node is created in $T$ and is colored black. If only one of them is black and the other is gray, the gray node will contain a subtree underneath. This subtree need not be traversed.
* If $v_1$ (respectively, $v_2$) is white, $v_2$ (respectively, $v_1$) and the subtree underneath it (if any) is copied to $T$ .
* If both $v_1$ and $v_2$ are gray, then the corresponding children of $v_1$ and $v_2$ are considered.

While this algorithm works, it does not by itself guarantee a minimally sized quadtree. For example, consider the result if we were to union a checkerboard (where every tile is a pixel) of size $2^ \times 2^$ with its complement. The result is a giant black square which should be represented by a quadtree with just the root node (coloured black), but instead the algorithm produces a full 4-ary tree of depth $k$. To fix this, we perform a bottom-up traversal of the resulting quadtree where we check if the four children nodes have the same colour, in which case we replace their parent with a leaf of the same colour.

The intersection of two images is almost the same algorithm. One way to think about the intersection of the two images is that we are doing a union with respect to the ''white'' pixels. As such, to perform the intersection we swap the mentions of black and white in the union algorithm.

Connected component labelling

Consider two neighbouring black pixels in a binary image. They are ''adjacent'' if they share a bounding horizontal or vertical edge. In general, two black pixels are ''connected'' if one can be reached from the other by moving only to adjacent pixels (i.e. there is a path of black pixels between them where each consecutive pair is adjacent). Each maximal set of connected black pixels is a ''connected component''. Using the quadtree representation of images, Samet showed how we can find and label these connected components in time proportional to the size of the quadtree. This algorithm can also be used for polygon colouring.

The algorithm works in three steps:
* establish the adjacency relationships between black pixels
* process the equivalence relations from the first step to obtain one unique label for each connected component
* label the black pixels with the label associated with their connected component
To simplify the discussion, let us assume the children of a node in the quadtree follow the ''Z''-order (SW, NW, SE, NE). Since we can count on this structure, for any cell we know how to navigate the quadtree to find the adjacent cells in the different levels of the hierarchy.

Step one is accomplished with a post-order traversal of the quadtree. For each black leaf $v$ we look at the node or nodes representing cells that are Northern neighbours and Eastern neighbours (i.e. the Northern and Eastern cells that share edges with the cell of $v$). Since the tree is organized in ''Z''-order, we have the invariant that the Southern and Western neighbours have already been taken care of and accounted for. Let the Northern or Eastern neighbour currently under consideration be $u$. If $u$ represents black pixels:
* If only one of $u$ or $v$ has a label, assign that label to the other cell
* If neither of them have labels, create one and assign it to both of them
* If $u$ and $v$ have different labels, record this label equivalence and move on
Step two can be accomplished using the union-find data structure. We start with each unique label as a separate set. For every equivalence relation noted in the first step, we union the corresponding sets. Afterwards, each distinct remaining set will be associated with a distinct connected component in the image.

Step three performs another post-order traversal. This time, for each black node $v$ we use the union-find's ''find'' operation (with the old label of $v$) to find and assign $v$ its new label (associated with the connected component of which $v$ is part).

Mesh generation using quadtrees

This section summarizes a chapter from a book by Har-Peled and de Berg et al.

Mesh generation is essentially the triangulation of a point set for which further processing may be performed. As such, it is desirable for the resulting triangulation to have certain properties (like non-uniformity, triangles that are not "too skinny", large triangles in sparse areas and small triangles in dense ones, etc.) to make further processing quicker and less error-prone. Quadtrees built on the point set can be used to create meshes with these desired properties.

Consider a leaf of the quadtree and its corresponding cell $v$. We say $v$ is ''balanced'' (for mesh generation) if the cell's sides are intersected by the corner points of neighbouring cells at most once on each side. This means that the quadtree levels of leaves adjacent to $v$ differ by at most one from the level of $v$. When this is true for all leaves, we say the whole quadtree is balanced (for mesh generation).

Consider the cell $v$ and the $5\times 5$ neighbourhood of same-sized cells centred at $v$. We call this neighbourhood the ''extended cluster''. We say the quadtree is ''well-balanced'' if it is balanced, and for every leaf $u$ that contains a point of the point set, its extended cluster is also in the quadtree and the extended cluster contains no other point of the point set.

Creating the mesh is done as follows:
# Build a quadtree on the input points.
# Ensure the quadtree is balanced. For every leaf, if there is a neighbour that is too large, subdivide the neighbour. This is repeated until the tree is balanced. We also make sure that for a leaf with a point in it, the nodes for each leaf's extended cluster are in the tree.
# For every leaf node $v$ that contains a point, if the extended cluster contains another point, we further subdivide the tree and rebalance as necessary. If we needed to subdivide, for each child $u$ of $v$ we ensure the nodes of $u$'s extended cluster are in the tree (and re-balance as required).
# Repeat the previous step until the tree is well-balanced.
# Transform the quadtree into a triangulation.
We consider the corner points of the tree cells as vertices in our triangulation. Before the transformation step we have a bunch of boxes with points in some of them. The transformation step is done in the following manner: for each point, warp the closest corner of its cell to meet it and triangulate the resulting four quadrangles to make "nice" triangles (the interested reader is referred to chapter 12 of Har-Peled for more details on what makes "nice" triangles).

The remaining squares are triangulated according to some simple rules. For each regular square (no points within and no corner points in its sides), introduce the diagonal. Note that due to the way in which we separated points with the well-balancing property, no square with a corner intersecting a side is one that was warped. As such, we can triangulate squares with intersecting corners as follows. If there is one intersected side, the square becomes three triangles by adding the long diagonals connecting the intersection with opposite corners. If there are four intersected sides, we split the square in half by adding an edge between two of the four intersections, and then connect these two endpoints to the remaining two intersection points. For the other squares, we introduce a point in the middle and connect it to all four corners of the square as well as each intersection point.

At the end of it all, we have a nice triangulated mesh of our point set built from a quadtree.

Pseudocode

The following pseudo code shows one means of implementing a quadtree which handles only points. There are other approaches available.

Prerequisites

It is assumed these structures are used.

''// Simple coordinate object to represent points and vectors''
struct XY

''// Axis-aligned bounding box with half dimension and center''
struct AABB

QuadTree class

This class represents both one quad tree and the node where it is rooted.

class QuadTree

Insertion

The following method inserts a point into the appropriate quad of a quadtree, splitting if necessary.

class QuadTree

Query range

The following method finds all points contained within a range.

class QuadTree

See also

* Adaptive mesh refinement
* Binary space partitioning
* Binary tiling
* Kd-tree
* Octree
* R-tree
* UB-tree
* Spatial database
* Subpaving
* Z-order curve

References

Surveys by Aluru and Samet give a nice overview of quadtrees.

Notes

General references

#
# Chapter 14: Quadtrees: pp. 291–306.
#

{{CS-Trees

Trees (data structures)
Database index techniques
Geometric data structures