Fast Algorithm for Solving Sheet Metal Scrap Nesting Problem Based on “Coarse-to-Fine” Strategy

The problem of recycling waste in sheet metal cutting can be considered as a problem of determining the nesting relationship between two simple polygons under the translation and rotation of a single polygon. By adopting the “coarse-to-fine” strategy and integrating the advantages of multiple methods, an algorithm for quickly solving this problem is proposed. Firstly, some rules are used to discretize and sort the rotation angles of polygons. Then, methods such as bounding box and rasterization are utilized to roughly determine whether polygons are nested under translation. Finally, the no-fit polygon algorithm is employed to accurately determine the nesting relationship between two polygons. Experimental results on 332 actual industrial laser cutting samples demonstrate that, while maintaining an accuracy of 98.5%, the proposed algorithm reduces the average time consumption to 23.8% of that of the single no-fit polygon algorithm.