Civil Engineering Reference
In-Depth Information
multi-grid insertion, leading to about four-time difference in the overall performance. As for
the kd-tree insertion, surprisingly, the NP value of 16 as well as the NR value of 27 are both
much higher than those of the multi-grid insertion, resulting in an insertion time about six
times of that of the multi-grid insertion for the insertion of 100 million points.
In spite of a change in the pattern shape, the results for the circle distribution are very
similar to those for the straight line distribution, such that the performance of the multi-
grid insertion is a couple of times better than that of the regular grid insertion. Considering
insertion time alone, kd-tree is the most efficient, but the multi-grid insertion is the best
overall if grid construction time is also taken into account.
The spiral distribution is perhaps the most difficult case for the various point insertion
schemes. The NP and NR values are considerably higher for the three insertion schemes com-
pared to other distributions, in which the multi-grid insertion is still the best overall. It is noted
that NP and NR values increased with the number of points leading to a non-linear increase
in CPU time with the number of points inserted. In particular, the NP and NR values of the
kd-tree insertion increased rather rapidly with the points in the set, and the high NR value of
28 makes the kd-tree insertion the least efficient among the three insertion schemes for the
insertion of 100 million points. The high NR value for kd-tree insertion was probably due to
the over-sorting of the points for highly non-uniform distributions such that many elongated
triangles had to be removed for each point insertion. As shown in Figure 8.44 for the triangu-
lation of a spiral distribution of 1000 points, elongated triangles are produced joining points
at different levels of the spiral, and much narrower triangles are expected when the number
of points increases to 100 million. As shown in Table 8.7, the NR value for regular insertion
was very stable at 7 or 8, but the NP value was rather high at 76. A good balance can be found
with the multi-grid insertion, with an NR value similar to that of the regular insertion and an
NP value smaller than that of the kd-tree insertion. This is really a challenging example for the
design of the insertion scheme as well as the numerical stability of the algorithm.
A cluster distribution is locally very similar to the uniform distribution, and not many elon-
gated triangles are expected in the triangulation. As points are drastically unevenly distributed,
the NP value for regular grid insertion was pretty high, which increased steadily with the
Figure 8.44
Delaunay triangulation of spiral distribution of 1000 points.
