Computer Aided Engineering Design

COMPUTATIONS FOR GEOMETRIC DESIGN 287

or on the boundary. This is a one-time computation and once the cells have been classified, given a
test point, all one needs to determine is the cell that holds the point. The status of the test point is the
same as that of the cell that holds it. To improve the accuracy, we need to decrease the grid size. This,
however, makes the computations more involved. Quadrees and octrees (in two-dimensions and
three-dimensions respectively) are grid structures having cells of different sizes that become smaller
as the level of decomposition increases. This grid structure has cells of smaller size near the boundary
and large sized cells within the interior. The degree of accuracy at the boundary is proportional to the
level of decomposition in the quadtree. A quadtree structure for the circular disc is shown in Figure
9.12 (b). A procedure to generate the quadtree structure and using the same for point membership
classification of complex shapes is discussed further.

Depth

Level 0

Level 1

Level 2

Full Partial Empty

Figure 9.13 Schematic representation of a quadtree structure

(a) (b)

Figure 9.12 (a) A circular disc and its grid and (b) its quadtree decomposition

9.6.1 Quadtree Decomposition

Figure 9.13 shows the schematic of a quadtree structure generation. Each node represents a square.
The node (parent square) at ‘level 0’ represents the initial bounding square within which the planar
object is enclosed. The parent square is divided into four children squares, and four corresponding