outline area is not positive with item_item minimum_spacing and more than 16 copies

[Cabalist]

compute_boolean_operation_component: outline area is not positive with item spacing on a convex item with more than 16 copies

packingsolver_irregular aborts on a small bin-packing instance: one convex quadrilateral item type with 20 copies and
allowed rotations 0° and 180°, one 120 × 120 bin, and item_item_minimum_spacing 0.5. Without the spacing the same
instance solves.

Error: std::vector<ShapeWithHoles> (anonymous namespace)::compute_boolean_operation_component(const std::vector<ShapeWithHoles> &, ComputeSplittedElementsOutput &, ComponentId, BooleanOperation, ShapePos, const std::vector<ShapePos> &, ShapePos): outline area is not positive.

To reproduce

instance.json is below.

packingsolver_irregular --input instance.json --certificate certificate.json --output output.json --time-limit 5 --verbosity-level 0

Expected: a solution, exit status 0. Actual: the error above, exit status 1, on every run.

{
  "objective": "bin-packing",
  "parameters": {
    "item_item_minimum_spacing": 0.5
  },
  "bin_types": [
    {
      "type": "polygon",
      "vertices": [
        {
          "x": 0,
          "y": 0
        },
        {
          "x": 120,
          "y": 0
        },
        {
          "x": 120,
          "y": 120
        },
        {
          "x": 0,
          "y": 120
        }
      ],
      "copies": 1
    }
  ],
  "item_types": [
    {
      "type": "polygon",
      "vertices": [
        {
          "x": 0.0,
          "y": 97.0568427929
        },
        {
          "x": 0.0,
          "y": 5.772230645
        },
        {
          "x": 89.0755109172,
          "y": 45.6743883907
        },
        {
          "x": 89.0722060425,
          "y": 57.2207573307
        }
      ],
      "copies": 20,
      "allowed_rotations": [
        {
          "start": 0.0,
          "end": 0.0,
          "mirror": false
        },
        {
          "start": 180.0,
          "end": 180.0,
          "mirror": false
        }
      ]
    }
  ]
}

The item is a valid, convex, counter-clockwise polygon: area 4 579.78, sides 91.28, 97.60, 11.55 and 97.57, interior
angles 65.90°, 65.87°, 114.11° and 114.11°. Its two long sides are nearly parallel.

Build

• packingsolver c767f5428 (master, 2026-09-12) with shape 6ab9cb6, as bundled in the pyckingsolver 0.8.1 macOS arm64
  wheel (packingsolver_irregular, sha256 0de0d36226fe080435e7901400fccb02ac53052efde8dc3e7224eb0214a46bc2). I did
  not build it from source myself.
• Also reproduces on the earlier pyckingsolver 0.8.0 build of packingsolver 9917fcb0f (master, 2026-09-02).
• Platform: macOS on Apple silicon. Not tried elsewhere.

What changes the outcome

Each row changes one thing from the instance above, run with the c767f5428 binary.

Change	Result
none	crash (3 of 3 runs)
remove item_item_minimum_spacing	solves
spacing 0.01, 0.1, 0.25 or 1.0	solves
spacing 2.0	crash
12 or 16 copies	solves
17, 20 or 40 copies	crash
only rotation 0°, only rotation 180°, or no allowed_rotations	solves
bin 100 × 100, 150 × 300 or 200 × 200	crash
item vertices rounded to 8, 6 or 3 decimals	solves
--use-tree-search-periodic-packing 0	crash
--use-tree-search-periodic-packing 1	crash
12 copies with --use-tree-search-periodic-packing 1	solves

• The crash starts at 17 copies, which matches the more-than-16-copies threshold for periodic packing, but
  --use-tree-search-periodic-packing 0 does not avoid it.
• It depends on the exact coordinates and on the spacing value in a non-monotonic way (0.25 and 1.0 solve, 0.5 and 2.0
  crash), which looks like a numerical degeneracy in the spacing-inflated shape rather than anything about the item.

The check that fires is in shape's compute_boolean_operation_component (src/boolean_operations.cpp):
strictly_lesser(new_shape.shape.compute_area(), 0.0).

Related

• Error: compute_boolean_operation_component: outline area is not positive. #473 reported the same error with non-zero item spacing and was fixed by Bump the shape dependency's pinned commit #474 (shape bump, 2026-07-26). Both builds
  above are later, so this is either a case that fix did not cover or a regression.
• Fix compute_line_intersection missing crossings at shallow angles shape#56 fixed face area is not positive from crossings missed at shallow angles against near-parallel
  lines, and irregular: compute periodic packings on simplified item shapes #569 bumped shape to include it. The c767f5428 build includes both and still crashes.
• Irregular: Periodic packing doesn't take account of spacings parameters #495 added item spacing to periodic packing.

For scale: this came from nesting flapped triangular panels at 2 mm spacing. Of 101 solver inputs from that workload
that failed with this error on the 9917fcb0f build, 99 still fail with it on c767f5428.

[fontanf]

Hi,

Thank you for reporting the issue.

It should be fixed now

[Cabalist]

Fantastic! Thank you so much