我正在寻找解决以下问题的指针:我有一组矩形,它们的高度和 x 位置也是已知的,我想将它们打包成更紧凑的形式。通过一点绘图(所有矩形的宽度相同,但在现实生活中宽度可能会有所不同),我想要,而不是。
-r1-
-r2--
-r3--
-r4-
-r5--
就像是。
-r1- -r3--
-r2-- -r4-
-r5--
所有提示将不胜感激。我不一定要寻找“最佳”解决方案。
我正在寻找解决以下问题的指针:我有一组矩形,它们的高度和 x 位置也是已知的,我想将它们打包成更紧凑的形式。通过一点绘图(所有矩形的宽度相同,但在现实生活中宽度可能会有所不同),我想要,而不是。
-r1-
-r2--
-r3--
-r4-
-r5--
就像是。
-r1- -r3--
-r2-- -r4-
-r5--
所有提示将不胜感激。我不一定要寻找“最佳”解决方案。
您的问题是一个更简单的变体,但您可能会获得一些关于为“装箱”问题开发的启发式方法的提示。已经有很多关于这个的文章,但是这个页面是一个好的开始。
矩形的高度都一样吗?如果它们是,问题只是将每个矩形放在哪一行,那么问题归结为对所有矩形对 (X,Y) 的一系列约束,形式为“矩形 X 不能与当矩形 X 在 x 方向上与矩形 Y 重叠时,矩形 Y"。
用于此的“贪婪”算法从左到右对矩形进行排序,然后将每个矩形依次分配给它适合的编号最小的行。因为矩形是从左到右处理的,所以只需要担心当前矩形的左手边是否会与其他矩形重叠,这在一定程度上简化了重叠检测算法。
我无法证明这是给出了最佳解决方案,但另一方面也想不出任何反例。任何人?
像这样的东西?
编写一个方法来检查在 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);
}
我以前曾研究过这样的问题。最直观的图片可能是大矩形在底部,小矩形在顶部,有点像将它们全部放入容器中并摇晃它,使重的矩形落到底部。所以要做到这一点,首先按面积(或宽度)递减的顺序对数组进行排序——我们将首先处理大项目并构建图片。
现在的问题是将 y 坐标分配给一组给出了 x 坐标的矩形,如果我理解正确的话。
遍历您的矩形数组。对于每个矩形,将矩形的 y 坐标初始化为 0。然后通过增加该矩形的 y 坐标进行循环,直到它不与任何先前放置的矩形相交(您需要跟踪先前放置的矩形)。提交您刚刚找到的 y 坐标,然后继续处理下一个矩形。
将类似俄罗斯方块的游戏放入您的网站。根据您的参数生成掉落的块和游戏区域的大小。根据设计的紧凑性(更少的可用空间 = 更多积分)向玩家奖励积分。让您的网站访问者为您执行工作。