尹 畅，张思全，刘 雨，齐 川

（上海海事大学物流工程学院，上海201306）

0 引 言

科学技术领域中系统数学模型往往采用偏微分方程形式来描述复杂的物理现象，而数值计算技术是这类数学模型的主要计算分析途径。PDE数值解法的核心是将全局定义域中连续未知函数转化为一定数量子定义域上的简单函数，进一步建立仅仅在定义域内一定数量的离散结点上处理的代数方程组。网格划分（Meshing Generation）就是将PDE全局定义域划分成离散单元（elements）或者控制体积（control volume）集合，其构成了系统的自定义域和离散节点集合。由于单元采用简单集合形状，因此可以方便地在这些子域上构造简单初等函数逼近连续的PDE系统响应。而且，可以通过调节网格类型、单元形状、尺寸和数量等因素来提高PDE系统的数值计算精度［1］。

三角形是二维空间的单纯形，故在二维空间的离散化封面占据主导地位，相继出现了插点增量式Delaunay三角形划分方法、推进波前法、分治算法以及扫描算法等。

由于Delaunay三角划分算法可以使全部三角形的最小内角为最大，且保证三角单元不会重叠（即所有边最多只被两个三角形共有），同时三角单元的三边之上不会有其他节点，故三角剖分以Delaunay法的应用最为广泛［2］。

1 算法思想与实现步骤

对形状规则的几何域进行网格划分比较容易，且易于控制单元网格形状与尺寸，故先建立一个足够大的矩形来包围不规则几何域。对矩形使用正交栅格得到节点p（x，y），利用函数d（x，y）表示点p与几何域的位置关系。……