改进的三维离散点集凸包求解算法

• 作者: 李日福 李晋芳
• 来源期刊: 现代计算机
• 关键词: 三维凸包 算法 主成分分析
• 年，卷（期）: 2017,（20）
• 所属期刊栏目: 图形图像
• 页码范围: 40-43,48
• 页数: 5页
• 字数: 2288字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-1423.2017.20.009

摘要

针对传统三维凸包算法的不足,阐述一种改进的凸包构造算法.该算法使用PCA主成分分析法对点集进行预处理,计算其相应的协方差矩阵,求出其特征值所对应的特征向量,并以之建立新的坐标系.再通过吸收QuickHull算法的构造思想,充分利用坐标轴端点来构造初始单形体,结合冲突图来更新凸包数据结构,这样大大提高构造凸包的效率.这个过程能达到时间复杂度下限O()n log n,实验证明该算法具有理论和实际应用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李晋芳	广东工业大学机电工程学院	29	82	5.0	7.0
2	李日福	广东工业大学机电工程学院	4	3	1.0	1.0