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.
Some common uses of quadtrees are:
- 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
Quadtrees are the two-dimensional analog of octrees.
A point region (PR) quadtree is a type of quadtree where each node must have exactly four children, or leaf, having no children. The PR quadtree represents a collection of data points in two dimensions by decomposing the region containing the data points into four equal quadrants, subquadrants, and so on until no leaf node contains more than a single point.
See also: data structure R tree
External links
- Spatial Index Demos (http://www.cs.umd.edu/~brabec/quadtree/)