Journal of Computer Applications ›› 2009, Vol. 29 ›› Issue (11): 3161-3164.
• Typical applications • Previous Articles Next Articles
Bang YANG,Li-liang REN,Ying-qing HE
Received:
Revised:
Online:
Published:
Contact:
杨邦1,任立良1,贺颖庆2
通讯作者:
基金资助:
Abstract: A new ranked algorithm to fill sinks in Digital Elevation Models (DEM) was introduced, including an improved quicksort algorithm to rank DEM data in pieces and a filling algorithm first developed by Olivier Planchon and Frédéric Darboux in 2001 (The idea was first suggested by Moran and Vezina, so it’s called the M&V algorithm). Since removing the depressions of a DEM is usually a time-consuming procedure, the new method keeps the integrity and continuity of the drainage networks extracted by the pits-removed DEM and well reduces the depth of seeking path in iteration to accelerate pits-removing process. Different from the constant time complexity of traditional algorithms, the time complexity of the new method is variable, and the best performance for a natural terrain appears to be in 200 to 500 divided-pieces. The application of the new method in 6 study areas shows a time complexity of about O(n1.29) on average, which is more efficient than the M&V algorithm and Arcgis 9.2 (improved Jenson & Domingue algorithm).
Key words: Digital Elevation Model (DEM), sinks filling, quicksort, time complexity, rank
摘要: 数字高程模型(DEM)的填洼过程是水系提取中最耗费时间的过程,在Moran和Vezina提出的填洼思想(M&V填洼算法)的基础上,建立了基于快速排序的分级填洼算法,既能有效地减少填洼过程中的搜索路径,提高填洼效率,又能保证依此提取水系的完整与连贯。对于一个给定的DEM地形,传统的填洼算法的执行效率是固定的,而分级填洼的实际执行效率取决于分级数量,对于自然流域,一般200至500的分级量可使计算效率达到最高。通过在6个不同流域上的应用表明,在平均情况下,分级填洼算法的时间复杂度约为O(n1.29),其执行效率远高于M&V填洼算法及Arcgis 9.2(采用改进Jenson&Domingue算法)的执行效率。
关键词: 数字高程模型, 填洼, 快速排序, 时间复杂度, 分级
Bang YANG Li-liang REN Ying-qing HE. Ranked algorithm to fill sinks in digital elevation model based on quicksort[J]. Journal of Computer Applications, 2009, 29(11): 3161-3164.
杨邦 任立良 贺颖庆. 基于快速排序的数字高程模型分级填洼算法[J]. 计算机应用, 2009, 29(11): 3161-3164.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/
http://www.joca.cn/EN/Y2009/V29/I11/3161