一种三维凸包的快速构造方法

摘要

本发明涉及凸包构造技术领域，具体地说是一种三维凸包的快速构造方法，该构造方法吸收了传统的QuickHull方法中每次选用凸包的极值点(Extream-Point)来构造新凸包的思想，在此基础上改进为选用二次极值点的方法来构造新凸包，并结合“冲突图”(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系，从而取得了快速排除凸包的内部点、缩小问题规模，避免了更新拓扑关系所带来的大量计算，实现了高效构建凸包的效果，其时间复杂度为O(nlogr)，通过实验证明，该方法与传统的QuickHull方法相比，平均执行消耗时间减少了20%，因此，本发明同现有技术相比，其在计算机图形学、图像处理、模式识别、几何建模、人工智能以及CAD/CAM等领域中具有理论和实际的重要应用价值。