凸壳在模式识别、图象处理、图形学和人工智能等方面有广泛的应用,许多实际问题都可以归纳成凸壳问题求解。本文对凸壳和凸壳直径计算进行了研究,提出了相关算法,同时对凸壳在轮廓匹配和高密度点集物碰撞检测中的应用进行了探讨,理论分析和实验结果验证算法的可行性和有效性。本文工作主要从以下六个方面展开:(1)实时凸壳算法。由于正切线算法计算凸壳时对新加入实时点进行编号的局限性,提出一种实时凸壳算法。算法通过极值点将平面划分为若干区域,根据实时点所在区域,确定受影响的单调段,对受影响单调段上的顶点通过正切线算法重新计算,以横坐标作为新加入点的编号实现自动编号,最终由新的单调段得到新的凸壳。(2)给定平面点集凸壳算法。将正切线算法应用到给定平面点集凸壳的计算中,通过凸壳的极值点定义了凸壳的单调段,并将点集分成若干个区域,对于点集中的点,若该点落在由各单调段所围成的区域内部,则该点一定不是凸壳上的点;计算落于其它区域中的点,只需通过该点与它所在区域的原单调段进行计算得到新单调段,从而得到给定平面点集的凸壳。(3)基于凸多边形顶点间距离性质的凸多边形直径算法。平面点集的直径问题可以转化为求凸多边形直径问题,论文研究了凸多边形的直径计算,得出凸多边形上顶点间距离关系的一些性质,提出一种基于顶点间距离性质的凸多边形直径算法,利用这些性质可减少大量夹角符号计算。(4)基于凸多边形顶点序列到边的距离单调性的凸多边形直径算法。论文研究了凸多边形顶点序列到边的距离单调性,算法根据这种单调性通过折半查找实现对首个对跖点对的查找,实现了一种快速的凸多边形直径算法。(5)凸壳在轮廓匹配中的应用研究。轮廓匹配是计算机视觉研究中的一个重要课题,论文研究了平移旋转和伸缩变换下的轮廓匹配问题,得出了重心是平移旋转和伸缩变换下的不变量,根据重心这一不变量计算变换中的平移量、旋转角度和缩放因子,实现轮廓匹配。(6)凸壳在高密度点集物碰撞检测中的应用研究。虚拟环境已成为计算机科学的一个重要研究领域,虚拟对象之间的碰撞检测是其关键问题之一。论文对二维平面对象碰撞检测问题进行研究,将凸壳应用到高密度点集物碰撞检测中,提出了一种基于凸壳包围盒的高密度点集物碰撞检测算法。首先计算待碰撞点集物的凸壳,通过对凸壳进行求交运算,若不相交,两点集物未发生碰撞;若相交,在两凸壳的交集区域中寻找碰撞点集。论文中的算法取得了如下结果:(1)实时凸壳算法实现了对实时点的自动编号,对每一个新增实时点最多只需对2个单调段进行计算,提高了运算效率。(2)对静态凸壳的计算,落于由各单调段所围成的区域外的点,只需跟该点所在区域的原单调段上的顶点进行计算,减少了处理的点,提高了算法执行速度。(3)利用顶点间距离关系的性质提高了夹角符号序列法的计算速度,空间复杂度为O(n),存储效率高。(4)查找首个对跖点对所需时间复杂度为O(logn),整个算法所需辅助空间为常量,时间和空间两方面都优于同类算法,该算法效率高、可靠性好、实用性较强。(5)轮廓匹配算法时间和空间复杂度均为O(n),匹配可靠,效率高,具有一定实用性。(6)高密度点集物碰撞检测算法简单、高效、可靠、实用。