pressions, no CAVs need to be calculated, however,
since all cells of the depression fully belong to the de-
pression’s basin.
7. WORK IN PYRAMID STRUCTURE
The upper limit of DEM-sizes is caused by the (virtual)
memory available. A maximum of 3 floating point matri-
ces are to be held in memory simultaneously for the
calculation of the drainage accumulation values in the
iterative process (chapter 3.2) or 2 floating point matri-
ces and one integer array of the same size for the or-
dered calculation. Most usual word-lengths are 32 bits
for both floating point and integer values, therefore the
indexing array uses the same size as the floating point
array. For 1,000,000 grid-cells, e.g., this means about
12 MB of virtual storage. With modern workstations
this is no real problem in terms of memory usage.
Table 1 lists computing times for one step of the itera-
tive calculation of the drainage accumulation values and
for the sorting of the indexing array in different DEMs of
different sizes. After sorting, the calculation of the
drainage accumulation values will take additional time
of one step of iteration.
No. of points Iter Sort
10,201 0.61 1.02
58,081 3.81 7.57
152,348 9.87 20.05
231,361 15.53 37.03
301,101 20.48 45.89
535,200 36.31 86.45
1,204,200 87.13 313.02
Table 1: CPU-times in seconds on a VAX-Station 3100/
M76 with 32 MBytes of main memory under the VMS
operating system. "Iter" means one iteration of iterative
calculation, "Sort" means sorting of indexing array by
the ANSI-C function "qsort". These values are mean
values and may differ about 296 up or down on repeat-
ed calculations.
The ordered calculation will take the time of about 3 to
5 steps of the iterative calculation for model sizes up to
over one million of points. This factor includes the time
of calculation of the drainage accumulation value in the
ordered calculation. Thus, the use of sorting is greatly
justified.
Nevertheless it is not commendable to use too large
matrices, since terrain may strongly change in terms of
roughness within larger regions, thus the grid width
should be adapted individually. Furthermore, it is pretty
unwieldy to work on very large matrices, and, overall,
matrices are always limited in size.
For work on very large DEMs (from several 100,000
points upwards), the pyramid structure, as described in
chapter 2, is proposed. When using this structure, the
following advantages result:
- Work in different levels corresponds to scale-depen-
dent generalization; it is possible to obtain river
networks in a resolution that corresponds to the
wanted scale.
- |n each level the same algorithms can be used with-
out any changes.
- Data sets of higher levels (finer resolutions) can use
information of those of lower levels. This may allow
for acceleration as well as - in some cases - for
quality improvement. In particular, this can be used
648
for:
- Pit removal: In lower levels there are generally
less pits. Flow directions can then be taken from
pitless zones in lower levels - a priori pitless or
after removing pits - to use the correct outflow
point.
- Catchment areas: The approximate knowledge of
the catchment areas in the higher level allows for
work within a single (larger) catchment area.
Within such an area fast river-course extraction is
as well possible as fast sorting and sub-water-
shed delineation.
- River networks: When splitting larger regions, it
is possible to impact drainage accumulation val-
ues obtained from lower levels (in regard of the
changed grid cell size) along the edge of a region
section as a constraint. This allows for splitting
very long rivers without loss of information about
its drainage accumulation values.
- Overview calculations are possible for quick terrain
analyses. Detailed work then can be restricted to
zones of special interest.
- The structure can easily be adapted for data cap-
turing techniques such as progressive sampling.
Picture 11 shows a series of the test region of picture
4 calculated in different levels.
8. CONCLUSION AND OUTLOOK
Rectangular grid-DEMs in form of matrices can easily be
expanded to grid-GISs. Elementary functions on such
matrices allow for a huge range of applications. Com-
plex problems often relatively simply can be resolved.
Algorithms and visualization techniques of digital image
processing can be used. The extraction of river lines
and catchment areas can be seen as one example of
these features. More complex hydrological modelling
could take place with additional data layers, such as
roughness, soil conditions, slant (for water flow veloci-
ty); rainfall layers would allow for simulation of specific
rainfall characteristics, especially in conjunction with a
hill exposition layer.
The pyramid data structure proves to be a simple but
efficient means for grid GIS and raster data analyses,
saving the administrative amount of quadtrees and
similar structures. For better accuracy, after the opera-
tions have taken place in the grid structure, it is possi-
ble to make finer adjustments in regions of special inter-
est, i.e. along the river-courses and the catchment
borders, using vector-based algorithms in hybride or
vector DEMs.
