[1]朱伟,沈婕,郭立帅.线要素光滑算法的时间复杂度分析[J].南京师大学报(自然科学版),2012,35(04):112-117.
　Zhu Wei,Shen Jie,Guo Lishuai.Analysis of the Time Complexity of Line Smoothing Algorithms[J].Journal of Nanjing Normal University(Natural Science Edition),2012,35(04):112-117.
点击复制

线要素光滑算法的时间复杂度分析()
分享到：

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

卷:
第35卷
期数:
2012年04期
页码:
112-117
栏目:
地理学
出版日期:
2012-12-20

文章信息/Info

Title:
Analysis of the Time Complexity of Line Smoothing Algorithms
作者:
朱伟1; 2; 3; 沈婕1; 2; 3; 郭立帅1; 2; 3
( 1． 南京师范大学地理科学学院，江苏南京210023) ( 2． 虚拟地理环境教育部重点实验室，江苏南京210023) ( 3． 地理信息科学江苏省重点实验室，江苏南京210023)
Author(s):
Zhu Wei1; 2; 3; Shen Jie1; 2; 3; Guo Lishuai1; 2; 3
1.School of Geography Science,Nanjing Normal University,Nanjing 210023,China
关键词:
线要素; 光滑算法; 时间复杂度; 并行算法
Keywords:
line;  smoothing algorithm;  time complexity; parallel algorithm
分类号:
TP391.41;P208
摘要:
线要素光滑算法是地图综合及地理信息可视化中的一类重要的算法,它可以实现线状地物的连续化表达,增强地图的表达效果.随着高性能GIS乃至云GIS的飞速发展,如何在并行计算环境和云计算环境中提高线要素光滑算法的效率,满足人们对地图综合的效率和地理信息表达的实时性需求成为该领域发展的关键问题.本文调研了常见的线要素光滑算法,按照拟合方式将算法分类,每一类中选取了一种代表性的算法,对其时间复杂度进行分析,并对这些算法的并行化进行了初步探讨.
Abstract:
Line smoothing algorithm is an important algorithm in map generalization and geo-information visualization． It can achieve a continuous representation of linear features， thus enhance the effect of map representation． With the rapid development of high-performance GIS and even cloud GIS， how to improve the efficiency of line smoothing algorithm in parallel and cloud environments， and to meet the demand of map generalization efficiency and real-time geo-information representation have become the key issues in this field． In this paper， the previous algorithms of line smoothing are reviewed and classified into four categories according to their fitting methods． One representative algorithm of each category is selected to be particularly analyzed for their time complexities． The way of parallelize these algorithms is also discussed．

参考文献/References:

［1］ 王鹏． 等值线快速绘图方法研究及系统设计与实现［D］． 成都: 电子科技大学通信学院， 2011．
［2］ Yu K． Performance improvement of Bezier spline fitting for more accurate approximation of natural linear entities［J］． KSCE Journal of Civil Engineering， 1999，3 ( 2) : 181-193．
［3］ 刘放，罗磊，胡俊，等． 复杂轮廓曲线的样条插补与速度规划方法［J］． 上海交通大学学报， 2009， 43( 5) : 834-836．
［4］ Zeng Y，Nguyen T A，Yan B， et al． A distance-based parameter free algorithm for curve reconstruction［J］． Computer-Aided Design， 2008， 40( 2) : 210-222．
［5］ 翟永强，刘正林． 计算机制图中一种新的曲线光滑方法［J］． 计算机工程与应用， 2003( 14) : 93-95．
［6］ Yue Y， Speckman P， Sun D． Priors for Bayesian adaptive spline smoothing［J］． Annals of the Institute of Statistical Mathematics， 2012， 64( 3) : 577-613．
［7］ 张凤蛟． 快速曲线拟合的方法［J］． 延边大学学报: 自然科学版， 2006， 32( 3) : 208-211．
［8］ 徐庆荣． 曲线插值中步长的确定［J］． 武汉测绘学院学报， 1983( 1) : 77-86．
［9］ 韩光瞬，郭金丽． 等高线光滑中不合理尖角钝化方法研究［J］． 北京测绘， 2010( 4) : 72-73．
［10］ 赵博，谈俊仲． 对MapInfo 系统中线状要素光滑的研究［J］． 测绘通报， 2005( 6) : 25-27．
［11］ 王延亮，王明爽． 新型曲线光滑法———切线抹角法［J］． 测绘通报， 2005( 3) : 52-54．
［12］ 潘正风，罗年学，黄全义． 近似斜轴抛物线加权平均插值法曲线光滑［J］． 测绘学报， 1991， 20( 1) : 60-65．
［13］ 李云锦，钟耳顺，黄跃峰． 斜轴抛物线插值的改进算法与近似算法［J］． 武汉大学学报: 信息科学版，2009，34( 12) : 1 490-1 494．
［14］ 孟雅琴，叶正麟，王小平，等． 空间均匀有理张力样条参数曲线［J］． 计算机学报， 2003， 26( 12) : 1 776-1 780．
［15］ 赵春宇． 高性能并行GIS 中矢量空间数据存取与处理关键技术研究［D］． 武汉: 武汉大学遥感信息工程学院， 2006．
［16］ 徐庆荣． 计算机地图制图原理［M］． 武汉: 武汉测绘科技大学出版社， 1993: 110-115．
［17］ 毋河海． 地图综合基础理论与技术方法研究［M］． 北京: 测绘出版社， 2004: 54 － 61．
［18］ Schweikert D． An interpolation curve using a spline in tension［J］． Journal of Mathmatical Physics， 1966，2 ( 45) : 312-317．
［19］ 王晓理． 在线光滑法优化线要素多尺度表示［C］/ /信息工程大学测绘学院第五届博士生学术论坛论文集． 郑州， 2010．
［20］ 张成岗，徐勇勇，陈长生． 曲线拟合中的几个问题［J］． 中国卫生统计， 1994， 11( 2) : 58-60．
［21］ 金旭亮． NET 4． 0 面向对象编程漫谈( 应用篇) ［M］． 北京: 电子工业出版社， 2010: 161．
［22］ 孙世新，卢光辉，张艳，等． 并行算法及其应用［M］． 北京: 机械工业出版社， 2005: 54 － 70．

备注/Memo

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