中国公路学报
CHINA JOURNAL OF HIGHWAY AND TRANSPORT
2002 Vol.15 No.3 P.18-22

约束Delaunay三角剖分动态算法研究

Dynamical algorithm for constructing constrained delaunay triangulation

宋占峰　 詹振炎　 蒲浩　

摘　要：提出了动态建立约束Delaunay三角剖分(CDT)的算法,即在三角网剖分中可以动态地插入点或约束边,因此,该算法构建CDT的点集是可以动态扩充的.通过对动态算法的执行过程分析得出,在约束边已知的条件下,应尽早在三角剖分中嵌入约束边.这样,相对于传统算法,不仅能减少嵌入约束边的时间,同时也能减少插入点重新构网的时间.最后,通过实例比较了动态算法构建CDT、传统算法构建CDT和只构建标准Delaunay三角剖分三者间的时间效率,得出动态算法优于传统算法的结论.
关键词：约束Delaunay三角剖分;算法;数字地面模型;拓扑关系
分类号：U412.2　文献标识码：A
文章编号：1001-7372(2002)03-0018-05

基金项目：铁道部科技发展计划项目(97G23-F;96G30G-1);湖南省科委项目(01-961-18-4)
作者简介：宋占峰(1973-),男,河南杞县人,中南大学讲师,工学博士研究生.
作者单位：宋占峰（中南大学土木建筑学院,湖南,长沙,410075）　
　　　　　詹振炎（中南大学土木建筑学院,湖南,长沙,410075）　
　　　　　蒲浩（中南大学土木建筑学院,湖南,长沙,410075）　

参考文献：

［1］SLOAN S W. A fast algorithm for constructing delaunay triangulation in the plane [J]. Advanced Engineering Software, 1987,9 (1): 34-55.
［2］李立新,谭建荣.约束Delaunay三角网剖分中强行嵌入约束边的对角线交换算法[J].计算机学报,1999,22(10):1 114-1 118.
［3］周晓云,刘慎权.实现约束Delaunay三角剖分的健壮算法[J].计算机学报,1996,19(8):613-624.
［4］刘学军,龚健雅.约束数据域的Delaunay三角剖分与修改算法[J].测绘学报,2001,30(1):82-88.
［5］刘学军,符锌砂,赵建三.三角网数字地面模型快速构建算法研究[J].中国公路学报,2000,13(2):31-36.
［6］OHYA T,IRI M,MUROTA K. Improvements of the incremental methods for the voronoi diagram with computational comparison of various algorithms [J].Oper. Res. Soc. Japan, 1984,27(2) :151-163.
［7］LEE D T , SCHACHTER B J . Two algorithms for constructing a delaunay triangulation [J]. int. J. of Computer and Information Science, 1980, 9 (3): 219-242.


收稿日期：2001年8月18日

出版日期：2002年7月1日