An efficient method for identifying and filling surface depressions in digital elevation models for hydrologic analysis and modelling

Identification and removal of surface depressions is a critical step for automated modelling of surface rainfall runoff based on Digital Elevation Models (DEMs). At present, nearly all GIS and hydrologic software packages employ Jenson and Domingue's method for preparing depressionless DEMs for hydrologic analysis. This conventional method is computationally intensive and time-consuming. With the growing availability of high-resolution DEMs produced by airborne LIDAR and InSAR techniques, GIS-based hydrologic applications often need to handle larger geographic areas at finer resolutions. In the face of high-resolution DEMs, the conventional method becomes inadequate and deficient. In this paper, we present a new method for efficiently identifying and filling surface depressions in DEMs. This method can simultaneously determine flow paths and spatial partition of watersheds with one pass of processing. A novel concept of spill elevation and the least-cost search for optimal flow paths are the two cornerstones of our method. The time complexity of our method is in O(Nlog N). It has been implemented using C+ + programming language and successfully applied to USGS DEMs and LIDAR DEMs of various sizes. Experiments show that our method outperforms the conventional method by a factor of over 30, in terms of running time.