线要素化简算法的时间复杂度分析

摘要

Liner element is the largest various elements in the map and its simplification is very important in automatic map generalization. There has been a lot of work on the improvement of these algorithms, quality assessment and geometric accuracy of these line simplification algorithms. But the work on the efficiency of these algorithms is less. The efficiency of the line simplification algorithms was studied on the basis of considering the simplifying quality. The line simplification algorithms were divided into six categories through analyzing its constraint parameters, several typical algorithms were selected and its time complexity were analyzed. The line simplification algorithms were divided into two categories, such as linear and nonlinear algorithm through analyzing its time complexity features. And the parallel computing environment which was suitabe to these two types of algorithms were preliminary studied.%线状要素是地图中数量最大、要素类型最多样的要素,其化简在地图自动综合中占据了重要的地位.目前对线状要素化简算法的改进、化简质量、化简精度等方面的研究较多,对线状要素化简算法的效率研究较少.此处是在兼顾化简质量的前提下研究算法效率,通过分析化简算法约束参数的特征,将线状要素化简算法分为6类,选取其中的几个典型算法,分析了其时间复杂度,并按照线状要素化简算法的时间复杂度将其分为线性算法和非线性算法两类,初步探讨了适合这两类算法的并行计算方法.