黄中展，徐世明

（清华大学地球系统科学系，北京 100084）

（*通信作者电子邮箱xusm@tsinghua.edu.cn）

0 引言

动画电影技术、天气预报、工业制造等多个与人们生活息息相关的领域都离不开科学计算，随着这些领域对高质量计算的需求的增大，对数值算法的要求也随之增大。一般来说，在科学计算当中，主要采用的三类数值算法分别为有限差分方法［1］、有限体积方法［2］以及有限元方法［3］。它们广泛地应用于各类计算当中，而这些方法的有效实施离不开高质量的离散化方案，即网格的划分。

在不同的应用场景，网格有很多不同的类型，可从网格形状、目标区域类型、目标区域的维度三个方面来划分。如图1（a）和图1（b）分别展示了二维平面和三维空间中的正交网格样例。

对于二维平面上的网格，除了在图1（a）中所展示的四边形网格之外，还有如图2 所示的三角形网格。相较于四边形网格，三角形网格的生成相对容易。另外，图1（a）中的网格和图2中的网格还有一个显著的差异在于其目标区域的连通性上，图2 所展示的目标区域是多连通区域。多连通区域相对于单连通区域而言，在实际生活和科学计算需要中更为普遍，但是同时网格生成难度也更大，特别是正交网格。

图2 多连通区域的三角网格［6］Fig.2 Triangular grid of multiconnected region

对于平面上的目标区域，三角网格和四边形网格的算法都均可以对目标区域进行离散化。三角形网格主要采用的是Delaunay 三角剖分法［7］、四叉树法［8］以及波前法［9］，其中Delaunay 法使用最为普遍，这是由于它在数学上十分成熟，具有较好的网格质量且收敛性也能较好地保证；……