The Research Of The Two-Dimensional Irregular Shape Problem

In theory, the packing problem of two-dimensional irregular shapes belongs to the NP-hard problems. It is very difficult to find the optimal solution for such a problem because of the high complexity of shapes and computation. Most of the papers published in this field are concerned with the packing problem of regular shapes (such as), only a few are about the irregular shapes. One method about irregular shapes is approximately rectangle solution method based on regular shapes packing, the other method is to deal with the irregular shapes directly. This paper presents a new approximation optimal about the packing space based on the combination of the two methods. Using this algorithm, we can improve the packing efficiency and the using ratio of material. In this paper, the approximate polygon for irregular shapes, the protruding and concave point of polygon, the direction of polygon, the area of polygon, the single, face to face, frock, combinable packing are talked. Also, the algorithm about inner and outer point of polygon, the overlapping about polygons, the bumping region of polygon, the bumping zonal region of polygon and the least bumping distance of polygon are realized. In addition, the design about ruling storeroom is given and the packing space through the organizing and updating of the borderline about packing space is formed combined with the character of the Irregular shapes.