改进的构建约束Delaunay三角网的算法.pdfVIP

北京石油化工学院学报 第 18卷 第 2期 Vo1．18 NO．2 JournalofBeijingInstituteof 2010年 6月 Jun．2O10 Petro—chemicalTechnology 改进的构建约束 Delaunay三角网的算法六 颜 林 朱永杰 (1．北京化工大学 ，北京 100029；2．许 昌学院，许 昌 461lOO) 摘 要 当前构建约束 Delaunay三角网的算法在影响域为凹多边形的情况下不是很稳定 ， 甚至失效 。在介绍 了Delaunay三角网的相关的概念和算法基础上 ，重点研究了约束 Delaunay三角网生 成算法以及影响域为凹多边形的相关 问题 ，提 出基于对角线交换的改进算法 。实验表 明，该算法能够解 决影响域为凹多边形等的各种特殊情况 ，程序稳定简单 ，易实现 。 关 键 词 Delaunay三角网；约束边 ；对角线 ；凹多边形 中图法分类号 TP312 近年来随着科技的进步 ，计算机图形学逐 L一{P J EP，PE-P，P，P 的二端点}组 渐成为计算机领域研究热点之一 ，构建不规则 成 ，并且 L 中任意两条直线段之间除端点外没 三角网(TriangulatedIrregularNetwork，简称 有其它交点。PSLG扩展 了传统 的以内、外环 TIN)是三维建模 、有 限元分析 、可视化等领域 定义平面 图形的方式 ，可 以表示任 意复杂的正 的一项重要 的应用 技术 。特别 是约束 Delau— 则及非正则图形 。三角网可 以看作一个平面直 nay三角网格化 问题更是人们研 究 的对象 ，因 线 图。 为约束 Delaunay三角 网是三角剖分 中最优且 定义 2 嵌入边 的影响域是指要嵌入的边 它使用原始数据建模 ，更能准确地 、客观地反应 e与已经构建成 Delaunay三角 网中的相交 的 真实信息 。在地质领域 ，像等高线 、断裂线等这 三角形组成的多边形 。 些大量 的离散数据 并不是独立的，而是存在一 定义 3 影响域 的对角线指与嵌入边 e相 定约束关系 ，若在构建三角网中没有约束数据 ， 交的边 。 那 么生成 的模 型不能准确表达地表 的复杂关 定义 4 非端点相交是指两条线段相交 ， 系。国内外大量学者对此进行 了研究 ，对 于构 交点不是端点 。 建非约束 Delaunay三角网算法相对成熟 ，取得 定理 1 对于采用 PSIG作为输入的任意 较好的研究成果，但是在构建约束 Delaunay三 复杂多边形 ，总可以通过普通边交换对其实现 角 网尤其是在不加附加点算法还不是很成熟 ， 约束 Delaunay三角剖分 ，边交换的次数在最坏 还需进一步研究 。因此 ，笔者重点研 究约束 的情况下为 O(”)，其 中，”为 P 中的点的个 Delaunay三角网生成算法 ，提出一种不添加附 数。该定理说 明了基于边交换 的约束 Delau— 加点 的对角线交换改进算法 。 nay三角剖分算法总是收敛 的口]，同时也可以 得到笔者所采用的基于对角线交换来实现对凹 1 基本概念 多边形 的约束 Delaunay三角剖分算法的收敛