什么是算法收拾正方形和长方形？ [英] What's the algorithm to pack squares and rectangles?
问题描述
类似于Windows 8的石板界面，如何很好地填补正方形和长方形的屏幕，不留漏洞？
假设：
- 在一个长方形基本上是两个相连的广场
- 矩形可进行水平或垂直
- 屏幕宽度为方 的宽度的3倍
- 的画面从顶部填充底部
- ，使得屏幕的最低部分可能不完全对齐
- 矩形和正方形的顺序进来随机的（但可以被重新排序中之前放置到屏幕上一个小的高速缓存，所述缓存的大小是有限的，说12）
例如：
+ - + - + - +
| || || |
+ - + - + | |
+ - + - + | |
| || || |
+ - + | | + - +
+ - + | | + - +
| || || |
+ - + - + - +
+ -------- + - +
| || |
+ -------- + | |
+ - + - + | |
| || || |
| | + --- + --- +
| |
| |
+ - +
我相信这是包装的一个子集问题的。
一个算法来解决这个问题是使用线性规划。
定义约束确保矩形不重叠，进而解决了点。然后加权算法以有利于屏幕的上/左上角，并且最窄宽度/高度。另外加权算法有利于间隔出较大的矩形。
既然你有一个目标的屏幕分辨率，可以添加约束的宽度和高度，并放宽高度限制，如果该算法无法找到解决的办法。
这是pretty的重量级的，虽然。你也许可以用一个更强大的算法来简化问题，仍然可以得到好的结果。例如：
以项目为了显示preference
开始在左上角
对于每个项目：
尝试堆栈水平，去右（偏袒左）
如果它不适合在屏幕上：
尝试叠下一行上
当试图堆叠的下一行上：
如果存在于当前行中的任何空白：
看看你是否有一个不太正规的矩形，将适合的差距
其他
有利于把它放在更远的左
编辑：的
我发布这个答案后，看了你的存在的制约因素。
这矩形具有相同的尺寸，这一事实可能会允许你优化的问题 - 例如，使用比特列的索引，而不是一些基于树的空间容器。
这将可能让你快捷和特殊情况下的某些决定 - 如：把所有的1x1方格，再配合双高的，取代了广场，然后配合双宽，取代正方形和长方形。或者相反，因为装修的小长方形总是比配合较大的更容易。只要确保你的空间了大的矩形中一个可能的赏心悦目/有些随机的方式，并采取了第1卷数，所以你不要逼滚动不具有发生。
Similar to the Windows 8 Slate interface, how to nicely fill a screen with squares and rectangles without leaving holes?
Assumptions:
- a rectangle is basically two connected squares
- the rectangles can be horizontal or vertical
- the screen width is 3 times of the width of a square
- the screen is filled from top to bottom
- such that the lowest part of the screen may not be aligned fully
- the order of rectangles and squares come in randomly (but can be re-ordered in a small cache before put onto screen, the cache size is limited, say 12)
For example:
+---++---++---+
| || || |
+---++---+| |
+---++---+| |
| || || |
+---+| |+---+
+---+| |+---+
| || || |
+---++---++---+
+--------++---+
| || |
+--------+| |
+---++---+| |
| || || |
| |+---++---+
| |
| |
+---+
I believe this is a subset of Packing Problems.
One algorithm to solve this is to use Linear Programming.
Define constraints that ensure rectangles don't overlap, then solve for that. Then weight the algorithm to favor the upper/left corner of the screen, and the narrowest width/height. Also weight the algorithm to favor spacing out larger rectangles.
Since you have a target screen resolution, you can add constraints for width and height, and relax the height constraint if the algorithm fails to find a solution.
This is pretty heavy-weight, though. You could probably use a much less robust algorithm to simplify the problem and still get okay results. E.g.:
Take items in order of display preference
Start at the top-left
For each item:
Try to stack horizontally, going right ("favoring" left)
if it won't fit on the screen:
try to stack on the next row
when trying to stack on the next row:
if any "gaps" exist in the current row:
see if you have a less "regular" rectangle that will fit in the gap
else
"favor" placing it farther left
Edit:
I read your existing constraints after posting this answer.
The fact that rectangles have the same dimensions probably will allow you to optimize the problem - e.g. using a bit array and indexing rather than some tree-based spatial container.
It will probably let you short-cut and special case certain decisions - e.g. place all 1x1 squares, then fit double-tall, displacing squares, then fit double-wide, displacing squares and rectangles. Or the reverse, since fitting smaller rectangles is always easier than fitting larger ones. Just make sure you space out the large rectangles in a likely eye-pleasing/somewhat random way, and take a volume count first so you don't force scrolling that doesn't have to happen.
这篇关于什么是算法收拾正方形和长方形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
