Quadtree

from Wikipedia, the free encyclopedia
A point quaternary tree with point data. Container capacity: 1.
Quaternary tree compression of an image, step by step

A quadtree (dt disuse. Quadtree ) is in the computer science a tree structure in which each internal node has exactly four child nodes. Quaternary trees are mainly used to subdivide a two-dimensional space by recursively dividing it into four areas (quadrants). The areas can be square, rectangular, or any shape. A similar division is known as a Q-tree . All forms of quadtrees share certain characteristics:

  • They break the room down into customizable areas
  • Each area has a maximum capacity. If this is reached, the area is subdivided.
  • The tree directory follows the spatial subdivision of the quaternary tree.

species

Quadtrees can be categorized according to the type of data they represent, including areas, points, and lines. Quadtrees can also be classified according to whether the shape of the tree depends on the data processing sequence or not. Some common types of quaternary trees are:

The area quaternary tree

The area quaternary tree represents a division of space into two dimensions, which divides the area into four equal quadrants, sub-quadrants, etc., with each end node containing data of a specific sub-area. Each node in the tree either has exactly four children or none at all (leaf nodes). The area quaternary tree is a type of trie .

A range quaternary tree with a depth of n can be used to represent an image of 2 n × 2 n pixels, each pixel having the value 1 or 0. The root node represents the entire image area. If not all pixels are zeros or ones in an area, it is subdivided. In this application, each end node stands for an image area whose image points are all zeros or ones.

An area quaternary tree can also be used as a variable resolution representation of a data field. For example, the temperatures in an area can be stored as a quaternary tree, with the average temperature of the sub-area being stored in each leaf.

When a range quaternary tree is used to represent a point record (e.g. latitude and longitude of a number of cities), ranges are subdivided until each leaf contains at most one point.

Dot quaternary tree

The point quaternary tree is an adaptation of a binary tree that is used to represent two-dimensional point data. It shares the characteristics of a quaternary tree, but is a real tree because the center of a subdivision is always a point. The shape of the tree depends on the order of data processing. With an execution time of usually O (log n), it is often very efficient when comparing two-dimensional, sorted data points.

Nodal structure of a point quad tree

A node of a quadtree is similar to a node of a binary tree, from which it mainly differs from the two pointers (left and right) of an ordinary binary tree by the four pointers (one per quadrant). In addition, a key is usually broken down into two components that relate to the x and y coordinates. Therefore, a node contains the following information:

  • four pointers: quad ['NW'], quad ['NO'], quad ['SW'] and quad ['SO']
  • Point, which in turn contains:
    • Attribute, usually expressed as x and y coordinates
    • Value, for example a name

Edge quaternary tree

Edge quaternary trees are particularly used to store lines instead of points. Curves are approximated by finely divided cells. This can result in very unbalanced trees, which can be against the purpose of indexing.

Some common uses of quaternary trees

Quaternary trees are the two-dimensional equivalent of octagonal trees .

Individual evidence

  1. ^ Tomas G. Rokicki: An Algorithm for Compressing Space and Time . April 1, 2006. Retrieved May 20, 2009.
  2. ^ 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.

literature

  • Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50255-0 .
  • Hanan Samet: Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50300-X .
  • RA Finkel, JL Bentley: Quad trees a data structure for retrieval on composite keys . In: Acta Informatica . tape 4 , no. 1 , ISSN  0001-5903 , p. 1-9 , doi : 10.1007 / BF00288933 .
  • Mark de Berg, Marc van Kreveld, Mark Overmars , Otfried Schwarzkopf (eds.): Computational Geometry. Algorithms and applications . 2nd, rev. Edition. Springer, Berlin et al. 2000, ISBN 3-540-65620-0 , 14: Quadtrees, p. 291-306 .
  • Hanan Samet, Robert Webber: Storing a Collection of Polygons Using Quadtrees. (PDF) July 1985, accessed March 23, 2012 .

Web links

Commons : Quadtrees  - collection of images, videos and audio files

Implementations