基于三维凸包计算凸多面体Minkowski和算法  

Minkowski sum algorithm of convex polyhedron based on three-dimensional convex hull

作　　者：赵强[1] 郭希娟[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《燕山大学学报》2015年第2期152-157,181,共7页Journal of Yanshan University

基　　金：国家自然科学基金资助项目(51175446)

摘　　要：传统的Minkowski和算法在计算实际物体间的精确的碰撞干涉时,很难直接获取运算所需的数据,进而需要进行大量的数据预处理。为了提高运算速度,减少数据处理量,本文设计了一种新的三维凸包计算方法,通过空间两凸多面体外表的点云信息直接计算其Minkowski和,用计算得到的凸包的面集表示Minkowski和的边界信息。然后,给出详细的算法描述和复杂度分析,并通过对比分析实验数据,验证了该算法的有效性。In the calculation of the exact collision detection between the actual object,the traditional Minkowski sum algorithm are dif？ficult to directly obtain data required for operation,so there needs for large amounts of data pre？processing.In order to improve the computing speed,reduce the amount of data processing,a new calculation method of 3D convex hull is designed and used to calculate the Minkowski sum of two spatial convex polyhedrons directly through their point cloud information.And the Minkowski sum boundary information is represented by the calculated results of convex hull face set.A detailed description of the algorithm is given and the complexity of the algorithm is analyzed.The results show that the algorithm is effectiveness through comparing the experimental data.

关 键 词：凸包 MINKOWSKI 和 凸多面体 三维点云 

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