A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage
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 stan...
Published in: | Geoscientific Model Development |
---|---|
Main Authors: | , |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
Copernicus Publications
2016
|
Subjects: | |
Online Access: | https://doi.org/10.5194/gmd-9-4451-2016 https://doaj.org/article/35833a416cf540c7818d8a50e6f758bf |
id |
ftdoajarticles:oai:doaj.org/article:35833a416cf540c7818d8a50e6f758bf |
---|---|
record_format |
openpolar |
spelling |
ftdoajarticles:oai:doaj.org/article:35833a416cf540c7818d8a50e6f758bf 2023-05-15T16:30:15+02:00 A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage C. J. Berends R. S. W. van de Wal 2016-12-01T00:00:00Z https://doi.org/10.5194/gmd-9-4451-2016 https://doaj.org/article/35833a416cf540c7818d8a50e6f758bf EN eng Copernicus Publications http://www.geosci-model-dev.net/9/4451/2016/gmd-9-4451-2016.pdf https://doaj.org/toc/1991-959X https://doaj.org/toc/1991-9603 1991-959X 1991-9603 doi:10.5194/gmd-9-4451-2016 https://doaj.org/article/35833a416cf540c7818d8a50e6f758bf Geoscientific Model Development, Vol 9, Iss 12, Pp 4451-4460 (2016) Geology QE1-996.5 article 2016 ftdoajarticles https://doi.org/10.5194/gmd-9-4451-2016 2022-12-31T00:30:14Z 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. Article in Journal/Newspaper Greenland Ice Sheet Directory of Open Access Journals: DOAJ Articles Greenland Geoscientific Model Development 9 12 4451 4460 |
institution |
Open Polar |
collection |
Directory of Open Access Journals: DOAJ Articles |
op_collection_id |
ftdoajarticles |
language |
English |
topic |
Geology QE1-996.5 |
spellingShingle |
Geology QE1-996.5 C. J. Berends R. S. W. van de Wal A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
topic_facet |
Geology QE1-996.5 |
description |
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. |
format |
Article in Journal/Newspaper |
author |
C. J. Berends R. S. W. van de Wal |
author_facet |
C. J. Berends R. S. W. van de Wal |
author_sort |
C. J. Berends |
title |
A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
title_short |
A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
title_full |
A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
title_fullStr |
A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
title_full_unstemmed |
A computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
title_sort |
computationally efficient depression-filling algorithm for digital elevation models, applied to proglacial lake drainage |
publisher |
Copernicus Publications |
publishDate |
2016 |
url |
https://doi.org/10.5194/gmd-9-4451-2016 https://doaj.org/article/35833a416cf540c7818d8a50e6f758bf |
geographic |
Greenland |
geographic_facet |
Greenland |
genre |
Greenland Ice Sheet |
genre_facet |
Greenland Ice Sheet |
op_source |
Geoscientific Model Development, Vol 9, Iss 12, Pp 4451-4460 (2016) |
op_relation |
http://www.geosci-model-dev.net/9/4451/2016/gmd-9-4451-2016.pdf https://doaj.org/toc/1991-959X https://doaj.org/toc/1991-9603 1991-959X 1991-9603 doi:10.5194/gmd-9-4451-2016 https://doaj.org/article/35833a416cf540c7818d8a50e6f758bf |
op_doi |
https://doi.org/10.5194/gmd-9-4451-2016 |
container_title |
Geoscientific Model Development |
container_volume |
9 |
container_issue |
12 |
container_start_page |
4451 |
op_container_end_page |
4460 |
_version_ |
1766019961676890112 |