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

Question

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

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

我试图用一张图片来解释我的问题。

在此处输入图像描述

问题陈述有点像下面。

带有对角线的盒子是一个必须以最佳比例分布的物品，例如它应该适合所有可用的容器。
容器以不同的颜色显示。
现在所有容器都将呈矩形。
所有容器必须以纵向模式或横向模式放置。

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

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

这是一个二维排列
是的，我们可以重新排列容器以实现最佳模式。
项目的任何部分都不应在空白处。项目必须是任何容器的一部分。
项目可以与容器重叠，并且高度和宽度可以因容器而异。并且项目的高度宽度也可以变化，但形状将始终保持矩形。
如果项目的位置固定在左上角，则它是更可取的。
是的，它有点像 bin 打包算法，但该算法的唯一问题是，在 Bin 中打包项目更多，容器是一个，在我们的例子中，项目是一个，容器更多。所以基本上它是一个分布问题。
想法实际上是我们有容器的大小并且需要放置容器以便我们可以创建那个矩形的问题。

该程序应给出以下输出

容器的位置
容器内部的部分物品。
和排列图案。

score 1 · Accepted Answer

这里有一些简单但不理想但很容易作为起点的东西

根据我的评论
利用通用容器大小 480px

算法：

旋转所有容器（箱）以获得 480 高度
旋转降序后按宽度对箱进行排序
需要 ceil(1080/480)=3 行 480px bins
使用最宽的箱子来填充所有线条，但不要超过 1920 像素
- 它们是排序的，所以使用第一个
- 所有使用过的都标记为已使用
- 仅使用未使用的垃圾箱
将剩余的垃圾箱排列成行（到最短的行）
- 所以拿走未使用的垃圾箱
- 确定哪条线最短
- 如果最短的线已经是 1920px 宽或更大，则停止
- 如果不将垃圾箱移动到该行并将其标记为已使用

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]值
这不是最佳选择，但进行一些调整就足够了
例如，最后 2 行需要 600px 的高度，因此如果您有该尺寸或更大的设备，您可以使用它们将最后 2 行填充为 1 行...
如果不是，那么可能是一些图表或树方法会更好（由于容器数量少）

[Edit1] 通用尺寸

当您没有保证固定的通用容器大小时，您必须改为计算它......

//---------------------------------------------------------------------------
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[][]...
最后从未使用的垃圾箱中形成最后一行......
这既不健壮也不安全，但它主要是有效的（它需要一些调整，但我太懒了）
解决方案还取决于输入集的顺序，因此如果您稍微调整一下，您可以为相同的输入集找到更多解决方案......（如果某些常见尺寸具有相同的计数）

示例2

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

1 回答 1

Related

Reference