基于临界多边形的不规则件启发式排样算法
来源：计算机应用杂志2016年第9期北京时间：
作者：汤德佑, 周子琳
单位：华南理工大学 软件学院, 广州 510006
摘要：为提高不规则件启发式排样的材料利用率，提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先，定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度，在此基础上给出了将边适应度与重心NFP（GNFP）相结合的排放策略以减少排样过程中可能产生的空隙面积；其次，给出了基于Weiler-Atherton多边形裁剪算法的剩余原材料求解方法，重用排样过程中产生的孔洞，减少孔洞面积；最后，给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA，给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明，GEFHNA的耗时约为基于智能算法的排样方法的千分之一，同时在与两款商业软件NestLib和SigmaNest的11个基准测试的对比中，GEFHNA获得了7/11个相对最优的排样面积利用率。
关键词：二维不规则件,排样,临界多边形,启发式方法
基金资助：广东省重大科技专项（2012A010701011）；广州市科技计划项目（201200000034）。
