摘要： 在介绍Delaunay不规则三角网基本概念和TIN数据结构的基础上，主要对平面离散点构建凸壳的格雷厄姆算法进行了研究和改进，提出了一种“斜率扫描线法”，并进行了编程实现。实验表明改进后的算法实现简单，容易理解，对于D-TIN模型的生成行之有效。
关键词:
Delaunay三角剖分,
不规则三角网,
凸壳
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三角网中凸壳算法的研究与改进[J]. 计算机工程, 2007, 33(07): 70-72.
YUAN Han; LI Weibo; CHEN Tingting. Research and Improvement of Convex Hull Algorithm in Construction of Delaunay Triangulation[J]. Computer Engineering, 2007, 33(07): 70-72.