碰撞检测的快速算法

摘要

在智能机器人路径规划的仿真系统中,碰撞检测所用的时间占相当大的比例,其算法的实时性也非常关键.而碰撞检测可以数学建模成判断两个三维空间凸多面体是否相交的问题.本文把它转化为一个的线性规划,并利用该模型最多三维空间的特点,结合线性规划及其对偶理论进行简化,针对其特点提出了快速检测算法,实验结果表明算法是非常有效的.