基于“由粗到细”思想的钣金废料嵌套问题快速求解算法  

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

作　　者：陈播 胡银雷 陈发来[1] Chen Bo;Hu Yinlei;Chen Falai(School of Mathematical Sciences,University of Science and Technology of China,Hefei 230026)

机构地区：[1]中国科学技术大学数学科学学院,合肥230026

出　　处：《计算机辅助设计与图形学学报》2025年第1期28-39,共12页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61972368,12371383);安徽省自然科学基金(2308085QA07);中国博士后科学基金(2023M733383);中央高校基本科研业务费专项资金(WK0010000085).

摘　　要：钣金切割中的废料再利用问题,可视为允许单个多边形平移旋转的2个简单多边形嵌套关系的判断问题.采用“由粗到细”的思想,整合多种方法的优势,提出一种快速求解此类问题的算法.首先使用一些规则对多边形的旋转角度进行离散并排序;然后利用包围盒、栅格化等方法,粗略判断多边形在平移下是否嵌套;最后利用临界多边形算法,精确判断2个多边形的嵌套关系.在332个实际激光切割工业样例上的实验结果表明,在保证正确率为98.5%的情况下,所提算法的平均耗时降低到单一的临界多边形算法的23.8%.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.

关 键 词：废料再利用 钣金切割 简单多边形嵌套 二维排样 二维下料 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]