An efficient variant of the Priority-Flood algorithm for filling depressions in raster digital elevation models. (May 2016)

• Record Type: Journal Article
• Authors: Zhou, Guiyun; Sun, Zhongxuan; Fu, Suhua
• Is Part Of: Computers & geosciences. Volume 90(2016)Part A
• Page Start: 87
• Page End: 96
• Publication Date: 2016-05
• Subjects: Depression filling -- Flow direction -- DEM -- Hydrological analysis; Environmental policy -- Periodicals; 550.5
• DOI: 10.1016/j.cageo.2016.02.021
• Languages: English
• ISSNs: 0098-3004

Abstract

Abstract: Depressions are common features in raster digital elevation models (DEMs) and they are usually filled for the automatic extraction of drainage networks. Among existing algorithms for filling depressions, the Priority-Flood algorithm substantially outperforms other algorithms in terms of both time complexity and memory requirement. The Priority-Flood algorithm uses a priority queue to process cells. This study proposes an efficient variant of the Priority-Flood algorithm, which considerably reduces the number of cells processed by the priority queue by using region-growing procedures to process the majority of cells not within depressions or flat regions. We present three implementations of the proposed variant: two-pass implementation, one-pass implementation and direct implementation. Experiments are conducted on thirty DEMs with a resolution of 3m. All three implementations run faster than existing variants of the algorithm for all tested DEMs. The one-pass implementation runs the fastest and the average speed-up over the fastest existing variant is 44.6%. Graphical abstract: Highlights: An efficient variant of the Priority-Flood algorithm is proposed. The variant substantially reduces the running time of existing variants. Three implementations are provided for the proposed variant. The one-pass implementation runs the fastest. The average speed-up over the fastest existing variant is 44.6%.