矩形位置算法

Question

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

这就是问题所在:如果我的矩形的宽度和高度大小不同，布局的算法是什么以紧凑的方式放置矩形的位置？

Answer 1

终于有时间回答这个问题了，这是我的 bin pack 代码:

//---------------------------------------------------------------------------
//--- 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)

OK 现在一些 binpack 算法解释:

1. 准备数据

   • 按 Y 大小降序排列矩形(索引排序到 ix[] 数组)
   • 找到所有具有相同 Y 尺寸 (+/- acc) 的矩形
   • 按 X 大小降序排序(索引排序到 ix[] 数组)
   • 并记住它们在 ix[] 中的开始/结束索引 ... 到 lin[].i0,lin[].i1
   • 还将这些矩形的累积宽度计算到 lin[].xs

2. 使用整行(图片红色部分)

   搜索宽度大于换行大小的所有 lin[]。如果找到则用它填充行并将使用的矩形标记为已使用(也删除使用的宽度)并移至下一行

3. 尝试填充分行(不是整个页面)(图像的绿色部分)

   计算线分割的最小非零高度，并将其用作高度填充限制，并相邻堆叠分割，以便它们填充整条线。我使用除法 line/2 + line/4 + line/8 + line/16 ... = ~ line

4. 将未使用的矩形包裹到页面大小(图像的蓝色部分)

[注释]

这种方法远非最佳，代码未优化但仍然足够高效。对于大小为 (0.5 .. 10.0) 的 450 个线性随机框，平均运行时间为 ~2.8ms，我认为这很好。您可以通过分而治之而不是我的线划分来改进这一点。填充整行，然后使用其余部分递归地填充区域划分。

希望对您有所帮助...如果有任何不清楚的地方评论我...