Civil Engineering Reference
In-Depth Information
Non-Delaunay
triangles removed
k+1
k
p
p
p
Figure 3.22
Inserting point
p
by the insertion kernel.
TTCB
k+1
=−+
p
p
wher
p
= CORE = cavity of non-Delaunay triangles with respect to
p
p
= ball of triangles = patch of Delaunay triangles connected to
p
k
= the DTs of the first k and k + 1 points of the set
and
k+1
3.5.4.3 Determination of the CORE
When a new point
p
is inserted in a DT, it is required to find all the triangles whose circum-
circle contains the point
p
. A simple method to determine these non-Delaunay triangles is
to scan through all the existing triangles in the triangulation for those whose circumcircle
contains the point
p
. However, a more efficient approach is to start with the triangle con-
taining the inserted point
p
and to find the others by means of the adjacency relationship. In
this way, the boundary of the CORE (insertion polygon) is given by the common edge of two
triangles for which one is positive in the circle inclusion test while the other fails.
The circle containing the insertion point
p
is called the BASE, which is an integral part
of the CORE. It seems that finding a triangle whose circumcircle contains
p
is easier than
finding the BASE. However, it does not always work in case a wrong decision is made in the
circle inclusion test due to numerical error. The difficulty can be elucidated by the following
example for the insertion of a new point
p
.
Let
afb
be the triangle that contains
p
in a DT, and
a
,
b
,
c
,
d
and
e
be the five points
roughly on the circumference of a circle, as shown in Figure 3.23. In the circle inclusion test,
point
p
is found in the circumcircle of triangles
abc
and
cde
but not in that of
ace
. In this
case, the CORE is a disconnected piece if one has started building the CORE with a triangle
not containing
p
. On the other hand, if one insists that the construction of the CORE has
to be started with the containing triangle
afb
(BASE) and builds the CORE by means of
adjacency, then triangle
cde
can be excluded from the CORE and a valid CORE composed
of triangles
afb
and
abc
can be obtained in one piece.
3.5.4.4 Searching for the BASE
In principle, one would like to start the searching process for the containing circle of the
insertion point
p
from a point as close to point
p
as possible. However, when there is no
