算法的矩形位置 [英] Algorithm for rectangles position
问题描述
我有矩形和一个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 ...
这篇关于算法的矩形位置的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!