【doc】基于最大外接圆的约束delaunay三角剖分算法.doc

【doc】基于最大外接圆的约束Delaunay三角剖分算法基于最大外接圆的约束Delaunay三角剖分算法2008年11月沈阳建筑大学(自然科学版)第24卷第6期JournalofShenyangJianzhuUniversity(NaturalScience):1671—2021(2008)06—1094—05基于最大外接圆的约束Delaunay三角剖分算法宋晓宇,戚爰伟,王永会(沈阳建筑大学信息与控制工程学院,辽宁沈阳110168)摘要:目的研究构建约束Delaunay三角网的方法,,以约束边为基边分别向两侧重新构网,先构建Delaunay三角网,然后插入约束边并删除与约束边相交的边,按照构网条件对约束边两侧的空腔构网,直至约束边两侧构建成三角网,,在地形点数为5000时,传统算法构建CDT时间为6195ms,笔者算法构建CDT时间为6007ms,,运算速度快,内存开销小且易于实现.;Delaunay三角网;基点;基边关键词:约束中图分类号:TP317文献标志码:A0引言在许多实际情况中,当利用离散点构建不规则三角网(work,TIN)时,不仅对三角形的形状有要求,而且对离散数据本身也有特殊要求[,某些点的连线(地表的山脊线,断裂线等)对TIN的局部合理性有决定性影响,,约束图法效率较低;分割合并算法效率较高但难实现;加密算法简单,易实现,但内存开销大;,对已有算法做了详细分析,并针对传统算法运算速度慢的缺点,以具代表性的两步法[4-5J为基础,利用生长法和分治法的思想,以约束边为基边分别向两侧重新构网,提出了基于最大外接圆的约束Delau—,基于常规Delaunay三角网算法的研究有很多,而地理信息系统(GeographicInformationSystem或Geo—Informationsystem,GIS)工作者在充分考虑地形特征(如地形线,地物等)情况下,,被证明是对数字地面最佳且唯一的表达【6_,,分割一合并算法,加密算法,Shell三角化算法和两步法[.其中,(初始三角网),然后引人约束线段以嵌入之(调整过程).目前该算法的研究比较多,其中以Bemal,,而在调整过程中使之满足约束线段条件;Flo—riani的算法更具灵活性,只建立非约束数据点的初始三角网,,要求可交换对角线的四边形是严格凸的,,但其实现收稿日期:2007—11—12基金项目:国家十五科技攻关项目(2006BAJ06B08—03)作者简介:宋晓宇(1963一),男,教授,博士,主要从事管理信息系统与数据挖掘,图像处理技术研究第24卷宋晓宇等:基于最大外接圆的约束Delaunay三角剖分算法1095过程是递归执行,执行效率较高,但内存开销较大[.笔者以两步法为基础,利用生长法和分治法的思想,提出了基于最大外接圆的约束Delau—,定义了基边,:,当每次构网时,(有向)为PlP2…(?2),首先在离散点中加入约束线段顶点P,P2,…,P,构建Delaunay三角网;然后插入约束边,对三角网进行局部调整以满足P尸(i,J<),删除与P相