2D Irregular Nesting

Definition

Place a set of irregular (non-rectangular) 2D parts onto stock material without overlap and within the sheet boundary, so that material utilization is maximized.

Example

Place two “L”-shaped parts by their bounding boxes and the two rectangles claim a large area. Rotate one part 180° and tuck it into the other's concave notch (interlocking), and the pair fits into a much smaller region of the same sheet. Reducing waste by using each part's true shape, rather than a rectangular approximation, is the central gain of irregular nesting.

Industrial aliases

The same geometric core appears under many industry names:

• Shipbuilding — plate nesting, steel plate part nesting
• Apparel — marker making, lay planning
• Sheet-metal fabrication — true-shape nesting

These are not loosely analogous; they are industrial instances of one abstract problem, differing mainly in their side constraints (see Cross-domain analogues).

Formal model

• Input: a set of polygonal pieces (possibly with holes), one or more stock sheets, allowed rotations per piece.
• Decision variables: placement position $(x_i, y_i)$ and orientation $\theta_i$ for each piece $i$.
• Objective: typically minimize used sheet length (strip variant) or the number of sheets, equivalently maximize utilization.
• Constraints: no pairwise overlap; containment within the sheet; allowed orientation set; (industry-dependent) spacing, grain, and cutting constraints.

Complexity

Irregular nesting is NP-hard. Exact methods exist for small instances, but industrial-scale instances are addressed with constructive heuristics and metaheuristics rather than guaranteed-optimal solvers. [grade B — survey-level]

Key constraints

• Overlap-free placement (the hard geometric core)
• Containment within the sheet boundary
• Rotation — free, a discrete set, or fixed (apparel grain lines often fix it)
• Material direction / grain (apparel, some composites)
• Kerf and cutting-path constraints (sheet-metal, shipbuilding)
• Bevel, bridge, common-cut manufacturability (shipbuilding)

Algorithm families

• Constructive — bottom-left / bottom-left-fill placement rules
• Geometry primitives — No-Fit Polygon (overlap test), Minkowski sums
• Metaheuristic — genetic algorithms, simulated annealing, tabu search over sequence/orientation, with a placement heuristic as the inner loop
• Learning-based — reinforcement-learning approaches have been reported in recent literature under benchmark conditions; maturity for industrial use is not established here. [unverified — no grade-A source recorded]

Benchmarks

• Direct: ESICUP community instances for irregular nesting.
• Adjacent: 2DPackLib — targets two-dimensional orthogonal cutting and packing, so it is methodologically related but not a direct irregular benchmark. Recorded explicitly as has_adjacent_benchmark.

Tools

Commercial true-shape nesting tools are vendor-reported (grade C) and connected to specific application problems rather than to the abstract problem directly — see the application pages for Shipbuilding Plate Nesting and Sheet-metal True-shape Nesting.

Cross-domain analogues

Shipbuilding plate nesting, apparel marker making, and sheet-metal true-shape nesting share the overlap-free placement core (an E1_variant relationship). What differs is the side constraints: shipbuilding adds cutting-path, bridge, and bevel manufacturability; apparel adds grain/orientation locking and pattern matching; sheet-metal adds kerf and common-line cutting. Recording the equivalence and the difference is the point — see the Evidence policy.

Open questions

• How far do learning-based methods generalize across industry side-constraint sets, beyond single-benchmark reports?
• Where is the boundary between "same problem, different constraints" (E1) and a genuinely distinct formulation?

Related nodes

The graph below shows direct (depth-1) neighbors. Methods are violet, benchmarks amber; the dashed edge marks the adjacent (not direct) benchmark.