Computer Aided Engineering Design

292 COMPUTER AIDED ENGINEERING DESIGN

(i) A∪B: collect all edges from list 1 and 2 that are marked out. If there are edges marked
on, select one edge of the pair (since on segment will be in duplicate, one in list 1 and the
other in list 2) if they have the same direction (Figure 9.19 c).
(ii) A∩B: collect all edges from list 1 and 2 that are marked in. If there are edges marked
on, select one edge of the pair if they have the same direction (Figure 9.19 d).
(iii) A –*B: first, change the direction of all the edges in list 2 (since B is representing a hole
in this operation). This is illustrated in Figure 9.19(e). Collect edges, from list 1 that are
markedout, and from list 2 that are marked in. If there are edges marked on, select one
edge of the pair if they have the same direction (Figure 9.19 f).
(d) Chain all the collected edges to form a valid edge loop running counterclockwise to represent
a regular set.
The problem of accurate and robust implementation of geometric algorithms is still of considerable
research attention. Much difficulty arises from the fact that reasoning about geometry most naturally
occurs in the domain of real numbers, which can only be represented approximately on a digital
computer. Many times, the correctness of geometric algorithms depends on correctly evaluating the
signs of arithmetic expressions, and errors due to rounding or imprecise input can lead to incorrect
results or failure to run to completion. Another problem is that of dealing with degeneracies such as
the intersection of a line with a polygon only at one vertex, or along an edge. Degeneracies can be
a source of non-robustness on one hand, or of serious implementation difficulties on the other. For
simplicity, algorithms often assume that primitives are arranged so that there are no degeneracies (i.e.
they are placed in a general setting). In practice, however, primitives often are not in general position,
causing implementations to fail. Recasting an algorithm to handle degeneracies tends to result in a
situation in which much of the code is designed to handle special cases. In devising an algorithm for
solving a geometric problem, one thus has to keep in mind both robustness as well and the feasibility
of implementation.

9.8 Inter Section Between Free Form Curves

Letb(t) and c(s) be the two free form curves defined by

bbc( ) = ( ) and ( ) = ( ) c

=0 =0

tt s s

i

m

ii j

n

ΣΣφψjj

wherebi and cj are the control points and φi(t) and ψj(s) are the barycentric weights, for instance the
Bernstein polynomials or the Basis splines. The distance or residual g(s,t) between the two curves
can be computed as

g(s,t) = [b(t) – c(s)][b(t) –c(s)]T

The necessary conditions for the minimum of g(s,t) are ∂
∂

∂

∂

gs t

t

gs t

s

(, )

=

(, ) = 0 incorporating which

yields

gst t s

s

s

T

1 ( , ) [ ( ) – ( )]

()

≡ = 0

∂

∂

⎡

⎣⎢

⎤

⎦⎥

bc

c

gst t s

t

t

T

2 ( , ) [ ( ) – ( )]

()

≡ = 0

∂

∂

⎡

⎣⎢

⎤

⎦⎥

bc

b