|
TIN ＆ Voronoi ＆
Delaunay
（一堂之见／陈树铭 刘慧杰 王满春）
可以说TIN技术是三维图形技术，以及三维GIS的核心。在TIN中很重要的一个算法就是Voronoi图与Delaunay三角形。下面将分别就这些方面作些简单介绍和探讨
一、TIN
不规则三角网（TIN, Triangulated Irregular Network）是一种表示数字高程模型的方法，它既减少规则格网方法带来的数据冗余，同时在计算效率（如坡度）方面又优于纯粹基于等高线的方法。
TIN模型根据区域有限个点集将区域划分为相连的三角面网络，区域中的任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常通过线性插值的方法得到（在边上用边的两个顶点的高程，在三角形内则用三个顶点的高程）。所以TIN是一个三维空间的分段线性模型，在整个区域内连续但不可微。
对于不规则分布的高程点，可以形式化的描述为平面的一个无序的点集P，点集中每个点p，对应于它的高程值。将该点集转成TIN，最常用的方法是Delaunay三角剖分方法。
二、Voronoi ＆ Delaunay
一、基本概念
Voronoi图，又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Voronoi三角形是Delaunay图的偶图；
实线为Delaunay三角形，虚线为Voronoi图
对于给定的初始点集P，有多种三角网剖分方式，其中Delaunay三角网具有以下特征：
1、Delaunay三角网是唯一的；
2、三角网的外边界构成了点集P的凸多边形“外壳”；
3、没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。
4、如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。
Delaunay三角形网的特征又可以表达为以下特性：
1、在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；
2、在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；
3、形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；
4、不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。
Delaunay三角形产生的基本准则：任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[Delaunay 1934]。Lawson[1972]提出了最大化最小角原则，每两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。Lawson[1977提出了一个局部优化过程（LOP,
local Optimization Procedure）方法。
二、Delaunay三角形网的通用算法－逐点插入算法
基于散点建立数字地面模型，常采用在d维的欧几里得空间Ed中构造Delaunay三角形网的通用算法—逐点插入算法，具体算法过程如下：
1、遍历所有散点，求出点集的包容盒，得到作为点集凸壳的初始三角形并放入三角形链表。
2、将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
3、根据优化准则对局部新形成的三角形进行优化（如互换对角线等）。将形成的三角形放入Delaunay三角形链表。
4、循环执行上述第2步，直到所有散点插入完毕。
上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法不易引入地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。
为了克服基于散点构网算法的上述缺点，特别是为了提高算法效率，可以对网格中三角形的空圆特性稍加放松，亦即采用基于边的构网方法，其算法简述如下：
1、根据已有的地性线和特征线，形成控制边链表。
2、以控制边链表中一线段为基边，从点集中找出同该基边两端点距离和最小的点，以该点为顶点，以该基边为边，向外扩展一个三角形（仅满足空椭圆特性）并放入三角形链表。
3、按照上述第2步，对控制边链表所有的线段进行循环，分别向外扩展。
4、依次将新形成的三角形的边作为基边，形成新的控制边链表，按照上述第2步，对控制边链表所有的线段进行循环，再次向外扩展，直到所有三角形不能再向外扩展为止。
三、其它Delaunay优化算法
1、Watson的算法
Watson的算法一开始就要形成一个包含所有给定点区域的超级三角形。起初， 超级三角形是不完全的 (图2, 3, 4 and 5). 然后，通过算法继续递增地在已经存在的三角化格网内插入新的点。查找所有其外接圆包含新的点并且被删除掉给出已知的插入多边形。这样就产生了新的三角网。这个过一直将持续到用完所有的插入点以及所有拥有超级三角形顶点的三角形被删除掉。
Figure 2: Watson的算法: 初始的三角化
Figure 3: Watson的算法: 点的插入
Figure 4: Watson的算法: 元素的删除
Figure 5: Watson的算法:最终的格网
这是Delaunay三角化最简单和最广泛应用的算法
2、Lawson的算法或 对角线交换算法
如果将一个点加入到一个已经存在的三角网中，那么就形成了所有新的三角形的外接圆。如果任何 相邻的区域位于任何三角形的外接圆内，那么用三角形和它的相邻的区域便可形成一个四边形。四边形的对角线被转换为一个新的三角网。这个过程一直持续到不再有的错误三角形和不在需要变换。
3、限制性的Delaunay三角化（Constrained Delaunay Triangulation）
(CDT)
如果指定了平面的点集以及一系列不交错的边缘，那么CDT 将产生如下的网格：
a、在三角网中包含了所有给定的边缘
b、尽可能使其与Delaunay三角网相近
这种算法已经在N个给定点的区域在O(NlogN) 的时间复杂性下经过了测试。如果指定点集和不交叉边缘，那么给定点集的CDT具有所有新的边缘所具有的特性，即存在一个这样的圆，
a、边缘的终点都落在圆内
b、如果有任一个节点在圆内，那么至少边缘的一个节点是不可见的，例如，如果线是从点到边缘的两个节点来画的，那么至少有一条直线会与网格的边缘相交。
因此，如果没有指定边缘，那么CDT与Delaunay是一样的。CDT是一种分而取之的方法，因为给定的数据是依据任意的尺寸来筛选的，并且将区域划分成若干带。这个过程将一直重复，直到得到整个区域的CDT为止。
4、扫描线算法（Sweepline algorithm）
在Voronoi多边形中，扫描线被定义为一条移动的水平线与Voronoi 边界的交点。外接圆是通过找出连接节点的直线的三条平分线的交点来定位的。但是这样得到Voronoi
多边形不是太有力。一对一的几何变换在双曲线中绘制出一条平分线或者一条垂直的半条。任一两节点的平分线，命名为p 和q, 描述如下：
转换将x描述为这样，y为初始值，点与节点的距离为p。描述的Voronoi区域Rp*和Rq*是被画出的二分线限制的，为Cpq,，它是一个双曲线或是一个直的半条线。只有在扫描线到达所有的两个形成的节点，才能形生二分线。预期的顶点是两个邻近的二分线的交点。
三、对TIN、Voronoi、Delaunay的一点简单看法
Delaunay三角形是TIN中一种最为重要的算法，基于Delaunay、TIN，以及它们之间的关系，我们有以下一些不成熟的观点：
1、Delaunay三角形的本质是反映属性在平面上分布的距离相关性，这一点对于带约束条件的Delaunay三角形，或者其它改进的Delaunay三角形同样也是适用的。
2、TIN不只是数字高程模型实现方法的专利，其实上它早被广泛应用于有限元分析、复杂多边形填充，以及各种图形图像分析领域。
3、从本质上看，Delaunay三角形与有限元单元分析更具有天然的、内在的亲和性。无论是Delaunay三角形，还是基于约束条件的Delaunay三角形等其它改进的Delaunay三角形，都是反映有限元分析中三角单元剖分的最佳三角形单元组合，从整体上最佳的反映了区间上属性的分布。
4、Delaunay三角形很好的反映了数字高程模型的平面距离相关性，但是很难合理的反映其三维相关性，也就是说比较难反映数字高程的空间趋势面变化特征。造成这种因素的原因是由于TIN是三角片线性插值，通俗的说空间各点的命运取决于自己所被圈定的三角形三点的属性，与周围其它的兄弟没有任何关系。
5、Delaunay三角形的属性和要求只是数字高程模型中的TIN的可选条件之一，既不是充分条件，也不是必要条件，但当然是重要的可选条件。
6、数字高程分析中应考虑的三个重要原则是：
一是要能充分合理的反映三维相关性；
二是要能体现区域三维趋势面变化特征；
三是要能消除区域离散点聚集程度分布不均所带来的影响。
从目前各种算法看，前两个原则基本是可以通过采取各种办法来初步实现的（如带约束的Delaunay三角形通过迭代分析可以基本反映三维相关性，整体插值可以反映三维趋势面的变化特征）；但是对于第三个原则来说，目前各种算法是无法来描述和反映的。
7、Delaunay三角形分析中的难点，主要包括两个方面，一是如何去分析和考虑各种约束条件，二是如何应用优化方法确定Delaunay三角形。
8、应该来说，目前我们正在探讨将泛权算法应用于TIN分析中，而且思考的特点就是期望能从三个方面去综合考虑、分析，从而得到最佳结果，即：
一是能较好的反映三维空间距离上的相关性；
二是能反映区域三维趋势面变化特征；
三是在在考虑趋势面分析的同时又能反映区域离散点聚集程度分布不均所带来的影响。
| 
