亚克力抽奖箱
谢谢作者
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 三⾓⽹是“最接近于规则化的“的三⾓⽹。具体的说是指在两个相邻的三⾓形构成凸四边形的对⾓线，在相互交换后，六个内⾓的最⼩⾓不再增⼤。如下图所⽰： 制作ic卡>384孔板
1.4.Delaunay三⾓剖分的特性
以下是Delaunay剖分所具备的优异特性：
1.最接近：以最近临的三点形成三⾓形，且各线段(三⾓形的边)皆不相交。
2.唯⼀性：不论从区域何处开始构建，最终都将得到⼀致的结果。
3.最优性：任意两个相邻三⾓形形成的凸四边形的对⾓线如果可以互换的话，那么两个三⾓形六个内⾓中最⼩的⾓度不会变⼤。
4.最规则：如果将三⾓⽹中的每个三⾓形的最⼩⾓进⾏升序排列，则Delaunay三⾓⽹的排列得到的数值最⼤。
5.区域性：新增、删除、移动某⼀个顶点时只会影响临近的三⾓形。
6.具有凸多边形的外壳：三⾓⽹最外层的边界形成⼀个凸多边形的外壳。
1.5.局部最优化处理
理论上为了构造Delaunay三⾓⽹，Lawson提出的局部优化过程LOP(Local Optimization Procedure)，⼀般三⾓⽹经过LOP处理，即可确保成为Delaunay三⾓⽹，其基本做法如下所⽰： udn
1.将两个具有共同边的三⾓形合成⼀个多边形。
2.以最⼤空圆准则作检查，看其第四个顶点是否在三⾓形的外接圆之内。
3.如果在，修正对⾓线即将对⾓线对调，即完成局部优化过程的处理。
LOP处理过程如下图所⽰：
2.Delaunay剖分的算法
智能浴缸Delaunay剖分是⼀种三⾓剖分的标准，实现它有多种算法。高压直流供电
2.1.Lawson算法逐点插⼊的Lawson算法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：⾸先建⽴⼀个⼤的三⾓形或多边形，把所有数据点包围起来，向其中插⼊⼀点，该
点与包含它的三⾓形三个顶点相连，形成三个新的三⾓形，然后逐个对它们进⾏空外接圆检测，同时⽤Lawson设计的局部优化过程LOP进⾏优化，即通过交换对⾓线的⽅法来保证所形成的三⾓⽹为Delaunay三⾓⽹。上述基于散点的构⽹算法理论严密、唯⼀性好，⽹格满⾜空圆特性，较为理想。由其逐点插⼊的构⽹过程可知，遇到⾮Delaunay边时，通过删除调整，可以构造形成新的Delaunay边。在完成构⽹后，增加新点时，⽆需对所有的点进⾏重新构⽹，只需对新点的影响三⾓形范围进⾏局部联⽹，且局部联⽹的⽅法简单易⾏。同样，点的删除、移动也可快速动态地进⾏。但在实际应⽤当中，这种构⽹算法当点集较⼤时构⽹速度也较慢，如果点集范围是⾮凸区域或者存在内环，则会产⽣⾮法三⾓形。
2.2.Bowyer-Watson算法
Lawson算法的基本步骤是：
1、构造⼀个超级三⾓形，包含所有散点，放⼊三⾓形链表。
2、将点集中的散点依次插⼊，在三⾓形链表中出其外接圆包含插⼊点的三⾓形（称为该点的影响三⾓形），删除影响三⾓形的公共边，将插⼊点同影响三⾓形的全部顶点连接起来，从⽽完成⼀个点在Delaunay三⾓形链表中的插⼊。
3、根据优化准则对局部新形成的三⾓形进⾏优化。将形成的三⾓形放⼊Delaunay三⾓形链表。
4、循环执⾏上述第2步，直到所有散点插⼊完毕。
这⼀算法的关键的第2步图⽰如下：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议