Abstract: While infroducing the essential meaning and the data structure of TIN, this paper studies and improves the Graham algorithm which constructs the convex hull based on the plane discrete points, proposes one “slope-scan-line” method, and a programming algorithm is achieved also. Experimental results show that the method is easy to obtain and to understand. It is effective to build Delaunay TIN.

Key words: Delaunay triangulation, Triangulation irregular network (TIN), Convex hull

摘要： 在介绍Delaunay不规则三角网基本概念和TIN数据结构的基础上，主要对平面离散点构建凸壳的格雷厄姆算法进行了研究和改进，提出了一种“斜率扫描线法”，并进行了编程实现。实验表明改进后的算法实现简单，容易理解，对于D-TIN模型的生成行之有效。

关键词: Delaunay三角剖分, 不规则三角网, 凸壳