基于合并多边形的不规则图形排样优化  

Nesting Optimization of Irregular Graphs Based on Merged Polygons

作　　者：赵旭 朱志松[1] 高岚 ZHAO Xu;ZHU Zhisong;GAO Lan(School of Mechanical Engineering,Nantong University,Jiangsu Nantong 226019,China)

机构地区：[1]南通大学机械工程学院,江苏南通226019

出　　处：《机械设计与制造》2025年第2期119-123,共5页Machinery Design & Manufacture

基　　金：江苏省高等学校大学生创新创业训练计划(202110304022Z)。

摘　　要：为提高不规则图形排样问题的板材利用率,提出了一种合并多边形的临界多边形(NFP)算法与遗传算法相结合的解决方案。读取和整理DXF加工图形文件,得到不规则图形信息。通过生成不规则图形的包络多边形方法,简化含有圆弧或样条曲线的不规则图形。根据排样图形的靠接特点,合并已排样的多边形外轮廓,减少多边形数量,降低临界多边形算法计算量。通过宽度最小原则和合并多边形的NFP算法相结合的摆放策略设计适应度函数,采用混合编码的遗传算法优化排样过程中待排样图形顺序与旋转角度,最终得到排样问题的结果。利用上述方法与传统NFP算法分别对20个、60个图形进行排样优化。对比实验结果,该方法在保证排样优化效果的同时,求解速度提高了50%以上,验证了所提算法的可行性和有效性。In order to improve the sheet utilization rate of the irregular graphics layout problem,a method combining NFP algo⁃rithm with merging polygons and genetic algorithm was proposed.The DXF graphics file was read and sorted to get irregular graphics information.Through the method of generating envelope polygon of the irregular graphics,irregular graphics contain⁃ing the arc or spline curve were simplified.According to the abutment characteristics of the layout graphics,the outlines of the placed graphics were merged to reduce the number of polygons and the amount of calculation of the NFP algorithm.The fitness function was designed by the placement strategy that combined the principle of minimum width and the NFP algorithm of merg⁃ing polygon.The order and the placement angle of the graphics to be laid out in the irregular graphics layout process were opti⁃mized by the genetic algorithm of hybrid coding.The solution of the problem was obtained.The above method and the traditional NFP algorithm are used to optimize the layout of 20 and 60 graphics respectively.Comparing the experimental results,the meth⁃od can improve the solution speed by more than 50%while ensuring the layout optimization effect,which verifies the feasibility and effectiveness of the proposed algorithm.

关 键 词：不规则图形排样 板材利用率 合并多边形 临界多边形 

分 类 号：TH16[机械工程—机械制造及自动化] TP391.9[自动化与计算机技术—计算机应用技术]