[1]于艳平,沈婕,尚在颖,等.点群选取与化简算法时间复杂度研究[J].南京师大学报(自然科学版),2012,35(01):111-116.
　Yu Yanping,Shen Jie,Shang Zaiying.A Study on the Time Complexity of Point Cluster Selection and Simplification Algorithms[J].Journal of Nanjing Normal University(Natural Science Edition),2012,35(01):111-116.
点击复制

点群选取与化简算法时间复杂度研究()
分享到：

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

卷:
第35卷
期数:
2012年01期
页码:
111-116
栏目:
地理学
出版日期:
2012-03-20

文章信息/Info

Title:
A Study on the Time Complexity of Point Cluster Selection and Simplification Algorithms
作者:
于艳平1; 2; 3; 沈婕1; 2; 3; 尚在颖1; 2
( 1． 南京师范大学地理科学学院，江苏南京210046) ( 2． 虚拟地理环境教育部重点实验室，江苏南京210046) ( 3． 地理信息科学江苏省重点实验室，江苏南京210046)
Author(s):
Yu Yanping1; 2; 3; Shen Jie1; 2; 3; Shang Zaiying1; 2; 3
1.School of Geography Science,Nanjing Normal University,Nanjing 210046,China
关键词:
点群要素; 选取; 化简; 算法; 时间复杂度
Keywords:
point cluster; selection; simplification; algorithm; time complexity
分类号:
P283
摘要:
点群目标作为地图的基本要素，是普通地图及专题表达的重要内容． 近年来，随着网络地图与移动地图的发展，兴趣点已成为最为重要的表达要素，其数据生产、更新与表达逐渐成为研究热点． 针对点群要素的综合，选取与化简是两种常用的操作． 传统的点群选取与化简算法主要是针对地图的自动生产，因此较侧重于点综合的质量，而随着GIS 数据实时表达需求的增长和LBS 服务的发展，对点综合算法的效率提出了更高的要求． 本文在调研了常见点群选取与化简算法的基础上，按照实现原理的不同将算法分类，每一类中分别选取了一种具有代表性的算法，对其时间复杂度进行分析，并初步探讨了这些算法移植到并行计算环境下的可行性． 这一研究将为点群选取与化简算法在网络地图及应急地图服务的应用与拓展奠定基础．
Abstract:
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．

参考文献/References:

［1］ 王家耀． 普通地图制图综合原理［M］． 北京: 测绘出版社，1992．
［2］ Bereuter P，Weibel R． Generalisation of point data for mobile devices［C］/ /A problem-oriented approach: 13th Workshop of the ICA commission on Generalisation and Multiple Representation，Zurich，2010．
［3］ Langran C E，Poiker T K． Integration of name selection and name placement［C］/ /Proceedings of 2nd International Symposium on Spatial Data Handling． Seattle，Washington，USA，1986．
［4］ van Kreveld M，van Oostrum R，Snoeyink J． Efficient Settlement Selection for Interactive Display［C］/ /Proceeding of 12th Conference on Auto Carto． MD，USA，1997．
［5］ 毋河海． 凸壳原理在点群目标综合中的应用［J］． 测绘工程，1997( 1) : 1-6．
［6］ 艾廷华，刘耀林． 保持空间分布特征的群点化简方法［J］． 测绘学报，2002( 2) : 175-181．
［7］ 邓红艳，武芳，钱海忠等． 基于遗传算法的点群目标选取模型［J］． 中国图象图形学报，2003( 8) : 970-975．
［8］ 闫浩文，王家耀． 基于Voronoi 图的点群目标普适综合算法［J］． 中国图象图形学报，2005( 5) : 633-636．
［9］ Yan H W，Weibel R． An algorithm for point cluster generalization based on the Voronoi diagram［J］． COMPUTERS ＆ GEOSCIENCES， 2008，34( 8) : 939-954．
［10］ 钱海忠，武芳，谢鹏，等． 基于CIRCLE 特征变换的点群选取改进算法［J］． 测绘科学，2006( 5) : 69-70．
［11］ 蔡永香，郭庆胜． 基于Kohonen 网络的点群综合研究［J］． 武汉大学学报: 信息科学版，2007，32( 007) : 626-629．
［12］ 高三营，闫浩文，陈静静，等． 基于圆增长特征的点状要素群选取算法［J］． 测绘工程，2008( 6) : 20-23．
［13］ 周培德． 计算几何［M］． 北京: 清华大学出版社，2005．
［14］ Preparata F P，Shamos M I，庄心谷，等． 计算几何导论［M］． 北京: 科学出版社，1990．

备注/Memo

备注/Memo:
基金项目:国家自然科学基金( 41071288， 41171350) ．
通讯联系人:沈婕，博士，副教授，硕士生导师，研究方向: 地图自动综合并行计算、电子地图与网络地图设计． E-mail: shenjie@ njnu． edu． cn
更新日期/Last Update: 2013-03-11