«Previous Article|Table of Contents|Next Article»

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

Issue:

2012年01期

Page:

111-116

Research Field:

地理学

Publishing date:

Info

Title:

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

Author(s):

Yu Yanping¹; ²; ³; Shen Jie¹; ²; ³; Shang Zaiying¹; ²; ³

1.School of Geography Science,Nanjing Normal University,Nanjing 210046,China

Keywords:

point cluster; selection; simplification; algorithm; time complexity

PACS:

P283

DOI:

-

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:

-

Common functions

Last Update: 2013-03-11