# Rectangle packing, fixed sizes

I have rectangles of a given size to fit into a larger rectangle of a fixed size, with a specified gap between the packed rectangles. I would like to write some code that optimises the number of rectangles of each given size that I can pack.

For example, say I have a large rectangle of $$8' \times 4'\ \text{(}\approx 2438 \times 1219 \text{ mm)}$$, I would like to know the optimal placement and orientation of, say $$x\ \text{(}400 \times 450 \text{ mm)}$$ rectangles , $$y\ \text{(}300 \times 400 \text{ mm)}$$ rectangles and $$z\ \text{(}680 \times 390 \text{ mm)}$$ rectangles.

This is for a real life application (cutting ply into smaller boards), so ideally I would like to optimise for least number of cuts as they charge for each cut).

$$eg$$ (code standard manual Graphics manual placement:

Module[{s1, s2, s3}, s1 = {400, 450}; s2 = {300, 400}; s3 = {680, 390};
Graphics[{ EdgeForm[{Nest[Lighter, Blue, 2], Thin}], Nest[Lighter, Blue, 2],
Rectangle[{0, 0}, {#, #2}] & @@ {2438, 1219},
Nest[Lighter, Red, 2],
Rectangle[{0, 0}, {s1[], s1[]}],
Rectangle[{0, s1[] + 5}, {s1[], 2 s1[] + 5}],
Rectangle[{s1[] + 5, 0}, {2 s1[] + 5, s1[]}],
Rectangle[{s1[] + 5, s1[] + 5}, {2 s1[] + 5,
2 s1[] + 5}],
Rectangle[{s2[] + 5, 2 s1[] + 10}, {5 + 2 s2[],
2 s1[] + 15 + s2[]}],
Rectangle[{0, 2 s1[] + 10}, {s2[], 2 s1[] + 15 + s2[]}],
Rectangle[{2 s1[] + 10, 0}, {2 s1[] + 10 + s3[], s3[]}],
Rectangle[{2 s1[] + s3[] + 15,
0}, {2 s1[] + 15 + 2 s3[], s3[]}],
Rectangle[{2 s1[] + 2 s3[] + 20,
0}, {2 s1[] + 20 + 3 s3[], s3[]}],
Rectangle[{2 s1[] + 3 s3[] + 25,
0}, {2 s1[] + 25 + 4 s3[], s3[]}],
Rectangle[{2 s1[] + 10, s3[] + 5}, {2 s1[] + 10 + s3[],
s3[] + s3[]}],
Rectangle[{2 s1[] + 15 + s3[],
s3[] + 5}, {2 s1[] + 15 + s3[] + s2[],
s3[] + 5 + s2[]}],
Rectangle[{2 s1[] + 20 + s3[] + s2[],
s3[] + 5}, {2 s1[] + 20 + s3[] + 2 s2[],
s3[] + 5 + s2[]}],
Rectangle[{2 s1[] + 25 + s3[] + 2 s2[],
s3[] + 5}, {2 s1[] + 25 + s3[] + 3 s2[],
s3[] + 5 + s2[]}]   }]]


Have searched for rectangle packing algorithm, but can't find any with these constraints.

Using @GeorgeVarnavides ' code below, (though the Fitting option presents problems as outlined in comments below his answer), the method will also present practical problems as highlighted here images = ConstantImage[Nest[Lighter, Red, 2], #] & /@
Join[ConstantArray[#, 5], ConstantArray[#2, 4],
ConstantArray[#3, 6]] & @@ {{400, 450}, {300, 400}, {680, 390}};
Show[ImageCollage[images, Automatic, {2438, 1219},
Method -> "ClosestPacking", Background -> Nest[Lighter, Blue, 2], ImagePadding -> 5],
Graphics[{Opacity, EdgeForm[Black], Rectangle[{0, 0}, {2438, 1219}], EdgeForm[{Red, Thick}],
Disk[{1875, 435}, 200],
Opacity, Thick, Dashed, Line[{{#, 0}, {#, 1219}} &],
Line[{{0, #}, {2438, #}} &]}], Axes -> True]


as the guys at the timber yard will cut along the dashed lines since they can't cut part way accurately on a table saw. So noting @Syed 's comment, either strip-packing or bin-packing looks like the way to go. No idea how to implement this in MMA though.

Another issue is that the "ClosestPacking" method doesn't rotate automatically to optimise packing.

Having said that, @GeorgeVarnavides ' answer does give me a great starting point to then adjust manually (+1).

• Nice question, but very hard. Sep 29, 2021 at 21:25
• @yarchik I did wonder, though the guys at the local timber yard do have a programme that does this. I just wanted to optimize myself so I can play around with it. Sep 29, 2021 at 21:27
• stackoverflow.com/questions/1213394/…
– Syed
Sep 30, 2021 at 1:50
• Not relevant to the math solution you are seeking here, but there is a Woodworking SE (that I just discovered). Perhaps you can get distilled and heuristic advice there.
– Syed
Sep 30, 2021 at 7:21
• cutlistoptimizer.com
– Syed
Sep 30, 2021 at 7:33

Probably not a serious answer, but we could use the built-in "ClosestPacking" method available in ImageCollage, which conveniently also has a padding option:

SeedRandom;
images=ConstantImage[RandomColor[],#]&/@RandomInteger[{30,60},{12,2}]; • the Fitting option in ImageCollage resizes the rectangles. Is there any way to fix this? Sep 29, 2021 at 22:14
• Neither "Fit", "Fill" or "Stretch" work Sep 29, 2021 at 22:17
• images = ConstantImage[Nest[Lighter, Red, 2], #] & /@ Join[ConstantArray[#, 5], ConstantArray[#2, 4], ConstantArray[#3, 5]] & @@ {{400, 450}, {300, 400}, {680, 390}}; Show[ImageCollage[images, "Fit", {2438, 1219}, Method -> "ClosestPacking", Background -> Nest[Lighter, Blue, 2], ImagePadding -> 5], Axes -> True] Sep 29, 2021 at 22:17
• For example, if I change above to ConstantArray[#3, 50], it resiozes the rectangles to fit, rather than keep original dimensions Sep 29, 2021 at 22:18