一种三维物体碰撞检测的算法及其实现

摘要

本文介绍了一种三维物体碰撞检测的算法,而求二个简单多边形的外轮廓是碰撞检测问题的基础.为了解决这一问题,我们采用了平面扫描线算法求线段的交.当采用平衡二叉树结构存储全序关系时,算法的时间复杂性为0((m+n+k)log(m+n+k)),其中k为二个简单多边形的交点数.