Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation models

Richard Barnes, Clarence Lehman, D J Mulla

Research output: Contribution to journalArticlepeer-review

97 Scopus citations

Abstract

Depressions (or pits) are 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 was impermeable, is often necessary in preprocessing DEMs. The depression-filling algorithm presented here - called Priority-Flood - unifies and improves 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 log2 n) time, respectively. It is shown that by using a plain queue to fill depressions once they have been found, an O(m log2 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.

Original languageEnglish (US)
Pages (from-to)117-127
Number of pages11
JournalComputers and Geosciences
Volume62
DOIs
StatePublished - Jan 2014

Bibliographical note

Funding Information:
Funding for this work was provided by the Minnesota Environment and Natural Resources Trust Fund under the recommendation and oversight of the Legislative-Citizen Commission on Minnesota Resources (LCCMR) . David Mulla was the P.I. on this grant. Supercomputing time and data storage were provided by the Minnesota Supercomputing Institute . Adam Clark provided feedback on the paper; Joel Nelson provided LIDAR DEMs and ArcGIS support. In-kind support was provided by Earth Dance Farm , Tess Gallagher, Justin Konen, and Steffi O'Brien.

Keywords

  • Drainage network
  • GIS
  • Hydrology
  • Modeling
  • Pit filling
  • Terrain analysis

Fingerprint

Dive into the research topics of 'Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation models'. Together they form a unique fingerprint.

Cite this