quadtree
Sign in to savethumb|300px|A point-region quadtree with point data. Bucket capacity 1. thumb|300x300px|Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a
Key facts
- Data structure.name
- Quadtree
- Data structure.type
- Tree
- Data structure.invented_by
- Raphael Finkel and J.L. Bentley
- Data structure.invented_year
- 1974
via Wikipedia infobox
Wikidata facts
- Image
- Point quadtree.svg
Show 1 more fact
- Commons category
- Quadtrees
Sources (2)
via Wikidata · CC0
~23 min read
Article
22 sectionsContents
- Types
- Region quadtree
- Point quadtree
- Node structure for a point quadtree
- Point-region (PR) quadtree
- Edge quadtree
- Polygonal map (PM) quadtree
- Compressed quadtrees
- Some common uses of quadtrees
- Image processing using quadtrees
- Image union / intersection
- Connected component labelling
- Mesh generation using quadtrees
- Pseudocode
- Prerequisites
- QuadTree class
- Insertion
- Query range
- See also
- References
- Notes
- General references
thumb|300px|A point-region quadtree with point data. Bucket capacity 1. thumb|300x300px|Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".
The subdivided regions may be square or rectangular, or may have arbitrary shapes. Although similar subdivisions were used much earlier (for instance in the Whitney covering lemma of 1934), 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.