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
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
- Instance of
- data structure
- Subclass of
- spatial index
- Image
- Point quadtree.svg
Show 2 more facts
- Commons category
- Quadtrees
- maintained by WikiProject
- WikiProject Mathematics
Sources (2)
via Wikidata · CC0
Article · 日本語
四分木（しぶんぎ、英: Quadtree）は、各内部ノードが4個までの子ノードを持つ木構造のデータ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。 * 空間を適応可能セルに分割する。 * 各セル（またはバケット）は容量の上限がある。容量が最大に達すると、バケットは分割される。 * 木構造ディレクトリは四分木の空間分割に従う。
Abstract from DBpedia / Wikipedia · CC BY-SA