Getting the best fit match of boxes of varying dimensions in a bounding box

Question

I have a problem wherein I have to ensure optimal packing in a 2D rectangular frame of smaller 2D rectangular/square boxes.

I read that this may be termed as bin-packing problem or may also be considered as best fit bounding-box problem, where we try to find the best solution for above problem.

The dataset is something like this:

name     |  Width  |  Height
---------+---------+--------------
Rect 1   |  146    | 276
---------+---------+-------------- 
Rect 2   |  168    | 20
---------+---------+-------------- 
Rect 3   |   53    | 297
---------+---------+-------------- 
Rect 4   |   68    | 122
---------+---------+-------------- 
Rect n   |  167    | 229
---------+---------+-------------- 

The bounding box/frame I have is 1000 units wide and 800 units high, and can have more than 1 such boxes at a time.

I have to ensure that:

1. best fit for all these boxes from Rect 1 to Rect n (where n is a whole number),
2. that whatever best fit I have as the resultant, produces the least wasted space in all the bounding boxes available.
3. Ensure least processing time and resource utilization, though I know this would not be a reality for such a problem, so this is not a priority as of now.
4. Change orientation of the boxes, if it gives a better optimization result.

On searching through google, I found out a few solution and papers (example) explaining this problem, but I am having a hard time figuring the best way to do this using a coding language.

I tried this on paper, and figured out a way.

1. Sort all the boxes, basis their surface area, from largest to smallest.
2. Split this dataset into the number of bounding boxes/frames I have to fit in. Lets call each group as a batch.
3. Start by putting the biggest boxes in each frame first, from each batch.
4. Once we've exhausted all the biggest boxes, or cannot fit in further bigger boxes in bounding box, move to the next size batch (second largest), thus reaching to the smallest size batch.

I guess, this may not be optimal, since I am taking Surface area for placement, but orientation may still be a problem that is not being looked at.

I know this a fairly complex problem, but I guess there are still a few ways to do it.

Created a Python Notebook to solve this problem, because I think Python or R is the best fit as the programming language here.

import pandas as pd
import numpy as np
#Add JSON dataset
data= [{"name":"R1","width":"141","height":"241"},{"name":"R2","width":"58","height":"243"},{"name":"R3","width":"95","height":"75"},{"name":"R4","width":"76","height":"190"},{"name":"R5","width":"256","height":"213"},{"name":"R6","width":"163","height":"257"},{"name":"R7","width":"134","height":"108"},{"name":"R8","width":"276","height":"79"},{"name":"R9","width":"49","height":"70"},{"name":"R10","width":"158","height":"98"},{"name":"R11","width":"29","height":"280"},{"name":"R12","width":"137","height":"282"},{"name":"R13","width":"179","height":"247"},{"name":"R14","width":"157","height":"226"},{"name":"R15","width":"248","height":"200"},{"name":"R16","width":"171","height":"247"},{"name":"R17","width":"129","height":"34"},{"name":"R18","width":"41","height":"176"},{"name":"R19","width":"272","height":"74"},{"name":"R20","width":"83","height":"294"},{"name":"R21","width":"98","height":"111"},{"name":"R22","width":"135","height":"81"},{"name":"R23","width":"193","height":"294"},{"name":"R24","width":"75","height":"205"},{"name":"R25","width":"38","height":"165"},{"name":"R26","width":"117","height":"63"},{"name":"R27","width":"136","height":"64"},{"name":"R28","width":"167","height":"115"},{"name":"R29","width":"28","height":"236"},{"name":"R30","width":"241","height":"95"},{"name":"R31","width":"141","height":"150"},{"name":"R32","width":"296","height":"175"},{"name":"R33","width":"18","height":"284"},{"name":"R34","width":"64","height":"97"},{"name":"R35","width":"85","height":"163"},{"name":"R36","width":"61","height":"176"},{"name":"R37","width":"144","height":"172"},{"name":"R38","width":"121","height":"176"},{"name":"R39","width":"62","height":"274"},{"name":"R40","width":"271","height":"18"},{"name":"R41","width":"16","height":"62"},{"name":"R42","width":"275","height":"209"},{"name":"R43","width":"232","height":"293"},{"name":"R44","width":"48","height":"241"},{"name":"R45","width":"239","height":"16"},{"name":"R46","width":"176","height":"269"},{"name":"R47","width":"57","height":"43"},{"name":"R48","width":"36","height":"21"},{"name":"R49","width":"223","height":"249"},{"name":"R50","width":"89","height":"17"},{"name":"R51","width":"146","height":"121"},{"name":"R52","width":"63","height":"252"},{"name":"R53","width":"234","height":"107"},{"name":"R54","width":"275","height":"290"},{"name":"R55","width":"55","height":"159"},{"name":"R56","width":"87","height":"140"},{"name":"R57","width":"114","height":"294"},{"name":"R58","width":"297","height":"127"},{"name":"R59","width":"156","height":"53"},{"name":"R60","width":"120","height":"21"},{"name":"R61","width":"87","height":"222"},{"name":"R62","width":"197","height":"217"},{"name":"R63","width":"36","height":"66"},{"name":"R64","width":"211","height":"145"},{"name":"R65","width":"65","height":"256"},{"name":"R66","width":"155","height":"188"},{"name":"R67","width":"99","height":"221"},{"name":"R68","width":"129","height":"125"},{"name":"R69","width":"121","height":"288"},{"name":"R70","width":"29","height":"177"},{"name":"R71","width":"133","height":"166"},{"name":"R72","width":"95","height":"254"},{"name":"R73","width":"260","height":"175"},{"name":"R74","width":"185","height":"271"},{"name":"R75","width":"257","height":"229"},{"name":"R76","width":"30","height":"68"},{"name":"R77","width":"172","height":"40"},{"name":"R78","width":"264","height":"32"},{"name":"R79","width":"105","height":"123"},{"name":"R80","width":"64","height":"25"},{"name":"R81","width":"265","height":"269"},{"name":"R82","width":"169","height":"125"},{"name":"R83","width":"95","height":"15"},{"name":"R84","width":"116","height":"87"},{"name":"R85","width":"120","height":"22"},{"name":"R86","width":"133","height":"269"},{"name":"R87","width":"47","height":"131"},{"name":"R88","width":"134","height":"296"},{"name":"R89","width":"76","height":"300"},{"name":"R90","width":"210","height":"146"},{"name":"R91","width":"290","height":"74"},{"name":"R92","width":"16","height":"204"},{"name":"R93","width":"39","height":"184"},{"name":"R94","width":"290","height":"20"},{"name":"R95","width":"256","height":"272"},{"name":"R96","width":"112","height":"253"},{"name":"R97","width":"284","height":"92"},{"name":"R98","width":"220","height":"207"},{"name":"R99","width":"36","height":"191"},{"name":"R100","width":"247","height":"196"},{"name":"R101","width":"118","height":"171"},{"name":"R102","width":"272","height":"289"},{"name":"R103","width":"193","height":"252"},{"name":"R104","width":"39","height":"170"},{"name":"R105","width":"148","height":"86"},{"name":"R106","width":"15","height":"98"},{"name":"R107","width":"256","height":"198"},{"name":"R108","width":"65","height":"218"},{"name":"R109","width":"177","height":"167"},{"name":"R110","width":"106","height":"247"},{"name":"R111","width":"267","height":"56"},{"name":"R112","width":"134","height":"247"},{"name":"R113","width":"28","height":"131"},{"name":"R114","width":"147","height":"121"},{"name":"R115","width":"166","height":"204"},{"name":"R116","width":"75","height":"133"},{"name":"R117","width":"27","height":"279"},{"name":"R118","width":"291","height":"91"},{"name":"R119","width":"175","height":"180"},{"name":"R120","width":"61","height":"23"},{"name":"R121","width":"95","height":"183"},{"name":"R122","width":"70","height":"144"},{"name":"R123","width":"137","height":"96"},{"name":"R124","width":"58","height":"248"},{"name":"R125","width":"236","height":"224"},{"name":"R126","width":"272","height":"26"},{"name":"R127","width":"277","height":"40"},{"name":"R128","width":"21","height":"214"},{"name":"R129","width":"207","height":"215"},{"name":"R130","width":"71","height":"143"},{"name":"R131","width":"91","height":"283"},{"name":"R132","width":"235","height":"299"},{"name":"R133","width":"88","height":"91"},{"name":"R134","width":"23","height":"34"},{"name":"R135","width":"115","height":"124"},{"name":"R136","width":"156","height":"136"},{"name":"R137","width":"221","height":"167"},{"name":"R138","width":"226","height":"121"},{"name":"R139","width":"53","height":"226"},{"name":"R140","width":"262","height":"43"},{"name":"R141","width":"106","height":"63"},{"name":"R142","width":"127","height":"103"},{"name":"R143","width":"89","height":"105"},{"name":"R144","width":"71","height":"155"},{"name":"R145","width":"52","height":"276"},{"name":"R146","width":"85","height":"160"},{"name":"R147","width":"144","height":"236"},{"name":"R148","width":"282","height":"282"},{"name":"R149","width":"181","height":"229"},{"name":"R150","width":"135","height":"209"},{"name":"R151","width":"199","height":"109"},{"name":"R152","width":"212","height":"227"},{"name":"R153","width":"60","height":"67"},{"name":"R154","width":"92","height":"137"},{"name":"R155","width":"182","height":"77"},{"name":"R156","width":"226","height":"298"},{"name":"R157","width":"191","height":"160"},{"name":"R158","width":"235","height":"119"},{"name":"R159","width":"211","height":"35"},{"name":"R160","width":"175","height":"86"},{"name":"R161","width":"61","height":"173"},{"name":"R162","width":"299","height":"83"},{"name":"R163","width":"258","height":"140"},{"name":"R164","width":"17","height":"231"},{"name":"R165","width":"212","height":"172"},{"name":"R166","width":"203","height":"35"},{"name":"R167","width":"61","height":"21"},{"name":"R168","width":"132","height":"172"},{"name":"R169","width":"129","height":"243"},{"name":"R170","width":"175","height":"182"},{"name":"R171","width":"198","height":"138"},{"name":"R172","width":"141","height":"58"},{"name":"R173","width":"37","height":"143"},{"name":"R174","width":"255","height":"238"},{"name":"R175","width":"23","height":"72"},{"name":"R176","width":"103","height":"204"},{"name":"R177","width":"65","height":"130"},{"name":"R178","width":"239","height":"288"},{"name":"R179","width":"94","height":"150"},{"name":"R180","width":"68","height":"166"},{"name":"R181","width":"192","height":"172"},{"name":"R182","width":"160","height":"207"},{"name":"R183","width":"198","height":"271"},{"name":"R184","width":"123","height":"57"},{"name":"R185","width":"17","height":"269"},{"name":"R186","width":"140","height":"251"},{"name":"R187","width":"297","height":"218"},{"name":"R188","width":"32","height":"292"},{"name":"R189","width":"194","height":"193"},{"name":"R190","width":"209","height":"90"},{"name":"R191","width":"24","height":"264"},{"name":"R192","width":"67","height":"240"},{"name":"R193","width":"42","height":"55"},{"name":"R194","width":"23","height":"16"},{"name":"R195","width":"85","height":"181"},{"name":"R196","width":"223","height":"186"},{"name":"R197","width":"241","height":"229"},{"name":"R198","width":"182","height":"123"},{"name":"R199","width":"111","height":"178"},{"name":"R200","width":"27","height":"50"},{"name":"R201","width":"16","height":"75"},{"name":"R202","width":"128","height":"74"},{"name":"R203","width":"207","height":"43"},{"name":"R204","width":"31","height":"258"},{"name":"R205","width":"222","height":"256"},{"name":"R206","width":"246","height":"260"},{"name":"R207","width":"172","height":"126"},{"name":"R208","width":"201","height":"247"},{"name":"R209","width":"39","height":"216"},{"name":"R210","width":"84","height":"88"},{"name":"R211","width":"102","height":"33"},{"name":"R212","width":"299","height":"135"},{"name":"R213","width":"296","height":"287"},{"name":"R214","width":"113","height":"27"},{"name":"R215","width":"111","height":"64"},{"name":"R216","width":"24","height":"120"},{"name":"R217","width":"102","height":"258"},{"name":"R218","width":"39","height":"194"},{"name":"R219","width":"17","height":"275"},{"name":"R220","width":"233","height":"193"},{"name":"R221","width":"297","height":"83"},{"name":"R222","width":"89","height":"293"},{"name":"R223","width":"150","height":"155"},{"name":"R224","width":"66","height":"279"},{"name":"R225","width":"62","height":"38"},{"name":"R226","width":"148","height":"277"},{"name":"R227","width":"190","height":"195"},{"name":"R228","width":"34","height":"65"},{"name":"R229","width":"142","height":"175"},{"name":"R230","width":"34","height":"57"},{"name":"R231","width":"77","height":"177"},{"name":"R232","width":"69","height":"232"},{"name":"R233","width":"215","height":"198"},{"name":"R234","width":"136","height":"291"},{"name":"R235","width":"230","height":"134"},{"name":"R236","width":"273","height":"194"},{"name":"R237","width":"293","height":"236"},{"name":"R238","width":"28","height":"251"},{"name":"R239","width":"209","height":"201"},{"name":"R240","width":"263","height":"66"},{"name":"R241","width":"39","height":"296"},{"name":"R242","width":"166","height":"110"},{"name":"R243","width":"114","height":"123"},{"name":"R244","width":"24","height":"88"},{"name":"R245","width":"139","height":"94"},{"name":"R246","width":"109","height":"26"},{"name":"R247","width":"83","height":"108"},{"name":"R248","width":"253","height":"131"},{"name":"R249","width":"153","height":"248"},{"name":"R250","width":"205","height":"65"},{"name":"R251","width":"129","height":"50"},{"name":"R252","width":"108","height":"200"},{"name":"R253","width":"86","height":"209"},{"name":"R254","width":"231","height":"205"},{"name":"R255","width":"291","height":"93"},{"name":"R256","width":"109","height":"83"},{"name":"R257","width":"177","height":"104"},{"name":"R258","width":"123","height":"171"},{"name":"R259","width":"32","height":"152"},{"name":"R260","width":"234","height":"79"},{"name":"R261","width":"278","height":"183"},{"name":"R262","width":"280","height":"75"},{"name":"R263","width":"268","height":"249"},{"name":"R264","width":"75","height":"274"},{"name":"R265","width":"94","height":"205"},{"name":"R266","width":"130","height":"255"},{"name":"R267","width":"183","height":"287"},{"name":"R268","width":"142","height":"228"},{"name":"R269","width":"212","height":"134"},{"name":"R270","width":"76","height":"115"},{"name":"R271","width":"86","height":"64"},{"name":"R272","width":"244","height":"269"},{"name":"R273","width":"88","height":"34"},{"name":"R274","width":"164","height":"84"},{"name":"R275","width":"95","height":"114"},{"name":"R276","width":"140","height":"140"},{"name":"R277","width":"125","height":"76"},{"name":"R278","width":"168","height":"186"},{"name":"R279","width":"274","height":"183"},{"name":"R280","width":"275","height":"258"},{"name":"R281","width":"77","height":"270"},{"name":"R282","width":"237","height":"229"},{"name":"R283","width":"80","height":"280"},{"name":"R284","width":"181","height":"298"},{"name":"R285","width":"186","height":"42"},{"name":"R286","width":"203","height":"99"},{"name":"R287","width":"245","height":"208"},{"name":"R288","width":"180","height":"241"},{"name":"R289","width":"172","height":"231"},{"name":"R290","width":"63","height":"25"},{"name":"R291","width":"103","height":"17"},{"name":"R292","width":"68","height":"162"},{"name":"R293","width":"40","height":"165"},{"name":"R294","width":"116","height":"81"},{"name":"R295","width":"132","height":"245"},{"name":"R296","width":"236","height":"195"},{"name":"R297","width":"222","height":"288"},{"name":"R298","width":"74","height":"155"},{"name":"R299","width":"248","height":"177"},{"name":"R300","width":"79","height":"75"},{"name":"R301","width":"300","height":"26"},{"name":"R302","width":"72","height":"45"},{"name":"R303","width":"300","height":"277"},{"name":"R304","width":"291","height":"249"},{"name":"R305","width":"139","height":"107"},{"name":"R306","width":"164","height":"218"},{"name":"R307","width":"70","height":"93"}]

#Convert to Pandas dataframe
df = pd.DataFrame.from_dict(data, orient='columns');

#Convert the column type from string to float 
df["width"] = pd.to_numeric(df["width"],downcast='float')
df["height"] = pd.to_numeric(df["height"],downcast='float')

#Calculate Surface area (L*B or Width * Height) for each Rectangle
df["area"] = df.width * df.height

#Sort each record on surface area (Largest to smallest)
df = df.sort_values(by=["area"], ascending= False);

#number of Rectangle frames where above Rectangles need to fit
frameCount = 6;
frameWidth = 1000; #width of rectangle frame 
frameHeight = 800; #height of rectangle frame

#Split the above dataframe into same count of frames
dfs = np.array_split(df, frameCount)

Answer 1

Your problem is known to be NP-hard: https://en.wikipedia.org/wiki/Rectangle_packing#Packing_different_rectangles_in_a_given_rectangle

There is a similar question with an answers here: https://cs.stackexchange.com/questions/88499/fitting-different-rectangles-inside-a-rectangle

And there is indeed a software that is concerned with such problems: https://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu

Finally I found one more SO question concerned with a similar topic: What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? I guess it will be possible to adapt one of the heuristic algorithms listed in the answer to that question to your problem.

Answer 2

First, there is not an answer.

Discussing the problem as given, there are some solutions that can be starting points for a discussion:

1. Try fitting random boxes, in random orientations. Place the first box in the upper left (0,0), then in the next unused part of the top row, and then down. It should miss lots of cases, but a few random places might get you better than absolutely random. You can explore how many attempts are required to get 'decent' fits.

2. Try solving it for a one dimensional case, then going up to n-dimensional.

3. Try relating this to real world issues, like laser cutting pieces. Discuss the costs and value of better algorithms.

4. Try making more 'intermediate results', e.g., a rectangle of 80x20 and 10x20 could have intermediate recipes for 90x20 and for 80x30 with a 1600 wasted pieces.

5. Try to dig down and get new requirements or relaxations that may happen. Do you want to know many 100x100 pages this would fill up? Do you know if all sizes are even? Is there a pattern? etc.

Mostly, this is a sample of having you play with it and talk about it. There is not an 'answer'.