Civil Engineering Reference
In-Depth Information
number of points inserted up to more than 100 for a large point set of 100 million points, and as
a result, the performance of the regular grid insertion was even worse than the case of spiral dis-
tribution. On the other hand, similar to uniform point distribution, kd-tree insertion recorded
the best performance with low NP and NR values as the number of points in a kd-tree parti-
tion is always equal irrespective of the point distribution. Nevertheless, the performance of the
multi-grid insertion is still the best overall if grid construction is taken into consideration. Apart
from the number of points inserted, the impact of various non-uniform distributions for the
three insertion schemes has also been studied. The CPU times for various distribution patterns
by the three insertion schemes for the insertion of 1 million, 10 million and 100 million points
are plotted, respectively, in Figures 8.45 through 8.47. As shown in Figure 8.45, for the insertion
of 1 million points, regular grid insertion took much more CPU time (six times on average) for
non-uniform point distributions compared to uniform distributions, whereas kd-tree insertion
and multi-grid insertion could substantially reduce the CPU time taken except for the spiral
distribution for the multi-grid insertion and the cross and the spiral for the kd-tree insertion.
For the insertion of 10 million points, a similar trend is observed, as shown in Figure 8.46.
However, the CPU time taken for the regular grid insertion increased more rapidly for the
8
RG_1M
MG_1M
KD_1M
7
6
5
4
3
2
1
0
Uniform
Line
Cross
Circle
Spiral
Cluster
Point distributions
Figure 8.45
CPU time for various distributions of 1 million points.
160
RG_10M
MG_10M
KD_10M
140
120
100
80
60
40
20
0
Uniform
Line
Cross
Circle
Spiral
Cluster
Point distributions
Figure 8.46
CPU time for various distributions of 10 million points.
