2D Irregular Nesting

Place irregular parts on stock material without overlap, minimizing waste.

Also called: 2D Irregular Nesting · 불규칙 형상 패킹 · 트루셰이프 네스팅 · Irregular shape packing · True-shape nesting

On this page12 sections

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?

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 16

uses method
2D Irregular Nesting to No-Fit Polygon
The No-Fit Polygon is the canonical geometric primitive for testing and resolving overlap between two irregular pieces in nesting.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial
  Citation details
  Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.
uses method
2D Irregular Nesting to Inner-Fit Polygon
Containment within the sheet boundary is encoded by the Inner-Fit Polygon, which together with the No-Fit Polygon's overlap test forms the two geometric axes of irregular-nesting placement.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial
  Citation details
  Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.
uses method
2D Irregular Nesting to Phi-functions
Overlap in irregular placement can also be encoded with phi-functions, an alternative to the No-Fit Polygon that enables nonlinear-programming formulations with continuous rotation.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialPhi-Functions for 2D Objects Formed by Line Segments and Circular Arcs
  Citation details
  Chernov, N., Stoyan, Yu., Romanova, T., Pankratov, A. (2012). Phi-Functions for 2D Objects Formed by Line Segments and Circular Arcs. Advances in Operations Research, vol. 2012. Phi-functions encode pairwise interaction analytically (positive = apart, zero = touching, negative = overlapping), enabling nonlinear-programming packing models with continuous rotation.
uses method
2D Irregular Nesting to Bottom-Left Fill
Bottom-left and bottom-left-fill placement rules are widely used constructive heuristics for irregular nesting layouts.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialOn genetic algorithms for the packing of polygons
  Citation details
  Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
uses method
2D Irregular Nesting to Genetic Algorithm
Irregular nesting has been reported with genetic-algorithm-based search over piece sequence and orientation, paired with a placement heuristic.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems
  Citation details
  Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
direct benchmark
2D Irregular Nesting to ESICUP
ESICUP distributes community instances for irregular (nesting) problems used to compare reported results.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: B — Survey / tutorial / communityESICUP — EURO Special Interest Group on Cutting and Packing
  Citation details
  ESICUP maintains community data sets and instances for cutting & packing, including irregular (nesting) instances.
adjacent benchmark
2D Irregular Nesting to 2DPackLib
2DPackLib is adjacent, not direct: it targets two-dimensional orthogonal (rectangular) cutting and packing, whereas irregular nesting handles arbitrary polygons. Relevant for shared packing methodology but not a like-for-like benchmark.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / official2DPackLib: a two-dimensional cutting and packing library
  Citation details
  Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
open-source implementation
2D Irregular Nesting to SVGnest
SVGnest is an open-source implementation of irregular nesting using No-Fit Polygon placement and a genetic algorithm.
EvidenceC · Vendor / case-reported
Sources
- Source grade: C — Vendor / case-reportedSVGnest (open-source nesting) (Opens in a new tab)
open-source implementation
2D Irregular Nesting to libnest2d
libnest2d is an open-source C++ library providing 2D nesting of arbitrary polygons.
EvidenceC · Vendor / case-reported
Sources
- Source grade: C — Vendor / case-reportedlibnest2d (open-source 2D nesting library) (Opens in a new tab)
open-source implementation
2D Irregular Nesting to Deepnest
Deepnest is an open-source desktop nesting app built on the SVGnest algorithm.
EvidenceC · Vendor / case-reported
Sources
- Source grade: C — Vendor / case-reportedDeepnest (open-source nesting app) (Opens in a new tab)
uses method
2D Irregular Nesting to Simulated Annealing
Irregular nesting has been reported with simulated-annealing search over piece sequence and orientation, paired with a placement heuristic.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems
  Citation details
  Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
uses method
2D Irregular Nesting to Tabu Search
Irregular nesting has also been reported with tabu-search-based search, using a placement heuristic as the inner loop.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems
  Citation details
  Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
uses method
2D Irregular Nesting to Reinforcement Learning
RL-based nesting has been reported in recent literature, but its industrial maturity and generalization are not verified here. [unverified — no grade-A source recorded]
EvidenceD · Expert inference
Sources
No source listed
uses method
2D Irregular Nesting to Minkowski Sum
Because the No-Fit Polygon used for overlap testing is computed as a Minkowski sum, irregular nesting directly relies on the Minkowski sum.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial
  Citation details
  Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.
generalizes
2D Irregular Nesting to 2D Strip Packing
Irregular nesting generalizes rectangular strip packing: rectangles are a special case of arbitrary polygons.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
shares method with
2D Irregular Nesting to 2D Bin Packing
Irregular nesting and 2D bin packing belong to the same cutting & packing family and share metaheuristic search methodology.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 2D Irregular Nesting to No-Fit Polygon	The No-Fit Polygon is the canonical geometric primitive for testing and resolving overlap between two irregular pieces in nesting.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial Citation details Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.
uses method 2D Irregular Nesting to Inner-Fit Polygon	Containment within the sheet boundary is encoded by the Inner-Fit Polygon, which together with the No-Fit Polygon's overlap test forms the two geometric axes of irregular-nesting placement.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial Citation details Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.
uses method 2D Irregular Nesting to Phi-functions	Overlap in irregular placement can also be encoded with phi-functions, an alternative to the No-Fit Polygon that enables nonlinear-programming formulations with continuous rotation.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialPhi-Functions for 2D Objects Formed by Line Segments and Circular Arcs Citation details Chernov, N., Stoyan, Yu., Romanova, T., Pankratov, A. (2012). Phi-Functions for 2D Objects Formed by Line Segments and Circular Arcs. Advances in Operations Research, vol. 2012. Phi-functions encode pairwise interaction analytically (positive = apart, zero = touching, negative = overlapping), enabling nonlinear-programming packing models with continuous rotation.
uses method 2D Irregular Nesting to Bottom-Left Fill	Bottom-left and bottom-left-fill placement rules are widely used constructive heuristics for irregular nesting layouts.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialOn genetic algorithms for the packing of polygons Citation details Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
uses method 2D Irregular Nesting to Genetic Algorithm	Irregular nesting has been reported with genetic-algorithm-based search over piece sequence and orientation, paired with a placement heuristic.	B · Survey / tutorial / community	—	Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems Citation details Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
direct benchmark 2D Irregular Nesting to ESICUP	ESICUP distributes community instances for irregular (nesting) problems used to compare reported results.	B · Survey / tutorial / community	—	Source grade: B — Survey / tutorial / communityESICUP — EURO Special Interest Group on Cutting and Packing Citation details ESICUP maintains community data sets and instances for cutting & packing, including irregular (nesting) instances.
adjacent benchmark 2D Irregular Nesting to 2DPackLib	2DPackLib is adjacent, not direct: it targets two-dimensional orthogonal (rectangular) cutting and packing, whereas irregular nesting handles arbitrary polygons. Relevant for shared packing methodology but not a like-for-like benchmark.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / official2DPackLib: a two-dimensional cutting and packing library Citation details Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
open-source implementation 2D Irregular Nesting to SVGnest	SVGnest is an open-source implementation of irregular nesting using No-Fit Polygon placement and a genetic algorithm.	C · Vendor / case-reported	—	Source grade: C — Vendor / case-reportedSVGnest (open-source nesting) (Opens in a new tab)
open-source implementation 2D Irregular Nesting to libnest2d	libnest2d is an open-source C++ library providing 2D nesting of arbitrary polygons.	C · Vendor / case-reported	—	Source grade: C — Vendor / case-reportedlibnest2d (open-source 2D nesting library) (Opens in a new tab)
open-source implementation 2D Irregular Nesting to Deepnest	Deepnest is an open-source desktop nesting app built on the SVGnest algorithm.	C · Vendor / case-reported	—	Source grade: C — Vendor / case-reportedDeepnest (open-source nesting app) (Opens in a new tab)
uses method 2D Irregular Nesting to Simulated Annealing	Irregular nesting has been reported with simulated-annealing search over piece sequence and orientation, paired with a placement heuristic.	B · Survey / tutorial / community	—	Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems Citation details Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
uses method 2D Irregular Nesting to Tabu Search	Irregular nesting has also been reported with tabu-search-based search, using a placement heuristic as the inner loop.	B · Survey / tutorial / community	—	Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems Citation details Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
uses method 2D Irregular Nesting to Reinforcement Learning	RL-based nesting has been reported in recent literature, but its industrial maturity and generalization are not verified here. [unverified — no grade-A source recorded]	D · Expert inference	—	No source listed
uses method 2D Irregular Nesting to Minkowski Sum	Because the No-Fit Polygon used for overlap testing is computed as a Minkowski sum, irregular nesting directly relies on the Minkowski sum.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial Citation details Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.
generalizes 2D Irregular Nesting to 2D Strip Packing	Irregular nesting generalizes rectangular strip packing: rectangles are a special case of arbitrary polygons.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
shares method with 2D Irregular Nesting to 2D Bin Packing	Irregular nesting and 2D bin packing belong to the same cutting & packing family and share metaheuristic search methodology.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships to this entry 4

shares method with
2D Strip Packing to 2D Irregular Nesting
Rectangle strip packing and irregular nesting share placement heuristics (e.g. bottom-left) and sit in the same cutting & packing family; rectangles are the orthogonal special case.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
industry instance of
Apparel Marker Making to 2D Irregular Nesting
Apparel marker making is a canonical industrial instance of irregular 2D nesting, with grain-line orientation constraints.
EvidenceB · Survey / tutorial / community
Equiv.E1 · same base, different side constraints
Sources
- Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems
  Citation details
  Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
industry instance of
Sheet-metal True-shape Nesting to 2D Irregular Nesting
Sheet-metal true-shape nesting is an industrial instance of irregular 2D nesting (vendor-reported framing).
EvidenceC · Vendor / case-reported
Equiv.E1 · same base, different side constraints
Sources
- Source grade: C — Vendor / case-reportedRADAN Radnest — sheet-metal nesting (vendor materials)
  Citation details
  Vendor-reported true-shape nesting for sheet-metal fabrication. [unverified specifics]
industry instance of
Shipbuilding Plate Nesting to 2D Irregular Nesting
Shipbuilding plate nesting is an industrial instance of irregular 2D nesting, adding manufacturability constraints (bevel, kerf, bridge, cutting path).
EvidenceB · Survey / tutorial / community
Equiv.E1 · same base, different side constraints
Sources
- Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems
  Citation details
  Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with 2D Strip Packing to 2D Irregular Nesting	Rectangle strip packing and irregular nesting share placement heuristics (e.g. bottom-left) and sit in the same cutting & packing family; rectangles are the orthogonal special case.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
industry instance of Apparel Marker Making to 2D Irregular Nesting	Apparel marker making is a canonical industrial instance of irregular 2D nesting, with grain-line orientation constraints.	B · Survey / tutorial / community	E1 · same base, different side constraints	Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems Citation details Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.
industry instance of Sheet-metal True-shape Nesting to 2D Irregular Nesting	Sheet-metal true-shape nesting is an industrial instance of irregular 2D nesting (vendor-reported framing).	C · Vendor / case-reported	E1 · same base, different side constraints	Source grade: C — Vendor / case-reportedRADAN Radnest — sheet-metal nesting (vendor materials) Citation details Vendor-reported true-shape nesting for sheet-metal fabrication. [unverified specifics]
industry instance of Shipbuilding Plate Nesting to 2D Irregular Nesting	Shipbuilding plate nesting is an industrial instance of irregular 2D nesting, adding manufacturability constraints (bevel, kerf, bridge, cutting path).	B · Survey / tutorial / community	E1 · same base, different side constraints	Source grade: B — Survey / tutorial / communityA tutorial in irregular shape packing problems Citation details Bennell, J.A., Oliveira, J.F. (2009). A tutorial in irregular shape packing problems. JORS 60(S1):S93-S105.