保持拓扑一致性的等高线化简算法研究

Study on Simplification of Contour Lines Preserving Topological Coherence

等高线的化简是地图综合中的一个重要问题。而拓扑一致性的维持是化简的难点,应用常规的Douglas-Peucker算法可能引发相交和自相交。引入了基于约束Delaunay三角剖分和自适应单调链的等高线拆分算法,并在理论上证明了对拆分后的子曲线化简将不会产生拓扑异化。在实验中,该算法能将数据量压缩至10%,并依然未产生相交和自相交。

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.