Computer Aided Engineering Design

COMPUTATIONS FOR GEOMETRIC DESIGN 289

intersection between the square and the boundary (use line intersection recursively for all the
edges in the polygon with the edges in square), then it is a leaf node, else it may be either of
the following three cases:
(i) It is leaf node if it still envelopes the object
(ii) It is completely inside the object
(iii) It is completely outside the object
At this stage, the status of a child square is assigned. For the semi-circular lamina, checking the
queue part for the first square not yet classified, square 0 is taken for classification. It lies
outside the circular lamina and thus classified as out. Similarly, 1 , 2 and 3 are classified as leaf,
leaf and out respectively. Update the tree part (Figure 9.16a) to complete the quadtree generation
till level 1.
(d) The above two steps are performed recursively till the required depth of the tree is obtained. For
example, the first leaf square not yet decomposed is 1 and the same is decomposed into squares
10 , 11 , 12 and 13. Similarly, square 2 is decomposed and the queue becomes root square ⇔
0 ⇔ 1 ⇔ 2 ⇔ 3 ⇔ 10 ⇔ 11 ⇔ 12 ⇔ 13 ⇔ 20 ⇔ 21 ⇔ 22 ⇔ 23 ⇔ NULL. Classify the newly
generated queue entries with respect to the object (in this case the semi-circular lamina) and
update the tree. Figure 9.16(b) shows the tree for only the first leaf quadrant till level 2. At level
3 (Figure 9.15d), the queue part becomes root square ⇔ 0 ⇔ 1 ⇔ 2 ⇔ 3 ⇔ 10 ⇔ 11 ⇔ 12
⇔ 13 ⇔ 20 ⇔ 21 ⇔ 22 ⇔ 23 ⇔ 100 ⇔ 101 ⇔ 102 ⇔ 103 ⇔ 110 ⇔ 111 ⇔ 112 ⇔ 113 ⇔
120 ⇔ 121 ⇔ 122 ⇔ 123 ⇔NULL. The tree part is shown in Figure 9.16(c) (again only for
the first leaf quadrant in each level).
It is not necessary to use the square cells for quadtree decomposition. Triangular cells can also
be employed for the same and an example is shown in Figure 9.17(a) where the root is the
equilateral triangle sub-divided into four children triangles (Figure 9.17b) after every decomposition
level.

Level : 0

Level : 2

(a)

(c)

(b)

(d)

0

(^32)
10 11
13 12
Level : 1
Level : 3
01
32
0
32
13 12
(^10010111)
103 102
Figure 9.15 Quadtree decomposition of a semi-circular disc