2013/05/22 by Richard Barnes, Clarence Lehman, D. J. Mulla +1 · 3 citations
Computer Science · Environmental Science · Mathematics · #Algorithm #Artificial intelligence #Cartography #Computer science #Digital elevation model #Flood Risk Assessment and Management #Flood myth #Flooding (psychology) #Geography #Geology #Geometry #Groundwater flow and contamination studies #Hydrology and Watershed Management Studies #Mathematics #Point (geometry) #Preprocessor #Priority queue #Queue #Remote sensing #Terrain #Watershed #cs.DS
paper · pdf · doi:10.1016/j.cageo.2013.04.024
published as Computers & Geosciences. Vol 62, Jan 2014, pp 117--127 · 17 pages, 4 figures, 5 algorithms
openalex publication_date 2013/05/22 · crossref created 2013/05/22 · crossref issued 2014/01/01 · crossref published 2014/01/01 · crossref published-print 2014/01/01 · arxiv created 2015/11/13 · arxiv updated 2015/11/17 · crossref deposited 2018/10/15 · openalex created_date 2025/10/10 · crossref indexed 2026/07/29 · openalex updated_date 2026/08/05
Depressions (or pits) are low areas within a digital elevation model that are surrounded by higher terrain, with no outlet to lower areas. Filling them so they are level, as fluid would fill them if the terrain were impermeable, is often necessary in preprocessing DEMs. The depression-filling algorithm presented here---called Priority-Flood---unifies and improves on the work of a number of previous authors who have published similar algorithms. The algorithm operates by flooding DEMs inwards from their edges using a priority queue to determine the next cell to be flooded. The resultant DEM has no depressions or digital dams: every cell is guaranteed to drain. The algorithm is optimal for both integer and floating-point data, working in O(n) and O(n lg n) time, respectively. It is shown that by using a plain queue to fill depressions once they have been found, an O(m lg m) time-complexity can be achieved, where m does not exceed the number of cells n. This is the lowest time complexity of any known floating-point depression-filling algorithm. In testing, this improved variation of the algorithm performed up to 37% faster than the original. Additionally, a parallel version of an older, but widely-used depression-filling algorithm required six parallel processors to achieve a run-time on par with what the newer algorithm's improved variation took on a single processor. The Priority-Flood Algorithm is simple to understand and implement: the included pseudocode is only 20 lines and the included C++ reference implementation is under a hundred lines. The algorithm can work on irregular meshes as well as 4-, 6-, 8-, and n-connected grids. It can also be adapted to label watersheds and determine flow directions through either incremental elevation changes or depression carving. In the case of incremental elevation changes, the algorithm includes safety checks not present in prior works.