杨宏伟

(滨州学院 机电工程学院，山东 滨州 256600)

0 引 言

凸包是描述模型的一个重要特征，其求解算法在逆向工程、现代化农业、计算机图形学、先进制造技术等领域有着广泛的应用[1-3]。

文献[4]～[6]采用四边形法，分别求解点云在X轴及Y轴上的最大、最小点，标记为点A，点B，点C，点D，该四点组成四边形ABCD，判断点云中各点与该四边形的位置关系，若落入该四边形内部，则将其添加到内部点集L中，可证明，点集L中的点不可能是凸包点，将点集L中的点排除，实现对点云的精简，通过对精简后的点云求解凸包，实现对整个点云的凸包求解。该方案通过预处理排除大量不可能成为凸包顶点的点，可加速凸包的计算。

文献[7]～[9]对上述四边形法进行改进，首先求解点云的四边形ABCD，遍历四边形外部的点，分别求解距四条边AB，BC，CD，DA最远的点E，F，G，H，组成初始凸包AEBFCGDH，重复上述步骤，直到没有新的点加入到初始凸包中。

文献[10]～[11]提出一种基于网格和二叉树凸包求解算法，该算法基于网格和二叉树建立点云的拓扑关系，依据网格间的拓扑关系对点云进行精简，排除不可能成为凸包顶点的点，通过对精简后的点云求解凸包，实现对整个点云的凸包求解，该算法在点云精简前需先建立拓扑关系。

笔者提出一种平面散乱点云的凸包快速求解算法，该算法建立点云的最小外包围盒，分别求解距该外包围盒四个顶点最近的点，依据该点集建立最大内包围盒，可证明该最大内包围盒内的点不是凸包，将其排除，实现点云的精简，通过对精简后的点集求解凸包，实现对整个点云的凸包求解，实例表明该算法实现简单，且可显著提高凸包的求解效率。……