Civil Engineering Reference
In-Depth Information
uniform point distribution, the regular grid insertion takes slightly more CPU time in the
insertion of 10 million points, 16.71 s vs. 11.03 s, whereas the other two insertion schemes
take almost the same CPU time for the insertion of the same number of points. Surprisingly,
the kd-tree insertion scheme takes even slightly less CPU time as the kd-tree partition of
evenly distributed points takes slightly more CPU time than a non-uniformly point distribu-
tion. Again, the most efficient scheme is the multiple grid insertion if the grid construction
time is also taken into consideration.
8.2.6 Closure
The fundamentals for the DT of non-uniformly distributed points by the insertion method are
discussed in this section. In the light of the simplicity and linearity of regular grid insertion,
a multi-grid insertion scheme is presented for the triangulation of uniform and non-uniform
point distributions by recursive application of the regular grid insertion to an arbitrary subset
of the original point set. The regular grid insertion is very sensitive to point distributions, as
the time taken in searching for the base triangle increases rapidly with highly non-uniformly
distributed points. The kd-tree may have a rather poor performance for triangulations charac-
terised with a large amount of elongated triangles as conflicting triangles have to be removed
and reconstructed for the insertion of closely spaced points. The multi-grid insertion is the
most efficient and stable for all the distribution patterns tested among the three insertion
schemes if the grid construction time is also taken into account. A quasi-linear complexity can
be observed for the triangulation of point distribution patterns such as line, circle and cluster,
with local features similar to those of a uniform point distribution. However, substantially
more CPU time is needed for the triangulation of the more difficult distribution patterns, such
as cross and spiral, in which there are many elongated triangles in the triangulation, which
leads to a non-linear complexity. Nevertheless, with the multi-grid insertion, the triangula-
tion time of the worst non-uniform distribution of 100 million points tested is about only five
times more than that of a uniform distribution.
8.3 MULTI-GRID INSERTION OF NON-UNIFORM
POINT DISTRIBUTIONS (3D)
8.3.1 Introduction
Similar to 2D point insertion, relative to a uniform point distribution, non-uniform point sets
are significantly more difficult due to the following intrinsic properties of non-uniformly dis-
tributed points. (i) More efficient space control or partition has to be applied to highly non-
uniform distributed points so that each partitioned cell contains a roughly equal number of
points. (ii) In the location of the base tetrahedron by the point insertion algorithm, the CPU time
taken or the number of tetrahedra examined before the base tetrahedron could be determined
is much longer than the case of uniform distribution as there are many pointed tetrahedra in
the triangulation. (iii) In the creation of the insertion cavity (CORE) upon the introduction of
a new point, many tetrahedra have to be removed and reconstructed as long thin tetrahedra
have large circumspheres, and a point can be connected to many distant points through long
stretching tetrahedra. (iv) There are problems of numerical stability both in the determination
of the BASE tetrahedron and in the verification of the empty circumsphere criterion, and more
CPU time has to be allowed to exercise additional consistency checks and precautions.
As for the identification of the insertion cavity, the number of tetrahedra checked and
removed depends on the insertion sequence as well as the intrinsic characteristics and pattern
