Zhou et al. (2025) An efficient flow path traversal algorithm for watershed delineation from raster digital elevation models for multicore architectures

Identification

• Journal: Environmental Modelling & Software
• Year: 2025
• Date: 2025-10-18
• Authors: Guiyun Zhou, Zihao Zhang, Suhua Fu, Jiayuan Lin
• DOI: 10.1016/j.envsoft.2025.106743

Research Groups

• School of Resources and Environment, University of Electronic Science and Technology of China, Chengdu, China
• State Key Laboratory of Earth Surface Processes and Disaster Risk Reduction, Faculty of Geographical Science, Beijing Normal University, Beijing, China
• Chongqing Jinfo Mountain Karst Ecosystem National Observation and Research Station, School of Geographical Sciences, Southwest University, Chongqing, China

Short Summary

This study proposes a novel and efficient flow path traversal algorithm for watershed delineation from raster flow direction grids, specifically designed for multicore central processing unit (CPU) architectures, demonstrating superior performance compared to existing sequential and parallel methods.

Objective

• To develop and evaluate an efficient flow path traversal algorithm for delineating watersheds from raster flow direction grids, optimized for multicore CPU architectures.

Study Configuration

• Spatial Scale: Not explicitly stated for the test digital elevation models (DEMs), but applicable to raster DEMs of varying sizes.
• Temporal Scale: Not applicable, as the study focuses on the computational performance of an algorithm.

Methodology and Data

• Models used: Proposed "flow path traversal algorithm" for watershed delineation, implemented with OpenMP for parallel computing.
• Data sources: Raster digital elevation models (DEMs) processed into single-flow direction grids. Seven different flow direction grids were used for evaluation.

Main Results

• The proposed sequential algorithm outperforms two other sequential algorithms on test DEMs, even though it processes the entire grid while others process approximately one-third.
• The proposed parallel algorithm runs the fastest among all evaluated sequential and parallel algorithms.
• The algorithm achieves a time complexity of O(N) regardless of the number of watersheds, processes each cell a constant number of times, and requires no additional data structure.
• Experiments demonstrated high running times, speedups, and both strong and weak parallel efficiencies.

Contributions

• Introduction of a novel flow path traversal algorithm with an efficient tracing strategy for watershed delineation.
• Development of a highly efficient multicore parallel implementation (using OpenMP) that significantly outperforms existing sequential and parallel algorithms.
• Achieves optimal time complexity (O(N)) and constant cell processing, without requiring additional data structures.
• Enables full leverage of personal computer computational capabilities for high-performance watershed delineation, complementing GPU-based approaches.

Funding

• Not explicitly stated in the provided text.

Citation

@article{Zhou2025efficient,
  author = {Zhou, Guiyun and Zhang, Zihao and Fu, Suhua and Lin, Jiayuan},
  title = {An efficient flow path traversal algorithm for watershed delineation from raster digital elevation models for multicore architectures},
  journal = {Environmental Modelling & Software},
  year = {2025},
  doi = {10.1016/j.envsoft.2025.106743},
  url = {https://doi.org/10.1016/j.envsoft.2025.106743}
}