Computer Aided Engineering Design

288 COMPUTER AIDED ENGINEERING DESIGN

nodes at level 1 represent them. The shades represent whether a square is completely inside the object
(black), is completely outside (white) or is a leaf node that encompasses the boundary (gray). For
black or white cells, we are quite sure that all four children squares would lie within the geometry or
outside the geometry, respectively. Thus, only gray nodes are sub-divided further as the level increases
to facilitate robustness and minimum data storage. Since the parent cell encompasses the planar
object, the cell is neither completely inside nor completely outside the object, and therefore is a leaf

node.
Understanding the data structure storing the quadtree is equally essential. This data structure may
be grouped into two parts, the tree part and the queue part, as shown in Figure 9.14. The two parts
are uniquely connected with pointers for information in the tree part to be referred in the queue part
and vice versa.

The algorithm to generate a quadtree is illustrated using an example in Figure 9.15. Four levels of
decomposition for a semi circular disc are shown for the first quadrant at each level. The squares in
the first level are enumerated as 0 , 1 , 2 and 3 moving clockwise. The children of square 1 in the
second level are numbered 10 , 11 , 12 , and 13 moving clockwise.

(a) Generate the bounding square. Initialize the quadtree data structure by inserting the root square
into the queue part for decomposition, inserting the root square into tree part and classify as
‘leaf’ node and interconnect with the queue. For the example shown, the bounding square for
the 2D semi-circular lamina is shown in Figure 9.15 (a). The queue is root square ⇔NULL.
(b) Pull out the first ‘leaf’ square not yet decomposed from the queue part and divide it into four
children. Their nodes and position in the tree are calculated and pushed into the queue from the
end. Root square is divided into four children 0 , 1 , 2 and 3 (Figure 9.15 (b)). The queue part
consists of the following squares: root square ⇔ 0 ⇔ 1 ⇔ 2 ⇔ 3 ⇔NULL.
(c) Pull out a square not yet classified from the queue and check its status. If there exists an

Figure 9.14 Data structure used to store a quadtree structure

Tree part

Queue part

Quadrant

Quadrant

qptr

futher

level

flag

id

nodes

sonptrs

Quadrant

Quadrant

Queue up elptr down

Queue up elptr down