基于排序预处理的等高线提取算法

The Extraction of Contour Lines from Grid DEM Based on Sorting

从规则高程格网中自动提取等高线是地理信息系统以及计算机制图的基本功能。针对当前高程格网数据的海量性,在以往工作的基础上提出了基于常规顺序索引和桶式索引的等高线提取算法。在具体实现中与以往工作提出的基于区间树的算法进行了详细的效率比较,认为桶式索引在预处理效率、查询效率和占用空间等各方面具有较大优势。最后给出了进一步工作的内容。

The extraction of contour lines from Grid DEM is a primary function in computer-aided cartography and GIS. The Grid DEM is being the main data source of elevation data due to the fast development of RS data acquiring technology. This paper designs new efficient algorithms to extract contour lines based on ordinary sorting index and bucket index. The algorithms facilitate the determination of heading point of contour line in massive Grid DEM, which has not been recognized carefully in existing research. The result is very encouraging on efficiency issue. We compared the result with our previous work based on interval tree and found that the algorithm based on the third index structure is optimal concerning the time of pre-processing, querying, runtime memory and easiness to implement.