A QuadTree is a spatial partitioning strategy used to make
queries on relationships between 2D spatial data such as
coordinates in a Geographic Information System (GIS), or the
location of objects in a video game. For instance, you may need
to know all of the objects within a region on a map, test
whether objects are visible by a camera, or optimize a collision
detection algorithm. The QuadTree is so named because it
recursively partitions regions into four parts, with leaf nodes
containing references to the spatial objects. Querying the
QuadTree is a function of traversing the tree nodes that
intersect the query area. The OctTree is the analogous structure
used for 3 dimensional problems. For a masterful collection of
demos and variations on the QuadTree and other spatial indexing
methods, see Frantisek Brabec and Hanan Samet's site, or use the
references at the end of this article. There are many spatial
partitioning methods, each with the goal of providing an
efficient way of determining the position of an