23角剖分算法介绍.docVIP

2 三角剖分算法介绍 2.1Delaunay三角剖分理论基础 2.1.1VORONOI图 1908年，俄国数学家M.G. Voronoi提出了Voronoi图[1]，它是计算几何学上非常重要的工具之一，被广泛应用于各个领域中。Voronoi图是由平面区域中连接两邻点的线段的中垂线所形成的区域。它又叫Dirichlet图或Thiessen多边形[2]。Voronoi图是自然界中的宏观物体和微观物体以空间距离相互作用所形成的一种网格结构，应用的范围相当广泛，特别是在计算几何学领域的应用[3]。Voronoi图是一种关于平面或空间区域划分的基础数据结构。100多年来，它被广泛应用在与几何信息相关的各个领域。随着计算机科学技术的不断普及和发展，Voronoi图的应用领域也在不断地扩大。对于Voronoi图的应用，以90年代以来的应用更为突出。 Voronoi图的本质属性是由空间实体几何唯一确定的，不是通过其他方法强加上去的。从Voronoi图的数字几何角度来看，它是针对平面n个离散点而言的，把平面分为若干区域，每一个区域包含一个点，该点所在的区域就是到该点距离最近的点的集合。 设p1，p2是平面上两点，L是线段p1p2的中垂线，L将平面分成两部分LL和LR，位于LL内的点pl具有特性：d(pl,p1)d(pl,p2)，其中d(pl,pi)表示pl与pi之间的欧几里得距离，i=1，2。这意味着，位于LL内的点比平面上其他点更接近点p1，换句话说，LL内的点是比平面上其他店更接近于p1的点的轨迹，记为V(p1)，如图2.1所示。如果用H(p1,p2)表示半平面LL，而LR=H(p2,p1)，则有V(p1)=H(p1,p2)，V(p2)=H(p2,p1)。 给定平面上n个点的点集S，S={p1,p2, …,pn}。定义： V(pi)= 即V(pi)表示比其他点更接近pi的点的轨迹是n-1个半平面的交，它是一个不多于n-1条边的凸多边形区域，称为关于pi的Voronoi多边形或关于pi的Voronoi域 。对于S中的每个点都可以作一个Voronoi多边形，这样的n个Voronoi多边形组成的图称为Voronoi图。Voronoi多边形的每条边是S中某两点的连线的垂直平分线，所有这样的两点连线构成一个图，称为Voronoi图的直线对偶图。如图2.2所示，虚线表示voronoi图，实线表示其对偶图。 Voronoi图有以下一些性质： 性质1.n个点的点集S的Voronoi图至多有2n-5个顶点和3n-6条边。 性质2.每个Voronoi点点好是三条Voronoi边的交点。 性质3.Voronoi图的对偶图实际上时点集的一种那个三角剖分，该三角剖分就是Delaunay三角剖分[4]。 性质3实际上告诉我们可以用构造Voronoi图的方法来求平面点集的三角剖分，但实际上这种方法较少使用，因为算法的效率不好。 2.1.2Delaunay三角剖分的基本概念 1、基本概念 （1）域分割 给定平面上的n个不相重的散乱数据点，对每个散乱数据点构造一个域，使该域内的任一点离此散乱点比离其他散乱点更近，这种域分割就是上节介绍的Voronoi图，也称Dirichlet域分割，由上节可知，域边界其实就是连接两个相邻散乱点的直线的垂直平分线。 （2）Delaunay三角化 对平面上的散乱数据点进行域分割后，将具有公共域边界的散乱点对相连形成的三角剖分称为Delaunay三角剖分。 （3）优化 对三角网格进行优化，就是要使三角网格整体上尽量均匀，避免出现狭长三角形，也就是获得Delaunay三角化。 2、三角剖分优化准则 在三角剖分过程中，人们往往先用一种简单的方法构造散乱点的初始三角剖分，然后对其进行优化以获得Delaunay剖分。优化的方法取决于所采用的优化准则，平面三角剖分最常用的优化准则有Thiessen区域准则、最小内角最大准则、圆准则。Sibson证明了这三个准则的等价性，并指出符合这三个准则的三角剖分只有一个，即Delaunay三角剖分。 最小内角最大准则 对一个严格凸的四边形进行三角化时，有两种选择，最小内角最大准则就是要保证对角线两侧两个三角形中的最小内角为最大，如图2.3所示。 圆准则 严格凸四边形中的三个顶点确定一个圆，如果第四个顶点落在圆内，则将第四个顶底与其相对的顶点相连，否则将另外两个顶点相连，这个准则称为圆准则。也就是说，符合圆准则的三角剖分中，任一三角形的外接圆内不应该包含其他点，如图2.4所示。 局部优化 局部优化是指对任意一个凸四边形的对角线，依据某种优化准则做交还测试后所得到的三角剖分。 全局优化 当三角形剖分T中每一条内边上的两个三角形所形成的凸四边形都满足局部优化标准时，称该