我有矩形和一个GridLayout的，宽度和这些矩形的高度是相同的。这样的布局将矩形的位置，像下一张图片。

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?

推荐答案

终于得到了一些时间，这个问题，所以这里是我的箱子包code：

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;
                }
            }
        }
    };
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

用法：

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)

现在好了一些binpack算法解释：

OK now some binpack algorithm explaining:

1，prepare数据

1.prepare data

排序矩形用Y-大小降序（索引排序IX []数组） 找到具有相同的Y尺寸（+/- ACC）所有的矩形 用X-大小降序排序它们（指数排序IX []数组） 记得在九他们的开始/结束索引[] ...林[]。I0，林[]。I1 也计算这些矩形的宽累计成霖[]。XS 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，采用整线（影像的红色部分）

2.use whole lines (Red part of image)

搜索所有林[]有更大的宽度比换行尺寸 如果找到则补之行吧。而所用的标记使用的矩形（也取下旧的宽度） 并移动到下一行

3.try填写行都司（而不是整个页面）（图像的绿色部分）

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

在计算行部门的最低非零的高度，并用它作为高度填充限制 和堆栈部门彼此相邻，使他们填满了整个行 在我使用的分割线/ 2 +线/ 4 +线/ 8 +线/ 16 ... =〜行

4.wrap仍未使用矩形到页面大小（图像的蓝色部分）

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

[注：]

在这种方法很不理想和code没有优化 ，但仍然不够有效 450箱线性随机性 在尺寸（0.5 .. 10.0）的平均运行时间为〜2.8ms 这是很好的，我认为 您可以通过鸿沟改善这一点，征服我的分界线，而不是 在填补整行，然后用剩下的填充区域划分递归

希望它可以帮助... 如果有什么不清楚的评论我...

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