Quadtree

Quadtree

A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The 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. 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

Types

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 data is processed. Some common types of quadtrees are:

The region quadtree

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. Each node in the tree either has exactly four children, or has no children (a leaf node). The region quadtree is not strictly a 'tree' - as the positions of subdivisions are independent of the data. They are more precisely called 'tries'.

A region quadtree with a depth of n may be used to represent an image consisting of 2^n * 2^n 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.

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.

If a region quadtree is used to represent a set of point data (such as the latitude and longitude of a set of cities), regions are subdivided until each leaf contains at most a single point.

Point quadtree

The point quadtree 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. The tree shape depends on the order data is processed. It is often very efficient in comparing two dimensional ordered data points, usually operating in O(log n) time.

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 following information:

* 4 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

Edge quadtree

Edge quadtrees are specifically used to store lines rather than points. Curves are approximated by subdividing cells to a very fine resolution. This can result in extremely unbalanced trees which may defeat the purpose of indexing.

ome common uses of quadtrees

* Image representation

* Spatial indexing
* Efficient collision detection in two dimensions
* 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)

Quadtrees are the two-dimensional analog of octrees.

Caveats

If geometric subdividing fails to reduce the item count for each quadrant, (e.g., for overlapping data,) QuadTree subpartitioning fails, and the capacity must be breached for the algorithm to continue. For example, if the maximum capacity for a quadrant is 8, and there are 9 points at (0, 0), subpartitioning would produce three empty quadrants, and one containing the original 9 points, and so on. Because the tree must allow more than 8 points in such a quadrant, QuadTrees can approach O(N) complexity for data sets with arbitrary geometry (e.g., maps or graphs).

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 | url= | doi= 10.1007/BF00288933
* Chapter 14: Quadtrees: pp.291–306.

See also

* Octree
* Binary space partitioning
* Kd-tree
* R-tree
* UB-tree
* Spatial index

External links

* [http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html A discussion of the Quadtree and an application]
* [http://homepages.ge.ucl.ac.uk/~mhaklay/java.htm Considerable discussion and demonstrations of Spatial Indexing]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Quadtree — Saltar a navegación, búsqueda El termino Quadtree es utilizado para describir clases de estructuras de datos jerárquicas cuya propiedad común es que están basados en el principio de descomposición recursiva del espacio. En un QuadTree de puntos,… …   Wikipedia Español

  • Quadtree — Quadtree: Die Farbe eines Quadranten in der grafischen Darstellung (links) entspricht der Farbe des zugehörigen Blatts im Baum (rechts) …   Deutsch Wikipedia

  • Quadtree — Un Quadtree Un quadtree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu à quatre fils. Les quadtrees sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant récursivement… …   Wikipédia en Français

  • quadtree — noun A treelike data structure each of whose nodes has up to four children, most often used to partition a two dimensional space by recursively subdividing it …   Wiktionary

  • QSDPCM — Quadtree Structured Differential Pulse Code Modulation …   Acronyms

  • QSDPCM — Quadtree Structured Differential Pulse Code Modulation …   Acronyms von A bis Z

  • Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере …   Википедия

  • Z-order curve — Not to be confused with Z curve or Z order. Four iterations of the Z order curve …   Wikipedia

  • Hashlife — is an algorithm for computing the long term fate of a given starting configuration in various Life rules. The algorithm was invented by Bill Gosper in the early 1980s while he was engaged in research at the Xerox Palo Alto research center.… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”