【摘要】本文探讨了以平面散点集逐点插入的Delaunay三角化方法为基础,在三角化过程中采用一定策略,将其改进成为一种简单高效的方法。该方法能够适应各种边界,包括多岛、多连通域等复杂情况,能够生成贴体的三角网,网格能够保证符合Delaunay法则。
【关键词】Delaunay三角网三角剖分等值线
三角剖分是计算几何领域的主要课题之一,并具有广泛的应用前景。在计算机图形学、科学计算可视化、自然科学、特别是在地学领域,经常需要处理大量分布于某一区域内的离散数据。由于这些数据分布的不均匀性,就产生了一个如何合理有效地使用这些宝贵数据的问题。Voronoi图和Delaunay三角网是被普遍接受和广泛采用的用于分析研究区域离散数据的有力工具。当然,它不仅适用于地学,而且活跃于所有与简单三维分析有关的领域。
但经典的方法只能在平面散点集的凸集上构建,并且效率性态差,即随着点数的增加耗时急剧增加。为了适应工程的需要,本文改进了逐点插入法,使之成为简单易行具快捷高效的方法,并能适应各种边界,包括多岛、多连通域、凹边界等复杂情况。
1 Voronoi多边形和Delaunay三角网的定义及其性质[1]
设x为平面上的点,则区域V(i)={x∈E2|d(x,vi)≤d(x,vj), j=1,2,...,N, j≠I}称为Voronoi多边形(简称V-多边形)。各点的V-多边形共同组成Voronoi-图(简称V-图)。
Delaunay三角网的定义:有公共边的V-多边形称为相邻的V-多边形。连接所有相邻的V-多边形的生长中心所形成的三角网称为Delaunay三角网(简称D-三角网)。
D-三角网的外边界是一个凸多边形,它由节点集中的凸集形成,通常称为凸壳。D-三角网具有两个非常重要的性质。
(1)空外接圆性质:在由点集V所形成的D-三角网中,其每个三角形的外接圆均不包含点集V中的其他任意点。
(2)最大的最小角度性质:在由点集V所能形成的三角网中,D-三角网中三角形的最小角度是最大的。
由于这两个性质,决定了D-三角网具有极大的应用价值。同时,它也是二维平面三角网中唯一的、最好的。
2 改进方法中的数据结构
首先将需要三角剖分的点分为散点和边界点,边界点按一定的顺序(逆时针或顺时针)排列。点的数据结构为单向链表,定义如下。
typedef struct Vertex{
int ID; //ID号
double x,y,z;//坐标值
char mark;//材料、边界标记,区分散点、外边界点、内边界点
struct Vertex *next;//下一个节点
}* PVERTEX,VERTEX;
三角形单元的定义是三角剖分的基础,必须定义很好的结构表达三角形的拓扑结构,以提高算法的效率,并且必须方便三角形单元在三角网中脱离拓扑结构。本文定义如下。
typedef struct Triangle{
struct Edge *pe[3];//指向三角形的三个边
struct Vertex *pv[3];//指向三角形的三个顶点
int ID; //ID号
struct Triangle *next,*pre;//指向前后的三角形
}* PTRIANGLE,TRIANGLE;
三角形单元的拓扑结构还要通过边来实现,边的定义为:
typedef struct Edge{
struct Vertex *pv[2];//指向该边的两个顶点
struct Triangle *pt[2];//指向该边所属于的两个三角形
struct Edge *next,*pre;//指向前后的边
} *PEDGE, EDGE;
边界链表的定义如下:
typedef struct BndChain{
struct Vertex *chain;//一个边界
char mark;//边界标记,区分散点、外边界点、内边界点内边界点
struct BndChain *next;//下一个边界
}*PBNDCHAIN,BNDCHAIN;
3 判断一个点是否落在一个任意形状的多边形内的方法
一般来说,判断一个点是否落在一个任意形状的多边形内比较困难。本文使用了一种较为简单的方法来判断。
图1
输入为按一定顺序(逆时针或顺时针)排列的边界点集p1,p2,…pn,及点p的坐标。判断依据为:如果点落在多边形之外,则点与有向线段 所对应的有向弧的角度之和等于0;如果落在多边形之内,则有向弧的角度之和的绝对值等于2π,如图1。
4 核心算法
Tsai根据实现过程,把生成D-三角网的各种算法分为三类:分治算法、逐点插入法、三角网生长法[2]。本文采用逐点插入法,其核心思想[3]是:当添加一个新点时,找出包含此点的三角形(包括在三角形的边上)。如果落在三角形内,将此点与三角形的三个定点连接,并将三角形的三条边送入优化队列,按照Delaunay三角网的两个性质进行优化;如果落在三角形的边上,删除此边,重新建立两条新边,并将其余两边或四边(有公边的相邻三角形)送入优化队列优化。
5 优化算法
(1)从优化队列中取出一条边,开始优化此边。
(2)如果此边属于边界边,则此边不用优化。
(3)如果此边所在的正在被优化的三角形的外接圆包含了公用此边的三角形的除此边外的另一个顶点,将当前的优化边从优化队列中删除,将当前被优化的三角形删除,同时将该三角形的另外的两边加入到优化队列中;否则,将此边从优化队列中删除后送入优化后的队列,便于建立新的三角形单元。
(4)重复(1),(2),(3)步,直到优化队列为空。
最近点意义下的Voronoi图的直线对偶图就是Delaunay三角剖分,因此可以把上上篇描述的构造Voronoi图的分治算法用于Delaunay三角剖分。
增量算法:易于实现,使用广泛,适合小规模点集的三角化。具体过程如下:
1 遍历所有散点,生成一个包含所有散点的大三角形(顶点不在点集中)
2 有未处理过的点p,插入之,否则结束算法,退出
3 在已剖分好的三角网中找出包含点p的三角形t,把p与t的三个顶点相连,构成三个三角形
4 根据优化准则对局部生成的三角形进行优化(互换对角线等)
5 返回第2步
局部变换法:根据Delaunay三角剖分的性质2,首先构造一个不满足Delaunay三角剖分条件的三角网络,然后对两个共边三角形构成的凸四边形迭代换边使之满足Delaunay三角剖分的条件(主要是交换对角线的方法)
Delaunay三角剖分具有下列性质:
(1)Delaunay三角剖分所形成的三角形中,最小的内角是所有三角剖分中最大的。故Delaunay三角剖分所形成的三角形最接近于等边三角形,在很多应用中具有最优的性质。此性质等价于Delaunay三角剖分所形成的三角形的外接圆内不包含其他点。
(2)如果任意四点不共圆,则该四点只能形成唯一的Delaunay三角,否则不唯一。故可推知,对Delaunay三角剖分的局部确保可以保证使整体确保满足Delaunay三角剖分。
(3)在已Delaunay三角化的网格中加入一点P,只需要删除所有外接圆包含此点的三角形,并连接P与所有可见的点(即连接后不会与其他边相交),则形成的网格仍然满足Delaunay三角剖分的条件。
1、增量算法
该算法基于性质(3),算法简单,时间复杂度为O(nlogn),
使用广泛,基本步骤如下:
(1)生成一个包含所有点的大三角形(其定点不在点集中);
(2)对点集中的每个点,根据性质(3)进行处理(不删除大三角形的边);
(3)删除所有与大三角形相关的边。
该算法的时间主要用于对外接圆的搜索和对顶点的连接。其中,前者可以使用指南针算法进行优化;后者可以对点集进行排序,使加入网格的点均匀分布来降低复杂度。
2、局部变换法
该算法基于性质(2),首先构造一个不满足Delaunay三角剖分条件的三角网格,再对两个共边三角形构成的凸四边形迭代换边使之满足Delaunay三角剖分的条件(主要是交换对角线的方法)。
分享到:
相关推荐
定义了函数的分段三角形凸包,提出了一种控制顶点和权因子的确定方案。详细地讨论了函数的分段有理三次Bézier插值算法,定义了一种便于计算的新型误差。插值函数保持了原始函数的重要几何性质,如单调性、凹凸性、...
在Delaunay三角形网格立体图像编码算法的基础上,提出了一种特征点选取方法。该方法充分利用物体边缘进行特征点提取,建立Delaunay三角形时能根据物体的边缘分割物体,以便能更好地反映物体复杂运动与形变。PSNR值与...
针对DT模型基图像编码方法不能实现实时编码的不足,根据图像的多分辨率表示方法,采用分层搜索的思想,提出了一种基于MD或MV准则的图像描述中DT网格的快速生成方法,通过逐渐精细的搜索步长搜索网格节点,减少了逐点...
利用DT(Delaunay Triangulation)网格研究了彩色视频亮度和色度分量之间的相关性,提出了一种基于DT网格的彩色视频帧内编码方案。 该方案仅对亮度分量Y进行DT描述,利用亮度分量Y的部分网格节点经过相似变换生成...
2、知道几何边界时,用delaunay函数划分三角形网格由于区域内部没有点,质量很差,怎么改进 3、怎样避免产生过于狭长的delaunay 三角形 4、 凹多边形的情况怎么处理 第1个问题,看看帮助应该能解决。第2个问题,...
Delaunay算法的matlab实现,一种经典的三角网格划分方法。
点三角形 点多边形。 遭受浮点精度问题的困扰 三角三角 AABB-AABB 线线 射线平面 线平面 平面 点圆 2.生成网格 网格 网格形状:箭头,圆,线 3.凸包 计算几何中的一个常见问题是找到一组点的凸包。 2D空间...
针对任意平面多边形域,采用增量思想和均匀网格,在局部范围内快速生成约束Delaunay三角形.该方法 不会生成区域外的三角形;对存在折线、离散点以及含“洞”的情况不需要特殊处理.实验结果表明,该方法对于随机 生成...
(Delaunay是一种在离散点序列中快速构造三角形网格的方法,本代码依据的Delaunay三角形的性质:在已知的Dalaunay三角化的网格上加入一点P,只需要删除所有外接圆包含此点的三角形,并连接P与所有可见的点(即连接后...
这是一个delaunay三角剖分的代码。
Delaunay triangulation介绍文档,非常棒的讲义,处理网格划分和点的空间划分非常有用,作为参考
Delaunay三角形的网格剖分程序,用c++语言编写
二十面体网格的值3或4导致近似相等大小的三角形网格元素。 这些高密度情况下的节点位置可以用作球体均匀采样的近似值。 type当前可以采用三个字符串值: tet , oct和ico用于四面体,八面体和二十面体起始形状。 ...
文中给出了一种区域内布点的自动生成算法,可从...最终生成的内部点云和边界点既可以用来做无网格计算,也可以结合波前推进法生成Delaunay三角形网格。通过对网格生成算法的改进,算例表明该算法得到网格具有很好质量。
算法首次使用图像中物体边缘进行特征点提取,然后利用特征点建立 Delaunay三角形网格,并通过网格映射进行视差矢量场快速计算,最后通过内插算法进行中间视点图像生成.实验结果表明,合成的中间视点图像质量良 好,可以...
一种基于delaunay算法的凸多边形三角网格划分的实现
点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。计算误差会导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不...
针对任意域Delaunay三角剖分存在的局部网格质量不佳问题, 提出了一种改进的Delaunay算法。利用边界三角形单元节点和重心... 算例结果表明, 所提方法可以适应复杂几何边界区域的划分, 并可获得质量较高的三角形网格。
为提高带特征线约束的Delaunay三角剖分的速度和效率从两个方面进行改进一是生成无约束的...特征线的影响域及Delaunay三角形规则的边界条件在满足全局Delaunay三角剖分的前提下使插入的点最少对原有的网格影响最小
工程中加入CPP,配置好opencv运行即可。