Articles | Volume 9, issue 12
Geosci. Model Dev., 9, 4451–4460, 2016
Geosci. Model Dev., 9, 4451–4460, 2016

Development and technical paper 15 Dec 2016

Development and technical paper | 15 Dec 2016

A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage

Constantijn J. Berends and Roderik S. W. van de Wal Constantijn J. Berends and Roderik S. W. van de Wal
  • Institute for Marine and Atmospheric research Utrecht, Utrecht University, Utrecht, 3584 CC, the Netherlands

Abstract. Many processes govern the deglaciation of ice sheets. One of the processes that is usually ignored is the calving of ice in lakes that temporarily surround the ice sheet. In order to capture this process a “flood-fill algorithm” is needed. Here we present and evaluate several optimizations to a standard flood-fill algorithm in terms of computational efficiency. As an example, we determine the land–ocean mask for a 1 km resolution digital elevation model (DEM) of North America and Greenland, a geographical area of roughly 7000 by 5000 km (roughly 35 million elements), about half of which is covered by ocean. Determining the land–ocean mask with our improved flood-fill algorithm reduces computation time by 90 % relative to using a standard stack-based flood-fill algorithm. This implies that it is now feasible to include the calving of ice in lakes as a dynamical process inside an ice-sheet model. We demonstrate this by using bedrock elevation, ice thickness and geoid perturbation fields from the output of a coupled ice-sheet–sea-level equation model at 30 000 years before present and determine the extent of Lake Agassiz, using both the standard and improved versions of the flood-fill algorithm. We show that several optimizations to the flood-fill algorithm used for filling a depression up to a water level, which is not defined beforehand, decrease the computation time by up to 99 %. The resulting reduction in computation time allows determination of the extent and volume of depressions in a DEM over large geographical grids or repeatedly over long periods of time, where computation time might otherwise be a limiting factor. The algorithm can be used for all glaciological and hydrological models, which need to trace the evolution over time of lakes or drainage basins in general.

Short summary
This paper describes several improvements to the so-called "flood-fill algorithm" – a computer program widely known for its use in the "paint bucket" tool in several drawing programs such as MS Paint. However, it can also be used to determine the extent and depth of lakes in a topography map, which is useful in hydrology and climatology. In such cases, the default algorithm can be too slow to be of much use. Our improvements can make it up to 100 times faster, making it much more feasible.