Quadtree and Octree
- PDF / 148,346 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 102 Downloads / 176 Views
QGIS Quantum GIS
Qt Libray Quantum GIS
Q-Tree Quadtree and Octree
Quadtree Quadtree and Octree
Quadtree and Octree M ARCI S PERBER Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, USA Synonyms Quadtree; Q-tree; Octree; Data-structure, Spatial; PointQuadtree; MX-Quadtree; PR-Quadtree; PM-Quadtree Definition A quadtree is a spatial data structure which has four branches attached to the branch point or node. The records exist in the leaf nodes of the tree. An octree is the same concept except the branches are in groups of eight. An octree can represent and image by subdividing the cubical volume. The quadtree tree is greatly used for two-dimensional space and the octree is used for three-dimensional space.
Historical Background The name quadtree has developed through time. It was once called a Q-tree and then later termed quadtree. It was adapted from the binary search tree in order to be used for two dimensions. The name octree simply comes from the prefix “oct” and the word tree. These data structures were needed in order to save space. These structures were first built as pointers, but have now evolved to use leaf nodes encoded by a locational code. Scientific Fundamentals A quadtree is a class of spatial data structure methods used to put and/or locate files or records in a database. There is a base node which is split along d dimensions producing 2d children. Quadtrees are based on the rule of four, and therefore the order of the tree is four and there are four branches attached to the branch point or node. The terminal branches of the tree are referred to as leaf nodes since they are the end of the tree, and the records exist in those leaf nodes. A leaf node that does not contain a record is considered (to be) null. The data in the database is found by repeatedly dividing the number of files or records into four parts until there is only one left. An octree data structure consists of a cell with eight children where the cell is a cube in space. Octrees are the threedimensional version of quadtrees. The octree is used to index tree dimensions by subdividing a region of space into eight equal partitions called cells. Cells are divided using specific conditions like containing an object boundary or containing a specific number of objects. The octree data structure represents objects in threedimensional space. An octree is a spatial decomposition where the root of the tree is recursively divided by two in each coordinate direction until each cell holds at maximum a specified number of objects. The octree groups its objects hierarchically, which avoids the representation of empty portions of the space. The first node of an octree is called the root node or cell. The root node or cell points to eight elements or cells in which each element or cell can also point to eight children elements or cells, and so on.
932
Quadtree and Octree
Quadtree and Octree, Figure 1 Example of a quadtree representation of random points in a plane
Quadtree and Octree, Figure 3 Exam
Data Loading...
