期刊文献+

构建Delaunay三角网的一种新型生长法——壳外插入法 被引量:7

A new growth algorithm for creating delaunay triangulation:outside insertion algorithm
下载PDF
导出
摘要 基于逐点插入法中影响域的概念,提出一种新的三角网生长算法——壳外插入法。该算法以三角网外围的凸包生长为基础,通过查找生长边、内蚀既有网、重构三角网3个基本操作,达到既有网在保持Delaunay特性的同时纳入新点,从而实现三角网的生长。该算法克服了传统生长法需要查找第3点的缺陷,也避免了逐点内插法大量三角形定位的操作,因而算法的平均复杂度达到O(NlogN)。使用了大量的随机散点数据和常吉高速的实测地形点数据对算法进行测试,证实该算法快速有效。 The influential area which was a concept of incremental insertion algorithm was introduced and a new growth algorithm was presented.The method of fast creating Delaunay triangulation was named as outside insertion algorithm.The algorithm bases on the growth of convex hull,and through finding growth edges,eroding the existing net and restructuring these three essential operations to keep Delaunay character while bringing a new point into the net during the process.Using the algorithm,the disadvantages of finding the third point in the traditional growth algorithm was avoided and the mass operations that locate the triangles in the incremental insertion algorithm.So the average complexity of the algorithm is O(NlogN).The algorithm was tested with mass random points data and the real terrain points data from Chang-Ji expressway.The result proves that the algorithm is fast and efficiency.
出处 《铁道科学与工程学报》 CAS CSCD 北大核心 2007年第6期67-72,共6页 Journal of Railway Science and Engineering
基金 交通部西部交通建设科技项目(2003-318-802-01) 湖南省交通建设科技项目(2006-8)
关键词 三角剖分 DELAUNAY三角网 生长法 数字地面模型 triangulation delaunay triangulation growth algorithm digital terrain model
  • 相关文献

参考文献10

二级参考文献21

  • 1周晓云,刘慎权.实现约束Delaunay三角剖分的健壮算法[J].计算机学报,1996,19(8):615-624. 被引量:54
  • 2毋河海.地图数据库系统[M].北京:测绘出版社,1991..
  • 3柯正谊,数字地面模型,1993年
  • 4毋河海,地图数据库系统,1991年
  • 5柯正谊,数字地面模型,1993年
  • 6胡友元,计算机地图制图,1987年
  • 7Tsai V J D.Delaunay Triangulations in TIN Creatation:an Overview and a Linear-time Algorithm[J].Int Journal of GIS,1993,7(6):501-524.
  • 8Watson D F.Computing the n-dimension Delaunay Tesselation with Application to Voronoi Polytopes[J].Computer Journal,1981,24(2):167-172.
  • 9Sloan S W.A Fast Algorithm for Constructing Delaunay Triangulation in the Plane[J].Advanced Engineering Software,1987,9(1):34-55.
  • 10Lee D T,Schachter B J.Two Algorithm for Constructing a Delaunay Triangulation[J].International Journal of Computer and Information Science,1980,9(3):219-242.

共引文献399

同被引文献59

引证文献7

二级引证文献66

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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