包装矩形以实现紧凑表示
我正在寻找解决以下问题的指针:我有一组矩形,其高度已知,x 位置也已知,我想以更紧凑的形式打包它们。 通过一点绘图(其中所有矩形的宽度相同,但宽度在现实生活中可能会有所不同),我想要,而不是。
-r1-
-r2--
-r3--
-r4-
-r5--
就像是。
-r1- -r3--
-r2-- -r4-
-r5--
所有提示将不胜感激。 我不一定在寻找“最佳”解决方案。
I am looking for pointers to the solution of the following problem: I have a set of rectangles, whose height is known and x-positions also and I want to pack them in the more compact form. With a little drawing (where all rectangles are of the same width, but the width may vary in real life), i would like, instead of.
-r1-
-r2--
-r3--
-r4-
-r5--
something like.
-r1- -r3--
-r2-- -r4-
-r5--
All hints will be appreciated. I am not necessarily looking for "the" best solution.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(6)
您的问题是一个更简单的变体,但您可能会在阅读有关为“装箱”问题开发的启发式方法时获得一些提示。 关于这一点已经有很多文章,但是此页面是一个很好的开始。
Your problem is a simpler variant, but you might get some tips reading about heuristics developed for the "binpacking" problem. There has been a lot written about this, but this page is a good start.
Topcoder 举办了一场竞赛来解决此问题的 3D 版本。 获胜者在此处讨论了他的方法,它可能对您来说是一本有趣的读物。
Topcoder had a competition to solve the 3D version of this problem. The winner discussed his approach here, it might be an interesting read for you.
这些矩形的高度都相同吗? 如果是,并且问题只是将每个矩形放在哪一行,那么问题就归结为对所有矩形对 (X,Y) 的一系列约束,其形式为“矩形 X 不能与以下形式位于同一行”当矩形 X 在 x 方向与矩形 Y 重叠时,
“贪婪”算法会从左到右对矩形进行排序,然后将每个矩形依次分配给它适合的编号最低的行。 由于矩形是从左到右处理的,因此只需担心当前矩形的左边缘是否会与任何其他矩形重叠,这在一定程度上简化了重叠检测算法。
我无法证明这给出了最佳解决方案,但另一方面也无法立即想到任何反例。 任何人?
Are the rectangles all of the same height? If they are, and the problem is just which row to put each rectangle in, then the problem boils down to a series of constraints over all pairs of rectangles (X,Y) of the form "rectangle X cannot be in the same row as rectangle Y" when rectangle X overlaps in the x-direction with rectangle Y.
A 'greedy' algorithm for this sorts the rectangles from left to right, then assigns each rectangle in turn to the lowest-numbered row in which it fits. Because the rectangles are being processed from left to right, one only needs to worry about whether the left hand edge of the current rectangle will overlap any other rectangles, which simplifies the overlap detection algorithm somewhat.
I can't prove that this is gives the optimal solution, but on the other hand can't think of any counterexamples offhand either. Anyone?
像这样的东西吗?
编写一个方法来检查 x 轴的特定间隔上存在哪些矩形
在矩形集合上循环
Something like this?
write a method that checks which rectangles are present on a certain interval of the x-axis
loop over the collection of rectangles
将类似俄罗斯方块的游戏放入您的网站中。 根据您的参数生成掉落的块和游戏区域的大小。 根据设计的紧凑性(更少的可用空间=更多的积分)向玩家奖励积分。 让您的网站访问者为您执行这项工作。
Put a tetris-like game into you website. Generate the blocks that fall and the size of the play area based on your paramters. Award points to players based on the compactness (less free space = more points) of their design. Get your website visitors to perform the work for you.
我以前曾解决过这样的问题。 最直观的图片可能是大矩形在底部,较小的矩形在顶部,有点像将它们全部放在一个容器中并摇动它,使重的矩形落到底部。 因此,为了实现这一目标,首先按面积(或宽度)递减的顺序对数组进行排序——我们将首先处理大的项目并构建图片。
现在的问题是将 y 坐标分配给一组给定 x 坐标的矩形,如果我理解正确的话。
迭代矩形数组。 对于每个矩形,将矩形的 y 坐标初始化为 0。然后通过增加该矩形的 y 坐标进行循环,直到它不与任何先前放置的矩形相交(您需要跟踪先前放置的矩形)。 提交您刚刚找到的 y 坐标,并继续处理下一个矩形。
I had worked on a problem like this before. The most intuitive picture is probably one where the large rectangles are on the bottom, and the smaller ones are on top, kinda like putting them all in a container and shaking it so the heavy ones fall to the bottom. So to accomplish this, first sort your array in order of decreasing area (or width) -- we will process the large items first and build the picture ground up.
Now the problem is to assign y-coordinates to a set of rectangles whose x-coordinates are given, if I understand you correctly.
Iterate over your array of rectangles. For each rectangle, initialize the rectangle's y-coordinate to 0. Then loop by increasing this rectangle's y-coordinate until it does not intersect with any of the previously placed rectangles (you need to keep track of which rectangles have been previously placed). Commit to the y-coordinate you just found, and continue on to process the next rectangle.