Module quadtree

source code

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 or regions. The regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. A similar partitioning is also known as a Q-tree. All forms of Quadtrees share some common features:

• They decompose space into adaptable cells.
• Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits.
• The tree directory follows the spatial decomposition of the Quadtree.

(From Wikipedia, the free encyclopedia)