Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
A Watershed Delineation Algorithm for 2D Flow Direction Grids
arXiv (Cornell University)
01 Aug 2017
Abstract
In this paper we propose an algorithm and associated data model for creating
a watershed boundary using a 2D Flow Direction Grid. Flow Direction Grids
(FDGs) are common abstractions for hydrodynamic models and are utilized for
delineating physical systems (e.g. watersheds, fluvial, and non-fluvial flow
paths). The proposed algorithm and associated data model provides geometric
speed increases in watershed boundary retrieval while keeping storage
constraints linear in comparison to existing techniques. The algorithm called
Haag Shokoufandehs' March (HSM) relies on an existing data structure, the
modified nested set model, originally described by Celko and applied to
hydrodynamic models by Haag and Shokoufandeh in 2017. The proposed algorithm
creates watershed boundaries by marching around the edges of its' corresponding
region, never entering the internal area. In contrast to existing algorithms
that scales in proportional to the area of the underlying region, the
complexity of the HSM algorithm is proportional to the boundary length. Results
for a group of tested watersheds (n = 14,718) in the approximately 36,000 km^2
Delaware River Watershed show a reduction of between 0 and 99% in computational
complexity using a 30 m DEM vs. existing techniques. Larger watersheds have a
consistent reduction in the number of (read) operation complexity, with the
largest watershed resulting in approximately 35 million reads using traditional
techniques compared to approximately 45 thousand using the HSM algorithm,
respectively. Modelled estimates of the complexity for the approximately 6.1
million km^2 Amazon River basin show a reduction from 6.7 billion to 1.4
million reads.
Metrics
5 Record Views
Details
- Title
- A Watershed Delineation Algorithm for 2D Flow Direction Grids
- Creators
- Scott HaagAli Shokoufandeh
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991021862302804721