在3D建模中,通常得到一系列散乱的点集,该点集描述了物体外表面的几何特征和构造。为了用三角网格进行描述物体表面,沃恩则需要对其进行三角剖分。
二维Delaunay三角剖分:
Delaunay边:e是E中满足以下条件的边:存在一个圆经过其端点a b,圆内不包含点集V中的其他任何点。
Deluanay三角剖分:如果V的一个三角剖分T只包含Delaunay边,那么该三角剖分为Deluanay剖分。
Deluanay 三角剖分的特性:
(1)最大化三角剖分T中所有三角形的最小角,以避免出现过于扁平的三角形。
(2)三角剖分T的任何一个三角形的外接圆满足空圆性质:该圆内不包含任何其他点。(局部优化处理)
(3)四边形对应的剖分对角线两边的角度之和小于或者等于180,则该剖分满足Delaunay特性。
对于任意四边形,都可通过修改对角线的方法来得到Delaunay三角剖分。
算法描述:
输入:平面有限点集
输出:Delaunay三角剖分T
构建散点集V的任意一个三角剖分T
T中所有不满足空圆特性的内部边都压入栈并且做标记。
while 栈非空 do
begin
pq=pop()
去掉pq标记。
if pq不符合空圆特性 then
begin
用所在四边形的另一条对角线代替他,并将四边形的4条边中未标记的边压入栈。
end
end
return T
另一种方法:随机增量算法
该方法首先用一个足够大的三角形围住一堆随机排列的散列点,然后依次从点集中插入新点,不断更新当前的三角剖分,直至所有点插入完毕。
三维Delaunay三角剖分:
常用方法是,先在二维平面上对其进行三角剖分,然后加上高度数据,来得到三维三角形剖分。在各个方法存在投影变形。
有一个适用于平面和空间三角剖分的算法,该算法的实质上是不断往点集中添加新顶点,然后通过Delaunay空洞的特性构造新的剖分。
Delaunay空洞:在Delaunay三角剖分T中添加一个新顶点P,删除所有外接圆包含P的三角形,形成一个新的三角形集合B,则B成为Delaunay空洞。
分享到:
相关推荐
尤其是Delaunay三角剖分,由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关,如Voronoi图,EMST树,Gabriel图等。Delaunay三角剖分有最大化最小角,“最接近于规则化的“的三角网和唯一性(任意四点不...
Delaunay三角剖分算法 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格,这就是散点集的三角剖分问题,散点集的三角剖分,对数值分析以及图形学来说,都是极为重要的一项预处理技术。 ...
为提高带特征线约束的Delaunay三角剖分的速度和效率从两个方面进行改进一是生成无约束的Delaunay三角网时采用并行剖 分算法二是在约束线上插入点时应用取三角形外接圆与特征线交点的方法并行剖分算法具有较好的加速...
用python3.6实现delaunay三角剖分算法,读入存有坐标的csv文件,计算出结果用Tkinter库显示。
找了半天国内网站上都没找到好用的,好不容易从国外的网站上下载到的..带示例数据和源码 delaunay三角剖分
刚实现的VS2008+opengl实现的Delaunay三角剖分代码,代码是C++实现
用powercrust算法实现的delaunay三角剖分算法,用到了MATLAB的delaunayn函数库,有兔子等点云源数据和完整的代码,程序可运行,亲测可用
delaunay三角剖分,基于opencv
本书对二维平面和三维空间限定Delaunay三角剖分技术进行了系统全面介绍,给出了可以在任意点、线段和平面片的限定条件下完成限定Delaunay三角剖分及网格优化的算法,并论证了算法的有效性。本书可供计算机等领域的...
离散点生成三角网络的一个经典算法 算法原理:分为三步: 一、凸包生成:二、环切边界法凸包三角剖分三、离散的内插:
Delaunay三角剖分逐点插入算法实现
用vc实现任意多边形的Delaunay三角剖分(计算几何作业)
使用Matlab实现了delaunay三角剖分,delaunay三角形具有一些非常好的性质,可以用来生成Voronoi图。
基于python语言的Delaunay三角剖分算法实现
基于Delaunay三角剖分的中间视合成方法研究,李兵,孙汉旭,中间视合成是实现多视点自由立体显示的重要步骤。本文提出了一种基于Delauray三角剖分的中间视合成方法,其基本步骤为:首先得到样�
用VB做的交互式Delaunay三角剖分程序,用户用鼠标左键点击确定点的位置,每点一下就多一个点,根据新的点改变三角网。
用C语言写的关于Delaunay剖分的程序。 有详细的源代码。 程序清楚。
# ------Delaunay三角剖分,绘制Voronoi维诺图------------------------------------- # 输入:rgb人脸image、landmark坐标 (68, 2) # 输出:delaunay_image、Voronoi_image # 第1部分: 读取人脸landmark # ...
Delaunay 三角剖分 算法的实现和渲染 代码&文档
根据Delaunay 三角剖分唯一、最优的特点, 详细阐述了Delaunay 三角剖分应用于特定的任意多边形轮 廓的实现算法, 介绍了相关的轮廓预处理技术, 并对本算法提出了两点改进, 给出了该三角剖分的应用实例