在数学和计算几何中，三角化就是对于给定的平面中的离散点集P，生成三角形集合T的过程。一般来说给定一个点集，往往存在不止一个三角剖分。其中基于 Delaunay 准则的三角化是一种特殊的三角化，也叫 Delaunay三角化。
Delaunay定理由俄国数学家Delaunay提出，使用该准则进行剖分得到的三角网格叫作Delaunay三角网格。Delaunay网格的空外接圆特性和最小内角最大的特性决定了Delaunay网格是网格化质量最好的网格。
关于二维点集的Delaunay三角化算法，有逐点插入法、三角网生长法和分治法以及隶属于3类方法的各种不同实现算法。
Lawson算法是一种基于点插入的Delaunay三角剖分算法。该算法通过不断地向剖分中加入点，来逐步构建整个Delaunay三角剖分。Lawson算法中的局部优化过程（LOP：Local Optimization Procedure）是逐点插入法的关键，局部优化过程的思路是，如果一个三角形不符合Delaunay三角剖分的规则，则将一个包含一对三角形的四边形的对角线对换，从而构成符合Delaunay三角剖分的新三角形。简单来说，Lawson算法通过不断地将剖分中非Delaunay边上的点进行“翻转”，使得该边成为Delaunay边，直到所有边都是Delaunay边为止。
该算法基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，是一种比较理想的算法。其逐点插入的构网过程中如果遇到非Delaunay边时，可以通过删除调整，进而构造形成新的Delaunay边。在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部构网。但是在实际应用当中，点集数量较大，分布复杂时构网速度较慢，而且对于区域为非凸，存在内环时，则会产生非法三角形。
分治思想（Divide-and-Conquer）的Delaunay三角网构建算法由Lewis和Robinson提出，后由Lee和Schachter改进。Delaunay三角网分治算法的主要思想就是递归地将点集进行划分为多个子集，当每个子点集的点云数量被划分到一定程度时生成三角网格，通过递归的过程将不同三角网进行向上合并，最终得到一个完整的三角网。不同Delaunay三角网分治算法的实现差别往往体现在如何对数据划分进行。基于分治的Delaunay三角网生成算法，在最坏情况下的时间复杂度为O(nlogn)，在处理同样数量的点云数据的时候，分治的Delaunay三角网生成算法的时间复杂度最小，相对的，因为Delaunay三角网分治算法需要进行大量的递归，需要大量的内存。对于处理大规模的点云数据可能会因为内存空间问题而影响Delaunay三角网分治算法的使用。
三角形生长算法最早是由Green和Sibson提出，算法的主要思想是以点集中任意一个点开始，寻找与该点欧式距离最小的点构成一条边，根据最大最小角的原则寻找另一个点构成三角形，不断选择新的点与三角形的边构成新的三角形，使三角形的区域不断扩大，知道点集中所有的点都被并入三角网中。由于三角形生长算法需要为三角形的边寻找符合条件的点构成新的三角形，需要遍历点集中的点，往往需要消耗很多时间寻找点。因此，三角形生长法很难达到线性时间，如果点集分布不平均，最坏情况下时间复杂度为O(n2)。
三角网生成法的时间效率最低，分治算法的时间效率最高，逐点插入法效率居中。由于区域生长法本质的缺陷，导致其效率受限，这种方法在80年代中期以后已经很少使用。分治算法时间效率相对较高，但是由于其递归执行，所以需要较大的内存空间，导致其空间效率较低。此外，分治法的数据处理及结果的优化需要的工作量也比较大。逐点插入算法实现简单，时间效率比较高，而运行占用的空间也较小，从时间效率和空间效率综合考虑，性价比最高，因而应用广泛。
逐点插入算法最坏情况下的时间复杂度是O(N2)。但是，若点是随机插入的话，其性能将能达到O(NlogN)。但由于算法过程需要排序，其时间复杂度不能进一步改进。生长算法的效率最差，最坏情况下的时间复杂度为O(N2 )，性能最高也只能达到O(N3/2)。分治算法的效率很高，最坏情况下的时间复杂度都能达到O(NlogN)，最好情况下其性能甚至能达到O(loglogN)，同时输入点集对分治算法的效率影响较小，无论输入点集好坏都不会对分治算法的效率产生明显影响。3类方法各自典型的实现算法的时间复杂度如下表：
[1] Chuang T , 陶闯. A Comparative Research on Methods of Delaunay TriangulationDelaunay三角网构建方法比较研究[J]. 中国图象图形学报, 1995, 15(8):1158-1167.
