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