张鹏程,王春艳

(1.河北工程技术高等专科学校 电力工程系,河北 沧州 061001;2.沧州设备安装技工学校,河北 沧州 061000)

排样问题在机械制造、轻工、船舶、家具以及服装等行业中应用十分广泛。二维排样问题按形状可分为矩形、任意多边形排样,按单元排列方式分固定方向的、可旋转的等排样,按有无人的参与分为自动排样和辅助排样。实际生产中大部分二维零件毛坯是任意多边形,而单纯矩形件毛坯只占很少一部分。通常将矩形之外的其余形状图形的排样归类为二维不规则排样。

二维不规则排样问题属于最复杂的组合优化问题之一,从数学计算复杂性理论看,排样问题属于具有最高计算复杂性的一类问题—— NP完全问题,因为存在计算上的“组合爆炸”,其求解十分困难。对于NP完全问题,目前还没有找到解决该类问题的多项式算法[1],采用手工排样很难得到利用率很高的排样方案,即使采用计算机排样,也必须开发出高效的排样算法才能得到较好的排样方案。

1 二维不规则零件排样

二维不规则零件的排样问题是寻找平面最优布局的优化问题,其数学模型可进行如下描述[2]：

设有一块矩形待排板材,长为 L,宽为W,待排的多边形零件的面积分别为 S1,S2,…,Sn,n为多边形零件的数量,则排样方案的目标函数为

其约束条件为 0≤i≤n,i为已经完成排样的零件数量,多边形的顶点和各条边不越界并且不相互重叠。

目前,对不规则排样的处理方法大体上可以分两类[3]：基于规则零件排样处理的矩形近似法和不规则零件的直接处理法。以目前已有的算法来直接进行二维不规则零件排样,一般效果不佳且耗时较长。矩形近似法又称矩形包络法,是找到单个不规则零件或者多个不规则零件的组合的近似包络矩形,然后用矩形件代替原不规则零件进行排样,如图1所示,从而把不规则排样问题简化为矩形排样问题[4]。

图1 二维排样图形的外包络矩形

2 零件的位图表示

矩形包络法将多边形排样问题转化为矩形排样问题进行处理,简化了排样图形描述(不规则几何图形描述复杂度大大高于矩形),判交和碰靠过程只需记录已排零件有关顶点的信息(有关顶点的信息即为边界的约束信息),这样,插入新的排样图形时操作简单,计算量小。

文中利用位图方式来描述排样多边形零件。采用位图而非轮廓矢量信息来描述排样零件图形,其优势在于[5]：在整体上,基于位图的靠接在时间上优于基于轮廓靠接;位图文件通过象素的属性、颜色和灰度值描述图像,相对于用矢量描述的图形而言,其直接存取方式简化了信息的存储过程,而且使得基于位图的操作相对简便;排样不受图形凹凸的限制,更适合于形状怪异、空洞较多的图形排样。

3 最小包络矩形求解

3.1 位图多边形边界顶点的确定

在位图的存贮信息中,没有顶点、边等矢量信息,文中采用拐点检测的方法来获得顶点信息,以此来设计外包矩形集算法。

设 t时刻点(xt,yt)处于位图(如图2)中位置 0,为了查找和确定位图中的边界像素点,从位置 1开始依图中数字所示的方向和顺序对周围的像素点进行考察,搜索第一个非背景像素所在的位置(xi+1,yi+1),若(xi-1,yi-1)、(xi,yi)、(xi+1,yi+1)三点不在一条直线上,则记为拐点 Tj(xj,yj),位图所有拐点的集合记为 T。

如图2所示,取位图中的三个像素点：若(xi-1,yi-1)在位置 5,(xi,yi)在位置 0,(xi+1,yi+1)在位置 2,则记(xi,yi)为拐点;若(xi+1,yi+1)在位置 1则说明是非拐点。

图2 搜索拐点时依次搜索的像素位置图

3.2 最小外包络矩求解思想

设 G(θ)为图形 G旋转θ后得到的图形,z(t)=x(t)+iy(t),(0＜t＜1),z(0)=z(1),为封闭曲线,旋转θ后的坐标与原坐标之间的关系为：

在求解过程中,如选定的θ值越小,其求解得到的多边形的最小包络矩形越精确,但所耗费的计算时间也越长;如果选定的θ值较大,则可能会丢掉θ值区间上的最优解。在实际求解过程中,应根据多边形的形状和拐点的数量进行权衡选优,以求在较短的时间内获得最小的包络矩形。

3.3 外包络矩形覆盖率

采用包络矩形法求解多边形排样问题,是利用矩形代替多边形以完成全部排样计算。由于矩形的面积一般要大于多边形的面积(只有多边形也为矩形时面积相等),故该方法不可避免会产生一定量的材料浪费,在多边形的众多包络矩形中,只有最小包络矩形与其面积差值最小。

为了评定矩形代替多边形进行排样的效果,将多边形位图面积 Sraw与位图最小外包络矩形面积 Smabr的比值定义为位图对外包络矩形的覆盖率,即d=Sraw/Smabr。显然 0＜d≤1,d越大多边形越接近外包络矩形,d=1时位图本身即为矩形形状,而当d的值低于 0.7时,为了避免材料浪费过多,应首先将多边形零件进行拼接和组合,然后再求解其整体的外包络矩形以提高覆盖率d。

3.4 最小包络矩形的算法流程

利用位图表示多边形时,其最小包络矩形计算步骤如下：

Step1：输入零件位图G,将其转变为二值图B(G),并确定其边界 E(G)。

Step2：计算边界拐点 T(G)。

Step3：以零件位图的拐点集 T为依据,计算多边形重心O。

Step4：确定角度增量θ,将多边形绕其重心旋转,每次旋转角度均为θ,求得其对应状态下多边形的包络矩形 Rθ,获得外包络矩形集 R。

Step5：旋转角度 满 180°后 ,对各次的包络矩形 Rθ进行比较,从中取面积最小的矩形作为最小包络矩形。

4 应用实例及分析

利用 MATLAB编程[6]实现文中所给零件位图的最小包络矩形的求解。为了检测文中方法的可行性及优劣,取两种不同类种的多边形(一个直线多边形和一个任意多边形)进行计算,获得的多边形最小包络矩形分别如图3和图4所示,其求解结果数据如表 1所示。表 1中 Sraw为排样多边形零件位图面积,Smabr为多边形最小包络矩形面积,length为包络矩形的宽,height为包络矩形的高,d为位图在最小包络矩形中的覆盖率。

图3 直线多边形及其最小包络矩形

图4 多边形及其最小包络矩形比较图

表1 实例中多边形及其最小包络矩形结果数据

5 结论

采用位图表示排样多边形有利于对图形进行编码,快速的完成多边形图形的聚类、归类等相关运算,可以明显减少排样中多边形靠碰时间计算,从而完成高效的多边形二维零件自动排样系统的设计。实例测算表明,文中的方法可以快速有效地获得基于位图表示的多边形排样零件的最小包络矩形,从而为下一步二维多边形排样设计打下良好的基础。

[1]贾丹,董方敏.二维优化排样问题研究[J].计算机系统应用.2008(7)：21-24.

[2]靳旭玲.二维不规则排样问题的研究 [D].济南：山东科技大学,2003.

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

[4]查建中,唐晓君,陆一平.布局及布置设计问题求解自动化的理论与方法综述 [J].计算机辅助设计与图形学学报,2002,14(8)：705-712.

[5]宋亚男,杨宜民,叶家玮,等.排样图形预处理中的几个实用算法 [J].系统工程与电子技术,2005,27(6)：1102-1104.

[6]王志广.MATLAB工程计算 [M].北京：清华大学出版社,2008.