Oct 8, 2012

## Quadtree

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions.

## Some common uses of quadtrees

- 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 or for some matrix calculations
- Solution of multidimensional fields (computational fluid dynamics, electromagnetism)
- Conway’s Game of Life simulation program.
- State estimation Quadtrees are also used in the area of fractal image analysis

**About**

Blog comments powered by Disqus