Abstract: 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.

Key words: collision detection, convex hull, high density point set, extremum

摘要： 提出了一种基于凸壳的高密度点集物碰撞检测算法。根据高密度点集物紧密性好的特点，设计了一种快速的凸壳算法；当极值比较不能确定待检测点集物未碰撞时，用该算法计算待检测点集物的凸壳，并对凸壳进行求交运算，若不相交，两点集物未发生碰撞，否则在两凸壳的交集区域中寻找碰撞点集。算法简单、高效、可靠，在教育、国防、艺术等方面具有一定应用价值。

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