Research And Implementation Of Two-dimensional Irregular Nesting Algorithm

The nesting problem has a wide application, for example, in garment industry, in leather industry, in machinery industry. Improving utilization of material will inevitably reduce production cost, which will bring economic benefits to enterprise. So, the research of nesting problem has important economic value. The problem of two-dimensional irregular nesting has very high complexity and it is a NP complete problem. So, the research of nesting problem has important theoretical value.The algorithm of automatic nesting is studied according to polygon shapes. However, shapes are with circular arc and circle in the actual production, automatic nesting calculation can't be directly used. To be able to carry out nesting calculation, the paper puts forward the algorithm of automatic getting shape data and the algorithm of getting approximate polygon.How to find the positions where shapes are not overlapping and are contacted is one of crucial technologies of optimization problem during automatic nesting calculation. To reduce calculation of overlapping judgement, algorithm of no-fit polygon is employed to guarantee that shapes are not overlapping in the paper, and existing algorithm of no-fit polygon is improved.Besides, the paper designs some algorithms which are related with graphic algorithms in nesting algorithm, for example hull algorithm and composite polygon algorithm. After calculating no-fit polygon, a shape may be placed in many vertices of no-fit polygon. To find optimum location, optimum location is determined by convex hull algorithm. Utilization is calculated in every vertices of no-fit polygon to find optimum location. No-fit polygon is calculated according to two polygons, one shape can be calculated with the other shape when there is only one shape in the material. So, two polygons are composite to one polygon.Based on the research of above-mentioned algorithms, the paper has designed automatic nesting system of two-dimensional irregular shapes, and the system has friendly interface. System may directly handle AutoCAD drawing paper, and nesting drawing is automatically drawed through the determination of stock parameter and selection of shapes.It is inspiration meaning not only in the field, also in the other fields.