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?

Nappe

This is called a "bin packing problem", and a general solution is NP-Hard. – Dishevel

I think you should group the rectangles by height first. Apply a "bin packing" algorithm to each group separately. – Tamarra

The general problem is hard, for sure. But @BlackBear can you restrict the problem any? Or does it have to be an exact solution? If it doesn't, some other tricks might apply to get you relatively compact... – Chest

if number of boxes is not too high you still can use brute force attack. for starters consider the layout as single line wrapped by page width. so the only thing you need to change is the order of boxes in line. For speed up you can ignore permutations of the rectangles of the same size. of course if you have more than 100 recs it would be slow. In that case A. I. Breveleri's comment suggest better solution – Siclari

Like Jacob said, you can't find optimal solution efficiently. To find an approximately good solution, you have two choices. One is to use a greedy algorithm, adding rectangles one by one to the picture, try to increase the enclosing region rectangle by a minimal in each step. Another way is to use back-track search. In that case, you are responsible of designing an effective heuristics. – Shenika

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 ...

Siclari