矩形打包
0/5 (0投票)
将一组子矩形打包到矩形区域中，以最大化覆盖面积并最小化未覆盖面积
引言
本文旨在探讨如何使用一组子矩形来填充一个矩形区域。这些子矩形选自一个预定义的子矩形集合，它们将紧密地填充到更大的矩形容器中。子矩形覆盖的面积（填充面积）应最大化，而未填充区域（空闲区域）应最小化或为零。一个理想的填充矩形意味着在子矩形填充后，其中没有留下任何空闲区域。子矩形可以在填充区域中重复出现。
场景
在某些情况下，一个大的矩形区域需要用更小的矩形来填充。这些较小的矩形将来自一个预定义的子矩形集合。应采用算法使填充尽可能完整。未覆盖（未填充）区域应趋近于零。
-------------------------------------+
| ______________|_____
| +---| a | b | c | d... |<-sub-rectangles
| R | ----------|---------
| --------------v-------------v-----------------
| |----------------- ---------------- |
| || | | | unpacked|
| || a | | c | area |
| || | | | |
| |----------------- ---------------- |
| |--------------------------------------- |
| || d | |
+---->| | |
|--------------------------------------- |
----------------------------------------------
问题
用一组较小的子矩形填充一个较大的矩形需要无限次的尝试。可以尝试一组子矩形，然后测量未填充区域，接着再尝试另一组子矩形并测量不同的未填充区域。矩形的二维面积导致需要更多的尝试才能最终得到一组填充好的子矩形。因此，需要一个本质上确定性、能够概念性地解决问题的算法。
解决方案
本文提出了一种解决方案，即从子矩形集合 [a,b,c,d...] 中选择一个子矩形。所选的子矩形将放置在较大矩形（假设为 'R'）的“左上角”。当子矩形 'a' 放置在 'R' 的左上角时，其余未填充区域被分为两个部分：水平空间中的 'H' 区域和垂直空间中的 'V' 区域。
这种情况如下图所示：
____________________
| a | b | c | d... |<-subrectangles
R --|-----------------
--------------------------------|--------------
|----------------- | |
|| |<-------------+ |
|| a | H |
|| | |
|----------------- |
|..............................................
| |
| V |
| |
-----------------------------------------------
现在，'H' 和 'V' 部分被作为需要填充的独立矩形取出。此时，'H' 和 'V' 就像 'R' 一样是两个更大的矩形，面临相似的情况。
new 'R' new 'R'
-------------------------- -------------------------------------------
| | | |
| H | | V |
| | | |
| | -------------------------------------------
--------------------------
在这两个新的更大的“R”填充矩形中，将尝试从子矩形集合 ['a','b','c'...] 中选择一个子矩形，使其适合放置在新“R”（之前的“H”和“V”）的“左上角”。因此，其余区域再次以元方式划分为“H”和“V”部分。
__________________ ___________________
| a | b | c | d..| | a | b | c | d...|
H as 'R' --|--------------- V as 'R' ------|------------
---------------|-------------- ---------------------|--------------
|----------- | | |------------ | |
|| a |<--+ | || b |<-------+ H |
|| | H | |------------ |
|----------- | ....................................
|............................| | V |
| V | ------------------------------------
------------------------------
这一步骤持续进行，直到“H”或“V”太小，无法被子矩形集合 ['a','b','c','d'...] 中的任何子矩形填充。这些空的“H”或“V”作为空闲或未填充区域返回给父“R”。现在，这个“R”在元系统中成为叶节点“R”。这个叶节点“R”是一个包含一个子矩形（在左上角）和一个未填充空闲区域的矩形。这个叶节点“R”再次尝试用集合 ['b','c','d'..] 中剩下的其他子矩形放置在左上角。新的“H”或“V”将以元方式重复增长，或者它将不带子矩形并带有一个未填充区域返回。最终，节点“R”将返回给其父节点，带有一个子矩形或作为带有左上角子矩形和未填充区域的叶节点。
最后，带有子矩形和面积的叶子“R”被传递给父“R”。在父“R”中，再次选择集合 ['b','c','d'..] 中剩下的新子矩形，然后创建新的“H”和“V”。重复前面的步骤，直到到达顶层矩形“R”。在顶层“R”中，尝试集合 ['b','c','d',..] 中剩下的其他子矩形，直到叶子矩形“R”到达，以便最大化填充面积。选择最小面积的子矩形部分。___________________
returned to | a | b | c | d...|---------
<------- --|---------------- |
parent n|ode +-----------+ <<NO |SUBRECTANGLE|FITS
| | |IN >> |
| Leaf R | +----------+ |
| -----------------|----- --------- | |
| |-------------- | | | | <--+ |
----- || |<-+ | | | |
|| a | H | ------------> | H | |
|| | | \ | | |
|-------------- | \ | | |
|...................... \ --------- v
| v | \ -------------------------
----------------------- +->| V |
-------------------------
设计
这里使用了责任链设计模式。填充矩形有责任从子矩形中获得最大的填充面积，并返回最小的未填充面积。当一个子矩形放置在填充矩形的左上角时，寻找具有最小未填充空间的填充矩形的责任以元方式转移到两个部分，即矩形“H”和“V”。
new 'R'
-------------- -------------- ----------
| | | | | |
| 'R' | -----> | 'H' | -----> | 'H' |
| | ^ | | | |
-------------- . -------------- ----------
| . |
| <........... |
v new 'R' . v
------------- . --------------
| | . | 'V' |
| 'V' | . | |
| | . --------------
-------------- .
.
chain formation
矩形“R”将来自集合 ['a','b','c','d'...] 的子矩形“a”放置在左上角，然后将寻找最佳填充子矩形的责任以链式方式传递给新创建的“H”和“V”部分作为新矩形。“H”和“V”是新的矩形“R”，在放置了子矩形集合 ['a','b','c','d'..] 中的子矩形后，将责任传递给链中的下一个“H”和“V”。它一直链接，直到“H”和“V”足够小，无法放入集合中的任何子矩形。然后，这个叶子矩形/节点“R”将其“左上角”的子矩形以及未使用的区域传递给链中的父节点，父节点反过来再次尝试调用叶子矩形“R”以及子集 ['a','b','c','d'..] 中的下一个子矩形。最终，根节点根据可用的最小填充空闲区域决定采用哪条链。
程序
1 def getrect(x,y,width,height):
2 global rect
3 ixyarealist=None
4 ilist=[i for i in range(len(rect)) if rect[i][0]<=width and rect[i]
[1]<=height]
5 if len(ilist):
6 for i in ilist:
7 tixyarealist=[[[i,x,y]],0]
8 area=getrect(x+rect[i][0],y,width-rect[i][0],rect[i][1])
9 if not area:
10 tixyarealist[1]+=(width-rect[i][0])*rect[i][1]
11 else:
12 tixyarealist[0].extend(area[0])
13 tixyarealist[1]+=area[1]
14 area=getrect(x,y+rect[i][1],width,height-rect[i][1])
15 if not area:
16 tixyarealist[1]+=width*(height-rect[i][1])
17 else:
18 tixyarealist[0].extend(area[0])
19 tixyarealist[1]+=area[1]
20 if not ixyarealist:
21 ixyarealist=tixyarealist
22 elif tixyarealist[1]<ixyarealist[1]:
23 ixyarealist=tixyarealist
24 else:
25 return False
26 return ixyarealist
27 getrect(0,0,width,height)
在程序中，在根矩形 'R' 处，对于“左上角”子矩形 'a'，H 和 V 部分进行递归，并将得到的矩形和未填充的空闲区域总和添加到 `tixyarealist` 中，用于 `rect` 列表中的子矩形 'a'。`ilist` 是在每个递归级别上 `rect` 列表的剪裁版本，其中 `ilist` 中的子矩形具有比该级别上的 'R' 更小的宽度和高度。对于子矩形 'b'，采用相同的过程，并创建新的 H 和 V 部分，其中 H 和 V 再次从“左上角”子矩形 'a' 开始。最后生成矩形 'b' 的 `tixyarealist`。最小填充面积的 `tixyarealist` 最终被命名为 `ixyarealist`，返回这个具有最小未填充区域的新链。
- 第27行 - 调用算法，参数为0,0,width,height，因此根'R'的大小为width'x'height，需要用集合数组`rect`中的子矩形进行填充。
- 第2行 - `rect` 子矩形集合。
- 第4行 - 在每个级别上，`ilist` 都作为新的子矩形集合准备，其中每个子矩形都适合当前的 'R'（新的宽度和高度）。
- 第5行 - 检查 `ilist` 是否不为空，否则在第25行返回 `False`。
- 第6行 - 迭代 `ilist`，每个子矩形逐一放置在“左上角”。
- 第7行 - 初始化 `ixyarealist`，它存储带有 i,x,y 的子矩形列表。i 是 rectlist 中的索引，x,y 表示在较大矩形中的物理位置，而未填充区域是列表中的最后一个元素。
- 第8行 - 递归算法，处理“H”部分（新的“R”），而第14行递归算法，处理“V”部分作为新的“R”。
- 第9行 - 和第15行检查返回值，如果得到 `False`，则声明当前 'R' 为叶子矩形，并向其添加“未填充区域”。当 'H' 或 'V' 返回子矩形列表及其面积时，第12行和第18行就会起作用。
- 第22行,23行 - 确保选择具有最小未填充区域的子矩形列表。
- 第26行 - 返回具有最小未填充区域的子矩形链。
- 第27行 - 最终返回关于顶层矩形的信息，其中包含最能填充它的子矩形列表。
Index in subrectangle subset ['a','b','c''d'...]
/
| x,y of subrectangle from top left corner of bigger rectangle 'R'.
| /
-----|-|---------------------------------------------------------------
| --|-|---- --------- --------- |Non |
| | i,x,y | | i,x,y | | i,x,y | . . . . . |packing |
| --------- --------- --------- |area |
-----------------------------------------------------------------------
ixyarealist
工作原理
将区域划分为 H 和 V，这反过来又生成新的矩形 'R'。这形成了一个二叉树，其中每个节点在将子矩形集合 [a,b,c,d..] 中的所有子矩形逐一放置在左上角时都会调用子节点。
---------------
| root 'R' |
| |
---------------
'H' /\ 'V'
/ \
------------ ------------
| | | |
------------ ------------
. . Leaf 'R'
. . /
/ \ / \ /
'H'/ \'V' H' / \ 'V' |
------- ------ ------ --------<-----+
| | | | | | | |<---------+
------- ------ ------ -------- |
/\ /\ /\ /\ |
---- ---- ---- ---- ---------
| | | | | | | |<--- Too small to
---- ---- ---- ---- be packed by subrectangles
实验输出
来自 Qt6 的 `PySide6` 包用于将矩形绘制为 `PySide6.QtWidgets` 模块中派生的 `QWidget` 派生小部件类。子矩形在填充矩形 `'R'` 内的 `paintEvent` 重载函数中绘制为彩色矩形绘制区域，中心带有尺寸注释，而空的未填充区域则显示为灰色。
预定义了九个子矩形，尺寸分别为：[(160,600),(300,600),(250,250),(200,200),(970,90),(336,280),(300,250),(728,90), (468,60)]
填充矩形 'R'
- 950x160
- 690x200
- 840x550
- 840x560
- 600x450
进一步改进
- 在某些场景中，不允许重复使用集合 ['a','b','c','d'...] 中的子矩形。填充较大矩形 'R' 中的所有子矩形都应该是唯一的。在这种情况下，应将 `rect`（即子矩形列表）作为参数传递。
+-- subrectangle list passed as argument | v1 def getrect(x,y,width,height,rect): 2 global rect 3 ixyarealist=None 4 ilist=[i for i in range(len(rect)) if rect[i][0]<=width and rect[i] [1]<=height] .... 8 area=getrect(x+rect[i][0],y,width-rect[i][0],rect[i][1],ilist) .... 14 area=getrect(x,y+rect[i][1],width,height-rect[i][1],ilist) .... 26 return ixyarealist
第1行有一个新参数 `rect`，它是一个子矩形集合。第4行创建新的子矩形集合。第8行和第14行将新的子矩形列表作为参数传递给 `getrect` 递归调用。
- 填充后的子矩形应均匀放置。填充子矩形之间的间距应均匀。
1 def getrect(x,y,width,height,xrectcount=0,yrectcount=0): .... 7 tixyarealist=[[[i,x,y,xrectcount,yrectcount]],0] .... 8 area=getrect(x+rect[i][0],y,width-rect[i][0],rect[i] [1],xrectcount+1,yrectcount) .... 14 area=getrect(x,y+rect[i][1],width,height-rect[i] [1],xrectcount,yrectcount+1) .... 26 return ixyarealist 27 rectposition=getrect(0,0,width,height) xoffset,yoffset=int((width-max([x[1]+rect[x[0]][0] for x in rectposition[0]]))/(max([x[3] for x in rectposition[0]])+2)),int((height- max([x[2]+rect[x[0]][1] for x in rectposition[0]]))/(max([x[4] for x in rectposition[0]])+2)) rectposition[0]=[x[1]+int((x[3]+1)*xoffset),x[2]+int((x[4]+1)*yoffset) for x in rectposition[0]]
- 如果未填充的空闲区域可以与数量进行权衡，那么在填充的矩形数量较少但尺寸较大的情况下将优先考虑。
1 def getrect(x,y,width,height,factor=0.1): ... 8 area=getrect(x+rect[i][0],y,width-rect[i][0],rect[i][1],factor) ... 14 area=getrect(x,y+rect[i][1],width,height-rect[i][1],factor) ... # elif tixyarealist[1]<ixyarealist[1]: 22 elif tixyarealist[1]-((len(ixyarealist[0])- len(tixyarealist[0]))*sum([rect[x[0]][0]*rect[x[0]][1] for x in tixyarealist[0]])*factor if len(tixyarealist[0])<len(ixyarealist[0]) else 0) < ixyarealist[1]-((len(tixyarealist[0])-len(ixyarealist[0]))*sum([rect[x[0]] [0]*rect[x[0]][1] for x in ixyarealist[0]])*factor if len(ixyarealist[0])<len(tixyarealist[0]) else 0): 23 ixyarealist=tixyarealist 24 else: 25 return False 26 return ixyarealist
- 子矩形可以反向尝试，先 V 后 H。
---------------------------------- | | | | a | | | | | ----------------- H | | | | | V | | | | | ----------------------------------
限制
计算在两个维度上进行，沿 x 轴和 y 轴。与相同面积但形状更偏矩形的形状相比，趋向于正方形的形状需要更高的计算量。
摘要
本文讨论了用一组子矩形进行矩形填充。文中提出了一种算法，其中根矩形将子矩形集合中的一个子矩形放置在左上角，然后以链式方式将寻找最佳填充矩形的责任转移给新创建的矩形“H”和“V”。这导致了“责任链”设计模式的出现，归类为行为设计模式。文中还讨论了改进填充样式的各种方法。
历史
- 2023年12月5日：初始版本