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作者机构：Key Laboratory of Regional Climate-Environment Research for Temperate East Asia Institute of Atmospheric Physics Chinese Academy of Sciences Beijing 100029 China Center for Hydro-Sciences Research Nanjing University Nanjing 210093 China
出 版 物：《Atmospheric and Oceanic Science Letters》 (大气和海洋科学快报)
年 卷 期：2009年第4期
页 面：213-218页
基 金：financially supported by the National Basic Research Program of China (Grant No.2006CB400502) the Promotion of 100 Young Talent Scientist Project of the Chinese Acad-emy of Sciences (8-057493) the Special Meteorology Project(GYHY(QX)2007-6-1)
主 题：digital elevation models depression remov-ing priority queue quick algorithm
摘 要：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 *** depression-filling algorithm presented by Planchon and Darboux works very quickly compared to other published *** its simplicity and deli-cacy,this algorithm remains difficult to understand due to its three complex subroutines and its recursive *** fast algorithm is presented in this *** 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 *** depression-removing processing is performed using a priority ***,this new algorithm is a fast algorithm despite the fact that it runs more slowly than Planchon and Darboux’s *** 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 *** shown by the tests,the depres-sion-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 *** 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.
同方期刊数据库