Civil Engineering Reference
In-Depth Information
regions are partitioned by a plane perpendicular to x-, y- or z-axis in turn according to the
level of subdivision. Using notations of Section 8.2.3.1, if Q
k
is on the x-aligned plane, child
nodes Q
2k
and Q
2k+1
are on the y-aligned plane, and grandchild nodes Q
4k
, Q
4k+1
, Q
4k+2
and
Q
4k+3
are on the z-aligned plane and so forth. The construction of a static kd-tree of n points
takes
O
(nlog
2
(n)) time if an
O
(nlog(n)) sort is employed to compute the median for each
region subdivision. The complexity becomes
O
(nlog(n)) if a linear median-finding algorithm
is used. In the partition of regions, if the regions are cut along their longest side instead of
rotating through the axes, the pattern and the performance of the kd-tree are quite different.
The behaviour of the kd-trees are much better as points are more closely grouped together,
and they are called
squarish
kd-trees. It is noted that the construction of 2d-tree and 3d-tree
for the same number of points takes a roughly equal amount of CPU time as the procedure
is similar, and the number of operations involved is exactly the same. A
squarish
3d-tree of
1000 points distributed along a straight line is shown in Figure 8.50 in which small cells are
found near the diagonal.
The only difference between kd-tree insertions in 2D and 3D is how the space is parti-
tioned into cells according to the given point set. As for the sequence of point insertion,
exactly the same sandwich sequence for 2D can be applied in the 3D case
. For the sake of
completeness and easy referencing, some of the more important features of kd-tree insertion
are also highlighted in this section. A nice feature of kd-tree partition is that at any level of
subdivision, each region contains a roughly equal number of points irrespective of the point
distribution. In triangulation, it is not necessary to subdivide each region down to the lowest
level, such that each region contains no point or only one point. A more general approach
for point insertion by kd-tree partition is to allow each region to contain a specified number
of points. Let N be the number of points in the set and n be the desirable number of points
in a cell; the level of subdivision is given by
N
n
L
nN L
2
=
= log
2
The number of cells in the partition N
c
= 2
L
.
For a level L subdivision, N
c
cells are labelled as {2
L
, 2
L
+ 1,…, 2
L+1
− 1} and the pivot
points between cells are {1, 2,…, 2
L
- 1}.
Figure 8.50
Squarish
3d-tree of 1000 points.
