文章基本信息

标题：Another Fast and Simple DEM Depression-Filling Algorithm Based on Priority Queue Structure
其他标题：Another Fast and Simple DEM Depression-Filling Algorithm Based on Priority Queue Structure
本地全文：下载
作者：Liu Yong-He ; Zhang Wan-Chang ; Xu Jing-Wen 等
期刊名称：Atmospheric and Oceanic Science Letters
印刷版ISSN：1674-2834
电子版ISSN：2376-6123
出版年度：2009
卷号：2
期号：4
页码：214-219
DOI：10.1080/16742834.2009.11446800
出版社：Taylor and Francis Ltd
摘要：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 inun-dated 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(8nlog 2 (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 25002500 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.
关键词：digital elevation models ; depression removing ; priority queue ; quick algorithm