一种矩形的动态不干涉算法

A Dynamic Non-Interference Algorithm for Rectangles

针对处于相对运动状态下的两矩形图形之间在任一瞬间的不干涉判断问题 ,也即矩形的动态不干涉判断问题 ,根据不适合多边形 (No- Fit- Polygon)法和矩形的几何特性 ,给出了相对运动的矩形与矩形图形之间动态不干涉 (不重叠 )的判别条件及其证明 ,同时给出其不适合多边形 (转化为对称八边形 )顶点的简捷计算公式和相应的不干涉算法 .该算法具有优良的计算特性 ,特别适用于既有相对平移又有转动的这种相对运动的两矩形图形之间的动态不干涉判断 ,并具有一定的应用价值 .

The dynamic non interference judgement problem refers to the judgement on non interference between two geometric figures in relative motion at any instance which often occurs in layout optimization,route programming for robots,dynamic simulation,etc.It is of great computational complexity and is to be further discussed.This paper mainly deals with the case of two rectangles.According to the theory of the No Fit Polygon and rectangle's geometric feature,the authors give the rules of the judgment,the proof of the rules ,and the simple formulas to compute the apex of the No Fit Polygon(transformed into symmetrical octagon).As a result,the non interference algorithm of above two dimensional geometric figures is established.This algorithm is simple and efficient.In particular,it is suitable for the judgment on non interference between two rectangles in relative motion at any instance,so it is of the certain value of application.