关键词: 等高线, 拓扑一致性, D-P算法, 安全拆分

Abstract: Contour lines are lines connecting points of equal elevation. In maps of smaller scale derived from original map, they should be simplified so as to have acceptable visual effect for the target scale representation and hence simplification of contour lines is known as an important issue in cartographic generalization. There are many researches on line simplification. Among all the algorithms, Douglas-Peucker algorithm is recognized as the most visually effective way, which delivers the best perceptual representations of the original lines. On the other hand, classical D-P algorithm also has some drawbacks especially potential topological error. It is difficult to preserve topological consistency between simplified lines and original lines. Self-intersection or intersection of generalized lines may be yielded after D-P algorithm. In this paper, a pre-processing algorithm is proposed to divide contour lines safely based on constrained Delaunay triangulation and self-adaptive monotone chain, which is theoretically proved to preserve topological coherence after sequent D-P algorithm. Testing results show that original data can be compressed down to 10% through simplification, while no intersection or self-intersection occurs.

Key words: contour lines, topological coherence, Douglas-Peucker algorithm, safe split