基于MATLAB实现二维delaunay三角剖分

基于MATLAB实现二维delaunay三角剖分

刘锋涛 凡友华

（哈尔滨工业大学深圳研究生院 深圳 518055）

【摘要】在已知凸多边形的顶点坐标的前提情况下，利用MATLAB中的meshgrid函数产生多边

形附近矩形区域内的网格点的坐标，然后再利用inpolygon函数判断哪些点位于多边形内和哪

些点位于多边形的边界上。在此基础上利用delaunay函数来完成delaunay三角剖分。

【关键词】delaunay三角剖分；MATLAB

网格划分是有限元分析前处理中的关键步骤，网格划分的密度以及质量对有限元计算的精度、效率以及收敛性有着重要的影响作用。自20世纪70年代开始，关于有限元网格生成方法的研究已经取得了许多重要成果，提出许多有效的算法。Ho-Le对网格生成方法进行了系统的分类[1]。许多学者也对网格生成的方法进行了综述，如我国的学者胡恩球等[2]、关振群等[3]。

Delaunay三角剖分(简称DT)是目前最流行的通用的全自动网格生成方法之一。DT有两个重要特性：最大-最小角特性和空外接圆特性。DT的最大-最小角特性使它在二维情况下自动地避免了生成小内角的长薄单元。因此特别适用于有限元网格生成。大体上可将DT算法分为三大类：分治算法，逐点插入法和三角网生长法。经典DT技术已经相当成熟，近年来的研究重点是约束DT的边界恢复算法，以及如何克服算法退化现象所产生的薄元(sliver element)问题[3]。

然而，实现DT有限元网格生成，对于非计算机图形学专业的工程师来说还是很复杂的。在处理一些对有限元网格划分质量不过的问题时，如极限分析的有限元方法，可以采用一些更为简单的方法来实现。在Matlab计算软件中，已有一个成熟的函数delaunay可以实现对一系列点的DT划分。因此，本文基于Matlab的delaunay等一些函数来完成一个凸多边形的DT网格划分。

1 MATLAB中的函数

1.1 delaunay函数

delaunay函数可以按照DT网格划分的要求将一个点集中的点划归某一个有限网格所有。它在Matlab中的用法如下：

TRI=delaunay(x,y) or,

TRI=delaunay(x,y,options)

其输入为点集中所有点的横、纵坐标向量x和y，返回值为一个m×3的矩阵，矩阵中每一行表示DT网格中一个三角形网格的三个顶点。

1.2 meshgird函数

为了在任意凸多边形内产生一个点集，可以利用Matlab中的meshgrid命令。其用法如下：

[X,Y] = meshgrid(x,y)

34

其输入为矩形的x、y方向上的范围，输出为两个向量，分别表示x和y方向上满足一定间距的点的坐标。

1.3 inpolygon函数

inpolygon函数的作用是判断一个点是否存在于一个多边形内。它的用法是，

[IN ON] = inpolygon(X,Y,xv,yv)

其输入值X和Y分别表示点集中每个点的x和y坐标值，而xv和yv则分别表示多边形定点的x和y坐标值。若点集中某一点在多边形内则其返回值IN为1，若不在则IN为0，若某一点在多边形的边界上则ON为1，若不在边界上则ON为0。

1.4 基于MATLAB的简单DT方法

在MATLAB中，基于delaunay函数、meshgrid函数和inpolygon函数完成DT网格划分的步骤是：

（1）定义一个多边形，并求出多边形顶点最大的x、y坐标值。

（2）以最大的x、y坐标值作为x和y方向上的长度构造一个矩形。

（3）利用meshgrid函数在构造的矩形区域内构造出一个点集，其密度可以根据需要进行加密。

（4）利用inpolygon函数判断点和多边形的位置关系，求出位于多边形内和边界上的点。

（5）再利用delaunay函数将在多边形内和边界上的点进行三角形划分，之后，可以利用trimesh函数将图形绘制出，并可以得出三角形的顶点坐标和编号。

2 一个简单的例子

任意定义一个凸多边形，如图1。按照2.4节中的步骤，对其进行网格划分，划分结果见图2。部分主要的程序见附录。

图1 定义的多边形 图2 delaunay网格划分结果

从图2中，可以看出凸多边形内部的三角形划分结果比较理想，但是边界处出现了很薄的三角形单元，并且内部的网格划分的密度一致。然而，对于一些对网格质量要求不高的具体问题还是可以忍受的。

3 讨论

此种方法主要是基于Matlab中现有的函数命令来实现DT网格划分的，因此对于那些不熟悉计算机图形学基础知识的工程技术人员而言，很容易掌握并自己编程实现。这也是使

35

用该方法的主要目的。然而，在此方法中还存在着几个问题：

（1）此种方法只能用于凸多边形的DT划分；

（2）网格划分结果不能实现在同一个区域内不同网格密度的划分；

（3）边界处网格划分的结果不理想，有很薄的三角形单元出现。

若对以上三个要求的不高，则此种方法可以发挥其简单易用的优势，使DT网格划分技术更加容易掌握。

参考文献

[1] K. Ho-Le. Finite element mesh generation method: A review and classification. Computer Aided Design, 1988, 20(1): 27~38

[2] 胡恩球, 张新访, 向文, 周济. 有限元网格生成方法发展综述. 计算机辅助设计与图形学学报. 1997, 9(4): 378~383

[3] 关振群, 宋超, 顾元宪, 隋晓峰. 有限元网格生成方法研究的新进展. 计算机辅助设计与图形学学报. 2003, 15(1): 1~14

――――――――――――――――――――――――――――――――――――――――――――――

《工程地质计算机应用》征稿启事

《工程地质计算机应用》杂志自2008年由河海大学科学研究院负责编辑出版发行，现已发行三期(总第51期)，感谢各位作者和各家单位的支持，希望大家一如既往的关注本杂志，踊跃投稿。

投稿信箱如下：

电子邮箱1: geocom05@http://www.77cn.com.cn

电子邮箱2: hetc@http://www.77cn.com.cn

电子邮箱3: wjhfish@http://www.77cn.com.cn

《工程地质计算机应用》编辑部

36