剩余矩形算法的MATLAB实现论文

1、剩余矩形算法的MATLAB实现河海大学12级物理(1)班functionmathmode_lsize=zeros(25,2);%表示小矩形的尺寸.M(i,1)、M(i,2)分别表示序号为i的小矩形的宽和高.D=zeros(25,2);%排样方案数组.D(i,1)、D(i,2)分别表示第i个矩形的序号以及r(i).rest=zeros(50,4);%剩余矩形数组.记录每个矩形的左下角坐标(x,y)、宽和高.A=zeros(25,4);%记录数组(记录每个矩形件在样板上的位置).%初始值均为零。(zeros)size=12,6;4,7;6,7;10,2;2,5;6,4;4,2;4,6;7,9;4,

2、5;6,4;4,6;6,3;4,5;2,4;8,4;8,6;8,3;6,3;2,6;8,2;3,5;2,5;3,4;2,4;%小矩形件的尺寸.P1=zeros(1,25);P2=zeros(1,25);P3=zeros(1,25);R1=zeros(1,25);R2=zeros(1,25);R3=zeros(1,25);P1=4,2,1,3,6,5,7,9,8,10,11,12,14,13,19,15,18,17,20,16,21,22,24,23,25;R1=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;P2=10,5,1,13,23,2

3、4,22,8,14,4,7,25,11,19,6,2,16,20,18,9,17,3,12,15,21;R2=0,1,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,0,0,0,1,1,0,0;P3=23,21,20,16,17,2,24,25,9,3,5,8,22,14,15,18,7,6,10,19,4,12,11,13,1;R3=0,0,1,0,1,1,0,0,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0;D1=P1',R1'D2=P2',R2'D3=P3',R3'%至此，数据初始化完毕D=D3;%选择

4、排样方案.w=zeros(25,1);h=zeros(25,1);%矩形件的宽和高N=1;%N1剩余矩形的个数.rest(1,:)=0,0,15,60;%样板的尺寸设为：宽15，高60.H=0;%占用高度，用来求样板利用率.fori=1:25%矩形件i的宽和高w(i)=size(D(i,1),1+D(i,2);h(i)=size(D(i,1),2-D(i,2);endre=zeros(30,4);fori=1:25%放置25个矩形件%i=3;n=1;j=0;whilen<=N%求能包含小矩形件的剩余矩形re，j表示个数.ifrest(n,3)>=w(i)&&rest

5、(n,4)>=h(i)j=j+1;re(j,:)=rest(n,:);endn=n+1;endk=2;whilek<=j献用到的剩余£!形(放在re的第一行)，根据BL条件.ifre(k,2)<re(1,2)|(re(k,2)=re(1,2)&&re(k,1)<re(1,1)re(1,:)=re(k,:);endk=k+1;endA(i,1)=re(1,1);A(i,2)=re(1,2);A(i,3)=w(i);A(i,4)=h(i);%第i个矩形件的位置信息ifH<(A(i,2)+A(i,4)%占用高度的更新.H=(A(i,2)+A(i

6、,4);end%剩余矩形数组的处理更新.NA(i,)n=1;Now=N;whilen<=Now;m=0;k=N+1;%if(A(i,2)>rest(n,2)&&(A(i,2)<(rest(n,2)+rest(n,4)&&(A(i,1)<rest(n,1)+rest(n,3)&&(A(i,1)+A(i,3)>rest(n,1)N=N+1;rest(k,1)=rest(n,1);rest(k,2)=rest(n,2);rest(k,3)=rest(n,3);rest(k,4)=A(i,2)-rest(n,2);k=k+1

7、;m=1;endifrest(n,1)+rest(n,3)>A(i,1)+A(i,3)&&A(i,1)+A(i,3)>rest(n,1)&&(A(i,2)<rest(n,2)+rest(n,4)&&(A(i,2)+A(i,4)>rest(n,2)N=N+1;rest(k,1)=A(i,1)+A(i,3);rest(k,2)=rest(n,2);rest(k,3)=rest(n,1)+rest(n,3)-A(i,1)-A(i,3);rest(k,4)=rest(n,4);k=k+1;m=1;endifA(i,1)>re

8、st(n,1)&&(A(i,1)<rest(n,1)+rest(n,3)&&(A(i,2)<rest(n,2)+rest(n,4)&&(A(i,2)+A(i,4)>rest(n,2)N=N+1;rest(k,1)=rest(n,1);rest(k,2)=rest(n,2);rest(k,4)=rest(n,4);rest(k,3)=A(i,1)-rest(n,1);k=k+1;m=1;endifrest(n,2)+rest(n,4)>A(i,2)+A(i,4)&&A(i,2)+A(i,4)>rest(

9、n,2)&&(A(i,1)<rest(n,1)+rest(n,3)&&(A(i,1)+A(i,3)>rest(n,1)N=N+1;rest(k,2)=A(i,2)+A(i,4);rest(k,1)=rest(n,1);rest(k,4)=rest(n,2)+rest(n,4)-A(i,2)-A(i,4);rest(k,3)=rest(n,3);k=k+1;m=1;endifm=0n=n+1;elserest(n,:)=;N=N-1;Now=Now-1;rest(50,:)=0;%删除要注意！endend%求出剩余矩形数组，下面要对其进行整理.n=1;

10、m=0;whilen<=Nk=i+1;whilek<=25if(rest(n,3)>=w(k)&&rest(n,4)>=h(k)m=1;break;elsek=k+1;endendifm=1n=n+1;elseN=N-1;rest(n,:)=;rest(50,:)=0;%删去面积为零的或已无法排下所剩的任何一个矩形件的剩余矩形endendn=1;whilen<=Nk=1;whilek<Nifrest(n,1)>=rest(k,1)&&rest(n,2)>=rest(k,2)&&rest(n,1)+r

11、est(n,3)<=rest(k,1)+rest(k,3)&&rest(n,2)+rest(n,4)<=rest(k,2)+rest(k,4)ifn=kN=N-1;m=1;rest(n,:)=;rest(50,:)=0;%删去被包含的剩余矩形break;elsek=k+1;m=0;endelsek=k+1;m=0;endendifm=0n=n+1;endend%end%下面进行制图,0,0,15,60);axisequal ;rectangle('position'holdon;x=zeros(1,25);y=zeros(1,25);fori=1:25ifA(i,3)>0&&A(i,4)>0rectangle(endposition',A(i,:),'facecolor''g');x(1,i)=A(i,1)+A(i,3)/2;y(1,i)=A(i,2)+A(i,4)/2;endtext(x,y,num2str(D(:,1);holdoff;%求板材利用率.a='%'fpr