Abstract

         Delaunay Refinement是一种生成用于插值，有限元法和有限体积法的非结构化三角形网格的技术。在理论和实践中，由Delaunay细化产生的网格满足角度，边长，三角形数量以及三角形从小到大的渐变在一定的范围内。L. Paul Chew和Jim Ruppert分别以几种方式对算法进行了改进，最重要的是，它有助于解决将小角度的非流形域划分网格的难题。

         尽管小角度在输入的三角形中是一定存在且无法消除的，但是希望能够对一个区域进行三角剖分而不产生新的小角度。但是这个问题并不是总是可以解决的。Delaunay refinement algorithm 可以创建一种网格，大多数角为$30^\circ$或者更大，没有角小于$arcsin[(\sqrt{3}/2)sin(\phi/2)] \thicksim (\sqrt{3}/4)\phi$这里$\phi \leq 60^\circ$是分割两个区域的最小角度。只有输出的的角比$60^{\circ}$小才会出现新角小于$30^{\circ}$。Q1

        另一个新结果是，Ruppert的分析技术可用于重新分析Chew的一种算法。Chew证明了他的算法不会产生小于$30^{\circ}$的角度（除非输入角度很小），但不能保证渐变或三角形的数量。他的猜想在这里得到了有条件的确认：如果将角度范围放宽到小于$26.5^{\circ}$，则Chew'salgorithm生成的网格（无小输入角的域）将具有良好的渐变度和最佳尺寸。

Introduction

         Delaunay Refinement是一种生成适用于插值，有限元法和有限体积法的三角网格的技术。问题是要找到一个覆盖指定区域的三角剖分，并且仅包含形状和大小满足约束的三角形：角度不应太小或太大，并且三角形不应比所需的小很多，也不会比所需的大。

         文章有三个目的，一、它为Delaunay Refinement算法提供了理论框架。二、本文利用该框架来帮助找到一种实用的解决方案，以解决迄今为止难以提出的Delaunay Refinement算法无法啮合的小角度网格划分问题。第三，它介绍了程序员实现直线域的最新三角网格生成器所需的几乎所有算法。

         描述网格化的区域大多数用平面直线图(PSLG)来描述。PSLG是一组顶点和线段，线段是必须由最终网格中的一系列相邻边表示，PSLG包含其包含的每个线段的两个端点，并且一个线段只能在其端点处与顶点和其他线段相交。网格生成过程必须将每个线段划分为较小的边缘，称为子段。三角剖分区域不必是凸形的，线段必须位于平面的三角区域与非三角区域相交的任何位置。

         网格生成器会产生试图满足三个目标的三角剖分。一、三角形的并集是三角剖分域，并且三角剖分每个线段都是三角剖分边的并集。二、三角形的形状应相对“圆”。在插值中，大角度的三角形会导致插值曲面的梯度出现较大误差。在有限元法中，大角度会导致大的离散误差；在有限元法中，大角度会引起离散误差。许多网格采用限制最小角度的方法。三、对网格中的三角形大小有尽可能多的控制。

        给定一个粗网格，很难对其进行细化以生成另一个具有大量较小三角形的网格。反向过程并不容易。因此，网格生成算法通常将其目标设定为：原则上能够生成具有尽可能少的三角形的网格。

        Delaunay Refinement算法通过维持Delaunay或约束Delaunay三角剖分来工作，可通过插入精心放置的顶点进行细化，直到网格满足对三角形质量和大小的约束为止。Delaunay三角剖分的最重要属性是其具有空的外接圆属性(Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。)

         受约束的Delaunay三角剖分相似，但固定输入线段和顶点。 如果线段pq（省略p和q）不与输入PSLG的任何段相交，则两个点p和q彼此可见。PSLG的约束Delaunay三角剖分具有两个属性。 首先，没有线段与三角形的内部相交，因为三角剖分必须尊重线段。 其次，每个三角形的外接圆都不会包含从三角形内部可见的顶点，尽管可能封闭隐藏在线段后面的顶点。

        某些应用程序（例如某些有限体积方法）可能有一个额外的要求：网格必须是truly Delaunay（而不仅仅是约束Delaunay），并且每个三角形外接圆的中心都必须位于三角内。之所以出现此要求，是因为通过对Delaunay三角剖分进行二重化而得到的Voronoi图必须与三角剖分“恰好”相交。 只有少数应用程序具有此要求，但此处的某些网格生成算法很容易满足这一要求。

         Delaunay Refinement算法是成功的，因为它们利用了Delaunay三角剖分的几个有利特征。

感谢魏老师的解答！

几个问题

1.这里是输入网格的时候就要求角度必须大于30？还是在已有角度进行剖分时大于30的角剖分的角度不会小于给定的两个边界值，小于30度的角度会越来越差？

         第一个问题, 不是输入的网格要求角度大于 30 度, 而是输入的 PSLG 的相接线段的夹角有一个最小值 phi , 这篇文章的算法是说可以保证生成的大部分三角形的角度最小角大于 30 度, 整个网格的最小角度也有一个下界, 这个下界与 phi 有关

2.是p,q可见是连接两个顶点，不会与任何定点和线段相交么？

         第二个问题, 你的理解是对的, 但 p q 这个线段是开的, 也就是说, p, q 可以在 PSLG 的 线端上

3.truly Delaunay 和 constrained Delaunay定义是什么？这两个最主要的区别是什么?

         Delaunay 就是所有三角形满足空圆性质，onstrained Delaunay 就是一部分 edge 的外接圆(以edge 为直径) 不满足空圆性质