One Algorithm For Optimizing Nesting Pattern In 2D Irregular Graphic

Optimizing nesting generally refers to arranging as many as possible needed geometrical graphic in some plane regions with constrained length and width.,which appears in many industries, such as the industries of rag trade, leather, sports goods, mechanical manufacturing, and so on. There are thousands of enterprises ,which have Optimizing nesting problems in our country, but the majority of them use hand-generated cutting patterns in the nesting process. As a result, the material usage is low and the amount of waste is large. Improving material usage may reduce the costs of production and it is an efficient way to increase the profits of the enterprises. The optimization of two-dimensional irregular graphic layout is a basic problem in computer science and operational research, and has root key applications in many industries. But the current results from traditional methods do not satisfy real applications. In theory, the nesting 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 complexity of shapes and computation.Currently, most of the papers published in the area are concerned with the cutting problem of regular shapes (such as rectangular), only few is about the irregular shapes. One method about irregular shapes nesting is approximately rectangle solution method based on regular shapes, the other method is to deal with the irregular shapes directly. This paper presents a new approximation optimal method, named collision algorithm, about the packing space based on the latter method. Using this algorithm, we can improve the efficiency of cutting through colliding left and down in the processing of placement. So it undoubtedly decrease interspaces between two neighbor graphics and two chains of graphics. How to find the positions where shapes are not overlapping and are contacted is one of crucial technologies of optimization problem in the courses. It involves with some graphic algorithms . Following is its...