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

A Static and Dynamic No Fit Boundary Approach for Ellipse-Rectangle

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

When resolving problem of interference such as packing,robot motion planning,virtual assembly,collision detection and so on,the interference algorithm for ellipse-rectangle is often used.Aiming at problem of judgment on the non-interference for ellipse and rectangle at static and dynamic situation respectively,this paper defines a no fit boundary（NFB） for ellipse-rectangle based on the conception of no fit polygon （NFP） given by Adamowicz ＆ Albano, using graphics transformation method proves that static no fit boundary for ellipse-rectangle is a symmetrical curvilinear octagon which consists of four line segments and four elliptical arcs.Furthermore the simple formulas to compute the apex of the No fit Boundary are given and corresponding non-interference algorithm is presented in this paper.The algorithm is simple and is of the certain value of application.