高级检索

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

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

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

     

    Abstract: 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.

     

/

返回文章
返回