一种高效的平面点集凸包递归算法

An Efficient Convex Hull Algorithm for Planar Point Set Based on Recursive Method

凸包是计算几何的基本结构,在许多图形图像相关领域得到了广泛应用.本文提出了一种简单快速的平面点集凸包算法,使用了主成分分析法(Principle component analysis,PCA)对点集进行预处理,并研究了适用的排序规则和凸包边缘点判定原则.该算法已成功应用于一光栅投影三维形貌快速测量系统,对相位干涉图中密集残留点所形成的最小凸包进行提取.系统将提取的凸包区域进行掩码标记,从而避免密集残留点造成相位展开错误,保证了三维形貌重构的准确性.实验结果表明,该算法准确可靠,并且运行效率较高.

Convex hull is one of the basic structures in com- putational geometry, which is used in many fields of computer graphics and image. A novel algorithm of convex hull is pro- posed. Principle component analysis （PCA） is used to do the pretreatment on the planar point set. The applicable sort reg- ulation and determinant principle of edge points in convex hull are studied. The new algorithm is applied to a fast 3D mea- surement system based on digital fringe projection to extract the minimal convex hull formed by the intensive residual points in the phase interferogram. The system can avoid the phase unwrapping error caused by the residual points by masking the area of the extracted convex hull to guarantee the accuracy of three-dimensional shape reconstruction. Experimental results prove that the presented algorithm not only has high reliability, but also gets better operational efficiency.