三⾓剖分定义
【定义】三⾓剖分：假设V是⼆维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段，E为e的集合。那么该点集V的⼀个三⾓剖分T = (V,E)是⼀个平⾯图G，该平⾯图满⾜条件： 1、除了端点，平⾯图中的边不包含点集中的任何点。
2、没有相交边。// 边和边没有交叉点。
3、平⾯图中所有的⾯都是三⾓⾯，且所有三⾓⾯的合集是散点集V的凸包。 // 凸包的概念：⽤不严谨的话来讲，给定⼆维平⾯上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。
Delaunay三⾓剖分的定义
在实际中运⽤的最多的三⾓剖分是Delaunay三⾓剖分，它是⼀种特殊的三⾓剖分。先从Delaunay边说起：
象纸
【定义】Delaunay边：假设E中的⼀条边e (两个端点为a，b)，e若满⾜下列条件，则称之为Delaunay边：存在⼀个圆经过a，b两点，圆内（注意是圆内，圆上最多三点共圆）不含点集V中任何其他的点，这⼀特性⼜称空圆特性。
【定义】Delaunay三⾓剖分：如果点集V的⼀个三⾓剖分T只包含Delaunay边，那么该三⾓剖分称为Delaunay三⾓剖分。
Delaunay三⾓剖分的准则
要满⾜Delaunay三⾓剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三⾓⽹是唯⼀的（任意四点不能共圆），在Delaunay三⾓形⽹中任⼀三⾓形的外接圆范围内不会有其它点存在。如下图所⽰：
2、最⼤化最⼩⾓特性：在散点集可能形成的三⾓剖分中，Delaunay三⾓剖分所形成的三⾓形的最⼩ ⾓最⼤。从这个意义上讲，Delaunay三⾓⽹是"最接近于规则化的"三⾓⽹。具体的说是在两个相邻的三⾓形构成凸四边形的对⾓线，在相互交换后，两个内⾓的最⼩⾓不再增⼤。如下图所⽰：
Delaunay三⾓剖分的特性
以下是Delaunay剖分所具备的优异特性：
1、最接近：以最接近的三点形成三⾓形，且各线段（三⾓⾏的边）皆不相交。
2、唯⼀性：不论从区域何处开始构建，最终都将得到⼀致的结果。
3、最优性：任意两个相邻三⾓形构成的凸四边形的对⾓线如果可以互换，那么两个三⾓形六个内⾓中最⼩⾓度不会变化。
4、最规则：如果将三⾓⽹中的每个三⾓形的最⼩⾓进⾏升序排列，则Delaunay三⾓⽹的排列得到的数值最⼤。
5、区域性：新增、删除、移动某⼀个顶点只会影响邻近的三⾓形。 6、具有凸边形的外壳：三⾓⽹最外层的边界形成⼀个凸多边形的外壳。
局部最优化处理
理论上为了构造Delaunay三⾓⽹，Lawson提出的局部优化过程LOP(Local Optimization Procedure)，⼀般三⾓⽹经过LOP处理，即可确保为Delaunay三⾓⽹，其基本做法如下所⽰：
1、将两个具有共同边的三⾓形合成⼀个多边形。
2、以最⼤空圆准则作检查，看其第四个顶点是否在三⾓形的外接圆内。
发动机支撑架
3、如果在，修正对⾓线即将对⾓线对调，即完成局部优化过程的处理。
LOP处理过程如下图所⽰：
Delaunay剖分的算法joyvpn
Delaunay剖分是⼀种三⾓剖分的标准，实现它有多种算法。最常⽤的是逐点插⼊法。
Lawson算法的基本步骤是：
1、构造⼀个超级三⾓形，包含所有散点，放⼊三⾓形链表。
2、将点集中的散点依次插⼊，在三⾓形链表中出其外接圆包含插⼊点的三⾓形（称为该点的影响三⾓形），删除影响三⾓形的公共边，将插⼊点同影响三⾓形的全部顶点连接起来，从⽽完成⼀个点在Delaunay三⾓形链表中的插⼊。
3、根据优化准则对局部新形成的三⾓形进⾏优化。将形成的三⾓形放⼊Delaunay三⾓形链表。
4、循环执⾏上述第2步，直到所有散点插⼊完毕。
这⼀算法的关键的第2步图⽰如下：
伪代码表述
input: 顶点列表(vertices) // vertices为外部⽣成的随机或乱序顶点列表
output：已确定的三⾓形列表(triangles)
初始化顶点列表
创建索引列表(indices = new Array(vertices.length)) // indices数组中的值为0,1,2,3,......,vertices.length-1
基于vertices中的顶点x坐标对indices进⾏sort // sort后的indices值顺序为顶点坐标x从⼩到⼤排序（也可对y坐标，本例中针对x坐标） 确定超级三⾓形
将超级三⾓形保存⾄未确定三⾓形列表（temp triangles）
将超级三⾓形push到triangles列表
遍历基于indices顺序的vertices中每⼀个点 // 基于indices后，则顶点则是由x从⼩到⼤出现
初始化边缓存数组（edge buffer）
遍历temp triangles中的每⼀个三⾓形
计算该三⾓形的圆⼼和半径
如果该点在外接圆的右侧
则该三⾓形为Delaunay三⾓形，保存到triangles
并在temp⾥去除掉
跳过
如果该点在外接圆外（即也不是外接圆右侧）
则该三⾓形为不确定 //后⾯会在问题中讨论
跳过
如果该点在外接圆内
则该三⾓形不为Delaunay三⾓形
将三边保存⾄edge buffer
在temp中去除掉该三⾓形
对edge buffer进⾏去重
将edge buffer中的边与当前的点进⾏组合成若⼲三⾓形并保存⾄temp triangles中
将triangles与temp triangles进⾏合并
除去与超级三⾓形有关的三⾓形
end
MATLAB实现
clc;
clear;
close all;
rand('state', 0);
node = 8;
x = rand(1,node);
y = rand(1,node);
% delaunay是MATLAB中三⾓剖分的函数，返回的TRI是三⾓形的矩阵% TRI的每⼀⾏表⽰三⾓形的三个点
TRI = delaunay(x,y);
% 绘图
figure;
xmin = min(x(:)); xmax = max(x(:));
ymin = min(y(:)); ymax = max(y(:));
xl = xmax - xmin; yl = ymax - ymin;
axis([xmin-xl*0.1, xmax+xl*0.1,...
ymin-yl*0.1, ymax+yl*0.1]);
hold on;
n = size(TRI, 1);
for i = 1 : n
t1 = TRI(i, :);
for j = 1 : length(t1)-1
xt = [x(t1(j)) x(t1(j+1))];
yt = [y(t1(j)) y(t1(j+1))];
plot(xt, yt, 'k-', 'LineWidth', 2);
pause(0.1);
end
xt = [x(t1(end)) x(t1(1))];
yt = [y(t1(end)) y(t1(1))];
plot(xt, yt, 'k-', 'LineWidth', 2);
pause(0.1);
end
W = zeros(node);
for i = 1 : n
for j = 1 : length(TRI(i, :))-1
W(TRI(i, j), TRI(i, j+1)) = 1;
W(TRI(i, j+1), TRI(i, j)) = 1;
end
人脸识别智能门禁W(TRI(i, end), TRI(i, 1)) = 1;
W(TRI(i, 1), TRI(i, end)) = 1;
end
蚊帐 圆顶for i = 1 : node
别巡检2for j = 1 : node
if ~W(i, j)
W(i, j) = 10000;
end
end
end
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议