第１５卷第６期 ２００３年１２月 海军工程大学学报
ＪＯＵＲＮＡＬ ０Ｆ ＮＡＶＡＬ ＵＮＩＶＥＲＳＩＴＹ ＯＦ ＥＮＧＩＮＥＥＲＩＮＧ Ｖ０１．１５ Ｎｏ．６
Ｄｅｃ．２００３
文章编号：１００９—３４８６（２００３）０６—００４９—０３
二维约束点集Ｄｅｌａｕｎａｙ三角剖分算法研究
崔汉国，方锡武，简宪华 （海军工程大学基础部，湖北武汉４３００３３） 摘要：在已有算法基础上，提出了任意二维约束点集Ｄｅｌａｕｎａｙ三角剖分的新算法，算法仅在局部产生少量 新点，并在局部对三角剖分进行修改，便可保证整体三角剖分符合Ｄｅｌａｕｎａｙ性质． 关键词：二雏三角剖分；Ｄｅｌａｕｎａｙ三角剖分；计算几何；网格生成 中图分类号：ＴＰ３９１ 文献标识码：Ａ
Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ ａｒｂｉｔｒａｒｉｌｙ ｓｈａｐｅｄ ｐｌａｎａｒ ｄｏｍａｉｎｓ ＣＵＩ Ｈａｎ—ｇｕｏ，ＦＡＮＧ Ｘｉ—ＷＵ，ＪＩＡＮ Ｘｉａｎ－ｈｕａ （Ｄｅｐｔ．ｏｆ Ｂａｓｉｃ Ｃｏｕｒｓｅｓ，Ｎａｖａｌ Ｕｎｉｖ．ｏｆ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ ４３００３３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｎｓｔｒｕｃｔｉｎｇ Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ ａｒｂｉｔｒａｒｉｌｙ ｓｈａｐｅｄ ｐｌａｎａｒ ｄｏｍａｉｎｓ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｔｈｅ ｐｒｏｐｅｒｔｉｅｓ ｔｈａｔ ｏｎｌｙ ａ ｆｅｗ ｎｅｗ ｐｏｉｎｔｓ ａｒｅ ｃｒｅａｔｅｄ ｉｎ ｌｏｃａｌ ａｒｅａ，ａｎｄ ｏｎｌｙ ｔｈｅ ｔｒｉａｎｇｕｌａｔｉｏｎ ｉｎ ｌｏｃａｌ ａｒｅａ ｉｓ ｎｅｅｄｅｄ ｔｏ ｍａｋｅ ｔｈｅ ｇｌｏｂａｌ ｔｒｉａｎｇｕｌａｔｉｏｎ ｍａｔｃｈｉｎｇ ｗｉｔｈ ｔｈｅ Ｄｅｌａｕ— ｎａｙ ｆｅａｔｕｒｅ．
Ｋｅｙ ｗｏｒｄｓ：２Ｄ ｔｒｉａｎｇｕｌａｔｉｏｎ；ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ；ｃｏｍｐｕｔａｔｉｏｎａｌ ｇｅｏｍｅｔｒｙ；ｍｅｓｈ ｇｅｎｅｒａｔｉｏｎ
三角剖分（ｔｒｉａｎｇｕｌａｔｉｏｎ）是计算几何中的一个难题，它在有限元分析、ＣＡＤ及数据场的可视化等领 域均有重要应用．任意二维约束点集的三角剖分是指将欧几里德平面上的有穷个离散点连成三角形，使 得任何两条边不在非离散点处相交，且定义平面区域边界的直线段（不是直线段的边界可用直线段代 替）必须作为三角形的边而存在． 二维Ｄｅｌａｕｎａｙ三角剖分（简称二维ＤＴ剖分）是二维点集较理想的一种剖分方法［１ ］，剖分得到的 三角形满足最小内角之和最大的原则，使得任一三角形外接圆中均不包含点集中的其它点，各个三角形 尽可能接近于等边三角形，避免了狭长三角形的存在，这样各离散点对整个三角形网格的影响仅限于局 部．ＤＴ剖分技术发展到现在，已涌现了大量不同的算法，一般可将算法分为以下三类口］：以Ｂｏｗｙｅｒ、 Ｇｒｅｅｎ、Ｓｉｂｓｏｎｓ为代表的Ｖｏｒｏｎｏｉ图方法、以Ｗａｔｓｏｎ为代表的空外接圆法以及以Ｌａｗｓｏｎ为代表的对 角线交换算法．现有算法基本上都是以以上三类算法为原型并进一步改进的结果，但仍不能解决实际应 用中遇到的复杂情况：标准的二维ＤＴ剖分假定剖分是在给定点集凸包内进行的［１］，即为不带约束条件 的三角剖分，不能用于任意平面区域上点集的三角剖分；文献［２，４］提出在平面区域约束边界上插入新 点，使二维三角剖分的结果尽可能满足边界约束条件的算法，但在约束边界上如何插入新点？插入多少 新点？都值得研究，且多插入一点，则三角形的数量会急剧增加；文献Ｅｓ］提出“修正的外接圆”准则：三 角形外接圆内至多只能包含“不可见”顶点，而不能包含“可见”顶点，事实上依据该准则完成的三角剖分 已不再是通常意义上的ＤＴ剖分． 本文针对任意二维约束点集提出新的算法，用于自动生成平面上带约束条件点集的ＤＴ剖分．
收稿日期：２００３－０２－１５＃修订日期：２００３－０３－０９ 作者简介：崔汉国（１９６４－），男，教授，博士．
维普资讯 http://www.cqvip.com 海军 工程 大 学 学报 第ｌ５卷 １ 二维点集凸包的ＤＴ剖分 二维点集凸包的ＤＴ剖分是实现任意平面区域上点集ＤＴ剖分的基础．对于任意平面区域上点集 Ｐ一｛Ｐ ，ｉ一１，２，…，Ｎ｝，其凸包的ＤＴ剖分算法是一个递推过程：对已形成的ＤＴ剖分进行动态修改， 以构成新的ＤＴ剖分．本文算法 由以下几个步骤组成： （１）由不在同一条直线上的３个点组成第一个三角形，令ｉ一４； （２）在任意位置插入一点Ｐｉ； （３）如果Ｐ 包含在某些（至少一个）三角形的外接圆之内，则将这些三角形删除，只保留这些三角形 的外边界，形成一个多边形．该多边形包含新插入的点Ｐ ，将新插入的点Ｐ 与多边形的每个顶点相连， 便形成了新的ＤＴ剖分（见图１），令ｉ— ＋１，转（５）； （４）如果Ｐ 点不被任一个现有三角形的外接圆所包含，则Ｐ 点必在已形成的ＤＴ剖分子集凸包之 外（见图２），这时将Ｐ 点与原凸包所有“可见”的顶点相连，形成新的ＤＴ剖分，令ｉ－－ ＋１； （５）如果 ＜Ｎ，则转（２），否则结束．
图１ 新插入点位于部分三角形外接圆之内 图２ 新插入点位于已形成的三角剖分凸包之外 算法实例如图３所示．
图３二维点集凸包的ＤＴ剖分 ２任意二维约束点集的ＤＴ剖分 设有任意平面区域上点集Ｐ一｛Ｐｉ，ｉ一１，２，…，Ｎ｝，区域边界多边形Ｂ由一个外环及若干个内环组 成，即Ｂ一｛Ｂ。，Ｂ 一，Ｂ ），其中Ｂ。为外环，Ｂ 一，Ｂ 为内环，点集Ｐ中有部分点位于外环上，部分点 位于内环上，部分点位于内、外环之间的区域中． 当用二维点集凸包的ＤＴ剖分算法对上述区域进行剖分时，可形成三类三角形：之一为三角形在区 域内部；之二为三角形在区域外部；之三为三角形的一部分在区域内部，另一部分在区域外部．其中第一 类为符合要求的剖分结果；第二类可设法标记为“虚三角形”，如图４所示，并予以消除；第三类是不合要 求的剖分，需要特殊处理，如图５所示． 本文提出“交点插入算法”来恢复约束边界，其基本思想是用区域约束边界Ｂ一｛Ｂ。，Ｂ。，…，Ｂ ｝对 已形成的三角剖分集进行求交，用交点动态地对二维点集凸包的ＤＴ剖分的结果进行修改，从而将修改 后的三角形简单地分为在区域内部或在区域外部两种情况，且三角形以约束边界为其边界，“交点插入 算法”描述如下：
维普资讯 http://www.cqvip.com 第６期 崔汉国等：二维约束点集Ｄｅｌａｕｎａｙ三角剖分算法研究 ｏ （ａ）原始数据 （ｂ）标准ＤＴ剖分结果 图４带有“虚三角形”的情况 （ａ）原始数据 （ｂ）标准ＤＴ剖分结果
图５标准ＤＴ剖分出现错误的情况 将２Ｄ多边形内外环的直线段边界Ｂ＝｛Ｂ。，Ｂ ”，Ｂ ）汇总，形成一个边的链表Ｅｌｉｓｔ； 对给定点集的凸包按上面介绍的二维点集凸包的ＤＴ剖分算法进行剖分； Ｗｈｉｌｅ Ｅｌｉｓｔ非空 ｂｅｇｉｎ 从Ｅｌｉｓｔ中取出一条直线段与已形成的三角形集求交，得到交点； 用新求得的交点对三角剖分结果进行动态修改； ｅｎｄｗｈｉｌｅ 去除“虚三角形”得到正确的三角剖分结果． 算法说明：“用新求得的交点对三角剖分结果进行动态修改”的方法与“二维点集凸包的ＤＴ剖分” 算法步骤中的（３）、（４）相同． 算法实例如图６、７所示．
图６单孔约束点集ＤＴ剖分实例 ３ 结 论 图７多孔约束点集ＤＴ剖分实例 本文提出通过用约束边界与二维点集凸包的ＤＴ剖分形成的三角形集求交，并对交点进行分类的 办法，在约束边界上产生少量的新点，进而用这些新点对三角形集进行动态修改，使得约束边界被分割 成许多部分，每一部分又都成为三角形的边界，保证整体剖分符合ＤＴ剖分的性质，新点的产生不是盲 目的，而是必需的．本文算法针对复杂情况较文献［７３增加更少的新点．算法可用于具有复杂内外边界或 具有特征约束区域的二维点集三角剖分，算法简洁、适应性强．
参考文献： ［１］唐泽圣，徐志强．二维点集三角剖分动态生成和修改［Ｊ］．计算机辅助设计与图形学报，１９９０，２（３）：１—８． ［２］Ｓａｐｉｄｉｓ Ｎ，Ｐｅｒｕｅｅｈｉｏ Ｒ．Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｆ ａｒｂｉｔｒａｒｉｔｙ ｓｈａｐｅｄ ｐｌａｎａｒ ｄｏｍａｉｎｓ［Ｊ］．ＣＡＧＤ，１９９１，８：４２ｌ一４３７． ［３］胡恩球，张新访，向 文，等．有限元网格生成发展综述［Ｊ］．计算机辅助设计与图形学报，１９９７，９（４）：３７８—３８３． ［４］ Ｓｃｈｒｏｅｄｅｒ Ｗ Ｊ，Ｓｈｅｐｈａｒｄ Ｍ Ｓ．Ｇｅｏｍｅｔｒｙ—ｂａｓｅｄ ｆｕｌｌｙ ａｕｔｏｍａｔｉｃ ｍｅｓｈ ｇｅｎｅｒａｔｉｏｎ ａｎｄ ｔｈｅ Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ ［Ｊ］．Ｉｎｔ．Ｊ．Ｎｕｍｅｒ．Ｍｅｔｈ．Ｅｎｇ．，１９８８，２６：２５０３—２５１５． ［５］丁永详，夏巨谌，王英，等．任意多边形的Ｄｅｌａｕｎａｙ三角剖分［Ｊ］．计算机学报，１９９４，１７（４）：２７１—２７６． ［６］方锡武，崔汉国．有限元网格自动生成的Ｄｅｌａｕｎａｙ算法［Ｊ］．海军工程学院学报，１９９８，（４）：３１—３４． ［７］简宪华，崔汉国，曹茂春．带内边界约束散乱数据的Ｄｅｌａｕｎａｙ三角剖分算法研究［Ｊ］．计算机工程，２００１，２７（５）： １０５－－１Ｏ６．
维普资讯 http://www.cqvip.com