基于轨迹计算的临界多边形求解算法

摘要

将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题.该算法的基本原理是:1)求解多边形顶点相对于另一多边形的轨迹线;2)求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形.该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度.