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

Blog comments powered by Disqus

About