irregular solver

The irregular solver solves problems where items are arbitrary two-dimensional polygons that must be placed inside polygonal bins without overlapping.

_images/irregular.png

These problems occur for example in the textile, leather, sheet metal, and wood industries.

Features:

  • Objectives:

    • Knapsack

    • Bin packing

    • Bin packing with leftovers

    • Open dimension X

    • Open dimension Y

    • Open dimension XY

    • Variable-sized bin packing

    • Feasibility

  • Item types

    • Polygon shapes (convex or concave)

    • Rectangular and circular shapes

    • Holes inside shapes

    • Discrete and continuous rotations

    • Mirroring (axial symmetry)

    • Multiple item shapes

  • Bin types

    • Polygon, rectangle and circle shapes

    • Defects

    • Item-bin minimum spacing

  • Spacing constraints

    • Item-item minimum spacing

    • Item-bin minimum spacing

    • Item-defect minimum spacing

Basic usage

An instance is described in the JSON format below. The online solver downloads its instances in this format (Download) and loads them (Load a JSON file), the command-line solver reads them (--input), and the Python package and the C++ library read them with InstanceBuilder.read. Instances can also be built directly with the InstanceBuilder of the Python package and of the C++ library.

This example has 8 item types: the 7 one-sided tetrominoes (I, O, T, S, Z, L and J, each made of 4 unit squares), with 2 copies of each, plus a cross-shaped piece (5 unit squares) with 3 copies (17 items in total). The objective is bin-packing in 180 × 160 bins. The solver packs all 17 items into a single bin, wasting less than 1.4% of its area — the pieces interlock almost exactly, like a jigsaw puzzle.

Open the example in the online solver: Basic example, then click Solve.

Basic example
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 180,
      "height": 160,
      "copies": 3
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 80, "y": 0},
        {"x": 80, "y": 20},
        {"x": 0,  "y": 20}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 40},
        {"x": 0,  "y": 40}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0, "end": 0}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 60, "y": 0},
        {"x": 60, "y": 20},
        {"x": 40, "y": 20},
        {"x": 40, "y": 40},
        {"x": 20, "y": 40},
        {"x": 20, "y": 20},
        {"x": 0,  "y": 20}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 20, "y": 0},
        {"x": 60, "y": 0},
        {"x": 60, "y": 20},
        {"x": 40, "y": 20},
        {"x": 40, "y": 40},
        {"x": 0,  "y": 40},
        {"x": 0,  "y": 20},
        {"x": 20, "y": 20}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 60, "y": 20},
        {"x": 60, "y": 40},
        {"x": 20, "y": 40},
        {"x": 20, "y": 20},
        {"x": 0,  "y": 20}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 60},
        {"x": 20, "y": 60},
        {"x": 20, "y": 20},
        {"x": 0,  "y": 20}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 20, "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 60, "y": 20},
        {"x": 60, "y": 40},
        {"x": 40, "y": 40},
        {"x": 40, "y": 60},
        {"x": 20, "y": 60},
        {"x": 20, "y": 40},
        {"x": 0,  "y": 40},
        {"x": 0,  "y": 20},
        {"x": 20, "y": 20}
      ],
      "copies": 3,
      "allowed_rotations": [
        {"start": 0, "end": 0}
      ]
    }
  ]
}

Solve it with the command-line solver:

packingsolver_irregular \
        --input instance.json \
        --certificate solution.json \
        --time-limit 5
Basic example
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 180, 0, 160), copies=3)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (80, 0), (80, 20), (0, 20)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 40), (0, 40)]),
        allowed_rotations=[(0, 0, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (60, 0), (60, 20), (40, 20), (40, 40), (20, 40), (20, 20), (0, 20)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(20, 0), (60, 0), (60, 20), (40, 20), (40, 40), (0, 40), (0, 20), (20, 20)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (60, 20), (60, 40), (20, 40), (20, 20), (0, 20)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 60), (20, 60), (20, 20), (0, 20)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_shape([(20, 0), (40, 0), (40, 20), (60, 20), (60, 40), (40, 40), (40, 60), (20, 60), (20, 40), (0, 40), (0, 20), (20, 20)]),
        allowed_rotations=[(0, 0, False)],
        copies=3,
)
instance = instance_builder.build()

Solve it:

parameters = psi.OptimizeParameters()
parameters.time_limit = 5
output = psi.optimize(instance, parameters)
output.solution.write("solution.json")
Basic example
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 180, 0, 160));
instance_builder.set_bin_type_copies(bin_type_id, 3);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {80, 0}, {80, 20}, {0, 20}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 40}, {0, 40}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {60, 0}, {60, 20}, {40, 20}, {40, 40}, {20, 40}, {20, 20}, {0, 20}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{20, 0}, {60, 0}, {60, 20}, {40, 20}, {40, 40}, {0, 40}, {0, 20}, {20, 20}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {60, 20}, {60, 40}, {20, 40}, {20, 20}, {0, 20}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 60}, {20, 60}, {20, 20}, {0, 20}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{20, 0}, {40, 0}, {40, 20}, {60, 20}, {60, 40}, {40, 40}, {40, 60}, {20, 60}, {20, 40}, {0, 40}, {0, 20}, {20, 20}})}}});
instance_builder.set_item_type_copies(item_type_id, 3);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
Instance instance = instance_builder.build();

Solve it:

#include "packingsolver/irregular/optimize.hpp"

OptimizeParameters parameters;
parameters.timer.set_time_limit(5);
irregular::Output output = optimize(instance, parameters);
output.solution_pool.best().write("solution.json");

Link the target PackingSolver::irregular of the CMake project.

The solution:

_images/irregular_example_solution.png

Instance format

An instance is a JSON object with the following fields:

Field

Description

objective

Mandatory. One of knapsack, bin-packing, bin-packing-with-leftovers, open-dimension-x, open-dimension-y, open-dimension-xy, variable-sized-bin-packing, feasibility; see Objectives

parameters

An object with the optional fields item_item_minimum_spacing (see Item-item spacing), open_dimension_xy_aspect_ratio (the ratio height / width of the bin for the open-dimension-xy objective), and leftover_mode (the corner or side from which the leftover is measured, for the bin-packing-with-leftovers objective: bottom-left (default), bottom-right, top-left, top-right, left, right, bottom, top)

bin_types

Mandatory. The bin types (array)

item_types

Mandatory. The item types (array)

A shape is an object with one of the following type:

  • "rectangle": an axis-aligned rectangle; fields width, height, and the position of its bottom-left corner x, y (default: 0);

  • "circle": a circle; fields radius, and the position of its center x, y (default: 0);

  • "polygon": a polygon; field vertices, a list of {"x": ..., "y": ...} objects in counter-clockwise order;

  • "general": a shape made of line segments and circular arcs; field elements.

A bin type is a shape with the following fields:

Field

Description

copies

The number of copies of the bin type. Default: 1; -1 for an unlimited number of copies

copies_min

The minimum number of copies of the bin type to use, for the variable-sized bin packing objective. Default: 0

cost

The cost of a bin of this type, for the variable-sized bin packing objective. Default: the area of the bin

item_bin_minimum_spacing

See Item-bin and item-defect spacing. Default: 0

defects

See Defects. Default: none

An item type is a shape (with optional holes, see Holes), or has a field shapes, a list of such shapes for an item type made of several shapes; with the following fields:

Field

Description

copies

The number of copies of the item type. Default: 1; -1 for an unlimited number of copies (knapsack objective only)

copies_min

The minimum number of copies of the item type to pack, for the knapsack objective. Default: 0

profit

The profit of an item of this type, for the knapsack objective. Default: the area of the item

allowed_rotations

See Discrete item rotations. Default: no rotation

In Python, the shapes are built with psi.build_rectangle, psi.build_circle and psi.build_shape; the optional fields of the bin types and of the item types are keyword arguments of InstanceBuilder.add_bin_type and InstanceBuilder.add_item_type. In C++, the shapes are built with shape::build_rectangle, shape::build_circle and shape::build_shape, and the optional fields are set with the InstanceBuilder.set_bin_type_<field> and InstanceBuilder.set_item_type_<field> methods; the examples below show the exceptions.

Certificate format

The solution is written (command-line option --certificate, Solution.write) as a JSON file with a bins array. Each entry is a bin of the solution, with:

  • id: its bin type, and copies: the number of identical bins it stands for;

  • shape: its shape;

  • items: its items, each with id, its item type; x, y, the position of its reference point; angle, its rotation angle in degrees; mirror, whether it is mirrored; and item_shapes, its shapes once placed.

To visualize a solution, open it in the solution viewer, or run:

python3 scripts/visualize.py solution.json

Irregular bins

Bin types are not restricted to rectangles or circles: a bin can be any polygon, convex or not.

In the example below, the bin is the irregular 15-vertex polygon container from the smallest instance (jigsaw_cf3_xcd14250_28, 28 item types) of the jigsaw puzzle challenge of the CG:SHOP 2024 competition (see data/irregular/cgshop2024/). The objective is knapsack: select and place a subset of the items that maximizes the total profit inside the single irregular bin.

_images/irregular_irregular_bin.png

Open the example in the online solver: Irregular bins.

Irregular bins
{
  "objective": "knapsack",
  "bin_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 92.6256, "y": 128.3531},
        {"x": 3.5672, "y": 126.2956},
        {"x": 0, "y": 114.3809},
        {"x": 0.3378, "y": 67.8126},
        {"x": 4.9241, "y": 42.1571},
        {"x": 14.2976, "y": 27.7697},
        {"x": 25.3555, "y": 18.5055},
        {"x": 57.7973, "y": 1.2628},
        {"x": 86.4377, "y": 0},
        {"x": 128.9083, "y": 7.5745},
        {"x": 134.4293, "y": 20.4941},
        {"x": 137.9851, "y": 33.4021},
        {"x": 137.861, "y": 46.0358},
        {"x": 120.4953, "y": 107.695},
        {"x": 101.2384, "y": 123.6866}
      ]
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "profit": 27,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 41.3038},
        {"x": 2.4887, "y": 27.3817},
        {"x": 11.8623, "y": 12.9942},
        {"x": 22.9201, "y": 3.73},
        {"x": 29.9381, "y": 0},
        {"x": 0.6258, "y": 45.3627}
      ]
    },
    {
      "type": "polygon",
      "profit": 8,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 22.7493},
        {"x": 15.6342, "y": 0},
        {"x": 18.8068, "y": 0.5658},
        {"x": 8.5017, "y": 17.8852}
      ]
    },
    {
      "type": "polygon",
      "profit": 9,
      "copies": 1,
      "vertices": [
        {"x": 7.4737, "y": 16.236},
        {"x": 0, "y": 27.8017},
        {"x": 4.9703, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 6,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 18.6329},
        {"x": 0.0794, "y": 7.6745},
        {"x": 0.9344, "y": 2.8916},
        {"x": 2.8029, "y": 0},
        {"x": 5.2162, "y": 15.6485}
      ]
    },
    {
      "type": "polygon",
      "profit": 18,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 17.3193},
        {"x": 10.3052, "y": 0},
        {"x": 25.5266, "y": 2.7147}
      ]
    },
    {
      "type": "polygon",
      "profit": 22,
      "copies": 1,
      "vertices": [
        {"x": 0.158, "y": 34.8436},
        {"x": 0, "y": 33.8185},
        {"x": 0.2236, "y": 2.9843},
        {"x": 5.4398, "y": 0},
        {"x": 10.2772, "y": 31.3669}
      ]
    },
    {
      "type": "polygon",
      "profit": 53,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 73.892},
        {"x": 47.4383, "y": 4.8639},
        {"x": 55.9399, "y": 0},
        {"x": 15.0504, "y": 68.7207}
      ]
    },
    {
      "type": "polygon",
      "profit": 320,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 83.3256},
        {"x": 40.8897, "y": 14.6046},
        {"x": 66.4161, "y": 0},
        {"x": 69.6256, "y": 0.5723},
        {"x": 75.1467, "y": 13.492},
        {"x": 78.7026, "y": 26.3999},
        {"x": 78.5783, "y": 39.0337},
        {"x": 73.186, "y": 58.1795}
      ]
    },
    {
      "type": "polygon",
      "profit": 7,
      "copies": 1,
      "vertices": [
        {"x": 0.7706, "y": 0},
        {"x": 6.3609, "y": 36.2484},
        {"x": 0, "y": 15.0024},
        {"x": 0.1075, "y": 0.2277}
      ]
    },
    {
      "type": "polygon",
      "profit": 271,
      "copies": 1,
      "vertices": [
        {"x": 95.0527, "y": 0},
        {"x": 94.2508, "y": 2.847},
        {"x": 44.9999, "y": 62.9355},
        {"x": 0, "y": 61.8958},
        {"x": 21.8665, "y": 25.1459}
      ]
    },
    {
      "type": "polygon",
      "profit": 7,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 31.3111},
        {"x": 2.461, "y": 17.5458},
        {"x": 13.8921, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 379,
      "copies": 1,
      "vertices": [
        {"x": 18.6586, "y": 90.2811},
        {"x": 0, "y": 95.8605},
        {"x": 0.2034, "y": 67.8127},
        {"x": 4.1747, "y": 45.5984},
        {"x": 7.6477, "y": 37.7706},
        {"x": 14.1632, "y": 27.7698},
        {"x": 25.2211, "y": 18.5055},
        {"x": 57.663, "y": 1.2629},
        {"x": 86.3035, "y": 0},
        {"x": 96.4547, "y": 1.8105},
        {"x": 101.1058, "y": 3.2082}
      ]
    },
    {
      "type": "polygon",
      "profit": 16,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 19.8143},
        {"x": 0.1034, "y": 5.5795},
        {"x": 18.7619, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 91,
      "copies": 1,
      "vertices": [
        {"x": 33.6256, "y": 44.4653},
        {"x": 0, "y": 43.6884},
        {"x": 61.5786, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 318,
      "copies": 1,
      "vertices": [
        {"x": 73.554, "y": 65.0777},
        {"x": 68.7348, "y": 72.7436},
        {"x": 72.0766, "y": 65.5194},
        {"x": 0, "y": 87.0728},
        {"x": 82.4473, "y": 0},
        {"x": 99.9507, "y": 5.2598},
        {"x": 109.3774, "y": 8.0927}
      ]
    },
    {
      "type": "polygon",
      "profit": 10,
      "copies": 1,
      "vertices": [
        {"x": 18.8534, "y": 10.666},
        {"x": 0, "y": 5.0003},
        {"x": 2.3129, "y": 0},
        {"x": 20.3297, "y": 3.2134},
        {"x": 21.6283, "y": 6.2522}
      ]
    },
    {
      "type": "polygon",
      "profit": 196,
      "copies": 1,
      "vertices": [
        {"x": 83.0832, "y": 14.294},
        {"x": 21.5046, "y": 57.9824},
        {"x": 3.5673, "y": 57.5681},
        {"x": 0, "y": 45.6533},
        {"x": 0.0311, "y": 41.3678},
        {"x": 18.7928, "y": 21.5534},
        {"x": 90.8693, "y": 0},
        {"x": 87.5276, "y": 7.2243}
      ]
    },
    {
      "type": "polygon",
      "profit": 13,
      "copies": 1,
      "vertices": [
        {"x": 0.9204, "y": 0},
        {"x": 37.3197, "y": 6.4916},
        {"x": 35.0065, "y": 11.4917},
        {"x": 0, "y": 0.972}
      ]
    },
    {
      "type": "polygon",
      "profit": 24,
      "copies": 1,
      "vertices": [
        {"x": 27.9529, "y": 1.24},
        {"x": 29.7006, "y": 0},
        {"x": 8.4683, "y": 45.9011},
        {"x": 0, "y": 45.7053}
      ]
    },
    {
      "type": "polygon",
      "profit": 105,
      "copies": 1,
      "vertices": [
        {"x": 35.8233, "y": 0},
        {"x": 38.4971, "y": 0.8036},
        {"x": 42.0825, "y": 9.1934},
        {"x": 45.6383, "y": 22.1014},
        {"x": 45.5327, "y": 32.8441},
        {"x": 19.8897, "y": 51.0372},
        {"x": 0, "y": 56.9849}
      ]
    },
    {
      "type": "polygon",
      "profit": 145,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 10.2946},
        {"x": 27.5139, "y": 0.5808},
        {"x": 40.6862, "y": 0},
        {"x": 75.3401, "y": 6.1806},
        {"x": 74.7687, "y": 7.4476},
        {"x": 25.3231, "y": 36.6128}
      ]
    },
    {
      "type": "polygon",
      "profit": 190,
      "copies": 1,
      "vertices": [
        {"x": 0, "y": 16.4927},
        {"x": 77.124, "y": 0},
        {"x": 56.6183, "y": 45.4835},
        {"x": 24.3942, "y": 44.7391}
      ]
    },
    {
      "type": "polygon",
      "profit": 33,
      "copies": 1,
      "vertices": [
        {"x": 72.5541, "y": 32.0205},
        {"x": 0, "y": 72.6477},
        {"x": 0.0048, "y": 71.9852},
        {"x": 70.8182, "y": 30.2164},
        {"x": 120.2639, "y": 1.0513},
        {"x": 122.046, "y": 0},
        {"x": 127.8798, "y": 1.0405},
        {"x": 117.6985, "y": 6.7415}
      ]
    },
    {
      "type": "polygon",
      "profit": 8,
      "copies": 1,
      "vertices": [
        {"x": 9.569, "y": 10.9707},
        {"x": 0, "y": 13.0171},
        {"x": 0.0945, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 57,
      "copies": 1,
      "vertices": [
        {"x": 34.0616, "y": 28.2462},
        {"x": 3.5671, "y": 27.5418},
        {"x": 0, "y": 15.627},
        {"x": 0.0986, "y": 2.0462},
        {"x": 9.6675, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 192,
      "copies": 1,
      "vertices": [
        {"x": 70.8135, "y": 26.3181},
        {"x": 0, "y": 68.0871},
        {"x": 0.0768, "y": 57.5181},
        {"x": 4.663, "y": 31.8625},
        {"x": 14.0365, "y": 17.4752},
        {"x": 25.0943, "y": 8.2108},
        {"x": 30.7555, "y": 5.202},
        {"x": 45.4905, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 259,
      "copies": 1,
      "vertices": [
        {"x": 95.5976, "y": 23.8833},
        {"x": 86.5985, "y": 43.8442},
        {"x": 9.4746, "y": 60.3369},
        {"x": 0, "y": 49.3662},
        {"x": 0.0633, "y": 40.6271},
        {"x": 72.6174, "y": 0}
      ]
    },
    {
      "type": "polygon",
      "profit": 26,
      "copies": 1,
      "vertices": [
        {"x": 23.392, "y": 14.9587},
        {"x": 0, "y": 19.961},
        {"x": 8.9991, "y": 0}
      ]
    }
  ]
}
Irregular bins
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.Knapsack)
instance_builder.add_bin_type(
        psi.build_shape([(92.6256, 128.3531), (3.5672, 126.2956), (0, 114.3809), (0.3378, 67.8126), (4.9241, 42.1571), (14.2976, 27.7697), (25.3555, 18.5055), (57.7973, 1.2628), (86.4377, 0), (128.9083, 7.5745), (134.4293, 20.4941), (137.9851, 33.4021), (137.861, 46.0358), (120.4953, 107.695), (101.2384, 123.6866)]),
)
instance_builder.add_item_type(
        psi.build_shape([(0, 41.3038), (2.4887, 27.3817), (11.8623, 12.9942), (22.9201, 3.73), (29.9381, 0), (0.6258, 45.3627)]),
        profit=27,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 22.7493), (15.6342, 0), (18.8068, 0.5658), (8.5017, 17.8852)]),
        profit=8,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(7.4737, 16.236), (0, 27.8017), (4.9703, 0)]),
        profit=9,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 18.6329), (0.0794, 7.6745), (0.9344, 2.8916), (2.8029, 0), (5.2162, 15.6485)]),
        profit=6,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 17.3193), (10.3052, 0), (25.5266, 2.7147)]),
        profit=18,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0.158, 34.8436), (0, 33.8185), (0.2236, 2.9843), (5.4398, 0), (10.2772, 31.3669)]),
        profit=22,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 73.892), (47.4383, 4.8639), (55.9399, 0), (15.0504, 68.7207)]),
        profit=53,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 83.3256), (40.8897, 14.6046), (66.4161, 0), (69.6256, 0.5723), (75.1467, 13.492), (78.7026, 26.3999), (78.5783, 39.0337), (73.186, 58.1795)]),
        profit=320,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0.7706, 0), (6.3609, 36.2484), (0, 15.0024), (0.1075, 0.2277)]),
        profit=7,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(95.0527, 0), (94.2508, 2.847), (44.9999, 62.9355), (0, 61.8958), (21.8665, 25.1459)]),
        profit=271,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 31.3111), (2.461, 17.5458), (13.8921, 0)]),
        profit=7,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(18.6586, 90.2811), (0, 95.8605), (0.2034, 67.8127), (4.1747, 45.5984), (7.6477, 37.7706), (14.1632, 27.7698), (25.2211, 18.5055), (57.663, 1.2629), (86.3035, 0), (96.4547, 1.8105), (101.1058, 3.2082)]),
        profit=379,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 19.8143), (0.1034, 5.5795), (18.7619, 0)]),
        profit=16,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(33.6256, 44.4653), (0, 43.6884), (61.5786, 0)]),
        profit=91,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(73.554, 65.0777), (68.7348, 72.7436), (72.0766, 65.5194), (0, 87.0728), (82.4473, 0), (99.9507, 5.2598), (109.3774, 8.0927)]),
        profit=318,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(18.8534, 10.666), (0, 5.0003), (2.3129, 0), (20.3297, 3.2134), (21.6283, 6.2522)]),
        profit=10,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(83.0832, 14.294), (21.5046, 57.9824), (3.5673, 57.5681), (0, 45.6533), (0.0311, 41.3678), (18.7928, 21.5534), (90.8693, 0), (87.5276, 7.2243)]),
        profit=196,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0.9204, 0), (37.3197, 6.4916), (35.0065, 11.4917), (0, 0.972)]),
        profit=13,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(27.9529, 1.24), (29.7006, 0), (8.4683, 45.9011), (0, 45.7053)]),
        profit=24,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(35.8233, 0), (38.4971, 0.8036), (42.0825, 9.1934), (45.6383, 22.1014), (45.5327, 32.8441), (19.8897, 51.0372), (0, 56.9849)]),
        profit=105,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 10.2946), (27.5139, 0.5808), (40.6862, 0), (75.3401, 6.1806), (74.7687, 7.4476), (25.3231, 36.6128)]),
        profit=145,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 16.4927), (77.124, 0), (56.6183, 45.4835), (24.3942, 44.7391)]),
        profit=190,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(72.5541, 32.0205), (0, 72.6477), (0.0048, 71.9852), (70.8182, 30.2164), (120.2639, 1.0513), (122.046, 0), (127.8798, 1.0405), (117.6985, 6.7415)]),
        profit=33,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(9.569, 10.9707), (0, 13.0171), (0.0945, 0)]),
        profit=8,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(34.0616, 28.2462), (3.5671, 27.5418), (0, 15.627), (0.0986, 2.0462), (9.6675, 0)]),
        profit=57,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(70.8135, 26.3181), (0, 68.0871), (0.0768, 57.5181), (4.663, 31.8625), (14.0365, 17.4752), (25.0943, 8.2108), (30.7555, 5.202), (45.4905, 0)]),
        profit=192,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(95.5976, 23.8833), (86.5985, 43.8442), (9.4746, 60.3369), (0, 49.3662), (0.0633, 40.6271), (72.6174, 0)]),
        profit=259,
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(23.392, 14.9587), (0, 19.961), (8.9991, 0)]),
        profit=26,
        copies=1,
)
instance = instance_builder.build()
Irregular bins
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::Knapsack);
instance_builder.add_bin_type(shape::build_shape({{92.6256, 128.3531}, {3.5672, 126.2956}, {0, 114.3809}, {0.3378, 67.8126}, {4.9241, 42.1571}, {14.2976, 27.7697}, {25.3555, 18.5055}, {57.7973, 1.2628}, {86.4377, 0}, {128.9083, 7.5745}, {134.4293, 20.4941}, {137.9851, 33.4021}, {137.861, 46.0358}, {120.4953, 107.695}, {101.2384, 123.6866}}));
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 41.3038}, {2.4887, 27.3817}, {11.8623, 12.9942}, {22.9201, 3.73}, {29.9381, 0}, {0.6258, 45.3627}})}}});
instance_builder.set_item_type_profit(item_type_id, 27);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 22.7493}, {15.6342, 0}, {18.8068, 0.5658}, {8.5017, 17.8852}})}}});
instance_builder.set_item_type_profit(item_type_id, 8);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{7.4737, 16.236}, {0, 27.8017}, {4.9703, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 9);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 18.6329}, {0.0794, 7.6745}, {0.9344, 2.8916}, {2.8029, 0}, {5.2162, 15.6485}})}}});
instance_builder.set_item_type_profit(item_type_id, 6);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 17.3193}, {10.3052, 0}, {25.5266, 2.7147}})}}});
instance_builder.set_item_type_profit(item_type_id, 18);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0.158, 34.8436}, {0, 33.8185}, {0.2236, 2.9843}, {5.4398, 0}, {10.2772, 31.3669}})}}});
instance_builder.set_item_type_profit(item_type_id, 22);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 73.892}, {47.4383, 4.8639}, {55.9399, 0}, {15.0504, 68.7207}})}}});
instance_builder.set_item_type_profit(item_type_id, 53);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 83.3256}, {40.8897, 14.6046}, {66.4161, 0}, {69.6256, 0.5723}, {75.1467, 13.492}, {78.7026, 26.3999}, {78.5783, 39.0337}, {73.186, 58.1795}})}}});
instance_builder.set_item_type_profit(item_type_id, 320);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0.7706, 0}, {6.3609, 36.2484}, {0, 15.0024}, {0.1075, 0.2277}})}}});
instance_builder.set_item_type_profit(item_type_id, 7);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{95.0527, 0}, {94.2508, 2.847}, {44.9999, 62.9355}, {0, 61.8958}, {21.8665, 25.1459}})}}});
instance_builder.set_item_type_profit(item_type_id, 271);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 31.3111}, {2.461, 17.5458}, {13.8921, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 7);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{18.6586, 90.2811}, {0, 95.8605}, {0.2034, 67.8127}, {4.1747, 45.5984}, {7.6477, 37.7706}, {14.1632, 27.7698}, {25.2211, 18.5055}, {57.663, 1.2629}, {86.3035, 0}, {96.4547, 1.8105}, {101.1058, 3.2082}})}}});
instance_builder.set_item_type_profit(item_type_id, 379);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 19.8143}, {0.1034, 5.5795}, {18.7619, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 16);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{33.6256, 44.4653}, {0, 43.6884}, {61.5786, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 91);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{73.554, 65.0777}, {68.7348, 72.7436}, {72.0766, 65.5194}, {0, 87.0728}, {82.4473, 0}, {99.9507, 5.2598}, {109.3774, 8.0927}})}}});
instance_builder.set_item_type_profit(item_type_id, 318);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{18.8534, 10.666}, {0, 5.0003}, {2.3129, 0}, {20.3297, 3.2134}, {21.6283, 6.2522}})}}});
instance_builder.set_item_type_profit(item_type_id, 10);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{83.0832, 14.294}, {21.5046, 57.9824}, {3.5673, 57.5681}, {0, 45.6533}, {0.0311, 41.3678}, {18.7928, 21.5534}, {90.8693, 0}, {87.5276, 7.2243}})}}});
instance_builder.set_item_type_profit(item_type_id, 196);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0.9204, 0}, {37.3197, 6.4916}, {35.0065, 11.4917}, {0, 0.972}})}}});
instance_builder.set_item_type_profit(item_type_id, 13);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{27.9529, 1.24}, {29.7006, 0}, {8.4683, 45.9011}, {0, 45.7053}})}}});
instance_builder.set_item_type_profit(item_type_id, 24);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{35.8233, 0}, {38.4971, 0.8036}, {42.0825, 9.1934}, {45.6383, 22.1014}, {45.5327, 32.8441}, {19.8897, 51.0372}, {0, 56.9849}})}}});
instance_builder.set_item_type_profit(item_type_id, 105);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 10.2946}, {27.5139, 0.5808}, {40.6862, 0}, {75.3401, 6.1806}, {74.7687, 7.4476}, {25.3231, 36.6128}})}}});
instance_builder.set_item_type_profit(item_type_id, 145);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 16.4927}, {77.124, 0}, {56.6183, 45.4835}, {24.3942, 44.7391}})}}});
instance_builder.set_item_type_profit(item_type_id, 190);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{72.5541, 32.0205}, {0, 72.6477}, {0.0048, 71.9852}, {70.8182, 30.2164}, {120.2639, 1.0513}, {122.046, 0}, {127.8798, 1.0405}, {117.6985, 6.7415}})}}});
instance_builder.set_item_type_profit(item_type_id, 33);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{9.569, 10.9707}, {0, 13.0171}, {0.0945, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 8);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{34.0616, 28.2462}, {3.5671, 27.5418}, {0, 15.627}, {0.0986, 2.0462}, {9.6675, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 57);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{70.8135, 26.3181}, {0, 68.0871}, {0.0768, 57.5181}, {4.663, 31.8625}, {14.0365, 17.4752}, {25.0943, 8.2108}, {30.7555, 5.202}, {45.4905, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 192);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{95.5976, 23.8833}, {86.5985, 43.8442}, {9.4746, 60.3369}, {0, 49.3662}, {0.0633, 40.6271}, {72.6174, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 259);
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{23.392, 14.9587}, {0, 19.961}, {8.9991, 0}})}}});
instance_builder.set_item_type_profit(item_type_id, 26);
instance_builder.set_item_type_copies(item_type_id, 1);
Instance instance = instance_builder.build();

Discrete item rotations

The allowed_rotations field of an item type gives its allowed orientations. It is a list of rotation ranges, each with:

  • start: the start angle in degrees

  • end: the end angle in degrees

  • mirror: if true, the item is first mirrored about the Y axis, then rotated (default: false; see Item mirroring)

When start == end, only that exact angle is allowed. When start < end, any angle in [start, end] is allowed (continuous rotation range). If allowed_rotations is omitted, the items aren’t rotated.

In the Item types table, choose the Rotations of an item type: None, Half turns, Quarter turns, Any angle, or Custom ranges.

In an item type: "allowed_rotations": [{"start": 0, "end": 0}, {"start": 90, "end": 90}, {"start": 180, "end": 180}, {"start": 270, "end": 270}].

instance_builder.add_item_type(shape, allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)]): (start, end, mirror) tuples.

instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);, once for each rotation range.

In the example below, 2 copies of an L-shaped item must be packed into 60 × 60 bins (bin-packing objective). Without rotation, the two L-shapes cannot interlock, so 2 bins are needed. Allowing 90° rotations lets them interlock into a single bin.

Without rotation

With rotation

irregular_rotation_no

irregular_rotation_yes

Open the examples in the online solver: Item rotations: without rotations, Item rotations: with discrete rotations.

Item rotations: without rotations
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 60,
      "height": 60,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "copies": 2,
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "allowed_rotations": [
        {"start": 0, "end": 0}
      ]
    }
  ]
}
Item rotations: with discrete rotations
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 60,
      "height": 60,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "copies": 2,
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item rotations: without rotations
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 60, 0, 60), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False)],
        copies=2,
)
instance = instance_builder.build()
Item rotations: with discrete rotations
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 60, 0, 60), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance = instance_builder.build()
Item rotations: without rotations
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 60, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
Instance instance = instance_builder.build();
Item rotations: with discrete rotations
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 60, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();

Continuous item rotations

Setting start strictly lower than end in a rotation range allows any angle in between, instead of only a fixed set of discrete angles; {"start": 0, "end": 360} allows any angle. This is especially useful for irregular, non-rectangular shapes, where letting items nest at arbitrary angles (rather than only 0°/90°/180°/270°) can significantly reduce wasted space.

In the example below, 7 copies of a Christmas-tree-shaped item (from the Kaggle Santa 2025 competition) may be rotated by any angle and are packed with the open-dimension-xy objective, which finds the smallest bin (here constrained to a square, aspect ratio 1) containing all of them. Free rotation lets the trees nest into each other at odd angles rather than sitting axis-aligned, filling the bin far more tightly.

_images/irregular_rotation_continuous.png

Open the example in the online solver: Item rotations: continuous rotations.

Item rotations: continuous rotations
{
  "objective": "open-dimension-xy",
  "parameters": {
    "open_dimension_xy_aspect_ratio": 1
  },
  "bin_types": [
    {
      "type": "rectangle",
      "width": 300,
      "height": 300
    }
  ],
  "item_types": [
    {
      "copies": 7,
      "type": "polygon",
      "vertices": [
        {"x": -12.5, "y": 50.0},
        {"x": -6.25, "y": 50.0},
        {"x": -20.0, "y": 25.0},
        {"x": -10.0, "y": 25.0},
        {"x": -35.0, "y": 0.0},
        {"x": -7.5,  "y": 0.0},
        {"x": -7.5,  "y": -20.0},
        {"x": 7.5,   "y": -20.0},
        {"x": 7.5,   "y": 0.0},
        {"x": 35.0,  "y": 0.0},
        {"x": 10.0,  "y": 25.0},
        {"x": 20.0,  "y": 25.0},
        {"x": 6.25,  "y": 50.0},
        {"x": 12.5,  "y": 50.0},
        {"x": 0.0,   "y": 80.0}
      ],
      "allowed_rotations": [
        {"start": 0, "end": 360}
      ]
    }
  ]
}
Item rotations: continuous rotations
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.OpenDimensionXY)
instance_builder.set_open_dimension_xy_aspect_ratio(1)
instance_builder.add_bin_type(psi.build_rectangle(0, 300, 0, 300))
instance_builder.add_item_type(
        psi.build_shape([(-12.5, 50), (-6.25, 50), (-20, 25), (-10, 25), (-35, 0), (-7.5, 0), (-7.5, -20), (7.5, -20), (7.5, 0), (35, 0), (10, 25), (20, 25), (6.25, 50), (12.5, 50), (0, 80)]),
        allowed_rotations=[(0, 360, False)],
        copies=7,
)
instance = instance_builder.build()
Item rotations: continuous rotations
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::OpenDimensionXY);
instance_builder.set_open_dimension_xy_aspect_ratio(1);
instance_builder.add_bin_type(shape::build_rectangle(0, 300, 0, 300));
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{-12.5, 50}, {-6.25, 50}, {-20, 25}, {-10, 25}, {-35, 0}, {-7.5, 0}, {-7.5, -20}, {7.5, -20}, {7.5, 0}, {35, 0}, {10, 25}, {20, 25}, {6.25, 50}, {12.5, 50}, {0, 80}})}}});
instance_builder.set_item_type_copies(item_type_id, 7);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 360, false);
Instance instance = instance_builder.build();

Item mirroring

Each rotation range may set mirror: true, in which case the item is first mirrored about its Y axis, then rotated by the given angle range. Mirroring is off by default.

In the Item types table, check Mirror.

In an item type: "allowed_rotations": [{"start": 0, "end": 0}, {"start": 0, "end": 0, "mirror": true}].

instance_builder.add_item_type(shape, allowed_rotations=[(0, 0, False), (0, 0, True)])

instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, true);

Mirroring matters for shapes that are not symmetric: an L-shaped item is chiral, so it cannot be turned into its own mirror image by rotation alone. In the example below, 2 copies of an L-shaped item and a square item must be packed into 80 × 60 bins (bin-packing objective). Without mirroring, the two L-shapes (same orientation) leave two separate notches, too narrow for the square, so 2 bins are needed. Allowing the L-shapes to be mirrored turns one of them into a matching, opposite-handed piece: together the two L-shapes form a single wide notch that the square fits into exactly, so all three items pack into a single bin.

Without mirroring

With mirroring

irregular_mirroring_no

irregular_mirroring_yes

Open the examples in the online solver: Item mirroring: without mirroring, Item mirroring: with mirroring.

Item mirroring: without mirroring
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 80,
      "height": 60,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0, "end": 0}
      ]
    },
    {
      "type": "rectangle",
      "width": 38,
      "height": 38,
      "copies": 1,
      "allowed_rotations": [
        {"start": 0, "end": 0}
      ]
    }
  ]
}
Item mirroring: with mirroring
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 80,
      "height": 60,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0, "end": 0},
        {"start": 0, "end": 0, "mirror": true}
      ]
    },
    {
      "type": "rectangle",
      "width": 38,
      "height": 38,
      "copies": 1,
      "allowed_rotations": [
        {"start": 0, "end": 0}
      ]
    }
  ]
}
Item mirroring: without mirroring
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 80, 0, 60), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_rectangle(0, 38, 0, 38),
        allowed_rotations=[(0, 0, False)],
        copies=1,
)
instance = instance_builder.build()
Item mirroring: with mirroring
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 80, 0, 60), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (0, 0, True)],
        copies=2,
)
instance_builder.add_item_type(
        psi.build_rectangle(0, 38, 0, 38),
        allowed_rotations=[(0, 0, False)],
        copies=1,
)
instance = instance_builder.build()
Item mirroring: without mirroring
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 80, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_rectangle(0, 38, 0, 38)}}});
instance_builder.set_item_type_copies(item_type_id, 1);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
Instance instance = instance_builder.build();
Item mirroring: with mirroring
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 80, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, true);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_rectangle(0, 38, 0, 38)}}});
instance_builder.set_item_type_copies(item_type_id, 1);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
Instance instance = instance_builder.build();

Holes

The shape of an item type may have holes: a list of shapes inside it. Vertices must be in counter-clockwise order, for both the outer contour and the holes.

In the Item types table, click Add a hole below an item type.

In an item type: "holes": [{"type": "polygon", "vertices": [...]}].

instance_builder.add_item_type(psi.ShapeWithHoles(shape, [hole]))

instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape, {hole}}}});

In the example below, there are two item types: a pentagon (a 40 × 40 square with one corner cut off) and a small triangle, noticeably smaller than the hole so that the hole remains visible around it (bin-packing objective, 40 × 40 bins). Without a hole, the two items cannot share a bin, so 2 bins are needed. Cutting a triangular hole into the pentagon lets the small triangle nest inside it, so both items fit together in a single bin.

Without a hole

With a hole

irregular_holes_no

irregular_holes_yes

Open the examples in the online solver: Holes: without a hole, Holes: with a hole.

Holes: without a hole
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 40,
      "height": 40,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 30},
        {"x": 30, "y": 40},
        {"x": 0,  "y": 40}
      ],
      "copies": 1
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 12, "y": 0},
        {"x": 6,  "y": 12}
      ],
      "copies": 1
    }
  ]
}
Holes: with a hole
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 40,
      "height": 40,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 30},
        {"x": 30, "y": 40},
        {"x": 0,  "y": 40}
      ],
      "holes": [
        {
          "type": "polygon",
          "vertices": [
            {"x": 10, "y": 10},
            {"x": 30, "y": 10},
            {"x": 20, "y": 30}
          ]
        }
      ],
      "copies": 1
    },
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 12, "y": 0},
        {"x": 6,  "y": 12}
      ],
      "copies": 1
    }
  ]
}
Holes: without a hole
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 40, 0, 40), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 30), (30, 40), (0, 40)]),
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (12, 0), (6, 12)]),
        copies=1,
)
instance = instance_builder.build()
Holes: with a hole
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 40, 0, 40), copies=2)
instance_builder.add_item_type(
        psi.ShapeWithHoles(psi.build_shape([(0, 0), (40, 0), (40, 30), (30, 40), (0, 40)]), [psi.build_shape([(10, 10), (30, 10), (20, 30)])]),
        copies=1,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (12, 0), (6, 12)]),
        copies=1,
)
instance = instance_builder.build()
Holes: without a hole
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 40, 0, 40));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 30}, {30, 40}, {0, 40}})}}});
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {12, 0}, {6, 12}})}}});
instance_builder.set_item_type_copies(item_type_id, 1);
Instance instance = instance_builder.build();
Holes: with a hole
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 40, 0, 40));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 30}, {30, 40}, {0, 40}}), {shape::build_shape({{10, 10}, {30, 10}, {20, 30}})}}}});
instance_builder.set_item_type_copies(item_type_id, 1);
item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {12, 0}, {6, 12}})}}});
instance_builder.set_item_type_copies(item_type_id, 1);
Instance instance = instance_builder.build();

Defects

Defects are regions of a bin where items cannot be placed. They are given by the defects field of a bin type: a list of shapes (with optional holes), placed in the bin, each with the optional fields:

  • defect_type: a defect type identifier

  • item_defect_minimum_spacing: the minimum distance between the defect and the items (default: 0; see Item-bin and item-defect spacing)

In the Bin types table, click Add a defect below a bin type, and give its shape and its position.

In a bin type: "defects": [{"type": "rectangle", "x": 5, "y": 5, "width": 10, "height": 10}].

instance_builder.add_defect(bin_type_id, -1, psi.ShapeWithHoles(psi.build_rectangle(5, 15, 5, 15))): the bin type, the defect type (-1 for none), and the shape.

instance_builder.add_defect(bin_type_id, -1, shape::ShapeWithHoles{shape::build_rectangle(5, 15, 5, 15)});

In the example below, 2 copies of an L-shaped item must be packed into 60 × 60 bins (bin-packing objective). Without any defect, the two L-shapes interlock into a single bin, as in the rotation example above. Adding a small 10 × 10 defect in the corner where one of the L-shapes needs to sit breaks the interlocking pattern, and 2 bins become necessary.

Without a defect

With a defect

irregular_defects_no

irregular_defects_yes

Open the examples in the online solver: Defects: without a defect, Defects: with a defect.

Defects: without a defect
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 60,
      "height": 60,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Defects: with a defect
{
  "objective": "bin-packing",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 60,
      "height": 60,
      "copies": 1,
      "defects": [
        {
          "type": "rectangle",
          "x": 5,
          "y": 5,
          "width": 10,
          "height": 10
        }
      ]
    },
    {
      "type": "rectangle",
      "width": 60,
      "height": 60,
      "copies": 1
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 2,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Defects: without a defect
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
instance_builder.add_bin_type(psi.build_rectangle(0, 60, 0, 60), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance = instance_builder.build()
Defects: with a defect
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPacking)
bin_type_id = instance_builder.add_bin_type(psi.build_rectangle(0, 60, 0, 60), copies=1)
instance_builder.add_defect(bin_type_id, -1, psi.ShapeWithHoles(psi.build_rectangle(5, 15, 5, 15)))
instance_builder.add_bin_type(psi.build_rectangle(0, 60, 0, 60), copies=1)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=2,
)
instance = instance_builder.build()
Defects: without a defect
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 60, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();
Defects: with a defect
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPacking);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 60, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 1);
instance_builder.add_defect(bin_type_id, -1, shape::ShapeWithHoles{shape::build_rectangle(5, 15, 5, 15)});
bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 60, 0, 60));
instance_builder.set_bin_type_copies(bin_type_id, 1);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 2);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();

Item-item spacing

A minimum distance can be enforced between any two items, with the item_item_minimum_spacing field of the parameters object. Default: 0.

Fill the Minimum spacing between items below the objective.

In the instance: "parameters": {"item_item_minimum_spacing": 3}.

instance_builder.set_item_item_minimum_spacing(3)

instance_builder.set_item_item_minimum_spacing(3);

In the example below, 10 copies of an L-shaped item (with all 4 rotations allowed) must be packed into 160 × 100 bins (bin-packing-with-leftovers objective). Without any minimum spacing, the 10 L-shapes interlock exactly, filling a single bin with no waste at all. A minimum spacing of 3 between items breaks that tight interlocking pattern entirely: only 6 items fit per bin, each with a clearly visible gap around it, so a second bin is needed for the remaining 4.

Without spacing

With spacing

irregular_item_item_spacing_no

irregular_item_item_spacing_yes

Open the examples in the online solver: Item-item spacing: without spacing, Item-item spacing: with spacing.

Item-item spacing: without spacing
{
  "objective": "bin-packing-with-leftovers",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 160,
      "height": 100,
      "copies": 3
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 10,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item-item spacing: with spacing
{
  "objective": "bin-packing-with-leftovers",
  "parameters": {
    "item_item_minimum_spacing": 3
  },
  "bin_types": [
    {
      "type": "rectangle",
      "width": 160,
      "height": 100,
      "copies": 3
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 10,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item-item spacing: without spacing
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPackingWithLeftovers)
instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 100), copies=3)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=10,
)
instance = instance_builder.build()
Item-item spacing: with spacing
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPackingWithLeftovers)
instance_builder.set_item_item_minimum_spacing(3)
instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 100), copies=3)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=10,
)
instance = instance_builder.build()
Item-item spacing: without spacing
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 100));
instance_builder.set_bin_type_copies(bin_type_id, 3);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 10);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();
Item-item spacing: with spacing
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
instance_builder.set_item_item_minimum_spacing(3);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 100));
instance_builder.set_bin_type_copies(bin_type_id, 3);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 10);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();

Item-bin and item-defect spacing

A minimum distance can also be enforced between the items and the border of a bin, or between the items and a defect:

  • item_bin_minimum_spacing: the minimum distance between the items and the border of the bin, set on a bin type (default: 0)

  • item_defect_minimum_spacing: the minimum distance between the items and a defect, set on that defect (default: 0)

In the Bin types table, fill the Item spacing of a bin type, or the Spacing of a defect.

In a bin type: "item_bin_minimum_spacing": 3; in a defect: "item_defect_minimum_spacing": 5.

instance_builder.add_bin_type(shape, item_bin_minimum_spacing=3) and instance_builder.set_item_defect_minimum_spacing(bin_type_id, defect_id, 5)

instance_builder.set_item_bin_minimum_spacing(bin_type_id, 3); and instance_builder.set_item_defect_minimum_spacing(bin_type_id, defect_id, 5);

In the example below, the same 10 interlocking L-shapes as above are packed into 160 × 100 bins (bin-packing-with-leftovers objective), this time with no spacing between items. Without any minimum spacing, the 10 L-shapes still interlock exactly, filling a single bin with no waste. A minimum spacing of 3 between the items and the border of the bin leaves a clearly visible margin around the whole cluster of items — even though they still touch each other — and that margin alone is enough to break the tiling: only 6 items fit per bin, so a second bin is needed for the remaining 4.

Without item-bin spacing

With item-bin spacing

irregular_item_bin_spacing_no

irregular_item_bin_spacing_yes

Open the examples in the online solver: Item-bin spacing: without spacing, Item-bin spacing: with spacing.

Item-bin spacing: without spacing
{
  "objective": "bin-packing-with-leftovers",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 160,
      "height": 100,
      "copies": 3
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 10,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item-bin spacing: with spacing
{
  "objective": "bin-packing-with-leftovers",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 160,
      "height": 100,
      "copies": 3,
      "item_bin_minimum_spacing": 3
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 40, "y": 20},
        {"x": 20, "y": 20},
        {"x": 20, "y": 60},
        {"x": 0,  "y": 60}
      ],
      "copies": 10,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item-bin spacing: without spacing
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPackingWithLeftovers)
instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 100), copies=3)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=10,
)
instance = instance_builder.build()
Item-bin spacing: with spacing
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPackingWithLeftovers)
instance_builder.add_bin_type(
        psi.build_rectangle(0, 160, 0, 100),
        item_bin_minimum_spacing=3,
        copies=3,
)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (40, 20), (20, 20), (20, 60), (0, 60)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=10,
)
instance = instance_builder.build()
Item-bin spacing: without spacing
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 100));
instance_builder.set_bin_type_copies(bin_type_id, 3);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 10);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();
Item-bin spacing: with spacing
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 100));
instance_builder.set_item_bin_minimum_spacing(bin_type_id, 3);
instance_builder.set_bin_type_copies(bin_type_id, 3);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {40, 20}, {20, 20}, {20, 60}, {0, 60}})}}});
instance_builder.set_item_type_copies(item_type_id, 10);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();

The same idea applies to defects. In the example below, 23 copies of a right-triangle item (with legs of 40) are packed into 160 × 120 bins, one of which has a small triangular defect sitting well inside the bin, away from every border (bin-packing-with-leftovers objective). Without any minimum spacing, the items pack right up against the defect and all 23 fit into that single bin. A minimum spacing of 5 around the defect leaves a clearly visible gap around it, which is enough to push 3 items out, so a second (defect-free) bin is needed for them.

Without item-defect spacing

With item-defect spacing

irregular_item_defect_spacing_no

irregular_item_defect_spacing_yes

Open the examples in the online solver: Item-defect spacing: without spacing, Item-defect spacing: with spacing.

Item-defect spacing: without spacing
{
  "objective": "bin-packing-with-leftovers",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 160,
      "height": 120,
      "copies": 1,
      "defects": [
        {
          "type": "polygon",
          "vertices": [
            {"x": 40, "y": 40},
            {"x": 60, "y": 40},
            {"x": 40, "y": 60}
          ],
          "item_defect_minimum_spacing": 0
        }
      ]
    },
    {
      "type": "rectangle",
      "width": 160,
      "height": 120,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 0,  "y": 40}
      ],
      "copies": 23,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item-defect spacing: with spacing
{
  "objective": "bin-packing-with-leftovers",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 160,
      "height": 120,
      "copies": 1,
      "defects": [
        {
          "type": "polygon",
          "vertices": [
            {"x": 40, "y": 40},
            {"x": 60, "y": 40},
            {"x": 40, "y": 60}
          ],
          "item_defect_minimum_spacing": 5
        }
      ]
    },
    {
      "type": "rectangle",
      "width": 160,
      "height": 120,
      "copies": 2
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {"x": 0,  "y": 0},
        {"x": 40, "y": 0},
        {"x": 0,  "y": 40}
      ],
      "copies": 23,
      "allowed_rotations": [
        {"start": 0,   "end": 0},
        {"start": 90,  "end": 90},
        {"start": 180, "end": 180},
        {"start": 270, "end": 270}
      ]
    }
  ]
}
Item-defect spacing: without spacing
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPackingWithLeftovers)
bin_type_id = instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 120), copies=1)
defect_id = instance_builder.add_defect(bin_type_id, -1, psi.ShapeWithHoles(psi.build_shape([(40, 40), (60, 40), (40, 60)])))
instance_builder.set_item_defect_minimum_spacing(bin_type_id, defect_id, 0)
instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 120), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (0, 40)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=23,
)
instance = instance_builder.build()
Item-defect spacing: with spacing
import packingsolver.irregular as psi

instance_builder = psi.InstanceBuilder()
instance_builder.set_objective(psi.Objective.BinPackingWithLeftovers)
bin_type_id = instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 120), copies=1)
defect_id = instance_builder.add_defect(bin_type_id, -1, psi.ShapeWithHoles(psi.build_shape([(40, 40), (60, 40), (40, 60)])))
instance_builder.set_item_defect_minimum_spacing(bin_type_id, defect_id, 5)
instance_builder.add_bin_type(psi.build_rectangle(0, 160, 0, 120), copies=2)
instance_builder.add_item_type(
        psi.build_shape([(0, 0), (40, 0), (0, 40)]),
        allowed_rotations=[(0, 0, False), (90, 90, False), (180, 180, False), (270, 270, False)],
        copies=23,
)
instance = instance_builder.build()
Item-defect spacing: without spacing
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 120));
instance_builder.set_bin_type_copies(bin_type_id, 1);
DefectId defect_id = instance_builder.add_defect(bin_type_id, -1, shape::ShapeWithHoles{shape::build_shape({{40, 40}, {60, 40}, {40, 60}})});
instance_builder.set_item_defect_minimum_spacing(bin_type_id, defect_id, 0);
bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 120));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {0, 40}})}}});
instance_builder.set_item_type_copies(item_type_id, 23);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();
Item-defect spacing: with spacing
#include "packingsolver/irregular/instance_builder.hpp"

using namespace packingsolver;
using namespace packingsolver::irregular;

InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 120));
instance_builder.set_bin_type_copies(bin_type_id, 1);
DefectId defect_id = instance_builder.add_defect(bin_type_id, -1, shape::ShapeWithHoles{shape::build_shape({{40, 40}, {60, 40}, {40, 60}})});
instance_builder.set_item_defect_minimum_spacing(bin_type_id, defect_id, 5);
bin_type_id = instance_builder.add_bin_type(shape::build_rectangle(0, 160, 0, 120));
instance_builder.set_bin_type_copies(bin_type_id, 2);
ItemTypeId item_type_id = instance_builder.add_item_type({ItemShape{shape::ShapeWithHoles{shape::build_shape({{0, 0}, {40, 0}, {0, 40}})}}});
instance_builder.set_item_type_copies(item_type_id, 23);
instance_builder.add_item_type_allowed_rotation(item_type_id, 0, 0, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 90, 90, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 180, 180, false);
instance_builder.add_item_type_allowed_rotation(item_type_id, 270, 270, false);
Instance instance = instance_builder.build();