Space 利用算法或网格创建算法

Question

嘿，我们正面临一个 space 使用问题，或者我不清楚我应该给这个问题起什么名字。

基本上是网格问题。

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

问题陈述有点像下面。

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

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

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

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

程序应该给出以下输出

容器的位置
容器中的部分物品。
和排列模式。

Answer 1

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

基于我的评论
利用普通容器大小 480px

算法：

旋转所有容器（箱）以获得 480 高度
旋转降序后按宽度对 bin 进行排序
需要 ceil(1080/480)=3 行 480px bins
使用最宽的 bins 填充所有线条，但不要超过 1920px
- 它们已排序，所以使用第一个
- 所有用过的标记为已用
- 只使用未使用的垃圾箱
将其余的垃圾箱排列成行（转到最短的行）
- 所以拿走未使用的垃圾箱
- 确定哪条线最短
- 如果最短的线已经是 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 行需要 600 像素的高度，所以如果您有那个尺寸或更大的设备，您可以使用它们将最后 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-th 项 ... 索引从零开始
所以改写成你曾经使用过的东西...
List< List<int> > y; 是二维数组 y[][] ...
最后从未使用的容器中形成最后一行...
这既不稳健也不安全，但它大部分都能用（它需要一些调整，但我太懒了）
解决方案还取决于输入集顺序，因此如果稍微打乱一下，您可以为同一输入集找到更多解决方案...（如果某些常见尺寸具有相同的计数）

Space 利用算法或网格创建算法

Space utilization algorithm or Mesh creation algorithm

algorithm

geometry

bin-packing

computational-geometry