TY - JOUR
T1 - Computing water flow through complex landscapes - Part 3
T2 - Fill-Spill-Merge: Flow routing in depression hierarchies
AU - Barnes, Richard
AU - Callaghan, Kerry L
AU - Wickert, Andrew D.
N1 - Publisher Copyright:
© Author(s) 2021.
PY - 2021/3/2
Y1 - 2021/3/2
N2 - Depressions - inwardly draining regions - are common to many landscapes. When there is sufficient moisture, depressions take the form of lakes and wetlands; otherwise, they may be dry. Hydrological flow models used in geomorphology, hydrology, planetary science, soil and water conservation, and other fields often eliminate depressions through filling or breaching; however, this can produce unrealistic results. Models that retain depressions, on the other hand, are often undesirably expensive to run. In previous work we began to address this by developing a depression hierarchy data structure to capture the full topographic complexity of depressions in a region. Here, we extend this work by presenting the Fill-Spill-Merge algorithm that utilizes our depression hierarchy data structure to rapidly process and distribute runoff. Runoff fills depressions, which then overflow and spill into their neighbors. If both a depression and its neighbor fill, they merge. We provide a detailed explanation of the algorithm and results from two sample study areas. In these case studies, the algorithm runs 90-2600 times faster (with a reduction in compute time of 2000-63 000 times) than the commonly used Jacobi iteration and produces a more accurate output. Complete, well-commented, open-source code with 97 % test coverage is available on GitHub and Zenodo.
AB - Depressions - inwardly draining regions - are common to many landscapes. When there is sufficient moisture, depressions take the form of lakes and wetlands; otherwise, they may be dry. Hydrological flow models used in geomorphology, hydrology, planetary science, soil and water conservation, and other fields often eliminate depressions through filling or breaching; however, this can produce unrealistic results. Models that retain depressions, on the other hand, are often undesirably expensive to run. In previous work we began to address this by developing a depression hierarchy data structure to capture the full topographic complexity of depressions in a region. Here, we extend this work by presenting the Fill-Spill-Merge algorithm that utilizes our depression hierarchy data structure to rapidly process and distribute runoff. Runoff fills depressions, which then overflow and spill into their neighbors. If both a depression and its neighbor fill, they merge. We provide a detailed explanation of the algorithm and results from two sample study areas. In these case studies, the algorithm runs 90-2600 times faster (with a reduction in compute time of 2000-63 000 times) than the commonly used Jacobi iteration and produces a more accurate output. Complete, well-commented, open-source code with 97 % test coverage is available on GitHub and Zenodo.
UR - http://www.scopus.com/inward/record.url?scp=85102038642&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102038642&partnerID=8YFLogxK
U2 - 10.5194/esurf-9-105-2021
DO - 10.5194/esurf-9-105-2021
M3 - Article
AN - SCOPUS:85102038642
SN - 2196-6311
VL - 9
SP - 105
EP - 121
JO - Earth Surface Dynamics
JF - Earth Surface Dynamics
IS - 1
M1 - 7
ER -