|Table of Contents|

Analysis of the Time Complexity of Line Smoothing Algorithms(PDF)

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

Issue:
2012年04期
Page:
112-117
Research Field:
地理学
Publishing date:

Info

Title:
Analysis of the Time Complexity of Line Smoothing Algorithms
Author(s):
Zhu Wei123Shen Jie123Guo Lishuai123
1.School of Geography Science,Nanjing Normal University,Nanjing 210023,China
Keywords:
line smoothing algorithm time complexityparallel algorithm
PACS:
TP391.41;P208
DOI:
-
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:
-
Last Update: 2013-03-11