Treffer: An efficient flow path traversal algorithm for watershed delineation from raster digital elevation models for multicore architectures.

Watersheds are important inputs in many geospatial applications and watershed delineation is a fundamental task of hydrological processing. Existing efficient watershed delineation algorithms are either designed to exploit the massive parallelism of graphic processing units (GPUs) or rely on specific spatial patterns of watersheds to parallelize efficiently on multicore central processing units. In this study, we propose an efficient flow path traversal algorithm for delineating watersheds from raster flow direction grids. The proposed algorithm employs a novel tracing strategy and traces each cell until a cell with a known watershed label is encountered or the tracing terminates outside the study area. This approach limits the number of times each cell is processed to a constant, does not require any additional data structure, and achieves a time complexity of O(N) regardless of the number of watersheds to be delineated. We conducted three experiments using seven flow direction grids to evaluate the running times, speedups, both strong and weak parallel efficiencies of the algorithms. Our sequential algorithm outperforms two other sequential algorithms on the test DEMs even though those algorithms only process approximately one-third of the DEM cells, while our algorithm processes the entire grid. Our parallel algorithm runs the fastest among all sequential and parallel algorithms evaluated. Combined with highly efficient GPU-based algorithms, the sequential and multicore parallel implementations of our flow path traversal algorithm make it possible to fully leverage the computational capabilities of personal computers for high-performance watershed delineation. [Display omitted] • A novel efficient algorithm and its parallel version for delineating watersheds are proposed. • The time complexity does not depend on the number of watersheds to be delineated. • The algorithm is the fastest among existing sequential algorithms. • The OpenMP parallel version is the fastest among all algorithms for multicore architectures. [ABSTRACT FROM AUTHOR]

Copyright of Environmental Modelling & Software is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)