Polygon placement under translation and rotation

摘要

We present a gnerai algorithm which computes an exact description of the set of ail placements for a polygon I (with m edges) which is free to translate and/or to rotate but not to intersect another polygon E (with n edges). The time complexity of our algorithm is O(m 3 n 3 log mn) which is close to optimal in the worst-case. Moreover, in some practical situations, the time complexity is only O (n log n). This algorithm is rather simple and has been implemented. It can be used as an efficient tool in several applications such as cutting stock, inspection and motion planning for a two dimensional robot admidst polygonal obstacles.