11
$\begingroup$

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$

enter image description here

(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[[1]], s1[[2]]}],
Rectangle[{0, s1[[2]] + 5}, {s1[[1]], 2 s1[[2]] + 5}],
Rectangle[{s1[[1]] + 5, 0}, {2 s1[[1]] + 5, s1[[2]]}],
Rectangle[{s1[[1]] + 5, s1[[2]] + 5}, {2 s1[[1]] + 5, 
 2 s1[[2]] + 5}],
Rectangle[{s2[[2]] + 5, 2 s1[[2]] + 10}, {5 + 2 s2[[2]], 
 2 s1[[2]] + 15 + s2[[1]]}],
Rectangle[{0, 2 s1[[2]] + 10}, {s2[[2]], 2 s1[[2]] + 15 + s2[[1]]}],
Rectangle[{2 s1[[1]] + 10, 0}, {2 s1[[1]] + 10 + s3[[2]], s3[[1]]}],
Rectangle[{2 s1[[1]] + s3[[2]] + 15, 
 0}, {2 s1[[1]] + 15 + 2 s3[[2]], s3[[1]]}],
Rectangle[{2 s1[[1]] + 2 s3[[2]] + 20, 
 0}, {2 s1[[1]] + 20 + 3 s3[[2]], s3[[1]]}],
Rectangle[{2 s1[[1]] + 3 s3[[2]] + 25, 
 0}, {2 s1[[1]] + 25 + 4 s3[[2]], s3[[1]]}],
Rectangle[{2 s1[[1]] + 10, s3[[1]] + 5}, {2 s1[[1]] + 10 + s3[[1]],
  s3[[2]] + s3[[1]]}],
Rectangle[{2 s1[[1]] + 15 + s3[[1]], 
 s3[[1]] + 5}, {2 s1[[1]] + 15 + s3[[1]] + s2[[1]], 
 s3[[1]] + 5 + s2[[2]]}], 
Rectangle[{2 s1[[1]] + 20 + s3[[1]] + s2[[1]], 
 s3[[1]] + 5}, {2 s1[[1]] + 20 + s3[[1]] + 2 s2[[1]], 
 s3[[1]] + 5 + s2[[2]]}],
Rectangle[{2 s1[[1]] + 25 + s3[[1]] + 2 s2[[1]], 
 s3[[1]] + 5}, {2 s1[[1]] + 25 + s3[[1]] + 3 s2[[1]], 
 s3[[1]] + 5 + s2[[2]]}]   }]]

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

Added

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

enter image description 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[0], EdgeForm[Black], Rectangle[{0, 0}, {2438, 1219}], EdgeForm[{Red, Thick}], 
Disk[{1875, 435}, 200],
Opacity[1], Thick, Dashed, Line[{{#, 0}, {#, 1219}} &[1980]], 
Line[{{0, #}, {2438, #}} &[490]]}], 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).

$\endgroup$
8
  • 2
    $\begingroup$ Nice question, but very hard. $\endgroup$
    – yarchik
    Sep 29 '21 at 21:25
  • $\begingroup$ @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. $\endgroup$
    – martin
    Sep 29 '21 at 21:27
  • 2
    $\begingroup$ stackoverflow.com/questions/1213394/… $\endgroup$
    – Syed
    Sep 30 '21 at 1:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Syed
    Sep 30 '21 at 7:21
  • 1
    $\begingroup$ cutlistoptimizer.com $\endgroup$
    – Syed
    Sep 30 '21 at 7:33
5
$\begingroup$

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[0];
images=ConstantImage[RandomColor[],#]&/@RandomInteger[{30,60},{12,2}];
packing=ImageCollage[1->images,ImagePadding->2,Method->"ClosestPacking",Background->Black];
HighlightImage[packing,ImageCorners[packing]]

enter image description here

$\endgroup$
7
  • $\begingroup$ the Fitting option in ImageCollage resizes the rectangles. Is there any way to fix this? $\endgroup$
    – martin
    Sep 29 '21 at 22:14
  • $\begingroup$ Neither "Fit", "Fill" or "Stretch" work $\endgroup$
    – martin
    Sep 29 '21 at 22:17
  • $\begingroup$ 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] $\endgroup$
    – martin
    Sep 29 '21 at 22:17
  • $\begingroup$ For example, if I change above to ConstantArray[#3, 50], it resiozes the rectangles to fit, rather than keep original dimensions $\endgroup$
    – martin
    Sep 29 '21 at 22:18
  • $\begingroup$ Of course I can manually check, but was aiming at not doing that $\endgroup$
    – martin
    Sep 29 '21 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.