对构建Delaunay三角网中凸壳算法的研究与改进  

Research and Improvement of Convex Hull Algorithm in Construction of Delaunay Triangulation

作　　者：袁翰[1] 李伟波[1] 陈婷婷[1] 

机构地区：[1]武汉工程大学计算机科学与工程学院,武汉430073

出　　处：《计算机工程》2007年第7期70-72,共3页Computer Engineering

基　　金：湖北省教育厅资助重点项目(2004D003)

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

关 键 词：DELAUNAY 三角剖分 不规则三角网 凸壳 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]