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

摘要

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