改进的三维点集凸包求取算法  

Improved algorithm on determining convex hull of 3D point set

作　　者：张飞[1] 谢步瀛[1] 闫星宇[1] 刘政[1] 

机构地区：[1]同济大学土木工程学院,上海200092

出　　处：《计算机辅助工程》2009年第1期78-82,共5页Computer Aided Engineering

摘　　要：为提高三维点集凸包的求取效率,提出充分利用凸包极值点和性质改进的三维点集凸包求取算法.首先,求出三维点集中的极值点,并由它们形成初步凸包;其次,根据初步凸包与点的位置关系,排除其内部点;最后,依次考察其外部点,求出符合要求的点集、棱边集和面集,并对凸包进行扩展,得到凸包的点集、棱边集和面集.与普通算法进行时间的复杂度分析比较及实验表明,该算法效率较高.To improve the computation efficiency of convex hull of 3D point set, an improved algorithm on determining convex hull of 3D point set is proposed by making full use of the extreme points and the character of the convex hull. Firstly, the extreme points in 3 D point set are obtained to make up of the initial convex hull. Secondly, the internal points of the convex hull are eliminated according to the position relationship between the initial convex hull and the points. Finally, the external points are examined in turn, the point set, line set and face set that meet the requirements are acquired, and the convex huU is expanded to obtain the final point set, line set and face set of the convex hull. The comparison of time complexity analysis with normal algorithms and the experiments indicate that the algorithm has higher efficiency.

关 键 词：三维点集 凸包 极值点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]