摘要：提出了一种基于凸包构建Delaunay三角网的算法,它包括离散点数据的三角剖分及将约束边嵌入三角网.在对离散点数据进行三角剖分时,首先建立一个外轮廓为凸包的初始三角网,然后将剩余的点依次与既有三角网合并来生成包含所有数据点的三角网.为了将约束边嵌入三角网,找出约束边穿过的三角形,删除这些三角形并用约束边将这些三角形所围成的多边形分成两个简单多边形,再对这两个简单多边形进行Delaunay三角网剖分即可达到嵌入约束边的目的.

关键词：三角剖分 凸包 支撑线 

单位：中南大学土木建筑学院; 湖南; 长沙; 410075