三角剖分是计算几何中的一个非常重要的分支,是计算几何领域中的重要课题之一,它具有广泛的应用价值。对于三角剖分算法的研究,主要着眼于如何降低三角剖分计算复杂度和提高生成的三角网的质量。同时,在约束条件下的三角剖分,也是目前研究的一个热点。本文的研究内容主要包括:二维三角剖分算法、三维三角剖分算法和约束条件下三角剖分算法。其中,本文研究的重点是约束条件下三角剖分算法。在二维三角剖分算法方面,本文首先对平面点集三角剖分给出了定义;之后,将介绍一些经典的平面点集三角剖分算法,并对这些算法进行了分析与比较;在此基础上,本文将重点介绍两种三角剖分算法的新思路:逐层求凸包三角剖分算法和基于图的三角剖分算法,这两种算法思路新颖,并且有较好的算法复杂度。在三维三角剖分算法方面,本文将首先对三维点集三角剖分提出定义;然后将介绍传统的基于凸壳的三角剖分算法;由于基于凸壳的三角剖分算法在实际应用中存在一点的局限性,所以,本文提出了研究分析了一种任意域内点集三角剖分算法,该算法解决了任意域内三角剖分的问题,且有很好的计算复杂度。在约束条件下三角剖分算法方面,本文首先介绍了解决约束三角剖分问题的一些经典的算法,但是这些算法的计算结果往往无法满足Delaunay标准。基于这个问题,本文介绍了一种全局优化的约束Delaunay三角剖分算法。由于该算法是先计算剖分,然后添加约束条件,这样可能在约束条件较多的情况下,存在灾难性的后果,所以本文对该算法进行了改进,在剖分过程中,考虑了约束条件,使剖分过程更加稳定。