Journal
GEOMORPHOLOGY
Volume 238, Issue -, Pages 56-67Publisher
ELSEVIER
DOI: 10.1016/j.geomorph.2015.02.028
Keywords
Binary search tree; Depression filling; Digital elevation model; Drainage network extraction; Least-cost path search
Funding
- National Basic Research Program (973 program) of China [2013CB036402]
- National Key Technologies Research and Development Program of China [2013BAB05B03]
- R&D Special Fund for Public Welfare Industry of the Ministry of Water Resources in China [201301081, 201001015]
- State Key Laboratory of Hydroscience and Engineering [2014-KY-01]
Ask authors/readers for more resources
With the increasing resolution of digital elevation models (DEMs), computational efficiency problems have been encountered when extracting the drainage network of a large river basin at billion-pixel scales. The efficiency of the most time-consuming depression-filling pretreatment has been improved by using the O(NlogN) complexity least-cost path search method, but the complete extraction steps following this method have not been proposed and tested. In this paper, an improved O(NlogN) algorithm was proposed by introducing a size-balanced binary search tree (BST) to improve the efficiency of the depression-filling pretreatment further. The following extraction steps, including the flow direction determination and the upslope area accumulation, were also redesigned to benefit from this improvement. Therefore, an efficient and comprehensive method-was developed. The method was tested to extract drainage networks of 31 river basins with areas greater than 500,000 km(2) from the 30-m-resolution ASTER GDEM and two sub-basins with areas of approximately 1000 km(2) from the 1-m-resolution airborne LiDAR DEM. Complete drainage networks with both vector features and topographic parameters were obtained with time consumptions in O(NlogN) complexity. The results indicate that the developed method can be used to extract entire drainage networks from DEMs with billions of pixels with high efficiency. (C) 2015 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available