1.三角网格网络概述

网格主要用于计算机图形学中，有三角、四角网格等很多种。计算机图形学中的网格处理绝大部分都基于三角网格来模拟复杂物体的表面，如建筑、车辆、动物等。三角形表示网格也叫三角剖分。三角网格稳定性强、结构简单，可以非常方便并且快速生成，在非结构化网格中最常见。而且相对于一般多边形网格，许多操作对三角网格更容易。不规则三角网(TIN, Triangulated Irregular Network)模型采用一系列相连接的三角形拟合地表或其他不规则表面，常用来构造数字高程模型，常用的TIN生成方法是Delaunay 剖分方法。

2. Delaunay三角化方法

Delaunay三角化方法最早可以追溯到1850年Dirichlet的思想。1908年，Voronoi基于该思想，提出了Voronoi域的概念，又称为Voronoi图。1934年，Delaunay基于Voronoi图的思想，提出了平面域的Delaunay三角化方法。

直到20世纪80年代，Delaunay三角化方法才被应用于数值模拟的网格生成。1981年，Bowyer和Waston分别独立提出了基于Delaunay三角化方法的非结构网格生成方法。随后，众多学者提出了各种改进方法，使得Delaunay方法的自动化程度不断提高，并成功应用于复杂外形的非结构网格生成。

Delaunay三角化是一种三角剖分DT(P)，使得在P中没有点严格处于DT(P)中任意一个三角形外接圆的内部。Delaunay三角化最大化了此三角剖分中三角形的最小角，换句话，此算法尽量避免出现“极瘦”的三角形。此算法命名来源于BorisDelaunay，以纪念他自1934年在此领域的工作。

想要将很多离散的点组成，基于这个确定的点集，将点集连接成一定大小的三角形，且分配要相对合理，呈现出漂亮的三角化，则要求使用三角剖分算法（Delaunay），对Delaunay三角形的定义为：

【定义1】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：

（1）除了端点，平面图中的边不包含点集中的任何点。

（2）没有相交边。

（3）平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。

在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：

【定义2】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。

【定义3】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

【定义4】假设T为V的任一三角剖分，则T是V的一个Delaunay三角剖分，当前仅当T中的每个三角形的外接圆的内部不包含V中任何的点。 

3.案例实现

本内容通过C#语言借助Triangle.NET 库进行编译。Triangle.NET是生成 2D（约束）Delaunay 三角剖分和点集或平面直线图的高质量网格。此库是基于Jonathan Richard Shewchuk 的 Triangle 项目，主要用于图形学像Opengl中生成三角形使用。

图1 三角网格生成图

图2 三角面片顶点数据