点群选取与化简算法时间复杂度研究

A Study on the Time Complexity of Point Cluster Selection and Simplification Algorithms

点群目标作为地图的基本要素,是普通地图及专题表达的重要内容.近年来,随着网络地图与移动地图的发展,兴趣点已成为最为重要的表达要素,其数据生产、更新与表达逐渐成为研究热点.针对点群要素的综合,选取与化简是两种常用的操作.传统的点群选取与化简算法主要是针对地图的自动生产,因此较侧重于点综合的质量,而随着GIS数据实时表达需求的增长和LBS服务的发展,对点综合算法的效率提出了更高的要求.本文在调研了常见点群选取与化简算法的基础上,按照实现原理的不同将算法分类,每一类中分别选取了一种具有代表性的算法,对其时间复杂度进行分析,并初步探讨了这些算法移植到并行计算环境下的可行性.这一研究将为点群选取与化简算法在网络地图及应急地图服务的应用与拓展奠定基础.

Being a basic element of the map,point feature is the important content of general and thematic map representation.With the development of web maps and mobile maps,point of interest（POI） has become the most important element to be represented,and the production,updating and visualization of POI is becoming a top issue in recent years.Facing to point cluster generalization,the selection and simplification operations are often adopted.However,the traditional point cluster selection and simplification algorithms mainly aim at the automatic production of paper maps,which concern more about the quality of the generalization instead of the efficiency.This may not satisfy the needs of the real-time representation of GIS data and the development of LBS services.In this paper,the previous algorithms of point selection and simplification are reviewed and classified into four categories according to their implementation principles.One representative algorithm of each category are selected to be particularly analyzed for their time complexities.The feasibility of being applied to the parallel environment is also discussed.The study of this paper will lay a foundation for the application and development of the point cluster selection and simplification algorithms in web mapping and emergency mapping services.