Page 212 - Basic Structured Grid Generation

Unstructured grid generation 201

D
F

Y X
N
q M B
A

E

C

Fig. 8.14 Voronoi-segment point insertion.

Fig. 8.15 Delaunay triangulation. Voronoi-segment algorithm.

XA. We look for a new vertex Y on the perpendicular bisector of AX (Fig. 8.14). We
can re-label p as p 0 , and in the new construction, where the mid-point of AX is N,
√
we put AN = p 1 . Clearly, p 1 = p 0 / 2.
Now if p 1 >f N ,where f N is the value of the target circumradius at N, then the
previous step is repeated, and Y will be chosen such that the angle AYX is a right-
angle. But if p 1 <f N , we expect that, given that q is large compared with p 0 ,the
circumradius R AYX = f N according to eqn (8.7), and, by eqn (8.6),

2
2
NY = d 1 = f N + (f N ) − (p 1 ) . (8.8)