A FAST, SIMPLE AND VERSATILE ALGORITHM TO FILL THE DEPRESSIONS OF DIGITAL ELEVATION MODELS

Abstract

The usual numerical methods for removing the depressions of a Digital Elevation Model (DEM) gradually fill the depressions and merge the embedded ones. These methods are complex to implement and need large computation time, particularly when the DEM contains a high proportion of random noise. A new method is presented here. It is innovative because, instead of gradually filling the depressions, it first inundates the surface with a thick layer of water and then removes the excess water. The algorithm is simple to understand and to implement, requiring only a few tens of code lines. It is much faster than usual algorithms. Moreover, this method is versatile: depressions can be replaced with a surface either strictly horizontal, or slightly sloping. The first option is used for the calculation of depression storage capacity and the second one for drainage network extraction. The method is fully detailed and a pseudo-code is provided. Its practical computation time, evaluated on generated fractal surfaces, is asymptotically proportional to N1.2 where N is the number of grid points. The theoretical computation time is asymptotically proportional to N1.5 in all cases, with the exception of some exotic ones with no practical interest. By contrast, existing methods have a computation time asymptotically proportional to N2. Applications are done for both generated and measured surfaces with 256 cells to 6.2 million cells.