Rectangle Algorithm

Question

I have rectangles and GridLayout, the width and height of these rectangles are the same. therefore, the layout places the position of the rectangle, as in the following figure.

This is the problem: if the width and height of my rectangles are different in size, what is the layout algorithm to put the rectangular position in a compact way?

Answer 1

It finally took some time to answer this question, so here is my bin package code:

//--------------------------------------------------------------------------- //--- rectangle binpack class ver: 1.00 ------------------------------------- //--------------------------------------------------------------------------- const double _binpack_no_y_stop=1.0e+300; class binpack_rec { public: struct _rec { double x0,y0,xs,ys; _rec(){ x0=0.0; y0=0.0; xs=0.0; ys=0.0; }; _rec(_rec& a){ *this=a; }; ~_rec(){}; _rec* operator = (const _rec *a) { *this=*a; return this; }; /*_rec* operator = (const _rec &a) { ...copy... return this; };*/ }; struct _lin { double xs; int i0,i1; _lin(){ xs=0.0; i0=0; i1=0; }; _lin(_lin& a){ *this=a; }; ~_lin(){}; _lin* operator = (const _lin *a) { *this=*a; return this; }; /*_lin* operator = (const _lin &a) { ...copy... return this; };*/ }; _rec *rec; // rectangles rec[N] _lin *lin; // line blocks of recs lin[n] int *ix,*on,n,N; // ix[N] index sorted, on[N] is rectangle rec[ix[i]] used?, n number of line blocks, N number of rects binpack_rec() { rec=NULL; ix=NULL; on=NULL; N=0; } ~binpack_rec() { _free(); } void _free() // free memory { n=0; N=0; if (rec) delete[] rec; rec=NULL; if (lin) delete[] lin; lin=NULL; if (ix ) delete[] ix ; ix =NULL; if (on ) delete[] on ; on =NULL; } void _alloc(int _N) // allocate space for N rectangles { if (_N==N) return; _free(); if (_N<=0) return; rec=new _rec[_N]; if (rec==NULL) { _free(); return; } lin=new _lin[_N]; if (lin==NULL) { _free(); return; } ix =new int[_N]; if (ix ==NULL) { _free(); return; } on =new int[_N]; if (on ==NULL) { _free(); return; } N=_N; } // allocate and genere random _N rects with size [<xs0,xs1>,<ys0,ys1>] void genere_random(int _N,double xs0,double xs1,double ys0,double ys1) { int i; _rec r; _alloc(_N); for (i=0;i<N;i++) { r.x0=0.0; r.xs=xs0+Random(xs1-xs0); r.y0=0.0; r.ys=ys0+Random(ys1-ys0); rec[i]=r; } } // binpack main function [x0,y0] start position, xs page width, w - spae between rects, acc acuracy for the same ysize packing together void binpack(double x0,double y0,double xs,double w,double acc) { int i,j,k; double x,y,x1,y1,y2,xx,yy; _rec *r0,*r1; _lin l; // indexed insert sort by ys descending for (i=0;i<N;i++) on[i]=1; // none rec used yet for (i=0;i<N;i++) { for (r0=NULL,k=-1,j=0;j<N;j++) if (on[j]) { r1=&rec[j]; if ((!r0)||(r0->ys<r1->ys)) { k=j; r0=r1; } } ix[i]=k; on[k]=0; } for (i=0;i<N;i++) on[i]=1; // none rec used yet // fill line blocks for (n=0,i=0;i<N;) { // find all the same ys recs <l.i0,l.i1), l.xs=width r0=&rec[ix[i]]; l.xs=r0->xs; l.i0=i; for (l.i1=i+1;l.i1<N;l.i1++) { r1=&rec[ix[l.i1]]; if (fabs(r0->ys-r1->ys)>acc) break; l.xs+=r1->xs+w; } // buble sort them by xs descending for (j=1;j;) for (j=0,k=l.i0+1;k<l.i1;k++) if (rec[ix[k-1]].xs<rec[ix[k]].xs) { j=ix[k-1]; ix[k-1]=ix[k]; ix[k]=j; j=1; } // add line block to list lin[n]=l; n++; i=l.i1; } // first use and wrap recs with the same height which fills whole line (xs) x1=x0+xs; y1=_binpack_no_y_stop; for (x=x0,y=y0,i=0;i<n;) _binpack(i,x,y,x1,y1,w); // try to compute optimal height = y1 for line division fill (minimal nonzero so it can be filled completly) int divN=256; // max divider must be power of 2 !!! for (j=2;j<=divN;j<<=1) { y1=_binpack_ys(i,divide(xs,j)-w,w); if (j==2) yy=y1; if ((y1>=1e-6)&&(yy>y1)) yy=y1; } y1=y+(0.75*yy); // use 75% just to be sure ... // try to fill line division xx=x0; yy=y; y2=y; for (j=2;j<=divN;j<<=1) { x1=x0+divide(xs,j)-w; for (x=x0,y=yy,i=0;i<n;) _binpack(i,x,y,x1,y1,w); x0=x1+w; if (y2<y) y2=y; } x0=xx; x1=x0+xs; y=y2; // wrap the unused rest for (x=x0,yy=0,i=0;i<N;i++) if (on[i]) { r0=&rec[ix[i]]; if (x+r0->xs>x1) { x=x0; y+=yy+w; yy=0.0; } if (yy<r0->ys) yy=r0->ys; r0->x0=x; x+=r0->xs+w; r0->y0=y; on[i]=0; } } // binpack sub-function return aprox _binpack height of xs wrap for yet unused rectangles double _binpack_ys(int i,double xs,double w) { int j,k; _rec *r; _lin *l; double xx,ys=0.0; if (xs<=0.0) return ys; for (i=0;i<n;i++) { l=&lin[i]; xx=l->xs; // if line block not large enough while (xx>=xs) { xx-=xs; ys+=rec[ix[l->i0]].ys; } } return ys; } // binpack sub-function process single line <x,x1> update i,x,y void _binpack(int &i,double x,double &y,double x1,double y1,double w) { int j,k,e; _rec *r; _lin *l; double yy; for (;i<n;i++) { l=&lin[i]; // if line block not large enough if (l->xs<x1-x) continue; // if y stop ... if (y<_binpack_no_y_stop) { for (k=l->i0;k<l->i1;k++) if (on[k]) { if (y+rec[ix[k]].ys>y1) k=-1; break; } if (k<0) continue; } // wrap it to xs (whole line only) for (e=0,yy=0,k=l->i0;k<l->i1;k++) if (on[k]) { r=&rec[ix[k]]; if (x+r->xs>x1) // line done { //try to fit in smaller pieces at the end of line for (j=k+1;j<l->i1;j++) if (on[j]) { r=&rec[ix[j]]; if (x+r->xs<=x1) { // update used rec if (yy<r->ys) yy=r->ys; r->x0=x; x+=r->xs+w; r->y0=y; on[j]=0; l->xs-=r->xs+w; e=1; } } break; } // update used rec if (yy<r->ys) yy=r->ys; r->x0=x; x+=r->xs+w; r->y0=y; on[k]=0; l->xs-=r->xs+w; e=1; } if (e) // if any rectangle used { l->xs+=w; // add one space (for first rect) y+=yy+w; // update y to next line break; } } } }; //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- 

using:

 binpack_rec bp_rec; bp_rec.genere_random(N,x0,x1,y0,y1); // genere N random rectangles with sizes (x0..x1),(y0..y1) bp_rec.binpack(x0,y0,xs,w,acc); // compute positions for rectangles where: x0,y0-page start, xs-page size, w-space between rectangles, acc-acuracy for same Y-size bp_rec.rec[0..(bp_rec.N-1)] ... rectangle access (members: x0,y0 is position and xs,ys is size) 

OK, now the binpack algorithm explains:

• prepare data

  • sort rectangles in descending order of size Y (sort index to array ix[] )
  • find all rectangles with the same size Y (+/- acc)
  • sort them in descending order of size X (sort the index to the ix[] array)
  • and remember their start / end index in ix[] ... to lin[].i0,lin[].i1
  • also computes the cumulative width of these rectangles in lin[].xs

• use whole lines (red part of the image)

  Search for all lin[] with greater width than line size. If it is found, fill it with a line and mark the used rectangles as used (also delete the used width) and go to the next line

• try to fill the line break (not the whole page) (green part of the image)

  calculate the minimum non-zero line division height and use it as a limit to fill the height and split the stack next to each other so that they fill the entire line. I am using div line/2 + line/4 + line/8 + line/16 ... = ~ line

• snap all unused rectangles to page size (blue part of the image)

[Note]

This approach is far from optimal, and the code is not optimized, but still quite effective. For 450 boxes with linear randomness in size (0.5 .. 10.0) average ~2.8ms time is ~2.8ms , which I think. You can improve this by dividing and winning, not my linear division. Fill in all the rows, and then use the rest to recursively fill the areas.

Hope this helps ... if there is something obscure, comment on me ...