Quadtree
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
- Image display
- Area indexing (for example in GIS programs)
- Efficient collision detection in two dimensions
- Determination of the visual volume for terrain data
- Store sparse data such as formatting information for a table or for some matrix calculations
- Solution of multi-dimensional fields ( numerical fluid mechanics , electromagnetism)
- Conway's game of life
- State reconstruction
- Quaternary trees are also used in the field of fractal image analysis
- Largest disjointed sets
Quaternary trees are the two-dimensional equivalent of octagonal trees .
Individual evidence
- ^ Tomas G. Rokicki: An Algorithm for Compressing Space and Time . April 1, 2006. Retrieved May 20, 2009.
- ^ 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
- Space-division demos (English)
- Discussion of the quaternary tree with an application
- Discussion and demonstrations of spatial indexing ( Memento of February 4, 2012 in the Internet Archive )
Implementations
- Java implementation
- Java instructions
- C ++ implementation of a quaternary tree for the spatial indexing of triangles
- Objective-C implementation of a quaternary tree for GPS clustering
- SquareLanguage
- Functional demonstration of the quaternary tree algorithm in JavaScript
- MIT-licensed quaternary tree library in JavaScript