Quadtree Algorithm

A quadtree is a tree data structure in which every internal node has exactly four children, used to recursively partition two-dimensional space into four quadrants or regions. Raphael Finkel and Jon Louis Bentley coined the name and formally described the structure in 1974, building on similar subdivision ideas that had appeared earlier in other contexts. A quadtree recursively subdivides a region into four smaller regions whenever the data within it exceeds some capacity, so that its directory structure directly mirrors the spatial decomposition of the area it represents; this makes quadtrees useful for image representation, spatial indexing, point location and range queries, collision detection, terrain culling in games, sparse data storage and other applications where data density varies sharply across a two-dimensional area.