椭圆-矩形的静动态不适合边界算法

摘要

在求解Packing问题、机器人路径规划、虚拟装配、碰撞检测等常用到椭圆-矩形的不干涉算法.针对椭圆和矩形分别在静止、运动状态下的不干涉问题,该文在Adamowicz&Albano的NFP基础上,给出了椭圆-矩形的静、动态不适合边界(No Fit Boundary,NFB)的定义,用图形变换方法证明了静态不适合边界是由4条线段和4段椭圆弧组成的对称曲八边形,给出了对称曲八边形顶点计算公式,提出了椭圆-矩形的静、动态不干涉算法.该算法简单且具有一定的应用价值.