期刊文献+

基于Qi算法的Delaunay三角网逐点插入法 被引量:3

The Construction of Delaunay Triangulation Using Point-insertion Method Based on Qi Algorithm
下载PDF
导出
摘要 Delaunay三角网在很多领域都有着广泛的应用,快速高效地生成Delaunay三角网十分重要。逐点插入法是构建Delaunay三角网中使用最广泛的方法之一。本文深入研究了使用逐点插入法构建不带约束条件Delaunay三角网的过程。在使用该方法生成Delaunay三角网中建立结点拓扑关系这一影响构网效率的关键步骤中引入了Qi算法,简化了该方法生成Delaunay三角网的复杂度。然后在向Delaunay三角网内插入约束边的过程中,再次引入Qi算法,从而提高了构网的效率。为了验证上述模型,我们在Microsoft Visual Studio 2005开发环境下,以C#为开发工具,采用底层开发模式实现了改进的逐点插入法,实验证明引入Qi算法能够提高逐点插入法Delaunay三角网构建及插入约束边的效率。 Delaunay Triangulation has a wide range of application in various fields,and it is very important to generate Delaunay Triangulation efficiently.After analyzing the procedure of construction of Delaunay Triangulation without control boundary using point-insertion method,the authors introduced the Qi algorithm to the key step of building node-topology.The Qi algorithm was adopted again when inserting constrained boundaries into the Delaunay Triangulation to improve the efficiency.In order to verify the algorithm presented in this paper,the authors implemented algorithms using C in VS.NET.The experiment shows that the introduction of the Qi algorithm can improve the efficiency of building Delaunay Triangulation using point-insertion method.
出处 《遥感信息》 CSCD 2011年第1期92-96,共5页 Remote Sensing Information
基金 "十一五"国家科技支撑计划项目2006BAJ09B02
关键词 DELAUNAY三角网 拓扑关系 Qi算法 效率 delaunay triangulation topological relations Qi algorithm efficiency
  • 相关文献

参考文献11

  • 1吴立新 史文中.地理信息系统原理与算法[M].北京:科学出版社,2001..
  • 2邵春丽,胡鹏,黄承义,彭琪.DELAUNAY三角网的算法详述及其应用发展前景[J].测绘科学,2004,29(6):68-71. 被引量:65
  • 3Green P J. , Sibson R. Computing dirichlet tessellations in the plane[J]. The Computer Journal, 1978,21(2) :168-173.
  • 4Mc Cullagh M J ,Ross C G T. Delaunay triangulation of a random data set for lirarithmic mapping [J]. The Cartographic Journal, 1980(17) :93-99.
  • 5Lawson C L. Software for C surface interpolation[C] // RICE J R. Mathematical Software Ⅲ. New York:Academic Press, 1977 :161- 194.
  • 6Shanes M I,Hoey D. Closest-point problems [C] // Proceedings of the 16th IEEE Symposium on Foundations of Com- puter Science. Berkeley CA USA .. University of California, 1975:151 - 162.
  • 7吴燕来,朱莉.Delaunay三角网生成算法的研究与实现[J].计算机与信息技术,2007(3):21-22. 被引量:8
  • 8汤泉,牛铮.构建Delaunay三角网的改进算法[J].计算机应用,2007,27(B06):158-159. 被引量:13
  • 9Graham R L. An efficient algorithm for determining the convex hull of a finite planar set[J]. Info Proc Lett, 1972(1) :132-133.
  • 10齐华,刘文熙.建立结点上弧-弧拓扑关系的Qi算法[J].测绘学报,1996,25(3):233-235. 被引量:25

二级参考文献34

  • 1邵春丽,胡鹏,黄承义,彭琪.DELAUNAY三角网的算法详述及其应用发展前景[J].测绘科学,2004,29(6):68-71. 被引量:65
  • 2陈学工,陈树强,王丽青.基于凸壳技术的Delaunay三角网生成算法[J].计算机工程与应用,2006,42(6):27-29. 被引量:17
  • 3贺全兵,黎贵友,文进,杨萌.生成Delaunay三角网的改进算法[J].计算机与数字工程,2006,34(5):50-52. 被引量:10
  • 4李德仁.国际摄影测量与遥感学会的专业活动计划与研究方向(1988—1992)[J].测绘学报,1990,19(1):63-75. 被引量:3
  • 5[2]Lawson C L. Generation of a triangular grid with application to contour plotting[A]. In: Technical Memorandum [C],Institute of Technology, Jet Pollution Laboratory, California,1972:299.
  • 6[3]Lee D T and Schacher B J. Two algorithms for constructing a delaunay triangulation[J]. International Journal of Computer and Information Sciences, 1980,(9 ): 219-242.
  • 7[4]Dawyer R A.A fast divide-and-conquer algorithm for constructing Delaunay triangulations[J].Algorithmica, 1987, (2): 137-151.
  • 8[6]Macedonio G and Pareschi M T. An algorithm for the triangulation of arbitrarily distributed points: applications to volume estimate and terrain fitting[J]. Computers & Geosciences, 1991, 17: 859-874.
  • 9[7]Brassel K E and Reif D. Procedure to generate thissen polygons[J]. Geographical Analysis, 1979,11:289-303.
  • 10[8]Mc Cullagh M J and Ross C G T.Delaunay triangulation of a random data set for is arithmic mapping[J]. The Cartographic Journal,1980, 17:93-99.

共引文献223

同被引文献39

引证文献3

二级引证文献8

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部