Quadtree

A quadtree (Latin quadri, four - ' and English. Tree, tree ') is in the computer science a special tree structure in which each internal node has exactly four children.

Description

This structure is used mainly for the organization of two-dimensional data in the field of computer graphics. The root of the tree in this case represents a square area. This is recursively decomposed into four equal-sized quadrants until the desired resolution is reached and the recursion ends in a leaf. By recursive application of this division represented the area from the root node can be resolved arbitrarily fine. For three-dimensional data is commonly used octree.

Since a sheet can cover a relatively large area may, to search the data structure is memory efficient and relatively quick after a sheet that includes a certain point.

General Applications of quadtree are:

• Image representation
• Area index (for example, in GIS software )
• Efficient Collision Detection ( Collision Detection) in two dimensions
• HiddenSurfaceRemoval of terrain data.
• In the grid generation quadtrees for the generation of the 2D triangulation can be used.