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