nesting-optimization

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:

1. 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)?

2. 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?

3. 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?

4. Cutting Technology

   • Manual cutting, CNC router, laser, waterjet, plasma?
   • Cutting path optimization needed?
   • Bridge/tab requirements for part holding?
   • Entry/exit point constraints?

5. 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:

1. 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

2. Containment: Parts must be within sheet boundaries

   • p_i(x_i, y_i, θ_i) ⊆ S for all i

3. Spacing: Minimum distance between parts

   • d(p_i, p_k) ≥ d_min for all pairs (i, k)

4. 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
        """

        # In practice, use libraries like:
        # - pyclipper for Minkowski operations
        # - shapely for polygon operations
        # - SVGNest algorithms

        # Simplified: just return boundary approximation
        from shapely.ops import unary_union

        # Buffer approach (approximation)
        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
        """

        # This would implement:
        # 1. Compute NFPs for all part pairs
        # 2. Use NFPs to find valid placement positions
        # 3. Optimize placement order and positions
        

          

---

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

1. What shapes need to be nested?
2. Sheet dimensions?
3. Can parts rotate?
4. Minimum spacing?
5. 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