2D Irregular Nesting

2 min read•1 page

No-Fit Polygon (NFP for 2D Nesting): In laser cutting, sheet metal stamping, and CNC fabrication, minimizing scrap material requires packing irregular, non-convex parts tightly. The No-Fit Polygon (NFP) represents the exact locus of all positions where an orbiting polygon $B$ touches a stationary polygon $A$ without intersecting. If the reference origin of $B$ lies outside the NFP, collision is mathematically impossible.

NFP Orbital Invariant:

1. Minkowski Difference: NFP(A, B) = A ⊕ (-B). 2. Boundary Touch Locus: Orbiting B along the NFP boundary keeps parts in exact kissing contact. 3. Arbitrary Concavity: Handles re-entrant holes and inter-locking nesting patterns.

python

1import numpy as np
2
3def compute_nfp_minkowski(poly_a, poly_b):
4    """
5    Computes No-Fit Polygon (NFP) between stationary polygon A and orbiting polygon B.
6    NFP_AB = A Minkowski_Sum (-B).
7    If reference point of B is:
8    - Strictly inside NFP: A and B overlap (collision).
9    - On boundary of NFP: A and B touch without overlapping.
10    - Outside NFP: A and B are completely disjoint.
11    """
12    neg_b = -np.array(poly_b)
13    # Minkowski sum of A and (-B)
14    # In practice, computed via orbital sliding trace or slope diagram convolution
15    return "NFP Polygon Boundary"

Orbiting Position t

0.35

2 min read•1 page

Bottom-Left-Fill (BLF) Sheet Nesting: 2D strip packing is strongly NP-hard. In production, heuristic algorithms place parts sequentially, dropping each piece to the lowest available vertical level (minimum $Y$) and shifting it as far left as possible (minimum $X$). Combined with genetic angle permutation, this packs sheet stock to over 85% material utilization efficiency.

BLF Heuristic Rules:

1. Gravity Drop: Downward sliding along the Y axis until contacting existing parts or sheet bottom. 2. Leftward Compaction: Horizontal push towards the origin to close gaps between nested items. 3. Scrap Reduction: Consolidates offcut waste into a single contiguous reusable remnant sheet.

python

1def bottom_left_fill_nesting(parts, sheet_width, sheet_height):
2    """
3    Bottom-Left-Fill (BLF) nesting heuristic.
4    Places each incoming part at the lowest possible Y coordinate,
5    then slides it as far left (minimum X) as possible without colliding with prior parts.
6    """
7    placed_parts = []
8    
9    for part in parts:
10        best_pos = None
11        best_y = float('inf')
12        best_x = float('inf')
13        
14        # Search candidate positions on sheet
15        for candidate_pos in generate_candidate_positions(placed_parts, sheet_width, sheet_height):
16            if not overlaps_any(part, candidate_pos, placed_parts):
17                cx, cy = candidate_pos
18                if (cy < best_y) or (cy == best_y and cx < best_x):
19                    best_y = cy
20                    best_x = cx
21                    best_pos = candidate_pos
22                    
23        if best_pos:
24            placed_parts.append(part.translate(best_pos))
25            
26    return placed_parts

Packed Part Count

4.00