三角剖分

数学术语

三角剖分是代数拓扑学里最基本的研究方法。以曲面为例，我们把曲面剖开成一块块碎片，要求满足下面条件：（1）每块碎片都是曲边三角形；（2）曲面上任何两个这样的曲边三角形，要么不相交，要么恰好相交于一条公共边（不能同时交两条或两条以上的边）。

定义

拓扑学的一个已知事实告诉我们：任何曲面都存在三角剖分。

假设曲面上有一个三角剖分，我们把所有三角形的顶点总个数记为p(公共顶点只看成一个，下同),边数记为a,三角形的个数记为n,则e=p-a+n是曲面的拓扑不变量。也就是说不管是什么剖分， e总是得到相同的数值。 e被称为称为欧拉示性数。

假设g是曲面上洞眼的个数（比如球面没有洞，故g=0;又如环面有一个洞，故g=1），那么e=2-2g。

g也是拓扑不变量，称为曲面的亏格(genus)。

上面例举曲面的情形。对一般的拓扑对象（复形），我们有类似的剖分，通常成为单纯剖分。分割出的每块碎片称为单纯形（简称单形）。

相关概念

拓扑图

是图论的一个重要概念，能够嵌入在某一拓扑空间

(p为M的可定向亏格；q为M的不可定向亏格)

事实上，这个公式是于1812-1813年间由吕里尔(Lhuilier,S.J.)给出的.因为欧拉(Euler,L.)第一个注意到这类关系，这个公式仍称为欧拉公式。其中E(M)称为地图M的欧拉示性数。

对于地图M，在其每一面的内部选取一点作为顶点，对于每条边e，将与其关联的两面中选定的顶点用一条简单曲线e′连结，使得e′除与e有一个公共点外不与M的其他任何边有公共点。这样得到的地图M′称为M的对偶地图，这里的对偶性也是对称的，即,若M′为M的对偶地图,则M也为M′的对偶地图，若(不)可定向地图M对于任何亏格小于M的亏格的(不)可定向地图M′,G(M)与G(M′)是不同构的，则称M是(不)可定向的最大地图。因为在所有那些与G(M)同构的地图中，这个M的面数最多。若M是曲面S上的地图,且M的每个面都是三角形，则称M是S的一个三角剖分。凡三角剖分都是最大地图,但反之则不然，另一方面,若(不)可定向地图M，对于任何亏格大于M的(不)可定向地图M′，G(M)与G(M′)不同构，则称M为最小地图，因为在所有与G(M)同构的地图中以这个M的面数为最少，若一个地图仅有一个面,则称它为单面地图，凡单面地图均是最小地图，但反之则不然。

复形的多面体

亦称复形的基础空间，一类特殊的拓扑空间.复形是代数拓扑中的基本概念，以它作为工具进行研究，而最终目的是得出它所给出的拓扑空间，也就是多面体的拓扑性质，若K是n维欧氏空间R中的复形,则K中全体单形的所有点组成的集合

作为R的子空间称为K的多面体，记为|K|，K称为多面体|K|的一个单纯剖分或三角剖分。一般地，多面体可以有不同的单纯剖分.有限复形的多面体是紧致空间。

分类

二维区域的三角剖分

在二维场问题中，涉及的区域是以Γ为边界的平面区域Ω，三角剖分是常用的形式，它适用于各种几何形状的区域和非均匀介质的情况。其剖分原则是：

1.将Ω划分为若干三角形单元，三角形的顶点称为节点，用相邻边界节点连成的折线及其围成的区域近似代替曲线边界Γ和区域Ω，如图1。

2.每个单元的顶点只能是相邻单元的顶点，不能是相邻单元边上的内点，图2的情况是不容许的。

3.在u(x，y)变化可能剧烈的地方，网格要密，变化较小的地方网格可稀一些。

4.如果域内有不同介质，则不同介质的分界线为划分单元的分割线。

5.从收敛角度考虑，任一单元的三个边长度不可相差悬殊。

6.将所有单元和节点逐一编号，其方式和次序可以任意，不影响计算结果，但节点编号的次序对求解有限元法方程的工作量有重大影响。一般应将待定参数的节点集中在小号区，将节点参数已知的集中在大号区，而其中的零值节点则集中到最后。此外，要求两个相邻节点编号之差的绝对值中的最大者愈小愈好，例如，图3区域的三角剖分，(a)的编号方式形成的带状总体系数矩阵的带宽要比(b)的小，从而更节约存储和计算量。

简单多边形三角剖分

1.简单多边形的概念

三维地质建模中不仅会遇到平面点集的三角剖分，还会遇到多边形的剖分问题。这里主要介绍简单多边形的三角剖分问题。简单多边形具有以下几何特征：

(1)多边形的边界是由若干个结点顺序连接而成的闭合环，任意相邻两个结点对定义了一条有向边；

(2)任意两条有向边的交要么为多边形的边界上的一个结点，要么为空；

(3)经过多边形的边界上的任一个结点，有且仅有两条有向边。图4中(a)中的多边形不满足上述条件(1)，图4中(b)不满足上述条件(2)，图4中(c)中的多边形不满足上述条件(3)，图4中(d)中多边形属简单多边形。

2.简单多边形剖分问题

简单多边形的三角剖分问题是指将简单多边形划分成若干三角形的集合，即将简单多边形所围区域划分成二维单纯复形，而且，任意三角形的顶点均为简单多边形的边界结点。

3.简单多边形三角剖分的对角线法

由于简单多边形的三角剖分网格中，三角形的顶点均为简单多边形的边界结点，因此，所有三角形的边只能来自简单多边形的边与对角线。根据这个特点，我们可以采用对角线法进行简单多边形的三角剖分，算法过程如下：

(1)计算任意两非相邻结点之间的距离，即对角线长度，并存储到数组T中；

(2)根据对角线长短对T进行排序；