关键词: 数字高程模型, 填洼, 快速排序, 时间复杂度, 分级

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