Rectangle Packaging Problem / Efficient 2D Packing

Categories:
Tags:

Summary

Automatically fit 2D rectangular parts onto standard-sized CNC panels to reduce waste and manual layout work. This post outlines a Python-based approach using the rectpack library and OpenSCAD for visualization and tool path.

Using rectpack for Automated Layout

There’s a Python library called rectpack that implements several efficient algorithms for this task: https://github.com/secnot/rectpack

Background

I need to produce a bunch of 2D parts out of the same material. The parts are roughly rectangular and I need to produce an undefined large number (test jig stands for TheJigsApp.com). There are a ton of available panel sizes but the CNC I’m using can fit panels of 25x36" max. So our problem is to fit different size rectangles into a given rectangle [Wikipedia: Rectangle Packing].

One interesting paper on the topic is available here. The author’s original study code is up on Github here.

rectpack Library & Code Design

There’s a python library available that implements a few of the more efficient algorithms available [here].

Inputs

  • Panel Size
  • List of rectangle sizes

Outputs

  • Optimal number of panels of a given size to minimize waste
  • Total wasted area
  • Percentage of unused area
  • Number of sets packed
  • Spreadsheet with rectangle orientation/placement data

After packing, I visually verify placement using OpenSCAD.

Workflow Overview

  1. A CSV file defines part dimensions.
  2. Python uses rectpack to iteratively try panel configurations.
  3. The best packing (highest % used) is chosen.
  4. Outputs include:
    • Excel summary
    • OpenSCAD model for visual confirmation
  5. Results are rendered to review placement and panel usage.

Code

from rectpack import newPacker
import pandas
import jinja2
import numpy as np
import pprint
import click


def main(rects, width, length, bins=1):
    packer = newPacker()

    for rect in rects:
        packer.add_rect(*rect)

    for i in range(bins):
        packer.add_bin(width, length)
    packer.pack()

    all_rects = packer.rect_list()
    if len(all_rects) != len(rects):
        raise UserWarning("Cant fit rectangles %d/%d", len(all_rects), len(rects))

    dfout = {"bin": [], "x": [], "y":[], "w":[], "h":[], "area":[], "rotation":[]}
    for rect, transform in zip(rects, all_rects):
        b, x, y, w, h, rid = transform
        dfout["bin"].append(b)
        dfout["x"].append(x)
        dfout["y"].append(y)
        dfout["w"].append(w)
        dfout["h"].append(h)
        dfout["area"].append(h*w)

        for rect in rects:
            if (rect[0] == w and rect[1] == h):
                dfout["rotation"].append(0)
                break
            elif (rect[0] == h and rect[1] == w):
                dfout["rotation"].append(90)
                break
            else:
                print("error ", rect, transform)
                assert(0, "part not in expected order")

    return dfout


def to_scad(df):
    '''
    Return scad as a string
    '''
    template = '''function get_shapes() = [
        {% for _, l in df.iterrows() -%}
        [{{l['bin']}}, {{l['x']}}, {{l['y']}}, {{l['w']}}, {{l['h']}}],
        {% endfor %}
    ];
    '''
    return jinja2.Template(template).render(df=df)



def optimize(panels, max_bins):
    config = {"nbins": [], "panel width": [], "panel length": [], "packing": [], "% used": []}
    dfset = pandas.read_csv(f"rectangles.csv")
    rect_set = [[line["width"], line["length"], line["name"]] for _, line in dfset.iterrows()]

    for panel in panels:
        for nbin in range(1, max_bins+1):
            nsets = 1
            while True:
                try:
                    d = main(list(rect_set)*nsets, width=panel[0], length=panel[1], bins=nbin)
                    df = pandas.DataFrame(d)
                    config["packing"].append(df)
                    config["nbins"].append(nbin)
                    config["panel width"].append(panel[0])
                    config["panel length"].append(panel[1])
                    config["% used"].append(sum(df["w"]*df["h"])/(nbin*panel[0]*panel[1]))
                    nsets+=1
                except UserWarning:
                    break

    return pandas.DataFrame(config)


@click.command()
@click.option("--bins", "-n", type=int, default=1)
@click.option("--design", required=True)
@click.option("--output-scad", default="shapes.scad")
@click.option("--output-xlsx", default="shapes.xlsx")
def click_main(bins, design, output_scad, output_xlsx):
    panels = [
        [11.5, 35.5],
        [23.5, 35.5],
    ]

    config_df = optimize(panels=panels, max_bins=bins)
    max_percent = np.max(config_df["% used"])
    i = list(config_df["% used"]).index(max_percent)
    df = config_df.iloc[i]
    df_shapes = df["packing"]
    df_shapes.to_excel(output_xlsx)
    with open(output_scad, "w") as f:
        f.write(to_scad(df_shapes))

    pprint.pprint(list(config_df["% used"]))
    pprint.pprint(config_df)
    print(f"Min Error: {max_percent}\n Panel Size: {df['panel width']}x{df['panel length']}. nbins: {df['nbins']}")


click_main()

Our design file:

namewidthlength
upright 11.513.5
upright 21.513.5
short side 128
short side 228
long side 129
long side 229
top7.59
button1.59
cross4.58.5

OpenSCAD Visualization

After optimization, I used OpenSCAD to visually verify the layout and spacing. The code below imports the results and displays all the parts across multiple panels (bins). Each rectangle is shown with a small gap to highlight spacing.

use <./shapes.scad>;

/*
# b - Bin index
# x - Rectangle bottom-left corner x coordinate
# y - Rectangle bottom-left corner y coordinate
# w - Rectangle width
# h - Rectangle height
# rid - User assigned rectangle id or None
*/

bins = 8;
width = 24;
gap=0.5;
length=36;
space = 25;
difference() {
    for (i=[0:bins-1]) {
        translate([(width+space)*i, 0])square([width,length]);
    };
    union() {
        for (shape=get_shapes()) {
            translate([shape[1]+(width+space)*shape[0]+gap/2, shape[2]+gap/2])square([shape[3], shape[4]], center=false);
        };
    };
};
echo(len(get_shapes()));

Example Execution

python3 pack.py --design rectangles.csv --bins 8

Example result:

Min Error: 0.9099990010987913
Panel Size: 23.5x35.5. nbins: 3

In this case, the best solution used three 23.5x35.5" panels with ~9% material waste.

Visual Results

We’re left with the following wasted outline from panels of 24"x36" (including a 1/4" keep out around the panel).

Negative space (waste) after optimal packing: Remaining area from packing

Positive space (used areas) showing placement over 3 panels: Expanding the space around the parts a bit shows how the packing is done:

Final Thoughts

This approach gives the arrangement of the rectangles so I will need to go and match the size of each object to a suitable slot. You can do this in a cad program of choice or with OpenSCAD as long as you’re careful with the import/export formats. DXF works well in both directions but you need to worry about document size and line thickness if you’re using dxf. Seems to work well and this definitely speeds up the process!