Quadtree

From Free net encyclopedia

The 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. The quadtree data structure was created by Raphael Finkel and J.L. Bentley.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

Quadtrees can be divided into three different types:

Contents 1 The Region Quadtree 2 Point Quadtree 2.1 Node Structure for a Point Quadtree : 3 Edge Quadtree 4 Some common uses of quadtrees are: 5 See also 6 External links

The Region Quadtree

The point region quadtree is a type of quadtree where each node must have exactly four children, or leaf, having no children. The Region quadtree represents a collection of data points in two dimensions by decomposing the region containing the data points into four equal quadrants, subquadrants, and so on until no leaf node contains more than a single point.The Region Quadtree is not strictly a 'tree'. As the positions of subdivisions are independent of the data points they are 'Tries'.

Point Quadtree

Shares the features of all quadtrees but is a true tree as the centre of a subdivision is always on a point.

Node Structure for a Point Quadtree :

• 4 Pointers: quad [‘NW’], quad [‘NE’], quad[‘SW’], and quad[‘SE’]
• point, of type DataPoint, which in turn contains:
  • Name
  • (x,y) Coordinates

Edge Quadtree

Edge Quadtrees are specifically used to store lines rather than points. Curves are approximated by subdividing cells to a very fine resolution. This can result in extremely unbalanced trees which may defeat the object of indexing.

Some common uses of quadtrees are:

• 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

Quadtrees are the two-dimensional analog of octrees.

See also

• R-tree

External links

• Spatial Index Demos
• A discussion of the Quadtree and an application
• Considerable discussion and demonstrations of Spatial Indexing

Template:Comp-sci-stub Template:Compu-graphics-stubit:Quadtree de:Quadtree pl:Drzewo czwórkowe