algorithm - 空间利用算法或网格创建算法

Question

嘿，我们正面临空间利用问题，或者我不清楚我应该给问题起什么名字。

基本上这是一个网格问题。

我已尝试使用图像来解释我的问题。

问题陈述有点像下面。

1. 带对角线的盒子是必须按最佳比例分配的元素，例如它应该适合所有可用容器。
2. 容器以不同颜色显示。
3. 现在所有的容器都是矩形。
4. 所有容器都必须以纵向模式或横向模式放置。

容器和项目都可以测量宽度和高度，对于程序来说它们基本上是像素。

根据其他成员的评论，Spektre和 Lasse V. Karlsen这是相同的澄清

1. 这是一个二维排列
2. 是的，我们可以重新排列容器以实现最佳模式。
3. 项目的任何部分都不应为空白。项目必须是任何容器的一部分。
4. 项目可以与容器重叠，高度和宽度可以因容器而异。 Item 的高度宽度也可以变化，但形状始终保持矩形。
5. Item 的位置最好固定在左上角。
6. 是的，它有点像装箱算法，但该算法的唯一问题是，在装箱中，元素更多，容器是一个，在我们的例子中，元素是一个，容器更多。所以基本上这是一个分配问题。
7. 想法实际上是我们有容器的大小并且需要放置容器以便我们可以创建该矩形的问题。

程序应该给出如下输出

1. 容器的位置
2. 容器中的部分元素。
3. 和排列模式。

Answer 1

这里是一些简单的非最佳但简单的起点

• 基于我的评论
• 利用常见的容器大小 480px

算法:

1. 旋转所有容器(箱)以获得 480 度的高度
2. 旋转降序后按宽度对 bin 进行排序
3. 需要 ceil(1080/480)=3 行 480px bin

4. 使用最宽的 bins 来填充所有的线，但不要超过 1920px

   • 它们是排序的，所以使用第一个
   • 所有用过的标记为已用
   • 只使用未使用的垃圾箱

5. 将其余的 bin 排列成行(转到最短的行)

   • 所以拿走未使用的垃圾箱
   • 确定哪条线最短
   • 如果最短的线已经是 1920 像素宽或更宽则停止
   • 如果没有将垃圾桶移到该行并将其标记为已使用

C++ 源代码(丑陋的静态分配但简单且未使用 lib):

//---------------------------------------------------------------------------
struct _rec { int x,y,xs,ys,_used; };
_rec bin[128],item; int bins=0;
//---------------------------------------------------------------------------
void bin_generate(int n)    // generate problem
    {
    int i;
    Randomize();
    item.x=0;
    item.y=0;
    item.xs=1920;
    item.ys=1080;
    for (bins=0;bins<n;bins++)
        {
        bin[bins].x=0;
        bin[bins].y=0;
        i=Random(2);
             if (i==0) { bin[bins].xs=320; bin[bins].ys=480; }
        else if (i==1) { bin[bins].xs=480; bin[bins].ys=800; }
        else i=i;
//      if (i==2) { bin[bins].xs=1920; bin[bins].ys=1080; }
        }
    }
//---------------------------------------------------------------------------
void bin_solve()            // try to solve problem
    {
    int i,e,n,x,y,x0[128],y0[128],common=480;
    _rec *r,*s,t;

    // rotate bins to ys=480
    for (r=bin,i=0;i<bins;i++,r++) if (r->xs==common) { x=r->xs; r->xs=r->ys; r->ys=x; }
    // sort bins by xs desc
    for (e=1;e;) for (e=0,r=bin,s=r+1,i=1;i<bins;i++,r++,s++) if (r->xs<s->xs) { t=*r; *r=*s; *s=t; e=1; }
    // prepare lines needed ... n is num of lines, _rest is one common side height line is needed to add
    n=item.ys/common; if (item.ys%common) n++; item.x=0; item.y=0;
    for (i=0;i<n;i++) { x0[i]=0; y0[i]=common*i; }
    for (r=bin,i=0;i<bins;i++,r++) r->_used=0;
    // arrange wide bins to lines
    for (e=0;e<n;e++)
     for (r=bin,i=0;i<bins;i++,r++)
      if (!r->_used)
       if (x0[e]+r->xs<=item.xs)
        {
        r->x=x0[e];
        r->y=y0[e];
        r->_used=1;
        x0[e]+=r->xs;
        if (x0[e]>=item.xs) break;
        }
    // arrange rest bins to lines (goes to the shortest line)
     for (r=bin,i=0;i<bins;i++,r++)
      if (!r->_used)
        {
        // find shortest line
        for (e=0,x=0;x<n;x++) if (x0[e]>x0[x]) e=x;
        // stop if shortest line is already wide enough
        if (x0[e]>=item.xs) break;
        // fit the bin in it
        r->x=x0[e];
        r->y=y0[e];
        r->_used=1;
        x0[e]+=r->xs;
        }
    // arrange the unused rest below
    for (x=0,y=n*common+40,r=bin,i=0;i<bins;i++,r++) if (!r->_used) { r->x=x; r->y=y; x+=r->xs; }
    }
//---------------------------------------------------------------------------

用法:

• bin_generate(7);//生成 n 个随机设备到 bin[bins]矩形数组
• bin_solve();//尝试解决问题...只需重新排列 bin[bins]值(value)观
• >
• 这不是最佳选择，但进行一些调整就足够了
• 例如，最后 2 行需要 600 像素的高度，因此如果您的设备具有该尺寸或更大的尺寸，您可以使用它们将最后 2 行填充为 1 行 ...
• 如果不是，那么一些图或树方法可能会更好(由于容器数量少)

[Edit1] 通用尺寸

当你没有保证固定的公共(public)容器大小时，你必须计算它......

//---------------------------------------------------------------------------
struct _rec { int x,y,xs,ys,_used;      _rec(){}; _rec(_rec& a){ *this=a; }; ~_rec(){}; _rec* operator = (const _rec *a) { *this=*a; return this; }; /*_rec* operator = (const _rec &a) { ...copy... return this; };*/ };
List<_rec> bin,bintype;
_rec item;
//---------------------------------------------------------------------------
void bin_generate(int n)    // generate problem
    {
    int i;
    _rec r;
    Randomize();
    // target resolution
    item.x=0; item.xs=1920;
    item.y=0; item.ys=1080;
    // all used device sizes in portrait start orientation
    bintype.num=0; r.x=0; r.y=0; r._used=0;
    r.xs= 320; r.ys= 480; bintype.add(r);
    r.xs= 480; r.ys= 800; bintype.add(r);
    r.xs= 540; r.ys= 960; bintype.add(r);
//  r.xs=1080; r.ys=1920; bintype.add(r);
    // create test case
    bin.num=0; for (i=0;i<n;i++) bin.add(bintype[Random(bintype.num)]);
    }
//---------------------------------------------------------------------------
void bin_solve()            // try to solve problem
    {
    int i,j,k,e,x,y;
    _rec *r,s;
    List<int> hsiz,hcnt;    // histogram of sizes
    List< List<int> > lin;  // line of bins with common size
    // compute histogram of sizes
    hsiz.num=0; hcnt.num=0;
    for (r=bin.dat,i=0;i<bin.num;i++,r++)
        {
        x=r->xs; for (j=0;j<hsiz.num;j++) if (x==hsiz[j]) { hcnt[j]++; j=-1; break; } if (j>=0) { hsiz.add(x); hcnt.add(1); }
        x=r->ys; for (j=0;j<hsiz.num;j++) if (x==hsiz[j]) { hcnt[j]++; j=-1; break; } if (j>=0) { hsiz.add(x); hcnt.add(1); }
        }
    // sort histogram by cnt desc (most occurent sizes are first)
    for (e=1;e;) for (e=0,j=0,i=1;i<hsiz.num;i++,j++) if (hcnt[j]<hcnt[i])
        {
        x=hsiz[i]; hsiz[i]=hsiz[j]; hsiz[j]=x;
        x=hcnt[i]; hcnt[i]=hcnt[j]; hcnt[j]=x; e=1;
        }
    // create lin[][]; with ys as common size (separate/rotate bins with common sizes from histogram)
    lin.num=0;
    for (r=bin.dat,i=0;i<bin.num;i++,r++) r->_used=0;
    for (i=0;i<hsiz.num;i++)
        {
        lin.add(); lin[i].num=0; x=hsiz[i];
        for (r=bin.dat,j=0;j<bin.num;j++,r++)
            {
            if ((!r->_used)&&(x==r->xs)) { lin[i].add(j); r->_used=1; y=r->xs; r->xs=r->ys; r->ys=y; }
            if ((!r->_used)&&(x==r->ys)) { lin[i].add(j); r->_used=1; }
            }
        }
    for (i=0;i<lin.num;i++) if (!lin[i].num) { lin.del(i); i--; }
    // sort lin[][] by xs desc (widest bins are first)
    for (i=0;i<lin.num;i++)
     for (e=1;e;) for (e=0,k=0,j=1;j<lin[i].num;j++,k++)
      if (bin[lin[i][k]].xs<bin[lin[i][j]].xs)
        { s=bin[lin[i][j]]; bin[lin[i][j]]=bin[lin[i][k]]; bin[lin[i][k]]=s; e=1; }
    // arrange lines to visually check previous code (debug) ... and also compute the total line length (width)
    for (y=item.ys+600,i=0;i<lin.num;i++,y+=r->ys) for (x=0,j=0;j<lin[i].num;j++) { r=&bin[lin[i][j]]; r->x=x; r->y=y; x+=r->xs; }
    for (i=0;i<lin.num;i++)
        {
        j=lin[i][lin[i].num-1];                         // last bin in line
        hsiz[i]=bin[j].x+bin[j].xs;                     // total width
        hcnt[i]=bin[j].ys;                              // line height
        }
    // now compute solution
    for (r=bin.dat,i=0;i<bin.num;i++,r++) r->_used=0;   // reset usage first
    for (y=0,k=1,i=0;i<lin.num;i++)                     // process lines with common size
     while(hsiz[i]>=item.xs)                            // stop if line shorter then needed
        {
        x=0;
        // arrange wide bins to line
        for (j=0;j<lin[i].num;j++)
            {
            r=&bin[lin[i][j]];
            if ((!r->_used)&&(x+r->xs<=item.xs))
                {
                r->x=x; hsiz[i]-=x; x+=r->xs;
                r->y=y; r->_used=k;
                if (x>=item.xs) break;
                }
            }
        // arrange short bins to finish line
        if (x<item.xs)
         for (j=lin[i].num-1;j>=0;j--)
            {
            r=&bin[lin[i][j]];
            if (!r->_used)
                {
                r->x=x; hsiz[i]-=x; x+=r->xs;
                r->y=y; r->_used=k;
                if (x>=item.xs) break;
                }
            }
        // remove unfinished line
        if (x<item.xs)
            {
            for (j=0;j<lin[i].num;j++)
                {
                r=&bin[lin[i][j]];
                if (r->_used==k)
                    {
                    r->x=0; r->y=0;
                    r->_used=0;
                    hsiz[i]+=r->xs;
                    }
                }
            break;
            }
        // next line
        y+=hcnt[i];
        if (y>=item.ys) break;  // solution found already?
        }
    // rotate unused rest to have ys>=as needed but as wide as can be to form last line
    e=item.ys-y; x=0;
    if (e>0) for (r=bin.dat,i=0;i<bin.num;i++,r++)
     if (!r->_used)
        {
        if ((r->xs<e)&&(r->ys<e)) continue; // skip too small bins
        if (r->xs<r->ys) { j=r->xs; r->xs=r->ys; r->ys=j; }
        if (r->ys<    e) { j=r->xs; r->xs=r->ys; r->ys=j; }
        r->x=x; x+=r->xs;
        r->y=y; r->_used=1;
        }
    }
//---------------------------------------------------------------------------

• 它与以前几乎相同，但在计算容器大小直方图之前
• 选择最常出现的并组成兼容箱(容器)组
• 然后应用算法...
• 我添加了动态数组模板的用法List<>因为在静态分配上我会在写这个之前发疯......
• List<int> x;与 int x[] 相同；
• x.num是 x[] 中的项目数
• x.add()将新项目添加到 x[] 的末尾
• x.add(q)将新项目 = q 添加到 x[] 的末尾
• x.del(i)从 x[] 中删除第 i 个项目 ... 索引从零开始
• 所以改写成你曾经使用过的...
• List< List<int> > y;是二维数组 y[][] ...
• 最后从未使用的容器中形成最后一行 ...
• 这既不稳健也不安全，但它基本上可以工作(它需要一些调整，但我太懒了)
• 解决方案还取决于输入集顺序，因此如果稍微打乱一下，您可以为同一输入集找到更多解决方案......(如果某些常见尺寸具有相同的计数)