Del***n***剖分及其性质
在二维情况下的三角网格和在三维情况下的四面体网格，具有很强的表示模型的能力。Del***n***剖分是二维Del***n***三角形化和三维Del***n***四面体化的总称。在二维情况下，指的是将一些随机散乱的点，连成三角形网，并给出每个三角形的相邻信息。首先，需要定义一个数据结构，使得三角形的组成及其相邻关系均可以用这个数据结构表示出来。
在二维情况下，这个数据结构通常用一个n×6维的矩阵表示出来。如图2.1（b）是一个三角形网，图2.1（c）是其三角形构成和相邻关系。这个矩阵的头三列为三角形结点的编号，后三列为相邻三角形的编号。
图2.1 二维Del***n***剖分数据结构
（a）Dirichlet多边形；（b）Del***n***三角形化；（c）数据结构
如图，1号三角形是由15、5、4号点组成，其中15号点对边的相邻三角形编号4,5号点对边的三角形编号为2,4号点对边的三角形编号为0（指外边）。可见，当三角形的三个顶点的顺序在数据结构中确定下来以后，其相邻三角形编号的顺序和在数据结构中的位置也就确定下来了。在下面的所有Del***n***剖分算法，均是针对这一数据结构进行的。
给定一系列离散点坐标，所形成的三角形网并不是惟一的。目前应用最广泛的是Del***n***三角形化方法。
Del***n***三角形的定义应从Dirichlet多边形说起。在每个网格点附近划出一个邻域；邻域内的任一点到该网格点的距离小于到其他网格点的距离。这个邻域多边形称为Dirichlet多边形（图2.1（a）。将每个多边形内的格点与相邻的多边形的网格点连接起来，构成一个三角形，称为Del***n***三角形（图2.1（b））。Del***n***三角形具有一种性质，它可以尽可能的避免形成过瘦的三角形，因而在有限元计算中非常有用，因为有限元法的稳定性是由所有三角形的最小内角确定的。过瘦的三角形不利于射线追踪，因为它使得射线追踪经过的交点过多，从而会增加积累误差，增大计算量。Del***n***三角形的三角形数目大约为点的两倍。在三维情况下，Del***n***四面体的数目大约为点的7倍。文献（闵卫东、唐泽圣，1993）曾给出大量Del***n***三角形和四面体的点线、面的数量关系。
三维Del***n***算法
将Del***n***剖分算法推广到三维具有重要意义。三维Del***n***剖分构成的Del***n***四面体是进一步构成任意块体的中间工具。三维空间的四面体对于三维射线追踪非常方便。三维Del***n***算法基本原理与二维Del***n***算法十分相似，但编制起来更为复杂。它也要用一个n×8维数组记录四面体构成点和相邻四面体信息，它大致也分为以下几步：
（1）判断哪些四面体的外接球包含新加入的点；
（2）将这些四面体汇总到一块，形成一个凸多面体；
（3）找到这多面体外表面，用一个二维三角形相邻关系数组记录下来；
（4）由多面体表面的三角形与新加入的点构制新四面体，用一个三维四面体数据结构数组，存贮新形成的四面体信息；
（5）用新四面体信息去更新原来总的四面体数据结构信息。
其中第（3）步是比二维Del***n***剖分复杂。待修改的四面体的外表面不再能够用环表示，而要用一个二维Del***n***三角形数据结构来表示。这种三角形的相邻关系要从原四面体的数据结构关系中去寻找。A、C面是多面体的外表面。B是其内表面须寻找A的一个棱的相邻三角形B，从B找到下一个四面体，再从四面体上找到与B三角形棱相邻的面C。
在三维Del***n***算法中，在通过外接球找到所有待修改的四面体后，将其排成一个待修改四面体数据结构数组，将待修改四面体的所有面全部排列起来，其中包含各个四面体的相互公共面和这些四面体组成的多面体的外表面，构成一个关于面的数据结构数组。从这个数据结构中删去相互相邻的三角形面，这样就构成了外表面的数据结构数组。
三维Del***n***剖分时，我们总利用三角形网格中的数量关系，来检查所形成的四面体的正确性。如果待删四面体数目为T，外表面三角形的数目为F，则
地质模型计算机辅助设计原理与应用
空间点集的带权Del***n***三角化算法
构造点集的Del***n***三角化的著名增量算法有两种：一种称为局部变换法（也称为Flip-ping算法），另外一种称为Bowyer/Watson算法。构造空间点集的带权Del***n***三角化算法也主要有两种，分别是以上两种算法的推广。我们只介绍推广后的Bowyer/Watson算法，称之为“带权Del***n***空洞算法构造点集的带权Del***n***三角化”算法。
1.带权Del***n***空洞定义
给定Ed空间的点集S，设有一点p∉S位于点集S的凸包中。Δ=ΔT是点集S的带权Del***n***三角化中的任意一个单纯形，z=z（Δ）为Δ的正交中心。如果满足wp＞πz（p），则称为Δ和p点冲突（也可以将单纯形的正交中心理解为权为正交球半径平方的带权点，当该点与p点干涉时，单纯形和p点冲突）。在带权Del***n***三角化的结果中，将所有与p点冲突的单纯形从带权Del***n***三角化中删除，将形成一个空洞，称为带权Del***n***空洞，又称为Regular空洞（Regular Cavity）。
根据d维空间的带权Del***n***三角化与d+1维空间的凸包之间的关系，可以在d+1维空间的凸包CH（S+）上考察将p点加入带权Del***n***三角化中带权Del***n***空洞的形成过程：如果Δ=ΔT和p点冲突，意味着p+点在过ΔT+=CH（T+）的超平面的下方。在带权Del***n***三角化中，删除CH（S+）的所有p+在其下方的下部小面对应的单纯形，形成带权Del***n***空洞。
2.带权Del***n***空洞构造算法
带权Del***n***空洞构造算法的思路如下：带权Del***n***空洞构造算法是一种增量算法，S中的点是逐点加入、逐点处理的。与局部变换算法一样，需要选择一个初始的足够大的d-单纯形。设点集S={p1，p2，…，pn}，选择d+1的权为0的点构成点集S0={p-d，p-d+l，…，p0}，构造一个d-单纯形ΔS0=CH（S0）。选择的S0要保证ΔS0包含S中所有的点，并且保证WD（S）的每个d-单纯形是WD（S ∪ S0）的d-单纯形。
定义Si={p-d，p-d+1，…，pi}。给定R（Si-1），设Δ=ΔT是WD（Si-1）中包含pi点的d-单纯形。如果加入pi后，Δ仍然是正则的，则WD（Si）=WD（Si-1）。否则，删除Δ，并且根据邻接关系，删除Δ周围所有与pi冲突的d-单纯形，得到pi点的带权Del***n***空洞，并且将空洞多面体的每个小面的顶点和pi相连形成新的d-单纯形，从而得到WD（Si）。当点集S中所有的点处理完成后，将得到WD（S）。
算法：带权Del***n***空洞构造算法
{
1 构造WD（S0）=ΔS0
2 for i：=1 to n do
3 在WD（Si-1）中找到包含pi点的d-单纯形Δ
4 if WD（T ∪{pi}）≠ΔT then
删除Δ，并且根据邻接关系，删除Δ周围所有与pi冲突的d-单纯形，得到pi点的带权D el***n***空洞
6 while pi点的带权Del***n***空洞中存在未处理的小面do
7 得到一个未处理的小面，设其所有顶点组成的集合为U，生成新的d-单纯形ΔU ∪{pi}，在点集Si中是正则的，也就是说Δ属于W D（Si）设置新生成的d-单纯形之间的邻接关系，以及新的
地下水三维可视化系统开发与应用
Del***n***三角剖分算法的准则特性
准则:
要满足Del***n***三角剖分的定义，必须符合两个重要的准则：
1、空圆特性：Del***n***三角网是唯一的（任意四点不能共圆），在Del***n***三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：
2、***化最小角特性：在散点集可能形成的三角剖分中，Del***n***三角剖分所形成的三角形的最小角***。从这个意义上讲，Del***n***三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：
特性:
以下是Del***n***剖分所具备的优异特性：
1.最接近：以最近的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.***性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Del***n***三角网的排列得到的数值***。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
约束Del***n***剖分
约束Del***n***剖分就是强迫点按所需的连线进行连接。这种方法在构制含断层的曲面时非常有用。由于构造面上有断层存在，断层内是不需要连接线的，连接线必须含所需的线段。在这种情况下，就要用到约束Del***n***剖分。
Cline和Renka（1990）提出一种约束Del***n***剖分方法，这种方法首先将点按无约束Del***n***方法进行剖分。然后将所需的边加进去，形成对这种结构进行描述的数据矩阵。
约束Del***n***剖分的定义如下：一个三角形的外接圆内可以包含另一个结点，仅当该结点与该三角形被所需的连接边隔开的时候。
实际计算时，有如下算法：
（1）找到所有与要求的连接线相矛盾的三角形，将其中的内边去掉，构成一个多边形；
（2）将所要求的连接线加入到该多边形内；
（3）按照所对的顶点内角***的原则，继续形成剩余的三角形边。
图2.3～图2.6给出了约束Del***n***剖分用于含断层构造面的三角形化的例子。
图2.3 无约束Del***n***剖分（虚线为断层线）
图2.4 约束Del***n***剖分（虚线）与无约束Del***n***剖分（实线）的比较
图2.5 约束Del***n***剖分后挖去的断层
图2.6 约束Del***n***剖分用于含断层的网络
关于delaunay和Delaunay三角网的特性包括的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。