全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
-  2008 

一种快速生成平面Delaunay三角网的横向扩张法

Keywords: Delaunay三角网,快速算法,LOP优化,不规则三角网,时间复杂度

Full-Text   Cite this paper   Add to My Lib

Abstract:

摘要: 目前已有多种基于平面上离散点集构造Delaunay三角网的算法,其中三角网扩张法、逐点插入法的平均时间复杂度为O(n2),分治算法和其他分块合并算法能使平均时间复杂度接近线性,但增加了算法的复杂性,从而使浮点计算误差错误发生的机率增大。本文作者提出了一种新算法:将用于构网的离散点集先按横坐标从小到大排序,在空间上表现为从左到右排列;然后先以点序列中的前三个点作为初始三角网,每次将剩余点集中最左边的点联入三角网,最终得到一个三角剖分,再用LOP法优化三角剖分。该算法的优势是具有快速的三角剖分过程,使整体的平均时间复杂度为O(n),并且构网效率高,算法简单。

References

[1]  Green P J,Sibson R1 Computing D irichlet Tessellations inthe Plane.The Computer Journal,1978,21(2):168~173.
[2]  王家耀.空间信息系统原理.北京:科学出版社,2001.
[3]  吴立新,史文中.地理信息系统原理与算法.北京:科学出版社,2001.
[4]  Lawson.Software for C’Surface Interpolation.In M athematical Software(J R R ice ed.),Academ ic Press,NewYork,1977,161~194.
[5]  M I Shamos,D Hoey.Closet2point p roblem.In:Proceedings of 16thIEEE Symposium on Foundations of Computer Science,Berkeley,California,1975,(151):162.
[6]  Lee D T,Schachter B J.Two algorithm s for constructing aDelaunay triangulation.International Jounal of Computerand Information Science,1980,9(3):219~242.
[7]  Rex A Dwyer.A fast D ivide2and2Conquer algorithm forconstructing Delaunay triangulations.A lgorithm ica,1987,(2):137~151.
[8]  蒋红斐.基于分治算法构建Delaunay三角网的研究.计算机工程与应用,2003,(16):81~83.
[9]  胡金星,潘懋,马照亭.高效构建Delaunay三角网数字地形模型算法研究.北京大学学报(自然科学版),2003,39(5):736~741.
[10]  蒲浩,宋占峰,詹振炎.快速构建Delaunay三角网算法研究.铁道学报,2001,23(5):85~91.
[11]  徐青,常歌,杨力.基于自适应分块的TIN的三角网建立算法.中国图象图形学报,2000,5(6).
[12]  武晓波,王世新,肖春生.一种生成Delaunay三角网的合成算法.遥感学报,2000,4(1):32~35.
[13]  郭兆胜,张登荣.一种改进的高效Delaunay三角网的生成算法.遥感信息,2005,(1):15~17.
[14]  Law son C L.Generation of a triangular grid w ith app lication to contour p lotting.In:TechnicalM emorandum,In2stitute of Technology,Jet Pollution Laboratory,California,1972,2991.
[15]  陈慧群,陈少克.一种基于格子分块的快速Delaunay三角剖分算法.计算机与数字工程,35(2):9~20.
[16]  何俊,戴浩,谢永强等.一种改进的快速Delaunay三角剖分算法.系统仿真学报,2006,18(11):2055~3057.
[17]  徐道柱,刘海砚.Delaunay三角网建立的改进算法.测绘与空间地理信息,2007,30(1):38~40.
[18]  曾闽山,田冬玲,郭吉民.一种基于格网划分的高效Delaunay三角网格化算法.微计算机信息(管控一体化),2006,22(31~3):127~129.
[19]  方勇,刘鹏,胡海彦.一种Delaunay三角网的快速生成算法.测绘科学与工程,2006,26(3):1~4.
[20]  贺全兵,黎贵友,文进等.生成Delaunay三角网的改进算法.计算机与数字工程,2006,34(5):50~52.
[21]  刘永和,谢洪波,袁策.一种基于三角网扩张法的Delaunay三角网逐块归并算法.测绘科学,2007,32(3):52~54.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133