Determination of Translations to Create Layouts With Exact Placements for Two Moveable Items

This paper investigates the irregular shape packing problem. In these problems, it is necessary to obtain layouts in which all items are completely inside a container and do not collide with each other. In order to obtain such layouts, the concept of collision free region, which determines all possible placements for a new item, is adopted. With the use of this concept, special positions represented by degenerated edges and degenerated vertex can be detected. These positions represents placements with exact slides and exact fits and thus, are relevant to the container minimization problem. However, if no appropriate placement heuristic is adopted, these placements are not commonly obtained. In view of this, this work proposes an algorithm that determines all translations for a given item such that the next item admits exact fit and/or exact slide placements. Using slope ordered list of edges and binary search, an efficient version of this algorithm is obtained. Copyright ©2012 IFAC.