Computer Aided Engineering Design

290 COMPUTER AIDED ENGINEERING DESIGN

9.7 Boolean Operations on Polygons

Boolean operations are set theoretical operations performed on basic shapes to evolve more complex
definitions. Some basic Boolean operations are union, intersection and negation denoted by ∪,∩
and –, respectively as discussed in Chapter 8. All sets in the Euclidean space E^3 are not suitable for
geometrical representation and set theoretical operations. A subset of E^3 that is bounded, closed,
regular and semi analytic are only suitable for geometrical representation. They are called regularized
sets or r-sets. Under the conventional Boolean operations, r-sets are not algebraically closed, but they
are closed under the regularized set union, intersection and difference denoted by ∪,∩ and –* as
explained in Chapter 8.
An algorithm for determining the regularized Boolean for polygons is given below. Consider two
given polygons A and B (Figure 9.18) constituting of vertices and connecting edges such that the
boundaries are traversed in the counterclockwise fashion.

Level 0

Level 0

Level 1

Level 1

Level 2

0 1 23

0 1 2 3

(a) Level 1 (b) Level 2

Level 0

Level 1

10 11 12 13

0 1 2 3

10 11 12 13

Level 3

(c) Level 3

100 101 102 103

Level 2

Figure 9.16 The quadtree structure for semi-circular lamina in Figure 9.15

Figure 9.17 (a) Quadtree decomposition with equilateral triangles and (b) scheme of decomposition

1

0

3

2

(a) (b)