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