skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 10:00 PM ET on Friday, December 8 until 2:00 AM ET on Saturday, December 9 due to maintenance. We apologize for the inconvenience.

Title: Computing water flow through complex landscapes – Part 3: Fill–Spill–Merge: flow routing in depression hierarchies
Abstract. 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.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Earth Surface Dynamics
Page Range / eLocation ID:
105 to 121
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract. Depressions – inwardly draining regions of digital elevation models – present difficulties for terrain analysis and hydrological modeling. Analogous “depressions” also arise in image processing and morphological segmentation, where they may represent noise, features of interest, or both. Here we provide a new data structure – the depression hierarchy – that captures the full topologic and topographic complexity of depressions in a region. We treat depressions as networks in a way that is analogous to surface-water flow paths, in which individual sub-depressions merge together to form meta-depressions in a process that continues until they begin to drain externally. This hierarchy can be used to selectively fill or breach depressions or to accelerate dynamic models of hydrological flow. Complete, well-commented, open-source code and correctness tests are available on GitHub and Zenodo. 
    more » « less
  2. Abstract. Calculating flow routing across a landscape is a routine process in geomorphology, hydrology, planetary science, and soil and water conservation. Flow-routing calculations often require a preprocessing step to remove depressions from a DEM to create a “flow-routing surface” that can host a continuous, integrated drainage network. However, real landscapes contain natural depressions that trap water. These are an important part of the hydrologic system and should be represented in flow-routing surfaces. Historically, depressions (or “pits”) in DEMs have been viewed as data errors, but the rapid expansion of high-resolution, high-precision DEM coverage increases the likelihood that depressions are real-world features. To address this long-standing problem of emerging significance, we developed FlowFill, an algorithm that routes a prescribed amount of runoff across the surface in order to flood depressions if enough water is available. This mass-conserving approach typically floods smaller depressions and those in wet areas, integrating drainage across them, while permitting internal drainage and disruptions to hydrologic connectivity. We present results from two sample study areas to which we apply a range of uniform initial runoff depths and report the resulting filled and unfilled depressions, the drainage network structure, and the required compute time. For the reach- to watershed-scale examples that we ran, FlowFill compute times ranged from approximately 1 to 30 min, with compute times per cell of 0.0001 to 0.006 s. 
    more » « less
  3. Abstract

    Prior to hydrologic modelling, topographic features of a surface are derived, and the surface is divided into sub‐basins. Surface delineation can be described as a procedure, which leads to the quantitative rendition of surface topography. Different approaches have been developed for surface delineation, but most of them may not be applicable to depression‐dominated surfaces. The main objective of this study is to introduce a new depression‐dominated delineation (D‐cubed) method and highlight its unique features by applying it to different topographic surfaces. The D‐cubed method accounts for the hierarchical relationships of depressions and channels by introducing the concept of channel‐based unit (CBU) and its connection with the concept of puddle‐based unit (PBU). This new delineation method implements a set of new algorithms to determine flow directions and accumulations for puddle‐related flats. The D‐cubed method creates a unique cascaded channel‐puddle drainage system based on the channel segmentation algorithm. To demonstrate the capabilities of the D‐cubed method, a small laboratory‐scale surface and 2 natural surfaces in North Dakota were delineated. The results indicated that the new method delineated different surfaces with and without the presence of depressional areas. Stepwise changes in depression storage and ponding area were observed for the 3 selected surfaces. These stepwise changes highlighted the dynamic filling, spilling, and merging processes of depressions, which need to be considered in hydrologic modelling for depression‐dominated areas. Comparisons between the D‐cubed method and other methods emphasized the potential consequences of use of artificial channels through the flats created by the depression‐filling process in the traditional approaches. In contrast, in the D‐cubed method, sub‐basins were further divided into a number of smaller CBUs and PBUs, creating a channel‐puddle drainage network. The testing of the D‐cubed method also demonstrated its applicability to a wide range of digital elevation model resolutions. Consideration of CBUs, PBUs, and their connection provides the opportunity to incorporate the D‐cubed method into different hydrologic models and improve their simulation of topography‐controlled runoff processes, especially for depression‐dominated areas.

    more » « less
  4. null (Ed.)
    The prevalence of mobile phones and wearable devices enables the passive capturing and modeling of human behavior at an unprecedented resolution and scale. Past research has demonstrated the capability of mobile sensing to model aspects of physical health, mental health, education, and work performance, etc. However, most of the algorithms and models proposed in previous work follow a one-size-fits-all (i.e., population modeling) approach that looks for common behaviors amongst all users, disregarding the fact that individuals can behave very differently, resulting in reduced model performance. Further, black-box models are often used that do not allow for interpretability and human behavior understanding. We present a new method to address the problems of personalized behavior classification and interpretability, and apply it to depression detection among college students. Inspired by the idea of collaborative-filtering, our method is a type of memory-based learning algorithm. It leverages the relevance of mobile-sensed behavior features among individuals to calculate personalized relevance weights, which are used to impute missing data and select features according to a specific modeling goal (e.g., whether the student has depressive symptoms) in different time epochs, i.e., times of the day and days of the week. It then compiles features from epochs using majority voting to obtain the final prediction. We apply our algorithm on a depression detection dataset collected from first-year college students with low data-missing rates and show that our method outperforms the state-of-the-art machine learning model by 5.1% in accuracy and 5.5% in F1 score. We further verify the pipeline-level generalizability of our approach by achieving similar results on a second dataset, with an average improvement of 3.4% across performance metrics. Beyond achieving better classification performance, our novel approach is further able to generate personalized interpretations of the models for each individual. These interpretations are supported by existing depression-related literature and can potentially inspire automated and personalized depression intervention design in the future 
    more » « less
  5. Abstract

    Thousands of small wetland depression features (cypress domes) dot the low‐relief karst of Big Cypress National Preserve (BICY) in South Florida, USA. We hypothesized that these wetland depressions are organized in a regular pattern, which is atypical of wetlandscapes elsewhere. Regular patterning implies the existence of coupled feedbacks operating at different spatial scales, with local wetland depression expansion (facilitation via karst dissolution) limited by competition among adjacent depressions for finite water resources (inhibition). We sought to test the hypothesis that wetlands in BICY exhibit regular patterning, and to quantify pattern properties to evaluate competing genesis mechanisms. We tested four predictions about landscape structure and geometry using high‐resolution Light Detection and Ranging elevation data from six 2.25‐km2domains across BICY. Specifically, we predicted (1) feature overdispersion resulting from competition between adjacent basins; (2) truncated wetland area distributions due to growth inhibition feedbacks; (3) periodicity in surface elevation indicating a characteristic pattern wavelength; and (4) elevation bimodality indicating distinct upland and wetland states. All four predictions were strongly supported. Depressions were significantly overdispersed and efficiently fill the landscape, generating hexagonal patterning. Wetland areas followed truncated power law scaling, indicating incremental constraints on basin expansion, in contrast to depression areas elsewhere. Variogram and radial spectrum analyses revealed clear periodicity (~150‐ to 250‐m wavelength) in surface elevations. Finally, surface elevations were consistently bimodal with elevation divergence of 10 to 40 cm. Regular patterning of wetland depressions across BICY is clear, implying long‐term biogeomorphic control on landform structure in this karst landscape.

    more » « less