admin 管理员组文章数量: 1184232
2024年4月21日发(作者：冒泡排序算法动画演示)
３期 总５１
基于ＭＡＴＬＡＢ实现二维 ｄｅｌａｕｎａｙ三角剖分
刘锋涛凡友华
（哈尔滨工业大学深圳研究生院深圳５１８０５５）
【摘要】在已知凸多边形的顶点坐标的前提情况下，利用ＭＡＴＬＡＢ中的ｍｅｓｈｇｒｉｄ函数产生多边
形附近矩形区域内的网格点的坐标，然后再利用ｉｎｐｏｌｙｇｏｎ函数判断哪些点位于多边形内和哪
些点位于多边形的边界上。在此基础上利用ｄｅｌａｕｎａｙ函数来完成ｄｅｌａｕｎａｙ三角剖分。
【关键词】ｄｅｌａｕｎａｙ三角剖分；ＭＡＴＬＡＢ
网格划分是有限元分析前处理中的关键步骤，网格划分的密度以及质量对有限元计算的
精度、效率以及收敛性有着重要的影响作用。自２０世纪７０年代开始，关于有限元网格生成
方法的研究已经取得了许多重要成果，提出许多有效的算法。Ｈｏ．Ｌｅ对网格生成方法进行了
系统的分类 ¨。许多学者也对网格生成的方法进行了综述，如我国的学者胡恩球等嘲、关振
群等 。
Ｄｅｌａｕｎａｙ三角剖分（简称ＤＴ）是目前最流行的通用的全自动网格生成方法之一。ＤＴ有两
个重要特性：最大一最小角特性和空外接圆特性。ＤＴ的最大．最小角特性使它在二维情况下
自动地避免了生成小内角的长薄单元。因此特别适用于有限元网格生成。大体上可将ＤＴ算
法分为三大类：分治算法，逐点插入法和三角网生长法。经典ＤＴ技术已经相当成熟，近年
来的研究重点是约束ＤＴ的边界恢复算法，以及如何克服算法退化现象所产生的薄元（ｓｌｉｖｅｒ
ｅｌｅｍｅｎｔ）ｌ；－］题 。
然而，实现ＤＴ有限元网格生成，对于非计算机图形学专业的工程师来说还是很复杂的。
在处理一些对有限元网格划分质量不过的问题时，如极限分析的有限元方法，可以采用一些
更为简单的方法来实现。在Ｍａｔｌａｂ计算软件中，已有一个成熟的函数ｄｅｌａｕｎａｙ可以实现对
一
系列点的ＤＴ划分。因此，本文基于Ｍａｔｌａｂ的ｄｅｌａｕｎａｙ等一些函数来完成一个凸多边形
的ＤＴ网格划分。
１ ＭＡＴＵ 中的函数 ．
１．１ ｄｅｌａｕｎａｙ函数
ｄｅｌａｕｎａｙ函数可以按照ＤＴ网格划分的要求将一个点集中的点划归某一个有限网格所
有。它在Ｍａｔｌａｂ中的用法如下：
ＴＲｌ＝ｄｅｌａｕｎａｙ（ｘ，），）ｏｒ，
ＴＲｌ＝ｄｅｌａｕｎａｙ（ｘ，Ｙ，ｏｐｔｉｏｎｓ）
其输入为点集中所有点的横、纵坐标向量ｘ和Ｙ，返回值为一个ｍｘ３的矩阵，矩阵中每一
行表示ＤＴ网格中一个三角形网格的三个顶点。
１．２ ｍｅｓｈｇｉｒｄ函数
为了在任意凸多边形内产生一个点集，可以利用Ｍａｔｌａｂ中的ｍｅｓｈｇｒｉｄ命令。其用法如
下：
，
Ｙ］＝ｍｅｓｈｇｒｉｄ（ｘ， ）
３４
３ ５１
其输入为矩形的Ｘ、Ｙ方向上的范围，输出为两个向量，分别表示ｘ和Ｙ方向上满足一定间
距的点的坐标。
１．３ ｉｎｐｏｌｙｇｏｎ函数 ’
ｉｎｐｏｌｙｇｏｎ函数的作用是判断一个点是否存在于一个多边形内。它的用法是，
【ＩＮ ＯＮ］＝ｉｎｐｏｌｙｇｏｎ（Ｘ，Ｙ，ＸＶ，ｙｖ）
其输入值Ｘ和Ｙ分别表示点集中每个点的ｘ和Ｙ坐标值，而ＸＶ和ｙｖ则分别表示多边形定
点的ｘ和Ｙ坐标值。若点集中某一点在多边形内则其返回值ＩＮ为１，若不在则ＩＮ为０，若
某一点在多边形的边界上则ＯＮ为１，若不在边界上则ＯＮ为０。
１．４基于ＭＡＴＬＡＢ的简单ＤＴ方法
在ＭＡＴＬＡＢ中，基于ｄｅｌａｕｎａｙ函数、ｍｅｓｈｇｒｉｄ函数和ｉｎｐｏｌｙｇｏｎ函数完成ＤＴ网格划
分的步骤是：
（１）定义一个多边形，并求出多边形顶点最大的ｘ、Ｙ坐标值。
（２）以最大的ｘ、Ｙ坐标值作为ｘ和Ｙ方向上的长度构造一个矩形。
（３）利用ｍｅｓｈｇｒｉｄ函数在构造的矩形区域内构造出一个点集，其密度可以根据需要进行加
密。
（４）利用ｉｎｐｏｌｙｇｏｎ函数判断点和多边形的位置关系，求出位于多边形内和边界上的点。
（５）再利用ｄｅｌａｕｎａｙ函数将在多边形内和边界上的点进行三角形划分，之后，可以利用
ｔｒｉｍｅｓｈ函数将图形绘制出，并可以得出三角形的顶点坐标和编号。
２一个简单的例子
任意定义一个凸多边形，如图１。按照２－４节中的步骤，对其进行网格划分，划分结果
见图２。部分丰要的程序见附录。
图１定义的多边形 图２ ｄｅｌａｕｎａｙ网格划分结果
从图２中，可以看出凸多边形内部的三角形划分结果比较理想，但是边界处出现了很薄
的三角形单元，并且内部的网格划分的密度一致。然而，对于一些对网格质量要求不高的具
体问题还是可以忍受的。
３讨论
此种方法主要是基于Ｍａｔｌａｂ中现有的函数命令来实现ＤＴ网格划分的，因此对于那些
不熟悉计算机图形学基础知识的工程技术人员而言，很容易掌握并自己编程实现。这也是使
３５
３期 总５１
用该方法的主要目的。然而，在此方法中还存在着几个问题：
（１）此种方法只能用于凸多边形的ＤＴ划分；
（２）网格划分结果不能实现在同一个区域内不同网格密度的划分；
（３）边界处网格划分的结果不理想，有很薄的三角形单元出现。
若对以上三个要求的不高，则此种方法可以发挥其简单易用的优势，使ＤＴ网格划分技
术更加容易掌握。
参考文献
［１］Ｋ．Ｈｏ—Ｌｅ．Ｆｉｎｉｔｅ ｅｌｅｍｅｎｔ ｍｅｓｈ ｇｅｎｅｒａｔｉｏｎ ｍｅｔｈｏｄ：Ａ ｒｅｖｉｅｗ ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ．Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ
Ｄｅｓｉｇｎ，１９８８，２０（１）：２７ ３８
［２］胡恩球，张新访，向文，周济．有限元网格生成方法发展综述．计算机辅助设计与图形学学报．１９９７，
９（４）：３７８ ３８３ ‘
［３］关振群，宋超，顾元宪，隋晓峰．有限元网格生成方法研究的新进展．计算机辅助设计与图形学学报．
２００３，１５（１）：１ １４
《工程地质计算机应用》征稿启事
《工程地质计算机应用》杂志自２００８年由河海大学科学研究院负
责编辑出版发行，现已发行三期（总第５１期），感谢各位作者和各家
单位的支持，希望大家一如既往的关注本杂志，踊跃投稿。
投稿信箱如下：
电子邮箱１：ｇｅｏｃｏｍＯ５＠ｙａｈ００．ｃｏｍ．ｃｎ
电子邮箱２：ｈｅｔｃ＠ｈｈｕ．ｅｄｕ．ｃｎ
电子邮箱３：ｗｊｈｆｉ ｓｈ＠ｈｈｕ．ｅｄｕ．ｃｎ
《工程地质计算机应用》编辑部
版权声明：本文标题：基于MATLAB实现二维delaunay三角剖分 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713697911a647488.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论