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

Improved algorithm on determining convex hull of 3D point set

为提高三维点集凸包的求取效率,提出充分利用凸包极值点和性质改进的三维点集凸包求取算法.首先,求出三维点集中的极值点,并由它们形成初步凸包;其次,根据初步凸包与点的位置关系,排除其内部点;最后,依次考察其外部点,求出符合要求的点集、棱边集和面集,并对凸包进行扩展,得到凸包的点集、棱边集和面集.与普通算法进行时间的复杂度分析比较及实验表明,该算法效率较高.

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.