基于二维不规则图形的实用排样算法研究.pdf

《基于二维不规则图形的实用排样算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、·工艺与装备·组合机床与自动化加工技术文章编号：1001—2265(2010)03—0088—03基于二维不规则图形的实用排样算法研究木杨传华，吴锦文，李殿国，杨海(1．佳木斯大学机械212程学院，黑龙江佳木斯154007；2．奇瑞汽车股份有限公司，安徽芜湖241009：3．东芝大连有限公司，辽宁大连116600)摘要：论文对二维不规则图形进行排样，先采用最小矩形包络法对不规则图形进行矩形包络，并求取最小的包络矩形。而后采用基于最低水平线的搜索算法对最小包络矩形进行初步排样，在此基础上使用平移靠接算法对初步排样的二维不规则图形进行平移靠接，减少板材的局部浪

2、费，提高材料的利用率。实例证明了该综合算法的可行性和有效性。关键词：靠接算法；最低水平线算法；矩形包络法中图分类号：TH16；TG65文献标识码：AResearchonTwo-dimensionalIrregularGraphicsBasedonThePracticalPackingAlgorithmYANGChuanhua，WUJin—wen，LIDian—guo，YANGHan(1．CollegeofMechanicalEngineeringJiamusiUniversity，JiamusiHeilongjiang154007，China；2．Cher

3、yAu·tomobileCo．Ltd．，WuhuAnhui241009，China)Abstract：Thispaperadoptstheminimumrectangularenvelopemethodfortwo-dimensionalirregularshapesfirst，then，adoptsanimprovedalgorithmforbasisofthelowesthorizontalLineforpreliminarypacking,andoptim~edtheshapestouseparallelmovingcollisionalgorith

4、monthisbasis，improvesmaterialutilizationrate．Keywords：collisionalgorithm；improvedalgorithmforbasisofthelowesthorizontalline；rectangularenve-lopemethod0引言随着社会的发展、科技的进步，二维图形排样广泛存在于许多工业中，如：机械厂中金属板材的排样，玻璃厂中玻璃的排样，服装厂中布料的排样。长期以来，人们不断地研究各种排样算法，对于一维排样和二维规则图形排样已经有了比较成熟的排样算法，而对于不规则的图形⋯，现在采用

5、比较多是矩形包络法、遗传算法和模拟退火算法。本文先采用矩形包络法对不规则图形进行预处理，在此基础上采用基于最低水平线图1不规则图形包络矩形图2不规则图形包络矩形的搜索算法和平移靠接算法对预处理图形进行排1．2基于最低水平线的搜索算法样。分析BL算法和“下台阶算法”可以发现：前者1最小矩形包络法、基于最低水平线的搜索算法经常会出现排样左侧偏高的情况，而后者经常会出现右侧偏高现象。最低水平线算法解决了此问题，具体1．1最小矩形包络法步骤如下：最小矩形包络法就是用矩形将不规则的图形包络Step1：设置初始最高轮廓线为板材最下面的边；在矩形内，并使包络矩形的面积最

6、小。如图l，2所示：Step2：每当要排入一个零件P时，就在最高轮廓收稿日期：2009—09一O3基金项目：黑龙江省教育厅项目(11521295)；佳木斯大学项目(2007—09)作者简介：杨传华(197O一)，男，山东人，佳木斯大学机械工程学院副教授，从事CAD／CAM、钣金排样方面研究，(E—mail)chuanhua—yang@126·88·2010年第3期·工艺与装备·线集中选取最低的一段水平线，如有数段，则选取最左图形1的轮廓线相交，所以不作记录。各个水平靠接距边的一段，测试该段线的宽度是否大于或等于待排零离形成了数集W={，L：，，，⋯，。}。

7、件的宽度：(4)确定最终的水平靠接距离⋯(1)如果该段线的宽度大于或等于要排入零件的宽通过数值比较从数集中选出数值最小的值作度，则将该零件在此位置排放，同时更新零件最高轮廓线；为水平靠接距离⋯。(对于此例，8的值最小，所以(2)否则，查询与最低水平线段相邻的左、右两段W⋯=L8)。水平线，将最低水平线提升至相邻且高度较低的一段(5)进行水平靠接平齐，同时更新零件最高轮廓线；以￡为水平靠接距离进行水平靠接，靠接后的图Step3：重复Step2过程，直至能排入该零件，并求形如图4所示。出此时的最大高度；FMStep4：重复Step2和Step3过程，直至所有零

8、件排放完毕，最后所得的最大高度即为所需板材的高度。基于最低水平线的