An Efficient Algorithm for Calculating Drainage Accumulation in Digital Elevation Models Based on the Basin Tree Index

• Published in: IEEE geoscience and remote sensing letters 2015-02, Vol.12 (2), p.424-428
• Main Authors: Su, Cheng, Yu, Wei-bin, Feng, Cun-jun, Yu, Chun-na, Huang, Zhi-cai, Zhang, Xiao-can
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Basin; Buildings; Computational modeling; Digital elevation models; drainage accumulation; geographic information system (GIS); hydrology; Indexes; Sorting; Time complexity; watershed
• ISSN: 1545-598X; 1558-0571
• DOI: 10.1109/LGRS.2014.2345561

Calculating drainage accumulation in a digital elevation model (DEM) is a common requirement for hydrology and terrain analysis. This letter presents a basin tree index (BTI) algorithm to improve the efficiency of this calculation, achieving the time complexity of O(N) and the input-output efficiency of O(\hbox{Scan}(N)). We have developed a BTI to guide the calculation sequence, allowing us to avoid invalid and repeat manipulation and to reduce random scattered data access. The BTI provides a one-to-one correspondence between a basin and an outlet, and it maintains cells orderly in terms of both the elevation and the spatial distribution, as it is built by tracing the drainage path from the outlet to the source directly. This is achieved according to the drainage direction for each basin extracted from the DEM, where basins are divided based on watersheds. Therefore, the drainage accumulation can be calculated by traversing the BTIs from their leaves to roots linearly and simultaneously. These BTIs divide the entire study area into several basins that can be processed in isolation, reducing the search scope for basins and allowing the algorithm to efficiently utilize the main memory and decrease the data swapping between the main memory and the disk. A DEM for the Zhejiang Province in China was used to validate the results and compare the processing speeds. The results show that the algorithm provides the same calculation result as alternative algorithms but becomes more efficient as the volume of the DEM data increases. Furthermore, the BTI algorithm in this letter is easy to implement.