Civil Engineering Reference
In-Depth Information
160
140
120
Sorted data
100
Unsorted data
80
60
40
20
0
0.1
0.2
0.4
0.6
0.8
1
1.2
Number of points (million)
Figure 3.21
Delaunay triangulation for sorted and unsorted data.
can be sustained up to 200 million points in 295 s and beyond to the maximum machine
capacity of 16 GB.
This observation is in line with the second interesting remark under Notes and Discussion
of the paper by Su and Drysdale (1997), 'A simple enhancement of the naïve incremental
algorithm results in an easy to implement algorithm that runs in
O
in expected time for uni-
formly distributed sites. It is faster than previous incremental variants and competitive with
other known algorithms for constructing the DT for all but very bad sites'
.
3.5.4.2 Point insertion algorithm
Let
be the set of n distinct points on a 2D plane. A rectangular domain composed of two
triangles
()
0
large enough to contain all the points in
is first constructed. The DT by point
insertion algorithm is to insert all the points one by one in
, and each cycle of point inser-
tion can be divided into three steps (Borouchaki and Lo 1995):
i. For a newly inserted point, identify all the triangles whose circumcircles contain the
point. The cavity left behind upon the removal of these triangles forms a star-shaped
polygon, which will be referred to as the CORE.
ii. Owing to finite precision arithmetic, the boundary edges of the insertion polygon have
to be verified with visibility check and corrected before they could be connected with
the inserted point to form triangles.
iii. The triangulation of the cavity should be trivial. However, the adjacency relationship
among the new triangles and with the old triangles on the boundary edge of the inser-
tion polygon has to be established.
The point-by-point insertion algorithm can be summarised into a point insertion kernel
(module). Suppose
k
is the DT of the first k points in the set
; upon the introduction of
the next point
p
, the insertion kernel aims at producing a DT with point
p
included in the
triangulation, as shown in Figure 3.22.
