6

我正在寻找解决以下问题的指针:我有一组矩形,它们的高度和 x 位置也是已知的,我想将它们打包成更紧凑的形式。通过一点绘图(所有矩形的宽度相同,但在现实生活中宽度可能会有所不同),我想要,而不是。

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

就像是。

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

所有提示将不胜感激。我不一定要寻找“最佳”解决方案。

4

6 回答 6

2

Topcoder有一个比赛来解决这个问题的 3D 版本。获胜者在这里讨论了他的方法,这对你来说可能是一个有趣的读物。

于 2008-09-30T16:50:34.197 回答
2

您的问题是一个更简单的变体,但您可能会获得一些关于为“装箱”问题开发的启发式方法的提示。已经有很多关于这个的文章,但是这个页面是一个好的开始。

于 2008-09-30T14:44:35.547 回答
1

矩形的高度都一样吗?如果它们是,问题只是将每个矩形放在哪一行,那么问题归结为对所有矩形对 (X,Y) 的一系列约束,形式为“矩形 X 不能与当矩形 X 在 x 方向上与矩形 Y 重叠时,矩形 Y"。

用于此的“贪婪”算法从左到右对矩形进行排序,然后将每个矩形依次分配给它适合的编号最小的行。因为矩形是从左到右处理的,所以只需要担心当前矩形的左手边是否会与其他矩形重叠,这在一定程度上简化了重叠检测算法。

我无法证明这是给出了最佳解决方案,但另一方面也想不出任何反例。任何人?

于 2008-09-30T15:05:43.343 回答
1

像这样的东西?

  • 按 x 位置对矩形集合进行排序
  • 编写一个方法来检查在 x 轴的某个间隔上存在哪些矩形

    Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){
    ...
    }
    
  • 遍历矩形集合

    Collection<Rectangle> toDraw;
    Collection<Rectangle> drawn;
    foreach (Rectangle r in toDraw){
    Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn);
    int y = 0;
    foreach(Rectangle overlapRect in overlapping){
    y += overlapRect.height;
    }
    drawRectangle(y, Rectangle);
    drawn.add(r);
    }
    
于 2008-09-30T14:41:04.713 回答
0

我以前曾研究过这样的问题。最直观的图片可能是大矩形在底部,小矩形在顶部,有点像将它们全部放入容器中并摇晃它,使重的矩形落到底部。所以要做到这一点,首先按面积(或宽度)递减的顺序对数组进行排序——我们将首先处理大项目并构建图片。

现在的问题是将 y 坐标分配给一组给出了 x 坐标的矩形,如果我理解正确的话。

遍历您的矩形数组。对于每个矩形,将矩形的 y 坐标初始化为 0。然后通过增加该矩形的 y 坐标进行循环,直到它不与任何先前放置的矩形相交(您需要跟踪先前放置的矩形)。提交您刚刚找到的 y 坐标,然后继续处理下一个矩形。

于 2010-06-22T02:08:36.780 回答
0

将类似俄罗斯方块的游戏放入您的网站。根据您的参数生成掉落的块和游戏区域的大小。根据设计的紧凑性(更少的可用空间 = 更多积分)向玩家奖励积分。让您的网站访问者为您执行工作。

于 2008-09-30T14:44:37.807 回答