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 回答