Civil Engineering Reference
In-Depth Information
connects the centres of neighbouring sub-squares. By repeat subdivision of each sub-square,
the curve produced by linking up all the arrows becomes longer and longer, and it is called
a Hilbert curve. The division into smaller squares or cells is just like a Quadtree subdivision
applied uniformly over the entire domain to produce sub-squares of equal size, which can
be controlled by specifying the maximum number of points in a sub-square. The Hilbert
curve is designed to provide a path passing through all the sub-squares, so that points will
be inserted cell by cell in a reasonably contiguous manner. However, extra time has to be
allowed in the cell subdivision and management, and in formulating the path of insertion,
which may go through many empty cells.
8.2.2.4 Space partition (background grid)
In triangulation, a background grid is a partition of space to facilitate searching or to estab-
lish a neighbourhood relationship for various quantities. Depending on the distribution of
the points or objects under consideration and other specific requirements, grids of differ-
ent characteristics can be constructed. By the use of a background grid, the space will be
partitioned into cells, and the ideal scenario is to divide the space such that each cell will
hold roughly an equal number of points. According to different point distributions, regular
grids of equal and unequal spacings, Quadtree/Octree and kd-tree partitions, etc., have been
devised.
Regular grids with equal and unequal spacing are the simplest and easiest to cre-
ate with linear time complexity; hence, their construction is almost without any cost.
Nevertheless, they are very effective in dealing with objects with normal or random dis-
tributions, and they are also very useful as a space control even for mildly non-uniform
distributions. The basic properties, procedure of construction, general characteristics
and memory requirement of a regular grid will be elaborated in Section 8.2.3. Point
insertion by means of a regular grid for uniform and non-uniform point distributions
will be fully investigated in Section 8.2.5.
Kd-tree construction is an effective space control for highly non-uniformly distributed
data. Points are partitioned into two equal portions (which differ at most by one point) by
taking the median of the point set. This procedure is repeated as necessary until there is
no more than one point in each subdivided region. By the very construction of the kd-tree
taking the median to divide a point set, at an intermediate stage, the number of points in
a region (cell) is always equal no matter how points are distributed. The price to pay is
to determine the median of the points in a cell for each subdivision by means of a sort-
ing process or more effectively by means of the
bin sort
or
address sort
. The points in the
cells along with the sequence of pivots of subdivision points form a sorted insertion order
for the original point set. In a paper 'A New Insertion Sequence for Incremental Delaunay
Triangulation' by Liu et al. (2013), it is reported that kd-tree insertion is superior to random,
BRIO and Hilbert curve insertions up to 3 million 3D non-uniformly distributed points in
various patterns such as cluster, disc, curved surface, line, spiral, etc.
In view of the better performance of kd-tree insertion over random, BRIO and Hilbert
curve insertions for a wide range of non-uniform point distributions, random, BRIO and
Hilbert curve will not be further explored. On the other hand, the regular grid insertion,
the kd-tree insertion and its enhanced version developed in Section 8.2.3 will be rigorously
tested against a wide range of data points from 1 to 100 million over a variety of non-
homogeneous distribution patterns. In light of the ease of construction of the regular grid
and its linear characteristic for uniform distributed data, a new insertion scheme is pro-
posed by recursive application of regular grid insertion to non-uniform distributed points
