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

• 作者: 李儒琼 李志
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 三维凸包 二次极值 增量算法
• 年，卷（期）: 2011,（2）
• 页码范围: 129-132
• 分类号: TP301.6
• 字数: 2551字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2011.02.025

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李儒琼	上海师范大学信息与机电工程学院	15	135	4.0	11.0
2	李志	上海师范大学信息与机电工程学院	1	9	1.0	1.0