An Efficient Convex Hull Algorithm for Planar Point Set Based on Recursive Method
一种高效的平面点集凸包递归算法

Convex hull is one of the basic structures in computational geometry, which is used in many fields of computer graphics and image. A novel algorithm of convex hull is proposed. Principle component analysis (PCA) is used to do the pretreatment on the planar point set. The applicable sort regulation and determinant principle of edge points in convex hull are studied. The new algorithm is applied to a fast 3D measurement 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.