Civil Engineering Reference
In-Depth Information
If (n > 0) go to (2) else return;
End if
2
3
=
FI
n
=
; j = neighbour of triangle k opposite to node I2;
Fj
n
n = n + 1;
FI ;F
1
=
3
2
=
j = neighbour of triangle k opposite to node I1;
Fj
n
I;
2
3
=
n
n
Delete triangle k; go to (2);
Notations used
:
p
= point inserted; C
k
= circumcircle of triangle k; Δ(I1, I2, I3) = area of tri-
angle I1-I2-I3;
Vavertex of triangle ii
i
a
th
a
th
=
, a = 1,2,3; i = 1,N;
Taneighbour of triangle i
i
=
;
,
( )
= ii3
th
segment of the construction front;
F
i
3
= triangle connected to frontal segment i;
BB
i
12
FF
i
i
(
)
=
i
th
segment of the CORE boundary;
Btriangleconnected to boundary segmenti
12
,
3
=
.
i
i
Remarks:
Apart from the verification of the Delaunay property of the triangle associated
with the frontal segment, a visibility check on the other segments of the associated triangle
is also carried out to ensure that boundary segments are visible to the insertion point
p
.
One of the major difficulties in the implementation of the DT algorithm by point insertion
is to ensure consistency in the circle inclusion test based on finite precision arithmetic. An
inconsistent decision in the circle inclusion test may result in a disconnected CORE, as
described in Section 3.5.4.3. Imprecise numerical calculation may also introduce triangles
with negative area.
DT is not unique unless all the points are in general positions. On a 2D plane, a degen-
eracy occurs when four points are cyclic giving rise to two different DTs depending on how
these four points are connected into triangles, as shown in Figure 3.31. When a fifth point
p
is introduced, difficulty may arise unless both existing triangles are removed. As shown in
Figure 3.31, the algorithm will generate a consistent triangulation if both triangles
abc
and
acd
are regarded as non-Delaunay with respect to point
p
. A consistent triangulation will
also be produced if neither triangle is removed upon the introduction of point
p
. However,
if triangle
acd
is deleted but not triangle
abc
, then the new triangulation will be structurally
inconsistent. This situation may arise when four points are cyclic or almost cyclic, because
finite precision arithmetic that is used in the Delaunay test may cause one of the two tri-
angles to be accepted into the cavity list.
Using higher precision arithmetic can only postpone the problem to solve more cases,
which are near to degeneracy, but not solve it entirely. Baker (1992) proposed a solution in
which tolerances depending on the value of the data and the machine precision are applied
to all real number calculations. Empty-circle tests based on double precision computations
(8-byte variables) can only allow us to obtain a triangulation, which is close to DT.
d
c
a
b
p
Figure 3.31
Correction of the CORE.
