地学领域中表达地形信息的数据中包含大量山脊线、山谷线、断裂线、岛屿等地形特征,GIS工作者在充分考虑这类地形特征的情况下,发展了带约束条件的Delaunay三角剖分理论和算法。带地形特征约束的三角剖分是建立高精度数字地面模型的基础,在GIS、地学分析、多分辨率DTM、计算几何等领域中有着广泛的应用。阐述了带约束的Delaunay三角剖分的经典算法,研究了经典算法中的两步法,针对两步法的第一步,非约束Delaunay三角剖分中逐点插入算法的凸包包容盒算法,提出了一种边缘极值点求平面散乱点集凸包的算法。该算法利用极值点将平面点集划分为5个区,边缘4个区包含了所有凸包的凸点。通过求取边缘4个区的边缘子集的极值点,得到一个包含所有凸点的多边形点集,去掉凹点,得到平面点集的凸包。在两步法中的第二步嵌入约束条件的过程中,对约束线段的嵌入过程进行了分类,实现了带约束数据域的Delaunay三角剖分。对带岛屿约束数据域的Delaunay三角剖分算法进行了研究。在总结了前人研究成果的基础上,对带岛屿约束数据域的三角剖分算法进行了改进。改进算法的思想是:首先构建带岛屿多边形内边界约束的约束Delaunay三角网,然后利用边、面、弧段之间的拓扑关系,双向搜索查找岛屿内的三角形,进行相应的处理,完成带岛屿约束的Delaunay三角剖分。通过对实验结果的对比和分析,该改进算法具有更好的执行效率。通过对边缘极值点求平面散乱点集凸包算法和改进的带岛屿约束的Delaunay三角剖分算法的分析及与其它算法的比较,可以看出这两个算法在执行效率和效果上都有所提高,因此对两步法实现带约束三角剖分算法的构网效率有所提高。