Quadtree

A quadtree is a tree data structure in which each internal node has exactly four children.

[2] Quadtrees may be classified according to the type of data they represent, including areas, points, lines and curves.

Quadtrees may also be classified by whether the shape of the tree is independent of the order in which data is processed.

The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion.

The height of quadtrees that follow this decomposition strategy (i.e. subdividing subquadrants as long as there is interesting data in the subquadrant for which more refinement is desired) is sensitive to and dependent on the spatial distribution of interesting areas in the space being decomposed.

Rather than store a big 2-D array of every pixel in the image, a quadtree can capture the same information potentially many divisive levels higher than the pixel-resolution sized cells that we would otherwise require.

It shares the features of all quadtrees but is a true tree as the center of a subdivision is always on a point.

It is often very efficient in comparing two-dimensional, ordered data points, usually operating in O(log n) time.

Point quadtrees are worth mentioning for completeness, but they have been surpassed by k-d trees as tools for generalized binary search.

In a region quadtree, a uniform value is stored that applies to the entire area of the cell of a leaf.

As mentioned previously, for trees following this decomposition strategy the height depends on the spatial distribution of the points.

Near corners/vertices, edge quadtrees will continue dividing until they reach their maximum level of decomposition.

There are three main classes of PM Quadtrees, which vary depending on what information they store within each black node.

When we only keep important subtrees, the pruning process may leave long paths in the tree where the intermediate nodes have degree two (a link to one parent and one child).

at the beginning of this path (and associate some meta-data with it to represent the removed nodes) and attach the subtree rooted at its end to

Although we trim a lot of the tree when we perform this compression, it is still possible to achieve logarithmic-time search, insertion, and deletion by taking advantage of Z-order curves.

time the lowest common ancestor of two points/cells in the quadtree and establish their relative Z-ordering, and we can compute the floor function in

(i.e. find its cell in the compressed tree): Without going into specific details, to perform insertions and deletions we first do a point location for the thing we want to insert/delete, and then insert/delete it.

[4][16] 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.

As such, to perform the intersection we swap the mentions of black and white in the union algorithm.

The algorithm works in three steps: To simplify the discussion, let us assume the children of a node in the quadtree follow the Z-order (SW, NW, SE, NE).

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.

represents black pixels: Step two can be accomplished using the union-find data structure.

This section summarizes a chapter from a book by Har-Peled and de Berg et al.[24][25] Mesh generation is essentially the triangulation of a point set for which further processing may be performed.

Quadtrees built on the point set can be used to create meshes with these desired properties.

Creating the mesh is done as follows: We consider the corner points of the tree cells as vertices in our triangulation.

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[24] for more details on what makes "nice" triangles).

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.

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

The following pseudo code shows one means of implementing a quadtree which handles only points.