An efficient convex hull algorithm for planar point set based on recursive method

作者：Liu Bin^*; Wang Tao

来源：Acta Automatica Sinica, 2012, 38(8): 1375-1379.

DOI：10.3724/SP.J.1004.2012.01375

• 3-D measurement systems
• Basic structure
• Convex hull
• Convex hull algorithm
• Digital fringe projection
• Edge point
• Fringe projection
• High reliability
• Interferograms
• Minimal convex hulls
• Novel algorithm
• Operational efficiencies
• Phase unwrapping
• Planar point sets
• Pre-Treatment
• Principle component analysis
• Recursive methods
• Three-dimensional shape

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.

• 出版日期2012
• 单位天津大学