基于凸壳的高密度点集物碰撞检测算法  

Collision detection of high density point set based on convex hull

作　　者：唐培和[1] 蒋联源[1] 宋佩华[2] 苏勤[3] 

机构地区：[1]广西工学院计算机工程系,广西柳州545006 [2]广西师范学院教务处,南宁530001 [3]广西师范大学计算机科学系,广西桂林541004

出　　处：《计算机工程与应用》2008年第16期51-53,共3页Computer Engineering and Applications

基　　金：广西省教育厅科学基金(the Fund of Department of Education of Guangxi Province,China under Grant No.200707MS068)

摘　　要：提出了一种基于凸壳的高密度点集物碰撞检测算法。根据高密度点集物紧密性好的特点,设计了一种快速的凸壳算法;当极值比较不能确定待检测点集物未碰撞时,用该算法计算待检测点集物的凸壳,并对凸壳进行求交运算,若不相交,两点集物未发生碰撞,否则在两凸壳的交集区域中寻找碰撞点集。算法简单、高效、可靠,在教育、国防、艺术等方面具有一定应用价值。This paper presents a collision detection algorithm of high density point set based on convex hull.According to the characteristics of the point set tightness,a fast speed convex full algorithm is designed.If extremums cann＇t define un-collision, convex hull of the awaiting collision detection point set and intersection of the convex hulls are calculated.If they disjoint,the two point sets don＇t collide;if they intersect,we search for the collision point set in the intersection set region of the two convex hulls.The algorithm is simple,efficient and reliable.It has the certain application value for education,defense and art.

关 键 词：碰撞检测 凸壳 高密度点集物 极值 

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