Algorithm for rectangles position

Question

I have rectangles and a GridLayout, the width and the height of these rectangles are the same. so the layout put the rectangle's position like the next picture.

This is the problem: If the width and the height of my rectangles are of different size, what is the algorithm for the layout to put the rectangle's position in a compact way?

Answer 1

Finally got some time for this question so here is my bin pack 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;
                }
            }
        }
    };
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

usage:

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 some binpack algorithm explaining:

1. prepare data

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

2. use whole lines (Red part of image)

   Search all lin[] with bigger width than wrapped line size. If found then fill the line with it and mark used rectangles as used (also remove used width) and move to next line

3. try to fill line division (not whole page) (Green part of image)

   compute minimal nonzero height of line division and use it as height fill limit and stack divisions next to each other so they fill the whole line. I use division line/2 + line/4 + line/8 + line/16 ... = ~ line

4. wrap still unused rectangles to page size (Blue part of image)

[Notes]

This approach is far from optimal and code is not optimized but still efficient enough. For 450 boxes with linear randomness in size (0.5 .. 10.0) the average runtime is ~2.8ms which is fine I think. You can improve this by divide and conquer instead of my line division. Fill whole lines and then use the rest to fill area divisions recursively.

Hope it helps ... if there is anything unclear comment me ...