Delaunay三角剖分算法
默认分类2009-12-16 11:41:23 阅读33 评论0 字号：大中小订阅
转载：https://www.doczj.com/doc/765938372.html,/renliqq/archive/2008/02/06/1065399.html
1. 三角剖分与Delaunay剖分的定义
如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下：
1.1.三角剖分定义
【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：
1.除了端点，平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。
1.2. Delaunay三角剖分的定义
在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
1.3.Delaunay三角剖分的准则
要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：
2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：
1.4.Delaunay三角剖分的特性
以下是Delaunay剖分所具备的优异特性：
1.最接近：以最近临的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
1.5.局部最优化处理
理论上为了构造Delaunay三角网，Lawson提出的局部优化过程
LOP(Local Optimization Procedure)，一般三角网经过LOP处理，即可确保成为Delaunay三角网，其基本做法如下所示：
1.将两个具有共同边的三角形合成一个多边形。
2.以最大空圆准则作检查，看其第四个顶点是否在三角形的外接圆之内。
3.如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。
LOP处理过程如下图所示：
2.Delaunay剖分的算法
Delaunay剖分是一种三角剖分的标准，实现它有多种算法。
https://www.doczj.com/doc/765938372.html,wson算法
逐点插入的Lawson算法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，同时用Lawson设计的局部优化过程LOP进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。
上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，遇到非Delaunay边时，通过删除调整，可以构造形成新的Delaunay边。在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。
2.2.Bowyer-Watson算法
Lawson算法的基本步骤是：
1
2、将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
3、根据优化准则对局部新形成的三角形进行优化。将形成的三角形放入Delaunay三角形链表。
4、循环执行上述第2步，直到所有散点插入完毕。
这一算法的关键的第2步图示如下：
Delaunay三角剖分算法
目录
1. 三角剖分与Delaunay剖分的定义
如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下：
1.1.三角剖分定义
【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作
为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个
平面图G，该平面图满足条件：
1.除了端点，平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。
1.2. Delaunay三角剖分的定义
在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多
三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，
那么该三角剖分称为Delaunay三角剖分。
1.3.Delaunay三角剖分的准则
要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三
角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：
2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay 三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：
1.4.Delaunay三角剖分的特性
以下是Delaunay剖分所具备的优异特性：
1.最接近：以最近临的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
1.5.局部最优化处理
理论上为了构造Delaunay三角网，Lawson提出的局部优化过程LOP(Local Optimization Procedure)，一般三角网经过LOP处理，即可确保成为Delaunay三角网，其基本做法如下所示：
1.将两个具有共同边的三角形合成一个多边形。
2.以最大空圆准则作检查，看其第四个顶点是否在三角形的外接圆之内。
3.如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。
LOP处理过程如下图所示：
2.Delaunay剖分的算法
Delaunay剖分是一种三角剖分的标准，实现它有多种算法。
https://www.doczj.com/doc/765938372.html,wson算法
逐点插入的Lawson算法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，同时用Lawson设计的局部优化过程LOP进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。
上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，遇到非Delaunay边时，通过删除调整，可以构造形成新的Delaunay边。在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。
如下图所示：当离散点集构成圆环时，Lawson算法产生的非法三角形
离散点集合
正确的三角剖分
Lawson算法产生的三角剖分
2.2.Bowyer-Watson算法
Lawson算法的基本步骤是：
1、构造一个超级三角形，包含所有散点，放入三角形链表。
2、将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
3、根据优化准则对局部新形成的三角形进行优化。将形成的三角形放入Delaunay 三角形链表。
4、循环执行上述第2步，直到所有散点插入完毕。
这一算法的关键的第2步图示如下：
第36卷 第3期测 绘 学 报 Vol.36,No.3 2007年8月 ACTA GEODAETICA et CARTO GRAPHICA SINICA Aug ,2007 文章编号:100121595(2007)0320358205中图分类号:P208 文献标识码:A Delaunay 三角形构网的分治扫描线算法 芮一康,王结臣 (南京大学地理信息科学系,江苏南京210093) A N e w Study of Compound Algorithm B ased on Sw eepline and Divide 2and 2conquer Algorithms for Constructing Delaunay T riangulation RU I Y i 2kang ,WAN G Jie 2chen (Depart ment of Geographic Inf ormation Science ,N anji ng U niversity ,N anji ng 210093,Chi na ) Abstract :As one of the most important DTM model ,Delaunay triangulation is widely applied in manifold fields.A wide variety of algorithms have been proposed to construct Delaunay triangulation ,such as divide 2and 2conquer ,in 2cremental insertion ,trangulation growth ,and so on.The compound algorithm is also researched to construct Delau 2nay triangulation ,and prevalently it is mainly based on divide 2and 2conquer and incremental insertion algorithms.This paper simply reviews and assesses sweepline and divide 2and 2conquer algorithms ,based on which a new com 2pound algorithm is provided after studying the sweepline algorithm seriously.To start with ,this new compound al 2gorithm divides a set of points into several grid tiles with different dividing methods by divide 2and 2conquer algo 2rithm ,and then constructs subnet in each grid tile by sweepline algorithm.Finally these subnets are recursively merged into a whole Delaunay triangulation with a simplified efficient LOP algorithm.For topological structure is im 2portant to temporal and spatial efficiency of this algorithm ,we only store data about vertex and triangle ,thus edge is impliedly expressed by two adjacent triangles.In order to fit two subnets merging better ,we optimize some data structure of sweepline algorithm.For instance ,frontline and baseline of triangulation are combined to one line ,and four pointers point to where maximum and minimum of x axis and y axis are in this outline.The test shows that this new compound algorithm has better efficiency ,stability and robustness than divide 2and 2conquer and sweepline algo 2rithms.Especially if we find the right dividing method reply to different circumstance ,its superiority is remarkable.K ey w ords :Delaunay triangulation ;compound algorithm ;sweepline algorithm ;divide 2and 2conquer algorithm 摘 要:Delaunay 三角网作为一种主要的DTM 表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay 三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。 收稿日期:2006206221;修回日期:2007202206 基金项目:国家自然科学基金(40401046) 作者简介:芮一康(19832),男,江苏溧阳人,研究生,主要从事地理信息系统理论与应用研究。 关键词:Delaunay 三角网;合成算法;扫描线算法;分治算法 1 引 言 2维平面域内任意离散点集的不规则三角网(TIN 2Triangular Irregular Network )的构建是GIS 数据表达、管理、集成和可视化的一项重要内 容,也是地学分析、计算机视觉、表面目标重构、有限元分析、道路CAD 等领域的一项重要的应用技 术。在所有生成TIN 的方法中,Delaunay 三角网 最优,它尽可能避免了病态三角形的出现,常常被用来生成TIN 。Delaunay 三角网是Voronoi 图的直线对偶图,即是连接所有相邻的Voronoi 多边形的生长中心所形成的三角网。它有以下两条重要性质[1]:空外接圆性质,即由点集所形成的三角网中,每个三角形的外接圆均不包含点集中的
Delaunay三角剖分算法 默认分类2009-12-16 11:41:23 阅读33 评论0 字号：大中小订阅 转载：https://www.doczj.com/doc/765938372.html,/renliqq/archive/2008/02/06/1065399.html 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下： 1.1.三角剖分定义 【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件： 1.除了端点，平面图中的边不包含点集中的任何点。 2.没有相交边。 3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。 1.2. Delaunay三角剖分的定义 在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起： 【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。 【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。 1.3.Delaunay三角剖分的准则 要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。 然后有两个问题要解决：
1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”； 大概的道理我们是懂了，但是给你任意一些点，你采用什么思路
本课题的研究方法 三角网格化主要有两种准则:一种称为Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。 Delaunay的重要性质 空外接圆性质：在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。λ 最大最小角度性质：在由点集V生成的Delaunay三角网中，所有三角形中的最小角度是最大的，即在生成的三角形网格中,各三角形的最小内角和为最大。λ唯一性：不论从区域何处开始构网，最终都将得到一致的结果。λ 由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网；Lingas进一步论证了“在一般情况下，Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要算法依据。 3.3 详细算法描述 算法基于上述的传统构建算法，但仅有两步： 第一步： （1）在离散点集中寻找一纵坐标最小的点A。 （2）以点A为起点，寻找两个点B、D，使得向量AB与横坐标轴夹角最小，向量AD与横坐标轴夹角最大。若点A、B、D共线，将原B点标记为A，寻找点D，使得向量AD与直线AB夹角最大；寻找点C使得向量BC与线段AB夹角最小。否则，若A、B、D不共线，则寻找点C使得向量BC与线段AB夹角最小。这样，所有点都在逆时针旋转的折线DABC的左侧。 （3）上面一步生成的点C、D如果为同一点，则△ABC（或△ABD）即为包含所有不规则点的Delaunay三角形，生成凸包的过程结束跳过一下各步；否
最新文件---- 仅供参考------已改成word文本------ 方便更改 三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。
然后有两个问题要解决： 1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”；
第24卷 第2期2004年2月北京理工大学学报 T r ansactions of Beijing Instit ute o f T echnolog y V ol.24 N o.2F eb.2004 文章编号:1001-0645(2004)02-0129-04 平面点线集三角剖分的扫描算法 周培德 (北京理工大学信息科学技术学院计算机科学工程系,北京 100081) 摘 要:提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O (N lb N ),其中N 是点线集中点的数目与线段端点数之和. 关键词:散乱点线集;三角剖分;平面扫描;算法;时间复杂性中图分类号:T P 301.6 文献标识码:A Sweeping Algorithm for Triangulation of Plane Point -Line Set ZHOU Pei-de (Depar tment of Co mputer Science and Engineer ing ,School o f Infor matio n Science and T echno lo gy ,Beijing Instit ut e of T echno lo gy ,Beijing 100081,China) Abstract :Sw eeping alg orithm is presented fo r the tr iangulation of plane point -line set .T he algor ithm m akes use of the idea of plane sw eeping .When the sw eep -line reaches it ,the event -po int w ill be dealt w ith,viz.,the event-point is connected w ith so me points sw ept and thus the sw ept regions are triang ulated.When the sw eep-line r eaches the leftmost event-point,the point w ill be dealt w ith ,and the triang ulation of the plane point -line set is accom plished .It is prov ed in detail that the time co mplex ities o f the alg orithm is O (N lb N ),w here N is the sum of the num ber of points and the num ber of line-seg ment endpoints w ithin the point-line set. Key words :debunching point-line set;triang ulation;plane sw eep;alg orithm;tim e co mplex ity 收稿日期:20030321 作者简介:周培德(1941-),男,教授. 平面点集三角剖分问题是计算几何中的一个重要问题,它是从许多实际问题中提出来的,至今,人们已研究了求解该问题的许多算法,其中以Delaunay 算法最为著名.将平面点集中的某些点组成点对并满足某些特殊关系,比如它们为平面线段的两个端点,而另外一些点仍为孤立点,这样便构成点线集.平面点集三角剖分问题可以转换为平面点线集的三角剖分问题,并且它们具有相同的时间复杂性下界.平面点线集三角剖分问题要求三角形的三条边或为点线集中的线段,或为点线集中不同线段端点的连线,或为点线集中点与线段端点的连线, 或为点线集中点与点的连线.三角形的顶点为点线集中的点或线段端点.另外还要求连线与连线,连线与点线集中线段均不相交.给定的平面点线集中线段互不相交(线段端点处相交除外).不难看出,平面散乱点线集三角剖分问题是平面点集三角剖分问题的一个特殊情况.按照常规,求解平面点集三角剖分的算法(比如Delaunay 三角剖分算法)可以用于平面散乱点线集的三角剖分.但在平面点集三角剖分的算法中如何保证点线集中的线段必是三角形的一条边,以及连线与点线集中线段不相交.只要解决这个问题就可以实现点线集的三角剖分.目前解决这
第26卷 第5期2010年9月地理与地理信息科学 Geog ra phy and Geo-Infor matio n Science V ol.26 N o.5September 2010 收稿日期:2010-04-21; 修订日期:2010-06-10 基金项目:国家自然科学基金重点项目(50839001);国家自然科学基金项目(50874021、50779006);辽宁省高等学校科研项目计划(L20100321) 作者简介:赵晓东(1969-),男,博士,教授,从事GIS 在采矿、岩土工程应用和水动模型耦合的研究。E-mail:xdong.zhao@https://www.doczj.com/doc/765938372.html, 基于GIS 的高质量约束Delaunay 三角网格剖分 赵晓东1 ,晏小宝1 ,沈永明2 ,王 亮 2 (1.大连大学院士创业园中日地层环境科学研究中心,辽宁大连116622;2.大连理工大学海岸和近海工程国家重点实验室,辽宁大连116023) 摘要:在分析现有非结构化网格剖分算法的基础上,提出了一种GIS 支持下的改进分治算法实现约束Delaunay 三角网格剖分。该方法利用了GIS 的空间拓扑关系对算法输入数据进行预处理,基于三角形的统一数据结构实现了网格细化,对输出剖分网格进行准确的拓扑和约束条件的检查,并基于推进阵面算法思想,结合空间邻近拓扑关系实现了三角剖分节点和网格的重新编号,方便了实际问题中开边界条件的赋值,提高了计算效率。实例应用表明,该方法大大简化了数值模型非结构化网格剖分的前处理过程,集成了几种综合算法的优点,在保证原分治算法时间复杂度的基础上,提高了约束条件下Delauna y 三角网格生成的质量。关键词:网格剖分;GIS;约束Delaunay 三角剖分 中图分类号:P208 文献标识码:A 文章编号:1672-0504(2010)05-0024-05 0 引言 在应用有限元、有限差分和有限体积法对力学问题进行数值计算的前处理中,网格自动剖分占有重要的位置。目前,实现网格剖分的算法很多,而且不断有新的算法推出,其相关研究领域不仅针对数值模拟计算,对GIS 数据表达、地学分析、计算机视觉、表面目标重构等众多领域也是一项重要的应用技术[1-3]。网格剖分可分为结构化网格(Structured Gr id)和非结构化网格(Unstructured Grid)两种。非结构化网格易于控制网格单元大小、形状及网格点位置,可以实现合理分布网格的密度,提高计算精度,因此具有比结构化网格更大的灵活性和对复杂边界更强的适应性。生成二维非结构化网格的常用方法[4]有四叉树法(Quadtr ee)、Delaunay 三角剖分法(Delaunay T riangulation,DT)和推进阵面法(Ad -v ancing Fr ont M ethod,AFM)以及几种方法的综合和改进。由于Delaunay 三角网是Vor ono i 图的直线对偶图,具有空外接圆和最大最小角特性,还可以尽可能地避免病态三角形的出现,实现约束条件下的三角剖分,因此,在数值计算非结构化网格剖分和GIS 三角网(T IN)的数据格式表达中广泛使用。 目前常见的构建Delaunay 三角网的算法有:分治算法(Div ide -and -conquer )、逐点插入算法(Incre -m ental Insertio n)、生长算法和扫描线算法(Sw eep -line)[3,5-7],其中以分治算法效率最高,时间复杂度 为O(N logN)[5]。由于实际的不同需要,除几何约束条件外,对三角剖分的角度、大小和节点物理量的控制也都有相应约束,目前的剖分算法尚不能满足以上全部约束条件进行剖分。本文基于改进的分治 算法,提供了梯度变化和针对实际问题的单元和节点重编号,并利用GIS 强大的空间数据处理和分析功能对算法做数据前后处理,保证了高质量约束Delaunay 三角网格剖分的生成。 1 约束Delaunay 三角化方法 分治算法[5]的基本思路是把输入点集分割为数个较小的点集,在各个子点集内生成小三角网,再逐级合并的一个递归过程。子点集最终只有两点或者三点,形成一条边、共线边或者三角形。算法必须将点集连接为凸区域(凸壳),对凹区域和多连通区域会产生域外三角形,无法保证约束边的存在。约束Delaunay 三角化的分治算法的关键过程及实现方法如下。 1.1 点集划分 原分治算法只有Y 轴方向的分割,这里改进为交替分割[8],即点域X 轴方向的长度大于Y 轴方向的长度,则以X 轴方向对半分割点集,否则以Y 轴方向对半分割点集。该过程为递归调用的分割过程。 1.2 约束特征线重构 在Delaunay 三角剖分上,采用逐次加入约束特