平面散乱点云凸包快速求解算法  

Accelerating Algorithm for Convex Hull Construction of 2D Scattered Point Cloud

作　　者：杨宏伟 YANG Hong-wei(College of Mechanical and Electrical Engineering,Binzhou University,Binzhou Shandong 256600,China)

机构地区：[1]滨州学院机电工程学院,山东滨州256600

出　　处：《机械研究与应用》2021年第2期55-56,60,共3页Mechanical Research & Application

基　　金：国家自然科学基金资助项目:基于附加力矩和刚度演变的航空结构件加工全过程变形研究(编号:51605037);滨州学院航空专项项目:大型航空部件测量数据的边界特征快速提取算法(编号:BZXYLG2008)。

摘　　要：提出一种平面散乱点云凸包快速求解算法,该算法建立点云的最小外包围盒,分别求解距该外包围盒的四个顶点最近的点,依据该最近点集建立最大内包围盒,可证明该最大内包围盒内的点不是凸包,将其排除,实现点云精简,通过对精简后的点集求解凸包,近而实现对整个点云的凸包求解,实例表明该算法实现简单,且可显著提高凸包的求解效率。An accelerating algorithm for convex hull construction of 2D scattered point cloud is proposed,which has three steps:first,the outer and inner boundary box of scattered point cloud is constructed;secondly,the scattered point cloud is reduced according to the inner boundary box;then,solution for the convex hull construction of whole scattered point cloud is realized through constructing the convex hull of points after reduction.The example proves that the algorithm is simple and more efficient of solving the convex hull than the traditional methods.

关 键 词：平面散乱点云 凸包 最小外包围盒 最大内包围盒 精简 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]