Civil Engineering Reference
In-Depth Information
For example, a set of 20 points is divided into two regions (cells), in which the cell on the
left contains 10 points and the cell on the right contains 9 points, as shown in Figure 8.27a.
L = 1, regions = {2
1
, 2
2
- 1} = {2, 3} and pivot = {1}. For L = 2, the point set is partitioned into
four regions, as shown in Figure 8.27b, in which regions = {2
2
, …, 2
3
- 1} = {4, 5, 6, 7} and
pivots = {1, 2, 3}. Take for instance the level L = 2 partition of 20 points; the cells are {4, 5,
6, 7} and pivots = {1, 2, 3}. The insertion sequence is given as follows:
1. Five points in cell 4 are inserted, and 4 is divided by 2 hence, pivot = 4/2 = 2.
2. Pivot 2 is inserted.
3. Four points in cell 5 are inserted, and 5 is not divisible by 2, 5/2 = 2, and 2 is divisible
by 2; hence, pivot = 2/2 = 1.
4. Pivot 1 is inserted.
5. Four points in cell 6 are inserted, and 6 is divisible by 2; hence, pivot = 6/2 = 3.
6. Pivot 3 is inserted.
7. Four points in cell 7 are inserted.
8. All the 20 points in the set have been processed.
By means of the simple cell-pivot-cell sandwiched scheme, points partitioned into kd-tree
cells can be inserted in a reasonable contiguous manner without much computation.
8.2.3.4 Kd-tree grid insertion
As the number of points in a cell of kd-tree is roughly equal (differ at most by one), within
a kd-tree cell, more sophisticated insertion scheme, say the regular grid insertion, can be
applied to enhance the overall efficiency as shown in Figure 8.28. In the numerical tests of
insertion of 1 million to 100 million points for various non-uniform distribution patterns,
the most efficient scheme is to have about 16 points in each cell. However, if regular grid
insertion is available, a more efficient insertion scheme can be devised by putting 1000 to
10,000 points in a cell. Whichever the case, the number of points in a cell is not very sensi-
tive 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 the distribution of the points.
8.2.4 Multi-grid insertion
A multi-grid insertion is the result of applying the regular grid insertion to each cell of a
spatial partition in a recursive manner. The idea is based on the observation that the regular
Kd-tree partitions
Regular grid insertion
Figure 8.28
Regular grid insertion for kd-tree partitions.
