三维凸包的快速算法

Accelerating algorithm for 3D convex hulls construction

很多情况下点集的凸包只是由其中一部分点构成，在构造凸包时如能将其内部的点全部或大部分预先去掉，则可大大提高构造凸包的效率．通过对点集的最小包围盒进行剖分和利用凸集的凸性性质，给出了一个新的三维凸包快速算法．与传统方法相比，该方法具有计算简单，效率高的特点．

The convex hull for a set of points is consist only of a small part of the set generally. If we can remove those points lying in the interior of the hull in an efficient way,we can then construct the hull with fewer time. By dividing the bounding box of the point set and by exploiting the convex property of a convex set,we get an efficient quick hull algorithm. The new method is simple to implement and more efficient than some traditional accelerating methods.