irregular solver

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

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

The irregular solver takes as input a single JSON file and outputs:

• a solution JSON file; option: --certificate solution.json

The input file is a JSON file containing:

• The objective (objective field); possible values:

  • knapsack: maximize the profit of packed items in a single bin

  • bin-packing: pack all items using as few bins as possible

  • bin-packing-with-leftovers: bin packing, then maximize the leftover value in the last bin

  • open-dimension-x: minimize the X dimension of a single bin

  • open-dimension-y: minimize the Y dimension of a single bin

  • open-dimension-xy: minimize the area of a single bin (aspect ratio can be constrained)

  • variable-sized-bin-packing: pack all items minimizing total bin cost; bins may be used in any order

  • feasibility: determine whether a packing exists

• Optional global parameters (parameters field)

• A list of bin types (bin_types field)

• A list of item types (item_types field)

Each entry in bin_types describes one bin type. Common fields:

• copies: number of available copies of this bin type (default: 1)

• copies_min: minimum number of copies of this bin type that must be used (default: 0)

• cost: cost of one bin of this type, used for variable-sized bin packing (default: bin area)

Shape specification (one of the following), for both bin types and item types:

• type: "rectangle": axis-aligned rectangle

  • width (mandatory)

  • height (mandatory)

• type: "circle": circle

  • radius (mandatory)

• type: "polygon": arbitrary polygon

  • vertices (mandatory): list of {"x": ..., "y": ...} objects in counter-clockwise order

Each entry in item_types describes one item type. Common fields:

• copies: number of copies of this item type (default: 1)

• profit: profit of one item, used for knapsack (default: item area)

The output file is a JSON file with a single bins array. Each entry corresponds to one used bin and contains:

• id: bin type index

• copies: number of copies of this bin represented by this entry

• items: list of placed items, each with:

  • id: item type index

  • x, y: position of the item’s origin

  • angle: rotation angle in degrees

  • mirror: whether the item is mirrored

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 a 180×160 bin. 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.

instance.json

{
  "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:

packingsolver_irregular \
        --input instance.json \
        --certificate solution.json

=================================
          PackingSolver          
=================================

Problem type
------------
Irregular

Instance
--------
Objective:                    BinPacking
Number of item types:         8
Number of items:              17
Number of fixed items:        0
Number of bin types:          1
Number of bins:               3
Number of defects:            0
Number of rectangular items:  4
Number of circular items:     0
Item-item minimum spacing:    0
Open dim. XY aspect ratio:    -1
Total item area:              28400
Smallest item area:           1600
Largest item area:            2000
Total item profit:            28400
Largest item profit:          2000
Largest item copies:          3
Total bin area:               86400
Largest bin cost:             28800

        Time    Bins  Full waste (%)                         Comment
        ----    ----  --------------                         -------
       0.009       2           50.69                  TS g 1 d 0 q 1
       0.968       1            1.39                 TS g 1 d 0 q 94

Final statistics
----------------
Time (s):  0.977268

Solution
--------
Number of items:  17 / 17 (100%)
Item area:        28400 / 28400 (100%)
Item profit:      28400 / 28400 (100%)
Number of bins:   1 / 3 (33.3333%)
Bin area:         28800 / 86400 (33.3333%)
Bin cost:         28800
Full waste:       400
Full waste (%):   1.38889
X min:            0
Y min:            0
X max:            180
Y max:            160
Density X:        0.986111
Density Y:        0.986111
ODXY area:        28800
Leftover value:   0

The solution is written to solution.json.

A script is available to visualize the solution:

python3 scripts/visualize_irregular.py solution.json

Irregular bins

Bin types are not restricted to rectangles or circles: the type: "polygon" shape specification described above (see Basic usage) applies to bin_types exactly as it does to item_types, so 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 item types that maximizes total profit inside the single irregular bin.

instance.json (bin shape only; the 28 item types are omitted here for brevity)

{
  "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}
      ]
    }
  ],

packingsolver_irregular \
        --input instance.json \
        --certificate solution.json

=================================
          PackingSolver          
=================================

Problem type
------------
Irregular

Instance
--------
Objective:                    Knapsack
Number of item types:         28
Number of items:              28
Number of fixed items:        0
Number of bin types:          1
Number of bins:               1
Number of defects:            0
Number of rectangular items:  0
Number of circular items:     0
Item-item minimum spacing:    0
Open dim. XY aspect ratio:    -1
Total item area:              29548
Smallest item area:           57.0862
Largest item area:            4374.95
Total item profit:            2810
Largest item profit:          379
Largest item copies:          1
Total bin area:               14882.1
Largest bin cost:             14882.1

        Time        Profit   # items                         Comment
        ----        ------   -------                         -------
       0.005            27         1                  TS g 5 d 0 q 1
       0.005            53         1                  TS g 5 d 0 q 1
       0.008            91         1                  TS g 5 d 0 q 1
       0.012           318         1                  TS g 5 d 0 q 1
       0.017           320         1                  TS g 5 d 0 q 1
       0.021           379         1                  TS g 5 d 0 q 1
       0.025           387         2                  TS g 5 d 4 q 1
       0.028           406         2                  TS g 5 d 0 q 1
       0.031           411         2                  TS g 5 d 3 q 1
       0.033           436         2                  TS g 4 d 7 q 1
       0.037           591         2                  TS g 5 d 7 q 1
       0.039           699         2                  TS g 5 d 7 q 1
       0.042           708         3                  TS g 5 d 7 q 1
       0.046           709         3                  TS g 5 d 7 q 1
       0.050           712         3                  TS g 5 d 7 q 1
       0.052           726         3                  TS g 5 d 3 q 1
       0.056           790         3                  TS g 5 d 3 q 1
       0.059           889         3                  TS g 5 d 3 q 1
       0.064           895         3                  TS g 5 d 3 q 1
       0.068           968         3                  TS g 5 d 4 q 1
       0.074           976         4                  TS g 5 d 4 q 1
       0.078           986         4                  TS g 5 d 4 q 1
       0.080          1025         4                  TS g 5 d 4 q 1
       0.084          1059         4                  TS g 5 d 4 q 1
       0.089          1067         5                  TS g 5 d 4 q 1
       0.094          1077         5                  TS g 5 d 4 q 1
       0.099          1086         5                  TS g 5 d 4 q 1
       0.105          1094         6                  TS g 5 d 4 q 1
       0.109          1104         6                  TS g 5 d 4 q 1
       0.112          1110         7                  TS g 5 d 4 q 1
       0.115          1111         7                  TS g 5 d 4 q 1
       0.121          1117         8                  TS g 5 d 4 q 1
       0.127          1118         8                  TS g 5 d 4 q 1
       0.132          1126         9                  TS g 5 d 4 q 1
       0.137          1134        10                  TS g 5 d 4 q 1
       0.143          1138        18                  TS g 5 d 0 q 1
       0.159          1140         7                  TS g 5 d 0 q 2
       0.161          1158         8                  TS g 5 d 0 q 2
       0.168          1165         9                  TS g 5 d 0 q 2
       0.171          1166         9                  TS g 5 d 0 q 2
       0.178          1173         9                  TS g 5 d 0 q 2
       0.183          1179         9                  TS g 5 d 0 q 2
       0.188          1184         9                  TS g 5 d 0 q 2
       0.195          1187        10                  TS g 5 d 0 q 2
       0.200          1188        10                  TS g 5 d 0 q 2
       0.205          1195        10                  TS g 5 d 0 q 2
       0.211          1200        10                  TS g 5 d 0 q 2
       0.216          1206        10                  TS g 5 d 0 q 2
       0.221          1208        11                  TS g 5 d 0 q 2
       0.227          1210        11                  TS g 5 d 0 q 2
       0.232          1211        12                  TS g 5 d 0 q 2
       0.238          1218        12                  TS g 5 d 0 q 2
       0.244          1227        13                  TS g 5 d 0 q 2
       0.250          1234        14                  TS g 5 d 0 q 2
       0.255          1240        15                  TS g 5 d 0 q 2
       0.262          1241        15                  TS g 5 d 0 q 2
       0.272          1248        16                  TS g 5 d 0 q 2
       0.277          1255        17                  TS g 5 d 0 q 2
       0.387          1257        13                 TS g 5 d 4 q 13
       0.389          1258        14                 TS g 5 d 4 q 13
       0.439          1260        13                 TS g 5 d 4 q 19
       0.440          1262        13                 TS g 5 d 4 q 19
       0.448          1266        14                 TS g 5 d 4 q 19
       0.466          1270        17                 TS g 5 d 0 q 13
       0.667          1272        15                 TS g 5 d 0 q 28
       0.670          1278        16                 TS g 5 d 0 q 28
       1.490          1282        16                 TS g 5 d 0 q 94
       2.705          1285        15                TS g 5 d 0 q 211
       2.716          1286        15                TS g 5 d 0 q 211
       7.422          1291        16                TS g 5 d 4 q 711
       7.759          1292        16                TS g 5 d 0 q 711

Final statistics
----------------
Time (s):  10.0102

Solution
--------
Number of items:  16 / 28 (57.1429%)
Item area:        13463.4 / 29548 (45.5646%)
Item profit:      1292 / 2810 (45.9786%)
Number of bins:   1 / 1 (100%)
Bin area:         14882 / 14882 (100%)
Bin cost:         14882.1
Full waste:       1418.71
Full waste (%):   9.533
X min:            0.3378
Y min:            0.0363114
X max:            136.539
Y max:            128.211
Density X:        0.768231
Density Y:        0.76102
ODXY area:        17457.6
Leftover value:   204.936

Discrete item rotations

The allowed_rotations field on an item type controls which orientations are allowed. It is a list of rotation ranges, each with:

• start: start angle in degrees

• end: end angle in degrees

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

When start == end, only that exact angle is allowed. When start < end, any angle in [start, end] is allowed (continuous rotation range). When end == 360, a full 360° continuous rotation is allowed.

If allowed_rotations is omitted, the item is fixed at 0° (no rotation) by default.

Examples

Discrete 90° rotations only:

"allowed_rotations": [
  {"start": 0,   "end": 0},
  {"start": 90,  "end": 90},
  {"start": 180, "end": 180},
  {"start": 270, "end": 270}
]

Fixed orientation (no rotation):

"allowed_rotations": [
  {"start": 0, "end": 0}
]

Full 360° continuous rotation:

"allowed_rotations": [
  {"start": 0, "end": 360}
]

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
instance.json { "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} ] } ] }	instance.json { "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} ] } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json

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; end: 360 allows a full continuous rotation. 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 (allowed_rotations from 0° to 360°) 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.

instance.json

{
  "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}
      ]
    }
  ]
}

packingsolver_irregular \
        --input instance.json \
        --certificate solution.json

=================================
          PackingSolver          
=================================

Problem type
------------
Irregular

Instance
--------
Objective:                    OpenDimensionXY
Number of item types:         1
Number of items:              7
Number of fixed items:        0
Number of bin types:          1
Number of bins:               1
Number of defects:            0
Number of rectangular items:  0
Number of circular items:     0
Item-item minimum spacing:    0
Open dim. XY aspect ratio:    1
Total item area:              17193.8
Smallest item area:           2456.25
Largest item area:            2456.25
Total item profit:            17193.8
Largest item profit:          2456.25
Largest item copies:          7
Total bin area:               90000
Largest bin cost:             90000

        Time          XY           X           Y                         Comment
        ----          --           -           -                         -------
       0.017       49000     217.858     221.359          TS SF it 0 g 0 d 0 q 1
       0.035     48024.9     217.858     219.146          TS SF it 1 g 0 d 0 q 1
       0.056     47069.2     210.266     216.954          TS SF it 2 g 1 d 0 q 1
       0.074     42834.4     206.965     197.383          TS SF it 3 g 1 d 0 q 1
       0.092     40521.2     201.299     197.383          TS SF it 4 g 0 d 0 q 1
       0.107     39714.9     198.156     199.286          TS SF it 5 g 0 d 0 q 1
       0.121     38924.5     196.104     197.293          TS SF it 6 g 0 d 0 q 1
       0.135     38149.9      186.63      195.32          TS SF it 7 g 0 d 0 q 1
       0.148     36452.6     189.645     190.926          TS SF it 8 g 0 d 0 q 1
       0.164     35727.2     180.406     189.016          TS SF it 9 g 0 d 0 q 1
       0.179     34099.8     180.978     184.661         TS SF it 10 g 0 d 0 q 1
       0.193     33419.6     180.978      182.81         TS SF it 11 g 1 d 0 q 1
       0.210     32754.6     180.978     180.982         TS SF it 12 g 1 d 0 q 1
       0.357     32102.8     175.363     179.172         TS SF it 13 g 1 d 0 q 4
       0.535     31133.4     176.447     169.152         TS SF it 14 g 0 d 0 q 6
       3.027     29846.2     170.974     172.761        TS SF it 15 g 1 d 0 q 63
       7.912     29252.3     169.576     171.033        TS SF it 16 g 0 d 0 q 94

Final statistics
----------------
Time (s):  10.0034

Solution
--------
Number of items:  7 / 7 (100%)
Item area:        17193.8 / 17193.8 (100%)
Item profit:      17193.8 / 17193.8 (100%)
Number of bins:   1 / 1 (100%)
Bin area:         90000 / 90000 (100%)
Bin cost:         90000
Full waste:       72806.2
Full waste (%):   80.8958
X min:            -3.55271e-15
Y min:            0
X max:            169.576
Y max:            171.033
Density X:        0.337975
Density Y:        0.335096
ODXY area:        29252.3
Leftover value:   60996.9

Item mirroring

Each rotation range in allowed_rotations 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 (false) by default.

To allow both the original and mirrored orientation of an item at 0°:

"allowed_rotations": [
  {"start": 0,   "end": 0,   "mirror": false},
  {"start": 0,   "end": 0,   "mirror": 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 second L-shape to be mirrored turns it 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
instance.json { "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} ] } ] }	instance.json { "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} ] } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json

Holes

An item type’s polygon shape may have holes: a list of polygonal holes inside the shape. Each hole is a {"type": "polygon", "vertices": [...]} object. Vertices must be in counter-clockwise order, for both the outer contour and the holes.

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
instance.json { "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 } ] }	instance.json { "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 } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json

Defects

Defects are regions inside a bin where items cannot be placed. They are specified with the defects field on a bin type: a list of defects, each with:

• A shape (using the same shape fields as bin/item types: type: "rectangle", type: "circle", or type: "polygon"), placed at a position inside the bin

• defect_type: an optional defect type identifier

• item_defect_minimum_spacing: minimum distance between this defect and any item (default: 0; see Item-bin and item-defect spacing below)

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
instance.json { "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} ] } ] }	instance.json { "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} ] } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json

Item-item spacing

A minimum distance can be enforced between any two items, globally, via the item_item_minimum_spacing field of the optional parameters object (default: 0):

{
  "objective": "knapsack",
  "parameters": {
    "item_item_minimum_spacing": 2.0
  },
  "bin_types": [...],
  "item_types": [...]
}

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. Enforcing an item_item_minimum_spacing of 3 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
instance.json { "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} ] } ] }	instance.json { "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} ] } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json

Item-bin and item-defect spacing

A minimum distance can also be enforced between items and the bin boundary, or between items and defects.

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

• item_defect_minimum_spacing: minimum distance between items and a defect, set on that defect (default: 0; see Defects above)

{
  "objective": "knapsack",
  "bin_types": [
    {
      "type": "rectangle",
      "width": 1000,
      "height": 700,
      "item_bin_minimum_spacing": 5.0
    }
  ],
  "item_types": [...]
}

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. Enforcing an item_bin_minimum_spacing of 3 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
instance.json { "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} ] } ] }	instance.json { "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} ] } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json

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. Enforcing an item_defect_minimum_spacing of 5 on that 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
instance.json { "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} ] } ] }	instance.json { "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} ] } ] }
packingsolver_irregular \ --input instance.json \ --certificate solution.json	packingsolver_irregular \ --input instance.json \ --certificate solution.json