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

杨传华,吴锦文,李殿国,杨海

(1.佳木斯大学 机械工程学院,黑龙江 佳木斯 154007;2.奇瑞汽车股份有限公司,安徽 芜湖241009;3.东芝大连有限公司,辽宁大连 116600)

0 引言

随着社会的发展、科技的进步,二维图形排样广泛存在于许多工业中,如：机械厂中金属板材的排样,玻璃厂中玻璃的排样,服装厂中布料的排样。长期以来,人们不断地研究各种排样算法,对于一维排样和二维规则图形排样已经有了比较成熟的排样算法,而对于不规则的图形[1],现在采用比较多是矩形包络法、遗传算法和模拟退火算法。本文先采用矩形包络法对不规则图形进行预处理,在此基础上采用基于最低水平线的搜索算法和平移靠接算法[2]对预处理图形进行排样。

1 最小矩形包络法、基于最低水平线的搜索算法

1.1 最小矩形包络法[3]

最小矩形包络法就是用矩形将不规则的图形包络在矩形内,并使包络矩形的面积最小。如图 1,2所示：

1.2 基于最低水平线的搜索算法[4]

分析 BL算法[5]和“下台阶算法”可以发现：前者经常会出现排样左侧偏高的情况,而后者经常会出现右侧偏高现象。最低水平线算法解决了此问题,具体步骤如下：

Step 1：设置初始最高轮廓线为板材最下面的边;

Step 2：每当要排入一个零件 Pi时,就在最高轮廓线集中选取最低的一段水平线,如有数段,则选取最左边的一段,测试该段线的宽度是否大于或等于待排零件的宽度：

(1)如果该段线的宽度大于或等于要排入零件的宽度,则将该零件在此位置排放,同时更新零件最高轮廓线;

(2)否则,查询与最低水平线段相邻的左、右两段水平线,将最低水平线提升至相邻且高度较低的一段平齐,同时更新零件最高轮廓线;

Step 3：重复 Step 2过程,直至能排入该零件,并求出此时的最大高度;

Step 4：重复 Step 2和 Step 3过程,直至所有零件排放完毕,最后所得的最大高度即为所需板材的高度。

基于最低水平线的搜索算法是在最低水平线算法排样中出现了要排入的零件的宽度大于最高轮廓线集中最低的一段(或多段)水平线时,而不去更新零件的最高轮廓线,而是从未排样的零件中挑选宽度小于最低水平线宽度的零件[6]。将此两个零件交换顺序,而后重新生成新的排列顺序。

2 平移靠接算法原理[9-11]

平移靠接算法是将两个不规则图形在水平或竖直发方向上进行靠接,直至两个图形刚好相接(但不交叉,即无重叠区域)。以图 3在水平方向平移靠接为例进行说明：

图 3 平移靠接前

(1)首先扫描靠接区域和确定靠接轮廓线

通过扫描可以确定靠接区域为图形 1的右侧和图形 2的左侧,从而可以判断出图形 1的靠接轮廓线为ABCDE,图形 2的靠接轮廓线为 FGHIJK[7-8]。

(2)选取两个图形靠接轮廓线上的折点(即凸凹点)

对于图形 1轮廓线上的折点有：A、B、C、D、E,图形2轮廓线上的折点有 ：F、G、H、I、J、K。

(3)确定各个折点的水平靠接距离

先确定图形 1上折点的水平靠接距离,过 A点向右作水平线与图形 2的轮廓线相交(如图 3所示),并标记此线段的长度为 L1,用此方法可以求得过 B、C、D、E四点与图形 2轮廓线相交的水平线的长度,分别标记为 L3、L6、L8、L9。

同理可以确定图形 2上折点的水平靠接距离,分别标记为 L2、L4、L5、L7、L9。由于过 F点作水平线不与图形1的轮廓线相交,所以不作记录。各个水平靠接距离形成了数集 W={L1,L2,L3,L4,…,L9}。

(4)确定最终的水平靠接距离 Wmin

通过数值比较从 W数集中选出数值最小的 L值作为水平靠接距离 Wmin。(对于此例,L8的值最小,所以Wmin=L8)。

(5)进行水平靠接

以 L8为水平靠接距离进行水平靠接,靠接后的图形如图 4所示。

图 4 平移靠接后

3 基于 PRO/E平台的排样实例及说明

3.1 参与排样的钣金件的原始数据

参与排样的钣金件共有 8个,用 PRO/E软件绘出后如下图所示(单位为：mm),其中钣金件外的红线框为钣金件的最小包络矩形。

3.2 用 PRO/E软件中的排样系统的排样结果

将这8个钣金件放在宽 100mm,足够长的钣金件上排样,排样的顺序为零件 1、零件 7、零件 2、零件 6、零件4、零件 3、零件 8、零件 5。如果用的长度越小,则排样的效果就越好。PRO/E软件中的排样系统的排样结果如图 5所示,此时,钣金件所用的板材长度是 49mm。

3.3 用本论文的排样算法的排样结果

用上述同样的排样方式和排样顺序,钣金件所用的长度是 40mm。对上述的 8个钣金件进行排样,排样结果如图 6所示,此排样算法的排样过程说明：①从板材的最左下端排钣金件 1;②排钣金件 7并进行向左水平靠接;③排钣金件 2;④排钣金件 6并进行向左水平靠接;⑤排钣金件 4发现钣金件 6的右侧宽度不够,此时运用基于最低水平线的搜索算法从未排样的钣金件中搜索到能在此处排样的钣金件 8,交换钣金件 4和钣金件 8的排样顺序,(即未排钣金件的排样顺序为：钣金件 3、钣金件 4、钣金件 5),此时更新最低水平线为钣金件 6最小包络矩形的上端线段;⑥在更新后的最低水平线上排钣金件 3并进行向下靠接,此时更新最低水平线为钣金件 7最小包络矩形的上端线段;⑦在更新后的最低水平线上排钣金件 4并进行向左水平靠接;⑧排钣金件 5并进行向下靠接。经过此算法所得排样图如图 7所示。

4 结束语

[1]黄红兵,蒋望东.二维不规则零件排样问题的研究[J].广西科学院学报,2004,20(4)：225-227.

[2]Song Yanan,Ye Jiawei,Wei Liangliang,etal.The Analysis,New Development and of Packing(Nesting),Symposium on the Development of Ship-building＆Ship-repairing Industry 2003,Guangzhou China,2003(3)：21-22.

[3]曹新明,蒋瑞斌.不规则零件最小包络矩形的求解研究[J].科技通报,2007,1(23)：102-105.

[4]朱冠华.矩形件排样中基于最低水平线的改进算法[J].茂名学院报,2006,1(16)：28-32.

[5]Jokobs S.On genetic algorithms for the packing of polygons.European Journal of Operational Reseaech,1996,88：165-181.

[6]AdamowiczM,Albano A.A solution of the rectangular cutting-stock problem[J].IEEE Transactions on Systems,Man,and Cybernetics,1976,SMC-6(4)：302-310.

[7]覃中平,张焕国.确定凸多边形平移时最初碰撞部位的最优算法[J].计算机学报,1992,15(3)：171-177.

[8]汪嘉业.平面上简单多边形平移时确定碰撞部位的最优算法[J].计算机学报,1992,15(8)：582-588.

[9]Cheng S K,Rao K P.Large-Scale nesting of irregu lar patterns using compact neighborhood algorithm.Journal of Materials Processing Technology,2000,(103)：135-140.

[10]宋亚男,叶家玮,邓飞其,等.不规则图形排样系统中靠接算法比较研究[J].计算机工程,2004,19(30)：8-10.

[11]宋亚男,叶家玮,邓飞其,等.排样系统中基于位图的三种靠接算法比较[J].武汉科技大学学报,2004,1(27)：54-57.