A Dynamic Non-Interference Algorithm for Rectangles

摘要

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.