一种改进的快速三维凸包生成算法及实现

本文阐述一种快速的三维凸包构造新算法,算法吸收了Quick Hull方法中每次选用凸包的极值点(Extremal-Point)来构造新凸包的思想,在此基础上改进为选用二次极值点的方法来构造新凸包,并结合"冲突图"(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系,从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果。本文算法的时间复杂度为O(nlgr),通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%,因此本算法具有理论和实际应用价值。

An Improved Algorithm and Implementation of Three-Dimensional Convex Hulls

A novel and efficient approach to three-dimensional convex hulls is presented in the paper,compared with the QuickHull method,the quadratic extremal-point is employed to construct the convex hull in the method,combining with conflict map(Conflict-Graph) of this bipartite graph structure to update the topological relations between the points outside the convex hull and the current convex hull.This algorithm's time complexity is O(nlgr),and the experimental results shows that the algorithm is more efficient c...