area. We'll study the case where the threshold is set to 0. it is clear that the
dralnge network we obtain will include all drainage networks for larger threshold
values.
One can show a number of properties of the drainage network defined this
way. Most importantly, the drainage network consists of all valley edges, and
furthermore, exactly of all flow paths from their lower vertices. This follows from
the fact that water can only start accumulating at valley edges. The drainage
network will have merge points where two or more streams join and continue
together. These merge points are either vertices of the TIN, or points on valley
edges. Since we assumed that at every point of the TIN the direction of flow is
unique, streams cannot split.
When comparing the definitions of Frank et al. and Yu et al. we can easily
observe that under the former definition, the drainage network has complexity
at most linear in the number of edges of the TIN. It is considerably less obvious
what the size of the drainage network is under the second definition. De Berg
et al. [16] have shown that it is at most cubic in the number of edges of the
TIN, and that the cubic bound is tight for some artificially constructed TINs.
Whether the cubic worst case bound has any relevance in practice is doubtful.
An emperical study on this issue has been done and the actual size on real terrain
data appears to be roughly 20% more than under the definition by Frank et at.
The tests were done on six different terrains represented by TINs with up to
12,000 vertices [115].
To compute the drainage network by the definition of Yu et al., we first
identify all valley edges, and then follow the flow paths of their lower vertices
to the pits. Since flow paths can merge, we can stop tracing any flow path from
a point where another flow path has already gone through. So, whenever a flow
path is traced, it is marked on the terrain itself to make sure that the same
flow path isn't traced again and again. The resulting algorithm requires time
O(n + k),
where k is the complexity of the drainage network.
Drainage basins, catchment areas, generalization~ and spurious pits.
The study of drainage on a terrain using the definition of Yu et at. [129] can
be extended in various ways. Since it incorporates the notion of flow and ac-
cumulation, it becomes possible to determine the basins of the different river
systems, and also the area of the terrain that drains into each river system. For
any point on the terrain, we define the
catchment area
to be the part of the
terrain that drains through that point, eventually. The definition above of the
drainage network includes exactly the points that have a catchment area that
is 2-dimensional, no matter how small the area. As a consequence, many small
streams will be included in the drainage network.
We can also define a
generalized
drainage network by selecting the points of
which the catchment area has at least a certain size. Since it is possible to deter-
mine the size of the catchment area for each point on the terrain--in particular,
on the original drainage network--we can also compute the generalized drainage
network. Other methods to compute the generalized drainage network include
69