|
|
|
| Another Fast and Simple DEM Depression-Filling Algorithm Based on Priority Queue Structure |
| LIU Yong-He,ZHANG Wan-Chang,XU Jing-Wen |
| Key Laboratory of Regional Climate-Environment Research for Temperate East Asia, Institute of Atmospheric Physics, Chinese Academy of Sciences, Beijing 100029,Center for Hydro-Sciences Research, Nanjing University, Nanjing 210093,Key Laboratory of Regional Climate-Environment Research for Temperate East Asia, Institute of Atmospheric Physics, Chinese Academy of Sciences, Beijing 100029 |
|
|
|
|
Abstract Some depression cells with heights lower than their surrounding cells may often be found in Grid-based digital elevation models (DEM) dataset due to sampling errors. The depression-filling algorithm presented by Planchon and Darboux works very quickly compared to other published methods. Despite its simplicity and delicacy, this algorithm remains difficult to understand due to its three complex subroutines and its recursive execution. Another fast algorithm is presented in this article. The main idea of this new algorithm is as follows: first, the DEM dataset is viewed as an island and the outer space as an ocean; when the ocean level increases, the DEM cells on the island’s boundary will be inundated; when a cell is inundated for the first time, its elevation is increased to the ocean level at that moment; after the ocean has inundated the entire DEM, all of the depressions are filled. The depression-removing processing is performed using a priority queue. Theoretically, this new algorithm is a fast algorithm despite the fact that it runs more slowly than Planchon and Darboux’s method. Its time-complexity in both the worst case and in an average case is O(8nlog2(m)), which is close to O(n). The running speed of this algorithm depends mainly on the insertion operation of the priority queue. As shown by the tests, the depression-filling effects of this algorithm are correct and valid, and the overall time consumption of this algorithm is less than twice the time consumed by Planchon & Darboux’s method for handling a DEM smaller than 2500×2500 cells. More importantly, this new algorithm is simpler and easier to understand than Planchon and Darboux’s method. This advantage allows the correct program code to be written quickly.
|
|
Received: 20 April 2009
Revised: 27 June 2009
Accepted: 27 June 2009
|
|
|
|
|
|
|
