地学空间构模技术自二十世纪七十代发展至今已取得了极大的进步。目前，大概有二十多种构模方式，可归纳为三大类：基于面的构模方式，基于体的构模方式和混合构模方式。其中，基于四面体体元的构模方式是基于体的构模方式中的一种，由于结构简单，易于数据操作，引起了众多学者的关注。基于四面体体元的构模方法包括有八叉树法、推进阵面法和Delaunay三角化法。由于按Delaunay规则构造的四面体具有良好的数学特性，相较于其它两种方法生成的四面体网格形状质量高，所以成为目前最为流行的一种构模方法。本文所要研究的内容是总结、发展二维区域Delaunay三角化的理论和算法，讨论三维区域Delaunay三角化理论和算法。 二维区域的Delaunay三角剖分分为有约束三角剖分和无约束三角剖分两大类。无约束条件下的Delaunay规则体现为空外接圆规则，即生成的三角网中的每一个三角形的外接圆均不包含点集中的其它点。三角化算法主要分为三大类：分治法、逐点插入法、三角网生长法。本文简要介绍了这些算法的基本思想，并对三种方法进行了比较。同时本文还设计了一种基于排序的三角网生长算法，该算法首先对离散点进行字典排序，然后按照点的顺序构造一个初始的三角形，然后逐次加点，每次加入的点都在当前的三角网区域外，因此通过查找上下支撑点的方法，将点与原三角网合并形成新的三角网，并利用Delaunay规则进行局部调整，保证整个三角网的Delaunay特性。采用这种方法大大降低了传统的Delaunay三角剖分算法的时间复杂度。 针对最简单形式的约束delaunay三角化—简单多边形三角化，本文也设计了一种基于分割的三角化算法。该算法首先基于相邻凹点连线将简单多边形分割为多个子凸多边形，然后对每个凸多边形进行三角剖分，最后合并凸多边形同时在凸多边形的相邻边界上进行局部修改，实现简单多边形的Delaunay三角剖分。本文根据简单多边形的相邻凹点连线之间的位置关系，将简单多边形分为三类，根据不同的类别设计相应的切割方法，并从理论上证明了方法的正确性。该算法的收敛时间要比现有算法的收敛时间的更快。 二维区域的Delaunay三角剖分最后部分讨论了二维任意区域的Delaunay三角剖分。现有二维任意域的Delaunay三角剖分算法有五种：约束图法、加密算法、分割—合并算法、shell三角化、两步法。约束图法首先生成最小生成树，然后逐步加入边构成三角形网格，再通过局部变换，得到平面点集的Delaunay三角剖分。加密算法通过不断加入新点使得最终的三角网符合非约束Delaunay的空外接圆规则。该方法虽然实现简单，但大大增加了数据量。Shell三角化方法是二维区域delaunay三角网生长法在约束条件下的发展，其中Delaunay准则改为约束Delaunay准则，并以约束最大空圆凸多边形为单元生长。分割—合并算法是较为流行的一种算法。通常首先将二维区域分解为多个易处理的子区域，再对每个子区域进行Delaunay三解剖分，然后子区域合并。该方法的关键点在于如何分解子区域及子区域合并时如何保证Delaunay规则的一致性。两步法是最为流行的三角剖分方法。该方法首先不考虑约束条件，对所有的顶点进行无约束的Delaunay三角剖分，然后恢复所有的约束边。在恢复过程中，为保持Delaunay的特性，需要查找并修改约束边的影响域。 与二维区域Delaunay三角剖分不同，三维区域下的Delaunay三角剖分最终将产生符合Delaunay规则的四面体网格。在无约束条件下，三维Delaunay三角剖分主要算法为：分治法、逐点插入法和三角网生长法。这些算法其实是二维区域无约束条件下Delaunay三角剖分算法在三维上的发展。二维域的空外圆准则在三维中转化空外接球准则。本文在第三章分别详细介绍了这三种算法的具体实现。 三维区域的约束条件主要分为线约束和面约束，而在二维区域中只有线约束，因此三维约束Delaunay三角剖分要比二维区域的约束Delaunay三角剖分要复杂得多，而在二维域中有关Delaunay的理论和算法在向约束三维区域发展时出现了许多复杂的问题，到目前还不能很好地解决。现在，约束条件下的三维Delaunay三角剖分在理论上还不成熟，相应地这一领域的算法也比较少。为了实现三维约束Delaunay三角剖分，人们相继引入“虚四面体”、“过桥面”和“最大约束空球”等概念。其中，最常用的方法是凸包围盒法，首先不考虑约束条件直接对所有的顶点进行无约束条件下的Delaunay三角剖分，然后恢复约束边，接着恢复约束面，最后删除多余的四面体。这种方法的难点在于如何恢复约束面，本文在第三章详细介绍了这种方法。