The article discusses packing a rectangular area with a set of subrectangles, aiming to maximize the covered area and minimize the empty or unpacked area.
Introduction
This article is about packing a rectangular area with set of subrectangles. Subrectangle(s) are chosen from a predefined set of subrectangle(s), which would tightly pack into the bigger rectangular container. Packing area that is area covered by subrectangles should be maximum whereas unpacked area (empty area) should be minimum or zero. An ideal packed rectangle means no empty area left after packing of subrectangles in it. A subrectangle would repeat itself in the packing area.
Scenario
There are cases when a big rectangular area needs to be packed up with smaller rectangles. Smaller rectangle would come from a predefined set of subrectangles. Algorithms should be employed in such a way that packing must be as full as possible. Non covered (unpacked) area should tend to zero.
-------------------------------------+
| ______________|_____
| +---| a | b | c | d... |<-sub-rectangles
| R | ----------|---------
| --------------v-------------v-----------------
| |----------------- ---------------- |
| || | | | unpacked|
| || a | | c | area |
| || | | | |
| |----------------- ---------------- |
| |--------------------------------------- |
| || d | |
+---->| | |
|--------------------------------------- |
----------------------------------------------
Problem
Packing a bigger rectangle with set of smaller subrectangle needs infinite set of trials. A set of subrectangles can be tried and then unpacked area should be measured, followed by another set of subrectangles should be tried with different unpacked area measured. Two dimensional area of rectangle leads to more number of trials in order to finally get the set of packed subrectangles. An algorithm is required which would be deterministic in nature and solve the problem is conceptual way.
Solution
Solution is proposed where one subrectangle would be selected from a set of subrectangles [a,b,c,d...]. The selected subrectangle would pack on 'left top' corner in the bigger rectangle, say 'R'. When subrectangle 'a' is placed, in the left top corner of 'R', rest of the unpacked area is divided into two sections. 'H' area in horizontal space where as 'V' area in vertical space.
This scenario would be seen as follows:
____________________
| a | b | c | d... |<-subrectangles
R --|-----------------
--------------------------------|--------------
|----------------- | |
|| |<-------------+ |
|| a | H |
|| | |
|----------------- |
|..............................................
| |
| V |
| |
-----------------------------------------------
Now 'H' and 'V' sections are taken out as separate rectangles which needs to be packed. Now 'H' and 'V' are two bigger rectangles (like 'R') with similar scenario.
new 'R' new 'R'
-------------------------- -------------------------------------------
| | | |
| H | | V |
| | | |
| | -------------------------------------------
--------------------------
In both the new 'R' bigger packing rectangles, subrectangle from set of ['a','b','c'...], which would fit on 'left top' corner of new 'R' (previous 'H' and 'V'), would be tried. So dividing the rest of area into 'H' and 'V' sections again in a meta manner.
__________________ ___________________
| a | b | c | d..| | a | b | c | d...|
H as 'R' --|--------------- V as 'R' ------|------------
---------------|-------------- ---------------------|--------------
|----------- | | |------------ | |
|| a |<--+ | || b |<-------+ H |
|| | H | |------------ |
|----------- | ....................................
|............................| | V |
| V | ------------------------------------
------------------------------
This step is continued till 'H' or 'V' is too small to be packed in by any subrectangle in the subrectangle set ['a','b','c','d'...]. These empty 'H' or 'V' are returned to the parent 'R' as empty or unpacked area. This 'R' now becomes leaf node 'R' in meta system. This leaf node 'R' is a rectangle which has a subrectangle (on left top) and an unpacked empty area with it. This leaf node 'R' again tried with other subrectangles left in set ['b','c','d'..] on left top corner. The new 'H' or 'V' would repeat to grow in meta manner or it would return back without subrectangle with an unpacked area. Finally, the node 'R' would return back to its parent with a child rectangle or as a leaf node with a subrectangle on left top corner and an unpacked area.
Finally the leaf 'R', with subrectangle and area, is passed to the parent 'R'. In parent 'R' again new subrectangle left in set ['b','c','d'..] is chosen and then new 'H' and 'V' created. Previous steps are repeated till it reaches the top level rectangle 'R'. In top 'R' other subrectangles left in set ['b','c','d',..] is tried till leaf rectangle 'R' reaches so that packing area would be maximized. Lowest area subrectangle section is selected. ___________________
returned to | a | b | c | d...|---------
<------- --|---------------- |
parent n|ode +-----------+ <<NO |SUBRECTANGLE|FITS
| | |IN >> |
| Leaf R | +----------+ |
| -----------------|----- --------- | |
| |-------------- | | | | <--+ |
----- || |<-+ | | | |
|| a | H | ------------> | H | |
|| | | \ | | |
|-------------- | \ | | |
|...................... \ --------- v
| v | \ -------------------------
----------------------- +->| V |
-------------------------
Design
Chain of responsibility design pattern is used. Packing rectangle has responsibility to get the maximum packed area from subrectangles and return minimum unpacked area. When a subrectangle is placed at left top corner of the packing rectangle, finding packing rectangle with minimum unpacked space is transferred to two sections cum rectangle 'H' and 'V' in meta manner.
new 'R'
-------------- -------------- ----------
| | | | | |
| 'R' | -----> | 'H' | -----> | 'H' |
| | ^ | | | |
-------------- . -------------- ----------
| . |
| <........... |
v new 'R' . v
------------- . --------------
| | . | 'V' |
| 'V' | . | |
| | . --------------
-------------- .
.
chain formation
Rectangle 'R' places 'a' subrectangle from set of ['a','b','c','d'...] in left top corner and then passes the responsibility to find the best packing subrectangles to newly created sections 'H' and 'V' as new rectangles in a chain fashion. 'H' and 'V' which are new rectangles 'R', after placing subrectangle from set of subrectangle ['a','b','c','d'..] passes the responsibility to next 'H' and 'V' in chain. It chains till it reaches where 'H' and 'V' are small enough to place any subrectangles from the set in it. This leaf rectangle/node 'R' then passes subrectangle at 'left top' along with the unused area to its parent in the chain, which in turn tries again to call the leaf rectangle 'R' with next subrectangle in subset ['a','b','c','d'..]. Finally, root decides which chain to take up depending upon minimum packing free area available.
Program
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)
In program, at root rectangle 'R', for 'left top' subrectangle 'a' H and V section is recursed and resultant rectangle and free unpacked area sum is appended to tixyarealist for a subrectangle 'a' in the rect list. ilist is the curtained version of rect list at each recursion level where subrectangles in ilist has smaller width and height than the 'R' at that level. Same procedure is followed for subrectangle 'b' with new H and V section, where in H and V again it starts with 'left top' subrectangle 'a'. Finally tixyarealist for rectangle 'b' is made. Minimum packing area tixyarealist is finally named to ixyarealist, this new chain with minimum unpacked area is returned.
- Line 27 - calls the algorithms with parameter 0,0,width,height, so root 'R' is of size width'x'height which needs to be packed with subrectangle in set array
rect. - Line 2 -
rect set of subrectangles. - Line 4 - At every level
ilist is prepared as new subrectangle set where each subrectangle fits in current 'R' (new width and height). - Line 5 - checks if
ilist is not empty otherwise returns False at line 25. - Line 6 -
ilist is iterated and every subrectangle is placed at 'left top' corner one by one. - Line 7 -
ixyarealist is initialized, which keeps list of subrectangles with i,x,y. i is index in rectlist and x,y signifies physical position in bigger rectangle where as Unpacked area is last element in the list. - Line 8 - recurse the algorithms with 'H' section (new 'R') whereas line 14 recurse the algorithms with 'V' section as new 'R'.
- Line 9 - and 15 checks the return value, upon getting
False it declares the current 'R' as leaf rectangle and adds 'unpacked area' to it. Line 12 and line 18 comes into picture when 'H' or 'V' returns list of subrectangle and area with it. - Line 22,23 - makes sure that subrectangle list would be selected which has minimum unpacked area.
- Line 26 - return chain of subrectangle which has minimum unpacked area.
- Line 27 - finally returns information about top level rectangle which has the list of subrectangles which packs it best.
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
How It Works
Dividing area into H and V which in turns lead to new rectangles 'R'. This forms a binary tree where each node invokes children while placing all subrectangles from subrectangle set [a,b,c,d..] one by one at left top corner.
---------------
| root 'R' |
| |
---------------
'H' /\ 'V'
/ \
------------ ------------
| | | |
------------ ------------
. . Leaf 'R'
. . /
/ \ / \ /
'H'/ \'V' H' / \ 'V' |
------- ------ ------ --------<-----+
| | | | | | | |<---------+
------- ------ ------ -------- |
/\ /\ /\ /\ |
---- ---- ---- ---- ---------
| | | | | | | |<--- Too small to
---- ---- ---- ---- be packed by subrectangles
Experimental Output
PySide6 package from Qt6 is used to draw the rectangle as QWidget derived widget class from module PySide6.QtWidgets. Subrectangles are drawn as colored rectangular painted area in paintEvent overloaded function inside the packing rectangle 'R' with size annotation at the center whereas empty unpacked area is grayed out.
Nine subrectangles are predefined with sizes: [(160,600),(300,600),(250,250),(200,200),(970,90),(336,280),(300,250),(728,90), (468,60)]
Packing rectangle 'R'
- 950x160
- 690x200
- 840x550
- 840x560
- 600x450
Further Improvements
- In some scenarios, repetition of a subrectangle from set ['a','b','c','d'...] is not allowed. All subrectangles in, packing bigger rectangle 'R', should be unique. In this case,
rect that is subrectangle list should be passed as an argument.
+-- subrectangle list passed as argument
|
v
1 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
Line 1 has new argument as rect which is subrectangle set. Line 4 makes new subrectangle set. Line 8 and line 14 pass new subrectangle list as argument to getrect recursive call.
- Packed subrectangles should be evenly placed. Inter packing subrectangle space should be even:
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]]
- Priority would be given if less rectangle count is packed with bigger size when unpacking free area can be compromised against the count:
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)
...
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
- Subrectangle can be tried in reverse fashion, V and then H:
----------------------------------
| | |
| a | |
| | |
----------------- H |
| | |
| V | |
| | |
----------------------------------
Limitations
Computation happens in two dimensions, along x axis and y axis. For shapes that tend to be square in nature require much higher in computation in comparison to shape with same area and more rectangular in nature.
Summary
Rectangle packing with set of subrectangles is discussion in this article. Algorithm is suggested where root rectangle keeps one subrectangle from set of subrectangles in left top corner and transfers the responsibility to finding the best packing rectangle to newly created rectangles 'H' and 'V' in chain fashion. This leads to design pattern 'chain of responsibility' to take place, categorised in behavioural design pattern. Various ways to improve the packing style has also been discussed.
History
- 5th December, 2023: Initial version
