  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.
