Civil Engineering Reference
In-Depth Information
Figure 8.49
Elongated tetrahedra over a spiral point distribution.
of the point distributions. No theoretical results have been reported so far as to how to
devise an optimised order to minimise the number of conflicting tetrahedra in the entire tri-
angulation process. While this is not an issue in uniform point distribution, for non-uniform
point distributions, the total number of tetrahedra removed varies significantly with the
order of point insertion. For highly non-uniform point distributions, over many parts, long
thin tetrahedra with large circumscribing spheres exist. Upon the introduction of a newly
inserted point near a cluster of elongated tetrahedra, a large number of tetrahedra have to
be removed and reconstructed, as shown in Figure 8.49. If points are to be inserted in a con-
tiguous manner close to each other, the removal and reconstruction of elongated tetrahedra
have to be repeated for each point insertion. Obviously, this is rather time-consuming and
perhaps unnecessary. The dilemma is that in order to reduce the time in searching for the
base tetrahedron, the points have to be inserted in a contiguous manner; however, in order
not to remove and reconstruct elongated triangles in an excessive manner, the points have
to be inserted with sufficient separation. An effective algorithm ought to optimise both the
search for the BASE and the conflicting tetrahedra in the creation of the CORE.
Similar to the triangulation of non-uniform point distributions in 2D, the kd-tree inser-
tion and its enhanced version developed in Section 8.3.2 will be rigorously tested against a
wide range of data points from 0.4 to 20 million over a variety of non-uniform distribution
patterns. The idea of multi-grid insertion is generic, which is expected to perform well in
3D. A 3D multi-grid insertion scheme is developed by recursive application of regular grid
insertion to non-uniform distributed points partitioned into cells by regular grid or kd-tree.
Exploiting the local homogeneity of non-uniformly distributed points, regular grid insertion
is especially effective over uniform or non-uniform point distributions partitioned into tiny
cells of a large number of points. The procedure of multi-grid insertion will be presented in
Section 8.3.3, and the multi-grid insertion will be fully tested in Section 8.3.4.
8.3.2 Kd-tree insertion (3D)
8.3.2.1 3d-tree partition of space and points
The concept and the procedure for the construction of 2d-tree can be generalised naturally
to higher dimensions, as discussed in Section 2.7.8. In three dimensions, k = 3, the space/
