  In processing raster digital elevation models (DEMs) it is often necessary to
assign drainage directions over flats---that is, over regions with no local
elevation gradient. This paper presents an approach to drainage direction
assignment which is not restricted by a flat's shape, number of outlets, or
surrounding topography. Flow is modeled by superimposing a gradient away from
higher terrain with a gradient towards lower terrain resulting in a drainage
field exhibiting flow convergence, an improvement over methods which produce
regions of parallel flow. This approach builds on previous work by Garbrecht
and Martz (1997), but presents several important improvements. The improved
algorithm guarantees that flats are only resolved if they have outlets. The
algorithm does not require iterative application; a single pass is sufficient
to resolve all flats. The algorithm presents a clear strategy for identifying
flats and their boundaries. The algorithm is not susceptible to loss of
floating-point precision. Furthermore, the algorithm is efficient, operating in
O( N ) time whereas the older algorithm operates in O( N^(3/2) ) time. In
testing, the improved algorithm ran 6.5 times faster than the old for a 100 x
100 cell flat and 69 times faster for a 700 x 700 cell flat. In tests on actual
DEMs, the improved algorithm finished its processing 38--110 times sooner while
running on a single processor than a parallel implementation of the old
algorithm did while running on 16 processors. The improved algorithm is an
optimal, accurate, easy-to-implement drop-in replacement for the original.
Pseudocode is provided in the paper and working source code is provided in the
Supplemental Materials.
