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

约束Delaunay三角化在路线设计中的应用及其生成算法研究

Study of the applications of constrained delaunay triangulation in alignment and its creating algorithm

蒲浩　 詹振炎　 宋占峰　

摘　要：综合分析了CDT在路线设计中的应用,并提出了相应的解决方案.深入研究了适合各种应用的CDT构建算法,即先不考虑约束条件构建初级标准DT,再将约束边嵌入初始DT中的两步法.标准DT的构建采用改进和优化后的逐点插入算法,通过建立网格索引,实现数据的高效组织和管理,再结合方向搜索技术,研究出了三角形的快速定位算法.采用WATSON的"数据相关三角形"算法优化构网,为减少优化时间,提出了按网格轮流取点的策略.实践证明,该算法具有速度快、网形优、精度高、用途广的特点.
关键词：约束Delaunay三角化;数字地面模型;三维建模;不规则三角网
分类号：U412.3 　文献标识码：A
文章编号：1001-7372(2002)02-0022-06

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

参考文献：

［1］REPARATA F P.SHAMOS M I,庄心谷.计算几何导论[M].北京:科学出版社,1990.
［2］SAPIDIS N,PUCCHIO R. Delaunay triangulation of arbitrarily shaped planar domain[J]. Computer Aided Geometry Design, 1991,8(6) :421-437.
［3］BOISSINNAT J D. Shape reconstruction from plannar sections [ J ]. Computer Vision Graphics Image Process,1988,44(1) :1-29.
［4］JOE B.SIMPSON R B. Triangular meshes for regions of complicated shape [J]. International Journal for Numerical Methods in Engineering, 1986, 23 (5):751-778.
［5］FLORIANI L D. An online algorithm for constrained delaunay triangulation [J ]. CVGIP: Graphical Models and Image Processing, 1992,54 (3): 290-300.
［6］王福建,曾学贵,李方.三维表面模型在公路线形设计中的应用研究[J].中国公路学报,1 998.11(3):17-24.
［7］刘学军,符锌砂,赵建三.三角网数字地面模型快速构建算法研究[J].中国公路学报,2000,13(2):3l-36.
［8］蒲浩,宋占峰,詹振炎.基于Delaunay三角网数字地面模型的路线三维建模技术研究[J].铁道学报.2001,23(4):80-86.
［9］SHANES M I , HOEY D C . Closest - point problems[A]. Proceedings of the 16th Annual Symposium on the Fundations of Computer Science [ C ]. The University of California, Berkeley,IEEE, 1975. 151 -162.
［10］WATSON D F. Computing the n-dimension delaunay tesselation with application to voronoi polycopes[J ].Computer Journal, 1981,24 (2): 167- 172.


收稿日期：2001年4月28日

出版日期：2002年4月1日