View source for Quadtree

{{Short description|Tree data structure in which each internal node has exactly four children, to partition a 2D area}}
{{citation style|date=April 2015}}
{{Infobox data structure
| name               = Quadtree
| image              = 
| alt                = 
| caption            = 
| type               = Tree
| invented_by        = [[Raphael Finkel]] and [[J.L. Bentley]]
| invented_year      = 1974
| space_avg          = 
| space_worst        = 
| search_avg         = 
| search_worst       = 
| insert_avg         = 
| insert_worst       = 
| delete_avg         = 
| delete_worst       = 
| peek_avg           = 
| peek_worst         = 
| find_min_avg       = 
| find_min_worst     = 
| delete_min_avg     = 
| delete_min_worst   = 
| decrease_key_avg   = 
| decrease_key_worst = 
| merge_avg          = 
| merge_worst        = 
}}
[[Image:Point quadtree.svg|thumb|300px|A point-region quadtree with point data. Bucket capacity 1.]]
[[File:Quadtree compression of an image.gif|thumb|300x300px|Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image]]
A '''quadtree''' is a [[tree data structure]] in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of [[octree]]s 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]] and [[J.L. Bentley]] in 1974.<ref>{{cite journal |last1=Finkel |first1=R. A. |last2=Bentley |first2=J. L. |title=Quad trees a data structure for retrieval on composite keys |journal=Acta Informatica |date=1974 |volume=4 |issue=1 |pages=1–9 |doi=10.1007/BF00288933 |s2cid=33019699 |url=https://www.researchgate.net/publication/220197855 |access-date=6 November 2019}}</ref> A similar partitioning is also known as a ''Q-tree''. 

All forms of quadtrees share some common features:
* They decompose space into adaptable cells.
* Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits.
* The tree directory follows the spatial decomposition of the quadtree.

A '''tree-pyramid''' ('''T-pyramid''') is a "complete" tree; every node of the T-pyramid has four child nodes except leaf nodes; all leaves are on the same level, the level that corresponds to individual pixels in the image. The data in a tree-pyramid can be stored compactly in an array as an [[implicit data structure]] similar to [[binary heap#Heap implementation|the way a complete binary tree can be stored compactly in an array]].<ref>
Milan Sonka, Vaclav Hlavac, Roger Boyle.
[https://books.google.com/books?id=DcETCgAAQBAJ "Image Processing, Analysis, and Machine Vision"].
2014.
p. 108-109.
</ref>

==Types==
[[File:2D Binary Index.svg|thumb|An example of a recursive [[binary space partitioning]] quadtree for a 2D index.]]
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 following are common types of quadtrees.

===Region quadtree===
The region quadtree represents [[Space partitioning|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. Each node in the tree either has exactly four children, or has no children (a leaf node). 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. The region quadtree is a type of [[trie]].

A region quadtree with a depth of n may be used to represent an image consisting of 2<sup>n</sup> × 2<sup>n</sup> pixels, where each pixel value is 0 or 1. The root node represents the entire image region. If the pixels in any region are not entirely 0s or 1s, it is subdivided. In this application, each leaf node represents a block of pixels that are all 0s or all 1s. Note the potential savings in terms of space when these trees are used for storing images; images often have many regions of considerable size that have the same colour value throughout. 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. The tree resolution and overall size is bounded by the pixel and image sizes.

A region quadtree may also be used as a variable resolution representation of a data field. For example, the temperatures in an area may be stored as a quadtree, with each leaf node storing the average temperature over the subregion it represents.

===Point quadtree===
The point quadtree<ref>{{Cite journal|last1=Finkel|first1=R. A.|last2=Bentley|first2=J. L.|year=1974|title=Quad Trees A Data Structure for Retrieval on Composite Keys|journal=Acta Informatica|publisher=Springer-Verlag|volume=4|pages=1–9|doi=10.1007/bf00288933|s2cid=33019699}}</ref> is an adaptation of a [[binary tree]] used to represent two-dimensional point data. 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 [[Big O notation|O(log n)]] time. Point quadtrees are worth mentioning for completeness, but they have been surpassed by [[k-d tree|''k''-d trees]] as tools for generalized binary search.<ref name=Aluru2004>{{Cite book|title=Handbook of Data Structures and Applications|last=Aluru|first=S.|publisher=Chapman and Hall/CRC|year=2004|isbn=9781584884354|editor-last=D. Mehta and S. Sahni|pages=19-1 -- 19-26|chapter=Quadtrees and octrees}}</ref>

Point quadtrees are constructed as follows. Given the next point to insert, we find the cell in which it lies and add it to the tree. The new point is added such that the cell that contains it is divided into quadrants by the vertical and horizontal lines that run through the point. Consequently, cells are rectangular but not necessarily square. In these trees, each node contains one of the input points.

Since the division of the plane is decided by the order of point-insertion, the tree's height is sensitive to and dependent on insertion order. Inserting in a "bad" order can lead to a tree of height linear in the number of input points (at which point it becomes a linked-list). If the point-set is static, pre-processing can be done to create a tree of balanced height.

====Node structure for a point quadtree====
A node of a point quadtree is similar to a node of a [[binary tree]], with the major difference being that it has four pointers (one for each quadrant) instead of two ("left" and "right") as in an ordinary binary tree. Also a key is usually decomposed into two parts, referring to x and y coordinates. Therefore, a node contains the following information:
* four pointers: quad[‘NW’], quad[‘NE’], quad[‘SW’], and quad[‘SE’]
* point; which in turn contains:
** key; usually expressed as x, y coordinates
** value; for example a name

===Point-region (PR) quadtree===
Point-region (PR) quadtrees<ref>{{Cite journal|last=Orenstein|first=J. A.|year=1982|title=Multidimensional tries used for associative searching|journal=Information Processing Letters|publisher=Elsevier|volume=14 | issue = 4 |pages=150–157|doi=10.1016/0020-0190(82)90027-8}}</ref><ref>{{Cite journal|last=Samet|first=H.|year=1984|title=The quadtree and related hierarchical data structures|url=http://www.cs.umd.edu/~hjs/pubs/SameCSUR84-ocr.pdf|journal=ACM Computing Surveys |publisher=ACM|volume=16 | issue = 2 |pages=187–260|doi=10.1145/356924.356930|s2cid=10319214}}</ref> are very similar to region quadtrees. The difference is the type of information stored about the cells. In a region quadtree, a uniform value is stored that applies to the entire area of the cell of a leaf. The cells of a PR quadtree, however, store a list of points that exist within the cell of a leaf. As mentioned previously, for trees following this decomposition strategy the height depends on the spatial distribution of the points. Like the point quadtree, the PR quadtree may also have a linear height when given a "bad" set.

===Edge quadtree===
Edge quadtrees<ref>{{Cite journal|last=Warnock|first=J. E.|year=1969|title=A hidden surface algorithm for computer generated halftone pictures|journal=Computer Science Department, University of Utah|volume=TR 4-15}}</ref><ref>{{Cite journal|last=Schneier|first=M.|year=1981|title=Two hierarchical linear feature representations: edge pyramids and edge quadtrees|journal=Computer Graphics and Image Processing|publisher=Elsevier|volume=17 | issue = 3 |pages=211–224|doi=10.1016/0146-664X(81)90002-2}}</ref> (much like PM quadtrees) are used to store lines rather than points. Curves are approximated by subdividing cells to a very fine resolution, specifically until there is a single line segment per cell. Near corners/vertices, edge quadtrees will continue dividing until they reach their maximum level of decomposition. This can result in extremely unbalanced trees which may defeat the purpose of indexing.

===Polygonal map (PM) quadtree===
The polygonal map quadtree (or PM Quadtree) is a variation of quadtree which is used to store collections of polygons that may be degenerate (meaning that they have isolated vertices or edges).<ref>[[Hanan Samet]] and Robert Webber. "Storing a Collection of Polygons Using
Quadtrees". ''ACM Transactions on Graphics'' July 1985: 182-222. ''InfoLAB''. Web. 23 March 2012</ref>
<ref>{{Cite journal|last1=Nelson|first1=R. C.|last2=Samet|first2=H.|year=1986|title=A consistent hierarchical representation for vector data|journal=ACM SIGGRAPH Computer Graphics|volume=20 | issue = 4 |pages=197–206|doi=10.1145/15886.15908|doi-access=free}}</ref> A big difference between PM quadtrees and edge quadtrees is that the cell under consideration is not subdivided if the segments meet at a vertex in the cell.

There are three main classes of PM Quadtrees, which vary depending on what information they store within each black node. PM3 quadtrees can store any amount of non-intersecting edges and at most one point. PM2 quadtrees are the same as PM3 quadtrees except that all edges must share the same end point. Finally PM1 quadtrees are similar to PM2, but black nodes can contain a point and its edges or just a set of edges that share a point, but you cannot have a point and a set of edges that do not contain the point.

===Compressed quadtrees===
This section summarizes a subsection from a book by [[Sariel Har-Peled]].<ref>{{Cite book|title=Geometric approximation algorithms|last=Har-Peled|first=S.|author-link=Sariel Har-Peled|publisher=Mathematical Surveys and Monographs Vol. 173, American mathematical society|year=2011|chapter=Quadtrees - Hierarchical Grids}}</ref>

If we were to store every node corresponding to a subdivided cell, we may end up storing a lot of empty nodes. We can cut down on the size of such sparse trees by only storing subtrees whose leaves have interesting data (i.e. "important subtrees"). We can actually cut down on the size even further. 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). It turns out that we only need to store the node <math>u</math> 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 <math>u</math>. It is still possible for these compressed trees to have a linear height when given "bad" input points.

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 curve|''Z''-order curves]]. The ''Z''-order curve maps each cell of the full quadtree (and hence even the compressed quadtree) in <math>O(1)</math> time to a one-dimensional line (and maps it back in <math>O(1)</math> time too), creating a total order on the elements. Therefore, we can store the quadtree in a data structure for ordered sets (in which we store the nodes of the tree). 

We must state a reasonable assumption before we continue: we assume that given two real numbers <math>\alpha, \beta \in [0, 1)</math> expressed as binary, we can compute in <math>O(1)</math> time the index of the first bit in which they differ. We also assume that we can  compute in <math>O(1)</math> 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 <math>O(1)</math> time. 

With  these assumptions, point location of a given point <math>q</math> (i.e. determining the cell that would contain <math>q</math>), insertion, and deletion operations can all be performed in <math>O(\log{n})</math> time (i.e. the  time it takes to do a search in the underlying ordered set data structure).

To perform a point location for <math>q</math> (i.e. find its cell in the compressed tree):
# Find the existing cell in the compressed tree that comes before <math>q</math> in the ''Z''-order. Call this cell <math>v</math>.
# If <math>q \in v</math>, return <math>v</math>.
# Else, find what would have been the lowest common ancestor of the point <math>q</math> and the cell <math>v</math> in an uncompressed quadtree. Call this ancestor cell <math>u</math>.
# Find the existing cell in the compressed tree that comes before <math>u</math> in the ''Z''-order and return it.
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. Care must be taken to reshape the tree as appropriate, creating and removing nodes as needed.

==Some common uses of quadtrees==
[[Image:Quad tree bitmap.svg|thumb|upright=1.7|A bitmap and its compressed quadtree representation]]
* Image representation
* [[#Image processing using quadtrees|Image processing]]
* [[#Mesh generation using quadtrees|Mesh generation]]<ref>{{cite journal |first1=Damian |last1=Wanta |first2=Waldemar T. |last2=Smolik |first3=Jacek |last3=Kryszyn |first4=Przemysław |last4=Wróblewski |first5=Mateusz |last5=Midura |title=A Finite Volume Method using a Quadtree Non-Uniform Structured Mesh for Modeling in Electrical Capacitance Tomography |journal=Proceedings of the National Academy of Sciences, India Section A |year=2021 |volume=92 |issue=3 |pages=443–452 |doi=10.1007/s40010-021-00748-7 |s2cid=244224810 |doi-access=free }}</ref>
* [[Spatial index]]ing, 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]]<ref>{{Cite book
| title = Spreadsheet Implementation Technology: Basics and Extensions
| last = Sestoft
| first = Peter
| publisher = The MIT Press
| year = 2014
| isbn = 9780262526647
| pages = 60–63
}}</ref> or for some matrix calculations{{citation needed|date=June 2015}}
* Solution of multidimensional [[Field (physics)|fields]] ([[computational fluid dynamics]], [[electromagnetism]])
* [[Conway's Game of Life]] simulation program.<ref>{{cite web|url=http://www.ddj.com/hpc-high-performance-computing/184406478 |title=An Algorithm for Compressing Space and Time |author=Tomas G. Rokicki |date=2006-04-01 |access-date=2009-05-20}}</ref>
* [[State estimation]]<ref>Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, ''Density Trees for Efficient Nonlinear State Estimation'', Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.</ref>
* Quadtrees are also used in the area of fractal image analysis
* [[Maximum disjoint set#Fat objects with arbitrary sizes: PTAS|Maximum disjoint sets]]

==Image processing using quadtrees==
Quadtrees, particularly the [[#Region_quadtree|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.<ref name="Aluru2004" /><ref name=":0" />

===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.<ref name="Aluru2004" /><ref>{{Cite book|title=Efficient Computation and Data Structures for Graphics|last=Hunter|first=G. M.|publisher=Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University|year=1978}}</ref><ref>{{Cite journal|last1=Hunter|first1=G. M.|last2=Steiglitz|first2=K.|year=1979|title=Operations on images using quad trees|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=2|issue=2|pages=145–153|doi=10.1109/tpami.1979.4766900|pmid=21868843|s2cid=2544535}}</ref><ref>{{Cite journal|last=Schneier|first=M.|year=1981|title=Calculations of geometric properties using quadtrees|journal=Computer Graphics and Image Processing|volume=16 | issue = 3 |pages=296–302|doi=10.1016/0146-664X(81)90042-3}}</ref>
<ref>{{Cite book|title=Handbook of Data Structures and Applications|last=Mehta|first=Dinesh|publisher=Chapman and Hall/CRC Press|year=2007|pages=397}}</ref>
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 (<math>T_1</math> and <math>T_2</math>) while building the output quadtree <math>T</math>. Informally, the algorithm is as follows. Consider the nodes <math>v_1 \in T_1</math> and  <math>v_2 \in T_2</math> corresponding to the same region in the images.
* If <math>v_1</math> or <math>v_2</math> is black, the corresponding node is created in <math>T</math> 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 <math>v_1</math> (respectively, <math>v_2</math>) is white, <math>v_2</math> (respectively, <math>v_1</math>) and the subtree underneath it (if any) is copied to <math>T</math> .
* If both <math>v_1</math> and <math>v_2</math> are gray, then the corresponding children of <math>v_1</math> and <math>v_2</math> 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  <math>2^{k} \times 2^{k}</math> 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 <math>k</math>. 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.<ref name="Aluru2004" />

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, [[Hanan Samet|Samet]]<ref>{{Cite journal|last=Samet|first=H.|year=1981|title=Connected component labeling using quadtrees|journal=Journal of the ACM|volume=28 | issue = 3 |pages=487–501|doi=10.1145/322261.322267|author-link=Hanan Samet|citeseerx=10.1.1.77.2573|s2cid=17485118}}</ref>  showed how we can find and label these connected components in time proportional to the size of the  quadtree.<ref name="Aluru2004" /><ref name=":1" /> 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 curve|''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 [[Tree traversal#Post-order|post-order traversal]] of the quadtree. For each black leaf <math>v</math> 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 <math>v</math>). 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 <math>u</math>. If <math>u</math> represents black pixels:
* If only one of <math>u</math> or <math>v</math> 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 <math>u</math> and <math>v</math> have different labels, record this label equivalence and move on
Step two can be accomplished using the [[disjoint-set data structure|union-find data structure]].<ref>{{Cite journal|last=Tarjan|first=R. E.|year=1975|title=Efficiency of a good but not linear set union algorithm|url=http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/p215-tarjan.pdf|journal=Journal of the ACM|volume=22 | issue = 2 |pages=215–225|doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free}}</ref> 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 <math>v</math> we use the union-find's ''find'' operation (with the old label of <math>v</math>) to find and assign <math>v</math> its new label (associated  with the connected component of which <math>v</math> is part).

==Mesh generation using quadtrees==
This section summarizes a chapter from a book by Har-Peled and de Berg et al.<ref name=":2">{{Cite book|title=Geometric approximation algorithms|last=Har-Peled|first=S.|publisher=Mathematical Surveys and Monographs Vol. 173, American mathematical society|year=2011|chapter=Good Triangulations and Meshing}}</ref><ref>{{Cite book|title=Computational Geometry Algorithms and Applications|last1=de Berg|first1=M.|last2=Cheong|first2=O.|last3=van Kreveld|first3=M.|last4=Overmars|first4=M. H.|publisher=Springer-Verlag|year=2008|edition=3rd|chapter=Quadtrees Non-Uniform Mesh Generation}}</ref>

[[Mesh generation]] is essentially the [[point-set triangulation|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.
[[File:Fig-mesh-gen-balanced-leaves.svg|thumb|A balanced leaf has at most one corner in a side.]]
Consider a leaf of the quadtree and its corresponding cell <math>v</math>. We say <math>v</math> 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 <math>v</math> differ by at most one from the level of <math>v</math>. When this is true for all leaves, we say the whole quadtree is balanced (for mesh generation).

Consider the cell <math>v</math> and the <math>5\times 5</math> neighbourhood of same-sized cells centred at <math>v</math>. We call this neighbourhood the ''extended cluster''. We say the quadtree is ''well-balanced'' if it is balanced, and for every leaf <math>u</math> 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 <math>v</math> 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 <math>u</math> of <math>v</math> we ensure the nodes of <math>u</math>'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<ref name=":2" /> 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. 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.
<syntaxhighlight lang="c++">
 // Simple coordinate object to represent points and vectors
 struct XY
 {
     float x;
     float y;
 
     function __construct(float _x, float _y) {...}
 }
 
 // Axis-aligned bounding box with half dimension and center
 struct AABB
 {
     XY center;
     float halfDimension;
 
     function __construct(XY _center, float _halfDimension) {...}
     function containsPoint(XY point) {...}
     function intersectsAABB(AABB other) {...}
 }
</syntaxhighlight>

===QuadTree class===
This class represents both one quad tree and the node where it is rooted.
<syntaxhighlight lang="c++">
 class QuadTree
 {
     // Arbitrary constant to indicate how many elements can be stored in this quad tree node
     constant int QT_NODE_CAPACITY = 4;
 
     // Axis-aligned bounding box stored as a center with half-dimensions
     // to represent the boundaries of this quad tree
     AABB boundary;
 
     // Points in this quad tree node
     Array of XY [size = QT_NODE_CAPACITY] points;
 
     // Children
     QuadTree* northWest;
     QuadTree* northEast;
     QuadTree* southWest;
     QuadTree* southEast;
 
     // Methods
     function __construct(AABB _boundary) {...}
     function insert(XY p) {...}
     function subdivide() {...} // create four children that fully divide this quad into four quads of equal area
     function queryRange(AABB range) {...}
 }
</syntaxhighlight>
===Insertion===
The following method inserts a point into the appropriate quad of a quadtree, splitting if necessary.

<syntaxhighlight lang="c++">
 class QuadTree
 {
     ...
   
     // Insert a point into the QuadTree
     function insert(XY p)
     {
         // Ignore objects that do not belong in this quad tree
         if (!boundary.containsPoint(p))
             return false; // object cannot be added
     
         // If there is space in this quad tree and if doesn't have subdivisions, add the object here
         if (points.size < QT_NODE_CAPACITY && northWest == null)
         {
             points.append(p);
             return true;
         }
     
         // Otherwise, subdivide and then add the point to whichever node will accept it
         if (northWest == null)
             subdivide();
         // We have to add the points/data contained in this quad array to the new quads if we only want
         // the last node to hold the data
     
         if (northWest->insert(p)) return true;
         if (northEast->insert(p)) return true;
         if (southWest->insert(p)) return true;
         if (southEast->insert(p)) return true;
     
         // Otherwise, the point cannot be inserted for some unknown reason (this should never happen)
         return false;
     }
 }
</syntaxhighlight>

===Query range===
The following method finds all points contained within a range.
<syntaxhighlight lang="c++">
 class QuadTree
 {
     ...
   
     // Find all points that appear within a range
     function queryRange(AABB range)
     {
         // Prepare an array of results
         Array of XY pointsInRange;
     
         // Automatically abort if the range does not intersect this quad
         if (!boundary.intersectsAABB(range))
             return pointsInRange; // empty list
     
         // Check objects at this quad level
         for (int p = 0; p < points.size; p++)
         {
             if (range.containsPoint(points[p]))
                 pointsInRange.append(points[p]);
         }
     
         // Terminate here, if there are no children
         if (northWest == null)
             return pointsInRange;
     
         // Otherwise, add the points from the children
         pointsInRange.appendArray(northWest->queryRange(range));
         pointsInRange.appendArray(northEast->queryRange(range));
         pointsInRange.appendArray(southWest->queryRange(range));
         pointsInRange.appendArray(southEast->queryRange(range));
     
         return pointsInRange;
     }
 }
</syntaxhighlight>

==See also==
* [[Adaptive mesh refinement]]
* [[Binary space partitioning]]
* [[Binary tiling]]
* [[k-d tree|''k''-d tree]]
* [[Octree]]
* [[R-tree]]
* [[UB-tree]]
* [[Spatial database]]
* [[Subpaving]]
* [[Z-order curve]]

==References==
Surveys by Aluru<ref name=Aluru2004 /> and Samet<ref name=":1">{{Cite book|title=Theoretical Foundations of Computer Graphics and CAD|last=Samet|first=H.|publisher=Springer-Verlag|year=1988|editor-last=Earnshaw|editor-first=R. A.|pages=51–68|chapter=An overview of quadtrees, octrees, and related hierarchical data structures}}</ref><ref name=":0">{{Cite journal|last=Samet|first=H.|year=1989|title=Hierarchical spatial data structures|journal=Symposium on Large Spatial Databases|pages=191–212}}</ref> give a nice overview of quadtrees.

===Notes===
{{Reflist}}

===General references===
# {{cite journal | author=[[Raphael Finkel]] and [[J.L. Bentley]] | title= Quad Trees: A Data Structure for Retrieval on Composite Keys | journal=Acta Informatica | year=1974 | volume=4 | issue=1 | pages= 1–9 | doi= 10.1007/BF00288933| s2cid= 33019699 }}
# {{cite book | author = [[Mark de Berg]], [[Marc van Kreveld]], [[Mark Overmars]], and [[Otfried Schwarzkopf]] | year = 2000 | title = Computational Geometry | publisher = [[Springer-Verlag]] | edition = 2nd revised | isbn = 3-540-65620-0 | url-access = registration | url = https://archive.org/details/computationalgeo00berg }} Chapter 14: Quadtrees: pp.&nbsp;291–306.
# {{cite web |author-link=Hanan Samet|url= http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf|title= Storing a Collection of Polygons Using Quadtrees|last1 = Samet|first1 = Hanan| last2 = Webber| first2 = Robert |date= July 1985|access-date=23 March 2012}}

{{CS-Trees}}

[[Category:Trees (data structures)]]
[[Category:Database index techniques]]
[[Category:Geometric data structures]]
[[Category:Rectangular subdivisions]]