2D Irregular Nesting

1import numpy as np
2
3def compute_nfp_minkowski(poly_a, poly_b):
4    """
5    Computes convex No-Fit Polygon (NFP) between stationary polygon A and orbiting polygon B
6    via Minkowski difference: NFP(A, B) = A (+) (-B).
7    Sorts directed boundary edge vectors of A and (-B) by polar angle and assembles the loop.
8    """
9    a = np.asarray(poly_a, dtype=float)
10    b = -np.asarray(poly_b, dtype=float)
11
12    # Start at extreme bottom-left vertices of A and (-B)
13    idx_a = np.lexsort((a[:, 0], a[:, 1]))[0]
14    idx_b = np.lexsort((b[:, 0], b[:, 1]))[0]
15    start_pt = a[idx_a] + b[idx_b]
16
17    edges_a = np.roll(a, -1, axis=0) - a
18    edges_b = np.roll(b, -1, axis=0) - b
19    all_edges = np.vstack([edges_a, edges_b])
20
21    # Sort all edge vectors counter-clockwise by polar angle in [0, 2*pi)
22    angles = np.mod(np.arctan2(all_edges[:, 1], all_edges[:, 0]), 2.0 * np.pi)
23    sorted_edges = all_edges[np.argsort(angles)]
24
25    nfp_vertices = [start_pt]
26    for edge in sorted_edges[:-1]:
27        nfp_vertices.append(nfp_vertices[-1] + edge)
28    return np.array(nfp_vertices)

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