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