package ng.Algorithm.Layouts;
|
|
import java.util.ArrayList;
|
import java.util.List;
|
|
import ng.Algorithm.Layouts.LayoutAlgorithm.AlgorithmParams;
|
|
public class Heuristic {
|
|
public static class HeuristicParam{
|
public double RowWidthThreshold; //行宽度可接受阈值
|
public double RowLayoutThreshold; //行装载可率阈值
|
public double LayoutLengthThreshold; //整体装在长度阈值
|
public double LayoutRateThreshold; //面板装载率阈值
|
}
|
|
|
class Row{
|
int rowIndex;
|
List<RowResult> results=new ArrayList<RowResult>();
|
RowResult root;
|
RowResult best1;
|
//递归搜索结果
|
private void seek(RowResult result,RectDataContext dc){
|
int[] anchor=dc.getAnchor();
|
boolean ok=false;
|
for(int i=0;i<dc.groups.length;i++){
|
RectGroup g=dc.groups[i];
|
RectEx rect=g.getCurrent();
|
if(rect==null)
|
continue;
|
boolean a1=result.canPush(rect,false);
|
boolean a2=result.canPush(rect,true);
|
if(a1==false && a2==false){
|
continue;
|
}
|
if(a1==true){
|
RowResult r=result.Clone();
|
r.Push(rect,false);
|
g.next();
|
seek(r,dc);
|
dc.SetAnchor(anchor);
|
ok=true;
|
}
|
if(a2==true){
|
RowResult r=result.Clone();
|
r.Push(rect,true);
|
g.next();
|
seek(r,dc);
|
dc.SetAnchor(anchor);
|
ok=true;
|
}
|
|
}
|
if(ok==false){
|
result.compute();
|
results.add(result);
|
result.anchor=anchor;
|
}
|
}
|
|
|
|
void tryAddRow(List<Row> rrs,Row row){
|
int count=2;
|
if(rrs.size()==0){
|
rrs.add(row);
|
return;
|
}
|
for(int i=0;i<rrs.size();i++){
|
Row r=rrs.get(i);
|
if(r.best1.result_layoutrate<row.best1.result_layoutrate){
|
rrs.add(i,row);
|
break;
|
}
|
}
|
while(rrs.size()>=count){
|
rrs.remove(rrs.size()-1);
|
}
|
}
|
|
public void Compute(RectDataContext dc,AlgorithmParams param,RowResult result,List<RowResult> resultList){
|
if(result.nextRows.size()!=0)
|
return;
|
int rlen=result.getRemainLength(param.length,param.v_interval);
|
dc.SetAnchor(result.anchor);
|
List<Row> rrs=new ArrayList<Row>();
|
for(int i=0;i<dc.groups.length;i++){
|
RectGroup g=dc.groups[i];
|
RectEx rect=g.getCurrent();
|
if(rect==null){
|
continue;
|
}
|
|
|
boolean b1=rect.getLength()<=rlen && rect.getWidth()<=param.width && rect.canZhong();
|
boolean b2=rect.getLength()<=param.width && rect.getWidth()<=rlen && rect.canHeng();
|
if(b1){
|
g.next();
|
Row row=new Row(dc,rect,false,param,result);
|
if(row.best1!=null){
|
this.tryAddRow(rrs, row);
|
}
|
dc.SetAnchor(result.anchor);
|
}
|
|
if(b2){
|
g.next();
|
Row row=new Row(dc,rect,true,param,result);
|
if(row.best1!=null){
|
this.tryAddRow(rrs, row);
|
}
|
dc.SetAnchor(result.anchor);
|
}
|
}
|
if(rrs.size()>0){
|
result.nextRows.addAll(rrs);
|
for(int i=0;i<result.nextRows.size();i++){
|
Row row=result.nextRows.get(i);
|
row.Compute(dc, param,row.best1,resultList);
|
}
|
}
|
else{
|
resultList.add(result);
|
}
|
|
|
}
|
|
|
|
public Row(RectDataContext dc,RectEx first,boolean isheng,AlgorithmParams param,RowResult parent){
|
root=new RowResult(first,isheng,param,parent);
|
this.results.clear();
|
seek(root.Clone(),dc);
|
for(int i=0;i<results.size();i++){
|
results.get(i).compute();
|
}
|
if(results.size()>0){
|
results.sort(root);
|
this.best1=results.get(0);
|
}
|
}
|
}
|
|
class RowResult implements java.util.Comparator<RowResult>{
|
private RowResult parent;
|
private List<Row> nextRows=new ArrayList<Row>();
|
private int[] anchor;
|
private List<RectEx> rects=new ArrayList<RectEx>();
|
private int length;
|
private int remainwidth;
|
private int width;
|
private int interval;
|
private int ystart;
|
private int yend;
|
|
|
int rowIndex;
|
|
public double LayoutRate;
|
public double ComputeLayoutRectArea(){
|
double a=0;
|
RowResult r=this;
|
while(r!=null){
|
for(int i=0;i<r.rects.size();i++){
|
a+=r.rects.get(i).getArea();
|
}
|
r=r.parent;
|
}
|
return a;
|
}
|
|
|
|
public void adjust(){
|
int c=this.rects.size();
|
int size=0;
|
for(int i=0;i<c;i++){
|
size+= this.rects.get(i).getXSize();
|
}
|
if(c>1){
|
int iv=(this.width-size)/(c-1);
|
for(int i=1;i<c;i++){
|
Rect r2=this.rects.get(i);
|
Rect r1=this.rects.get(i-1);
|
r2.x=r1.x+r1.getXSize()+iv;
|
}
|
}
|
else{
|
Rect r1=this.rects.get(0);
|
r1.x=(this.width-r1.getXSize())/2;
|
}
|
}
|
|
|
public RowResult Clone(){
|
RowResult r=new RowResult();
|
r.width=this.width;
|
r.parent=parent;
|
r.anchor=this.anchor;
|
for(int i=0;i<rects.size();i++){
|
r.rects.add(rects.get(i).Clone());
|
}
|
r.length=length;
|
r.remainwidth=this.remainwidth;
|
r.interval=this.interval;
|
r.ystart=this.ystart;
|
r.yend=this.yend;
|
r.rowIndex=this.rowIndex;
|
|
return r;
|
}
|
|
|
public double result_layoutrate;
|
public RowResult(RectEx _first,boolean isheng,AlgorithmParams param,RowResult parent){
|
this.parent=parent;
|
RectEx first=_first.Clone();
|
first.isHeng=isheng;
|
if(this.parent==null){
|
this.rowIndex=1;
|
this.ystart=0;
|
|
this.yend=first.getYSize();
|
}
|
else{
|
this.ystart=this.parent.yend+param.v_interval;
|
this.yend=this.ystart+first.getYSize();
|
this.rowIndex=this.parent.rowIndex+1;
|
}
|
rects.add(first);
|
this.length=first.getYSize();
|
this.width=param.width;
|
this.interval=param.h_interval;
|
this.remainwidth=this.width-interval-first.getXSize();
|
this.yend=this.ystart+first.getYSize();
|
first.x=0;
|
first.y=this.ystart;
|
first.Row=this.rowIndex;
|
first.Col=1;
|
}
|
|
|
private RowResult(){
|
|
}
|
|
|
public void compute(){
|
double a=(this.width+interval)*this.length;
|
double b=0;
|
for(int i=0;i<this.rects.size();i++){
|
RectEx r=this.rects.get(i);
|
b+=(r.getXSize()+interval)*r.getYSize();
|
}
|
this.result_layoutrate=b/a;
|
}
|
|
//计算排炉剩余长度
|
public int getRemainLength(int maxlength,int yinterval){
|
int len=0;
|
RowResult r=this;
|
while(r!=null){
|
len+=r.length+yinterval;
|
r=r.parent;
|
}
|
if(len==0)
|
len=maxlength;
|
else
|
len=maxlength-len;
|
return len;
|
}
|
|
|
public boolean canPush(RectEx r,boolean heng){
|
if((heng && r.canHeng()==false) && (heng==false && r.canZhong()==false)){
|
return false;
|
}
|
r.isHeng=heng;
|
if(r.getXSize()>this.remainwidth){
|
return false;
|
}
|
if(r.getYSize()>this.length)
|
return false;
|
return true;
|
}
|
|
|
public void Push(RectEx r,boolean heng){
|
r=r.Clone();
|
r.isHeng=heng;
|
|
this.remainwidth-=r.getXSize()+interval;
|
Rect last=this.rects.get(this.rects.size()-1);
|
r.x=last.x+last.getXSize()+interval;
|
int k=this.ystart+r.getYSize();
|
if(k>this.yend)
|
this.yend=k;
|
r.y=this.ystart;
|
r.Row=this.rowIndex;
|
|
this.rects.add(r);
|
r.Col=this.rects.size();
|
}
|
|
|
|
|
|
|
@Override
|
public int compare(RowResult o1, RowResult o2) {
|
// TODO Auto-generated method stub
|
if(o1.result_layoutrate<o2.result_layoutrate)
|
return 1;
|
if(o1.result_layoutrate>o2.result_layoutrate)
|
return -1;
|
return 0;
|
}
|
}
|
|
class RectEx extends Rect{
|
public int groupNumber;
|
public int pieceIndex;
|
public RectEx(Piece source) {
|
super(source);
|
// TODO Auto-generated constructor stub
|
}
|
|
public RectEx Clone(){
|
RectEx r=new RectEx(this.getSource());
|
this.CopyTo(r);
|
r.groupNumber=this.groupNumber;
|
r.pieceIndex=this.pieceIndex;
|
return r;
|
}
|
|
}
|
|
class RectDataContext{
|
public RectGroup[] groups;
|
public int[] getAnchor(){
|
int[] r=new int[groups.length];
|
for(int i=0;i<r.length;i++){
|
r[i]=groups[i].index;
|
}
|
return r;
|
}
|
|
public void SetAnchor(int[] Anchor){
|
for(int i=0;i<groups.length;i++){
|
groups[i].index=Anchor[i];
|
}
|
}
|
|
public void Reset(){
|
for(int i=0;i<groups.length;i++){
|
groups[i].Reset();
|
}
|
}
|
|
public RectDataContext(List<Piece>[] rects){
|
groups=new RectGroup[rects.length];
|
for(int i=0;i<groups.length;i++){
|
RectGroup rg=new RectGroup();
|
rg.index=0;
|
for(int j=0;j<rects[i].size();j++){
|
Piece r=rects[i].get(j);
|
RectEx rr=new RectEx(r);
|
rr.groupNumber=i+1;
|
rr.pieceIndex=j;
|
rg.rects.add(rr);
|
}
|
groups[i]=rg;
|
}
|
}
|
}
|
|
class RectGroup{
|
private List<RectEx> rects=new ArrayList<RectEx>();
|
private int index;
|
|
public RectEx getCurrent(){
|
if(index<rects.size())
|
return rects.get(index);
|
return null;
|
}
|
|
|
|
public int getCount(){
|
return rects.size()-index;
|
}
|
|
public void next(){
|
if(index<rects.size())
|
index++;
|
}
|
|
public void Reset(){
|
index=0;
|
}
|
}
|
|
AlgorithmParams param;
|
HeuristicParam hparam;
|
RectDataContext dc;
|
List<RowResult> results=new ArrayList<RowResult>();
|
|
//重新初始化
|
public void SetParam(AlgorithmParams param){
|
this.param=param;
|
this.hparam=(HeuristicParam)param.methodParam;
|
}
|
|
|
public LayoutResult compute(List<Piece>[] rects){
|
this.dc=new RectDataContext(rects);
|
results.clear();
|
List<Row> rows=new ArrayList<Row>();
|
for(int i=0;i<this.dc.groups.length;i++){
|
RectGroup g=dc.groups[i];
|
RectEx rect=g.getCurrent();
|
if(rect==null)
|
continue;
|
boolean b1=rect.getLength()<=param.length && rect.getWidth()<=param.width && rect.canZhong();
|
boolean b2=rect.getLength()<=param.width && rect.getWidth()<=param.length && rect.canHeng();
|
|
if(b1){
|
g.next();
|
Row row=new Row(dc, rect,false, param, null);
|
rows.add(row);
|
dc.Reset();
|
}
|
if(b2){
|
g.next();
|
Row row=new Row(dc, rect,true, param, null);
|
rows.add(row);
|
dc.Reset();
|
}
|
}
|
for(int i=0;i<rows.size();i++){
|
Row row=rows.get(i);
|
row.Compute(dc, param,row.best1,results);
|
|
}
|
RowResult best=null;
|
double k=param.width*param.length;
|
for(int i=0;i<results.size();i++){
|
RowResult r=results.get(i);
|
double area= r.ComputeLayoutRectArea();
|
r.LayoutRate=area/k;
|
if(best==null)
|
best=r;
|
else
|
{
|
if(best.LayoutRate<r.LayoutRate){
|
best=r;
|
}
|
}
|
}
|
LayoutResult ret= this.getLayoutResult(best);
|
return ret;
|
}
|
|
|
void adjust(RowResult result){
|
RowResult r=result;
|
while(r!=null){
|
r.adjust();
|
r=r.parent;
|
}
|
}
|
|
LayoutResult getLayoutResult(RowResult oneResult){
|
List<Integer> ids=new ArrayList<Integer>();
|
List<RectEx> rects=new ArrayList<RectEx>();
|
RowResult r=oneResult;
|
while(r!=null){
|
for(int i=r.rects.size()-1;i>=0;i--){
|
RectEx re=r.rects.get(i);
|
ids.add(0,re.groupNumber*2+(re.isHeng?1:0));
|
rects.add(0,re);
|
}
|
r=r.parent;
|
}
|
dc.Reset();
|
boolean bug=false;
|
for(int i=0;i<ids.size();i++){
|
int a=ids.get(i);
|
int idx=a/2-1;
|
boolean ish=(idx%2)==1;
|
RectEx rr= dc.groups[idx].getCurrent().Clone();
|
dc.groups[idx].next();
|
rr.isHeng=ish;
|
if(rr.getSource()!=rects.get(i).getSource()){
|
//该条件 不可能 算法有 bug;
|
bug=true;
|
}
|
}
|
if(bug==true){
|
System.out.println("bug");
|
return null;
|
}
|
this.adjust(oneResult);
|
LayoutResult result=new LayoutResult();
|
result.layout=new Rect[rects.size()];
|
rects.toArray(result.layout);
|
result.rate=oneResult.LayoutRate;
|
|
return result;
|
}
|
|
}
|
