Page 213 - Basic Structured Grid Generation

202 Basic Structured Grid Generation

This means that since for the angle θ in Fig. 8.14

2

d 1 f N f N
tan θ = = + − 1,
p 1 p 1 p 1
provided that the value of f is essentially the same at M and N (and equal to f N ), so
√
that p 1 <f N < 2p 1 ,wehave
√
1 < tan θ< 2 + 1,
which implies that
◦
◦
45 <θ < 67.5 .
If AY is taken as the next active edge, we will have
2 2 2 2
AY = (2p 2 ) = (p 1 ) + (d 1 ) ,
and, using eqn (8.8), we obtain
1
2 2 2 2
(p 2 ) = (f N ) + f N (f N ) − (p 1 ) . (8.9)
2
√
Sinceweare assuming that p 1 <f N < 2p 1 , it follows that

1 p 2 1
√ < < 1 + √ .
2 p 1 2
If this procedure is repeated iteratively in the case where the value of f is assumed
to be effectively constant, the general step involves
1
2 2 2 2
(p n+1 ) = (f N ) + f N (f N ) − (p n ) (8.10)
2
and

2
2
d n = f N + (f N ) − (p n ) . (8.11)
The values of p n then converge to a value p satisfying, according to eqn (8.10),
 

2
 2
p 1 p
= 2 1 + 1 − . (8.12)
f N  f N 
It is straightforward to show that the solution of this equation is
√
3
p = f N , (8.13)
2
and, furthermore, the corresponding value of d, according to eqn (8.11), is
3
d = f N . (8.14)
2
These are characteristic measurements for an equilateral triangle of circumradius f N .
Thus this algorithm tends to produce approximately equilateral triangles of the target
circumradius after a few iterations.
Examples of triangulations in domains of various shapes using Voronoi point-
insertion are shown in Figs 8.15–8.18.