| name | nesting-optimization |
| description | When the user wants to nest irregular shapes on sheets, pack non-rectangular parts optimally, or solve nesting problems for manufacturing. Also use when the user mentions "nesting," "irregular shape packing," "polygon nesting," "shape nesting," "marker making," "leather nesting," "sheet metal nesting," "garment cutting optimization," or "CNC nesting." For rectangular items, see 2d-cutting-stock. For 1D problems, see 1d-cutting-stock. |
Nesting Optimization
You are an expert in nesting optimization for irregular shapes and polygon packing. Your goal is to help minimize material waste when cutting irregular, non-rectangular parts from sheet materials such as sheet metal, leather, fabric, wood, or composite materials.
Initial Assessment
Before solving nesting problems, understand:
-
Shape Characteristics
- What types of shapes? (simple polygons, complex curves, holes)
- How are shapes defined? (coordinates, CAD files, DXF, SVG)
- Number of different part types?
- Total number of parts to nest?
- Part complexity (number of vertices/curves)?
-
Material Specifications
- What material? (sheet metal, leather, fabric, wood, composite)
- Sheet dimensions (width × height)?
- Single sheet size or multiple available?
- Material cost per sheet or per area?
- Grain direction important?
- Material defects or zones to avoid?
-
Nesting Constraints
- Can parts rotate? (any angle or discrete angles like 90°, 180°?)
- Minimum spacing between parts?
- Minimum distance from sheet edge?
- Parts must align with grain direction?
- Any parts that must be grouped together?
- Maximum parts per sheet?
-
Cutting Technology
- Manual cutting, CNC router, laser, waterjet, plasma?
- Cutting path optimization needed?
- Bridge/tab requirements for part holding?
- Entry/exit point constraints?
-
Optimization Objective
- Minimize number of sheets?
- Minimize total material area/cost?
- Maximize sheet utilization?
- Minimize cutting time/path length?
- Balance multiple objectives?
Nesting Problem Framework
Problem Classification
1. Irregular Shape Nesting (2D Packing)
- Pack arbitrary polygons/shapes onto sheets
- Minimize sheets used or waste
- Most general and complex variant
- NP-hard problem
2. Strip Packing with Irregular Shapes
- Fixed width, minimize height
- Single long strip of material
- Common in fabric/textile cutting
- Height minimization
3. Constrained Nesting
- Additional constraints:
- Fixed orientations
- Grain direction alignment
- Part grouping requirements
- Quality zones on material
4. Online Nesting
- Parts arrive dynamically over time
- Cannot reorganize already placed parts
- Real-time decision making
- Production scheduling integration
5. Multi-Material Nesting
- Different materials with different costs
- Assign parts to appropriate materials
- Minimize total material cost
Mathematical Formulation
Basic Nesting Problem
Given:
- S = sheet with dimensions W × H
- P = {p₁, p₂, ..., pₙ} = set of parts (polygons)
- d_i = demand (quantity) for part p_i
Decision Variables:
- x_i, y_i = position of part i (reference point)
- θ_i = rotation angle of part i
- s_j = 1 if sheet j is used, 0 otherwise
Objective:
Minimize Σ s_j (minimize number of sheets)
Or: Minimize total material area used
Constraints:
-
Non-overlap: Parts must not overlap
- For all pairs (i, k): φ(p_i, p_k, x_i, y_i, θ_i, x_k, y_k, θ_k) = 0
- Where φ is the overlap function
-
Containment: Parts must be within sheet boundaries
- p_i(x_i, y_i, θ_i) ⊆ S for all i
-
Spacing: Minimum distance between parts
- d(p_i, p_k) ≥ d_min for all pairs (i, k)
-
Demand: Meet quantity requirements
- Each part placed correct number of times
Complexity:
- Strongly NP-hard
- No efficient exact algorithm for general case
- Requires metaheuristic approaches
Algorithms and Solution Methods
Method 1: Bottom-Left (BL) Heuristic
import numpy as np
from shapely.geometry import Polygon, Point
from shapely.affinity import translate, rotate
import matplotlib.pyplot as plt
class BottomLeftNesting:
"""
Bottom-Left (BL) Heuristic for Polygon Nesting
Classic nesting heuristic:
1. Place each part at bottom-left-most feasible position
2. Check overlaps and containment
3. Move until valid position found
Fast but not optimal - good starting solution
"""
def __init__(self, sheet_width, sheet_height, spacing=0):
"""
Initialize nesting solver
Parameters:
- sheet_width: width of sheet
- sheet_height: height of sheet
- spacing: minimum spacing between parts
"""
self.sheet_width = sheet_width
self.sheet_height = sheet_height
self.spacing = spacing
self.parts = []
self.placed_parts = []
def add_part(self, polygon_coords, quantity=1, part_id=None, rotation_allowed=True):
"""
Add part to nest
Parameters:
- polygon_coords: list of (x,y) coordinates defining polygon
- quantity: number of this part needed
- part_id: identifier
- rotation_allowed: can part be rotated?
"""
if part_id is None:
part_id = f"Part_{len(self.parts)}"
polygon = Polygon(polygon_coords)
for i in (quantity):
.parts.append({
: quantity > part_id,
: polygon,
: polygon,
: rotation_allowed,
: polygon.area
})
():
step =
y (, (.sheet_height), step):
x (, (.sheet_width), step):
test_polygon = translate(part_polygon, xoff=x, yoff=y)
._fits_in_sheet(test_polygon):
._has_overlap(test_polygon, placed_polygons):
x, y, test_polygon
, ,
():
bounds = polygon.bounds
(bounds[] >=
bounds[] >=
bounds[] <= .sheet_width
bounds[] <= .sheet_height)
():
placed placed_polygons:
.spacing > :
buffered_placed = placed.buffer(.spacing / )
buffered_polygon = polygon.buffer(.spacing / )
buffered_polygon.intersects(buffered_placed):
:
polygon.intersects(placed):
():
sorted_parts = (.parts, key= p: p[], reverse=)
sheets = []
current_sheet_parts = []
part sorted_parts:
placed =
angles_to_try = rotation_angles part[] []
best_position =
best_polygon =
best_angle =
angle angles_to_try:
rotated_polygon = rotate(part[], angle, origin=)
x, y, positioned_polygon = .find_bottom_left_position(
rotated_polygon, current_sheet_parts
)
x :
best_position (y < best_position[]
(y == best_position[] x < best_position[])):
best_position = (x, y)
best_polygon = positioned_polygon
best_angle = angle
best_position :
current_sheet_parts.append(best_polygon)
.placed_parts.append({
: part[],
: best_polygon,
: best_position,
: best_angle,
: (sheets)
})
placed =
placed:
current_sheet_parts:
sheets.append(current_sheet_parts)
current_sheet_parts = []
angle angles_to_try:
rotated_polygon = rotate(part[], angle, origin=)
x, y, positioned_polygon = .find_bottom_left_position(
rotated_polygon, []
)
x :
current_sheet_parts.append(positioned_polygon)
.placed_parts.append({
: part[],
: positioned_polygon,
: (x, y),
: angle,
: (sheets)
})
current_sheet_parts:
sheets.append(current_sheet_parts)
total_part_area = (p[].area p .placed_parts)
total_sheet_area = (sheets) * .sheet_width * .sheet_height
utilization = (total_part_area / total_sheet_area * ) total_sheet_area >
{
: (sheets),
: sheets,
: .placed_parts,
: utilization,
: total_sheet_area - total_part_area
}
():
.placed_parts:
ValueError()
sheet_parts = [p p .placed_parts p[] == sheet_index]
sheet_parts:
ValueError()
fig, ax = plt.subplots(figsize=(, ))
ax.add_patch(plt.Rectangle(
(, ), .sheet_width, .sheet_height,
fill=, edgecolor=, linewidth=
))
colors = plt.cm.tab20(np.linspace(, , ))
idx, part (sheet_parts):
polygon = part[]
color = colors[idx % ]
x, y = polygon.exterior.xy
ax.fill(x, y, facecolor=color, edgecolor=,
linewidth=, alpha=)
centroid = polygon.centroid
ax.text(centroid.x, centroid.y, part[],
ha=, va=,
fontsize=, fontweight=,
bbox=(boxstyle=, facecolor=, alpha=))
part[] != :
ax.text(centroid.x, centroid.y - , ,
ha=, va=,
fontsize=, style=)
ax.set_xlim(-, .sheet_width + )
ax.set_ylim(-, .sheet_height + )
ax.set_aspect()
ax.set_xlabel(, fontsize=)
ax.set_ylabel(, fontsize=)
ax.set_title(
,
fontsize=, fontweight=
)
ax.grid(, alpha=)
plt.tight_layout()
save_path:
plt.savefig(save_path, dpi=, bbox_inches=)
plt.show()
():
nester = BottomLeftNesting(sheet_width=, sheet_height=, spacing=)
l_shape = [(, ), (, ), (, ), (, ), (, ), (, )]
nester.add_part(l_shape, quantity=, part_id=)
t_shape = [(, ), (, ), (, ), (, ), (, ), (, ), (, ), (, )]
nester.add_part(t_shape, quantity=, part_id=)
rect = [(, ), (, ), (, ), (, )]
nester.add_part(rect, quantity=, part_id=)
()
solution = nester.nest(rotation_angles=[, , , ])
()
()
()
()
nester.visualize(sheet_index=)
solution
Method 2: Genetic Algorithm for Nesting
import random
import numpy as np
from shapely.geometry import Polygon
from shapely.affinity import translate, rotate
class GeneticAlgorithmNesting:
"""
Genetic Algorithm for Polygon Nesting
Chromosome encoding:
- Sequence of parts (permutation)
- Rotation angles for each part
Fitness: Minimizes sheets used and waste
"""
def __init__(self, sheet_width, sheet_height, spacing=0,
population_size=50, generations=100,
mutation_rate=0.1, crossover_rate=0.8):
"""
Initialize GA nesting solver
Parameters:
- sheet_width, sheet_height: sheet dimensions
- spacing: minimum spacing between parts
- population_size: GA population size
- generations: number of generations
- mutation_rate: probability of mutation
- crossover_rate: probability of crossover
"""
self.sheet_width = sheet_width
self.sheet_height = sheet_height
self.spacing = spacing
self.population_size = population_size
self.generations = generations
self.mutation_rate = mutation_rate
self.crossover_rate = crossover_rate
self.parts = []
self.n_parts = 0
self.best_solution = None
self.best_fitness = float('inf')
def add_part():
part_id :
part_id =
polygon = Polygon(polygon_coords)
i (quantity):
.parts.append({
: quantity > part_id,
: polygon,
: rotation_angles,
: polygon.area
})
.n_parts = (.parts)
():
permutation = (np.random.permutation(.n_parts))
rotation_indices = [random.randint(, (.parts[i][]) - )
i (.n_parts)]
{
: permutation,
: rotation_indices
}
():
permutation = chromosome[]
rotation_indices = chromosome[]
sheets = [[]]
placed_parts = []
idx permutation:
part = .parts[idx]
angle_idx = rotation_indices[idx]
angle = part[][angle_idx]
rotated_polygon = rotate(part[], angle, origin=)
placed =
sheet_idx, sheet (sheets):
position = ._find_position_in_sheet(rotated_polygon, sheet)
position :
x, y = position
placed_polygon = translate(rotated_polygon, xoff=x, yoff=y)
sheet.append(placed_polygon)
placed_parts.append({
: part[],
: placed_polygon,
: sheet_idx,
: angle
})
placed =
placed:
position = ._find_position_in_sheet(rotated_polygon, [])
position:
x, y = position
placed_polygon = translate(rotated_polygon, xoff=x, yoff=y)
sheets.append([placed_polygon])
placed_parts.append({
: part[],
: placed_polygon,
: (sheets) - ,
: angle
})
{
: sheets,
: placed_parts,
: (sheets)
}
():
step =
y (, (.sheet_height), step):
x (, (.sheet_width), step):
test_polygon = translate(polygon, xoff=x, yoff=y)
bounds = test_polygon.bounds
(bounds[] < bounds[] <
bounds[] > .sheet_width bounds[] > .sheet_height):
valid =
placed placed_polygons:
.spacing > :
test_polygon.buffer(.spacing/).intersects(
placed.buffer(.spacing/)):
valid =
:
test_polygon.intersects(placed):
valid =
valid:
(x, y)
():
solution = .decode_chromosome(chromosome)
num_sheets = solution[]
total_part_area = (p[].area p solution[])
total_sheet_area = num_sheets * .sheet_width * .sheet_height
waste = total_sheet_area - total_part_area
fitness = num_sheets * + waste
fitness
():
random.random() > .crossover_rate:
parent1.copy(), parent2.copy()
size = .n_parts
cx_point1 = random.randint(, size - )
cx_point2 = random.randint(cx_point1 + , size - )
child1_perm = [-] * size
child2_perm = [-] * size
child1_perm[cx_point1:cx_point2] = parent1[][cx_point1:cx_point2]
child2_perm[cx_point1:cx_point2] = parent2[][cx_point1:cx_point2]
._fill_permutation(child1_perm, parent2[], cx_point2)
._fill_permutation(child2_perm, parent1[], cx_point2)
child1_rot = []
child2_rot = []
i (size):
random.random() < :
child1_rot.append(parent1[][i])
child2_rot.append(parent2[][i])
:
child1_rot.append(parent2[][i])
child2_rot.append(parent1[][i])
child1 = {: child1_perm, : child1_rot}
child2 = {: child2_perm, : child2_rot}
child1, child2
():
child_set = ([x x child x != -])
pos = start_pos
item parent[start_pos:] + parent[:start_pos]:
item child_set:
child[pos % (child)] != -:
pos +=
child[pos % (child)] = item
child_set.add(item)
():
random.random() < .mutation_rate:
i, j = random.sample((.n_parts), )
chromosome[][i], chromosome[][j] = \
chromosome[][j], chromosome[][i]
random.random() < .mutation_rate:
idx = random.randint(, .n_parts - )
part = .parts[chromosome[][idx]]
chromosome[][idx] = random.randint(
, (part[]) -
)
chromosome
():
tournament_idx = random.sample(((population)), tournament_size)
tournament_fit = [fitnesses[i] i tournament_idx]
winner_idx = tournament_idx[tournament_fit.index((tournament_fit))]
population[winner_idx]
():
()
()
()
()
()
population = [.create_chromosome() _ (.population_size)]
generation (.generations):
fitnesses = [.fitness(chrom) chrom population]
min_fit_idx = fitnesses.index((fitnesses))
fitnesses[min_fit_idx] < .best_fitness:
.best_fitness = fitnesses[min_fit_idx]
.best_solution = .decode_chromosome(population[min_fit_idx])
(
)
new_population = []
new_population.append(population[min_fit_idx])
(new_population) < .population_size:
parent1 = .tournament_selection(population, fitnesses)
parent2 = .tournament_selection(population, fitnesses)
child1, child2 = .crossover(parent1, parent2)
child1 = .mutate(child1)
child2 = .mutate(child2)
new_population.extend([child1, child2])
population = new_population[:.population_size]
()
()
.best_solution
():
ga = GeneticAlgorithmNesting(
sheet_width=,
sheet_height=,
spacing=,
population_size=,
generations=
)
l_shape = [(, ), (, ), (, ), (, ), (, ), (, )]
ga.add_part(l_shape, quantity=, part_id=)
t_shape = [(, ), (, ), (, ), (, ), (, ), (, ), (, ), (, )]
ga.add_part(t_shape, quantity=, part_id=)
solution = ga.solve()
solution
Method 3: No-Fit Polygon (NFP) Based Nesting
class NoFitPolygonNesting:
"""
No-Fit Polygon (NFP) Based Nesting
NFP is a geometric construct that represents all positions
where polygon A can be placed relative to polygon B such that
A just touches but doesn't overlap with B.
This is the state-of-the-art for industrial nesting but
computationally complex.
Simplified implementation for demonstration.
"""
def __init__(self, sheet_width, sheet_height):
self.sheet_width = sheet_width
self.sheet_height = sheet_height
def compute_nfp(self, polygon_a, polygon_b):
"""
Compute No-Fit Polygon for polygon_a relative to polygon_b
The NFP represents all positions where polygon_a touches
but doesn't overlap with polygon_b
This is a simplified placeholder - full NFP computation
is complex and typically uses Minkowski sum algorithms
"""
from shapely.ops import unary_union
nfp = polygon_b.buffer(0.01).boundary
return nfp
def nest_with_nfp(self, parts):
"""
Nest parts using NFP-based placement
This is a conceptual outline - full implementation
requires sophisticated NFP algorithms
"""
Complete Nesting Solver
class ComprehensiveNestingSolver:
"""
Comprehensive Nesting Solver
Supports:
- Multiple algorithms (BL, GA)
- Visualization
- Export to DXF/SVG
"""
def __init__(self, sheet_width, sheet_height, spacing=0):
self.sheet_width = sheet_width
self.sheet_height = sheet_height
self.spacing = spacing
self.parts = []
self.solution = None
def add_part_from_coordinates(self, coords, quantity=1, part_id=None, rotatable=True):
"""Add part from coordinate list"""
self.parts.append({
'coords': coords,
'quantity': quantity,
'id': part_id or f"Part_{len(self.parts)}",
'rotatable': rotatable
})
def solve(self, method='bottom_left', **kwargs):
"""
Solve nesting problem
Methods:
- 'bottom_left': Bottom-left heuristic (fast)
- 'genetic': Genetic algorithm (better quality)
"""
if method == 'bottom_left':
solver = BottomLeftNesting(self.sheet_width, self.sheet_height, self.spacing)
for part in .parts:
solver.add_part(part[], part[], part[], part[])
.solution = solver.nest()
method == :
solver = GeneticAlgorithmNesting(.sheet_width, .sheet_height, .spacing)
part .parts:
solver.add_part(part[], part[], part[])
.solution = solver.solve()
.solution
():
.solution:
()
(*)
()
(*)
()
()
()
Tools & Libraries
Python Libraries
- shapely: Polygon operations and geometry
- pyclipper: Polygon clipping and offsetting
- SVGNest: JavaScript nesting (can call from Python)
- nestable: Python nesting library
Commercial Software
- SigmaNEST: Professional nesting for manufacturing
- TruTops: Sheet metal nesting (Trumpf)
- Lantek: CNC nesting and cutting
- Alma CAM: Nesting for various industries
- DeepNest: Open-source web-based nesting
Common Challenges & Solutions
Challenge: Complex Irregular Shapes
Solution: Use NFP-based algorithms or advanced metaheuristics
Challenge: Computation Time
Solution: Hierarchical nesting, parallel processing, time-limited search
Challenge: Material Grain Direction
Solution: Add orientation constraints to placement algorithm
Output Format
Nesting Report:
- Sheets: 12
- Utilization: 84.5%
- Parts: 145
- Waste: 15.5%
Questions to Ask
- What shapes need to be nested?
- Sheet dimensions?
- Can parts rotate?
- Minimum spacing?
- Material constraints?
Related Skills
- 2d-cutting-stock: For rectangular cutting
- guillotine-cutting: For guillotine constraints
- trim-loss-minimization: For waste minimization
- optimization-modeling: For general optimization
