Editing Quadtree (section)

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