○ Figure 19.3: Quadtree representation 19.3 Space subdivision 19.3. 1 Motivation and definitions Some of the motivations behind space subdivision methods include Exhaustive enumeration is memory intensive and typically has low accuracy Smaller memory requirements are possible, if adaptive subdivision is used Octree/quadtree representations lead to a recursive subdivision into 8 octants(or 4 qua rants)that can be represented as an 8-ary tree (or 4-ary tree) for which efficient algo- rithms are also known In an octree representation a solid region is represented by hierarchically decomposing a usually cubic volume of space into successively smaller cubes( 8 of them). Hierarchical division and cube orientation usually follows the spatial coordinate system. An example of quadtree, the two dimensional analogue, is shown Figure 19.3 This is a trivial example. The method can continue to many more levels for a much more complex model. Some tolerance for the minimum size block is required. In addition, this very concise representation would become very large if the coordinate system was changed; for example, rotated 45 degrees This method leads to a quick way to compute the area and other integral properties of a region. It is often used in data analysis in fields such as medical applications and sonar ging1 2 3 4 empty 1 2 3 4 full partially full Figure 19.3: Quadtree representation. 19.3 Space subdivision 19.3.1 Motivation and definitions Some of the motivations behind space subdivision methods include: • Exhaustive enumeration is memory intensive and typically has low accuracy. • Smaller memory requirements are possible, if adaptive subdivision is used; • Octree/quadtree representations lead to a recursive subdivision into 8 octants (or 4 quad￾rants) that can be represented as an 8-ary tree (or 4-ary tree) for which efficient algo￾rithms are also known. In an octree representation a solid region is represented by hierarchically decomposing a usually cubic volume of space into successively smaller cubes (8 of them). Hierarchical division and cube orientation usually follows the spatial coordinate system. An example of quadtree, the two dimensional analogue, is shown Figure 19.3. This is a trivial example. The method can continue to many more levels for a much more complex model. Some tolerance for the minimum size block is required. In addition, this very concise representation would become very large if the coordinate system was changed; for example, rotated 45 degrees. This method leads to a quick way to compute the area and other integral properties of a region. It is often used in data analysis in fields such as medical applications and sonar imaging. 6