Civil Engineering Reference
In-Depth Information
8.3.2.2 Insertion by a sandwich sequence
Again, a 2d-tree is taken to illustrate the sequence of point insertion cell by cell, and the
entire set of points will be inserted when all the cells and pivot points are processed. Unlike
the regular grid scheme, there is no natural contiguous sequence for cells generated by a
squarish
3d-tree partition. However, the region splitting pivot points can serve as a link
between two regions at a given level of subdivision. As shown in Figure 8.27, for partition
level L = 2, the insertion sequence for the cells and pivot points are given by
{cell 4 - pivot 2 - cell 5 - pivot 1 - cell 6 - pivot 3 - cell 7}
In 3D insertion, for a set of points partitioned into 2
L
cells, the insertion sequence is
also given by the cell-pivot-cell sandwiched scheme. The cells for a level L partition are
given by
{2
L
, 2
L
+ 1,…, 2
L+1
− 1}
and the pivot points are given by {1, 2,…, 2
L
- 1}.
In the cell-pivot-cell sandwiched scheme, cells of points are inserted sequentially starting
with cell 2
L
, and the pivot point k following cell j is given by k = j/2, if j is divisible by 2;
otherwise, set j
1
= j/2, and repeat the division process until j
m
is divisible by 2; then pivot k =
j
m
/2. By the kd-tree construction, such a pivot point always exists and is unique for all the
cells between 2
L
and 2
L+1
- 2.
8.3.2.3 Enhanced kd-tree insertion
Kd-tree insertion can be improved following the same idea as in 2D; within a kd-tree cell,
a more sophisticated insertion scheme, say the regular grid insertion, can be applied to
enhance the overall efficiency, as shown in Figure 8.28. For a classical kd-tree partition,
the space is partitioned until there are no more points left in each cell. There are two dis-
advantages in doing a full kd-tree partition: (i) more CPU time is required for the partition
down to the last point; and (ii) points are overly sorted in a full kd-tree partition so that,
on average, more non-Delaunay tetrahedra have to be removed in the insertion process.
In the numerical tests of insertion of 0.4 to 20 million 3D points for various non-uniform
distribution patterns, the most efficient scheme is to have about 20 points in each 3D cell.
However, if a regular grid insertion is available, a more efficient insertion scheme can be
devised by putting more than 1000 points in a cell. Similar to 2d-tree insertion, the num-
ber of points in a cell is not very sensitive to the overall performance as long as it is within
the right order, as it is only a statistical average depending also on the characteristics of
point distributions.
8.3.3 Multi-grid insertion
Following exactly what is done in 2D, a 3D multi-grid insertion is the result of applying
the regular grid insertion to each cell of a spatial partition in a recursive manner. Within
each cell, the points are more or less evenly distributed, and regular grid insertion can
be applied recursively to each cell resulting in a very simple efficient scheme with almost
linear complexity for locally evenly distributed points, such as line, ellipse and cluster dis-
tributions. Absolute linear complexity for the non-uniform point distributions with more
