@iyulab/u-nesting

2D/3D Spatial Optimization Engine — High-performance nesting and bin packing via WebAssembly.

Installation

npm install @iyulab/u-nesting

The package resolves per environment via a conditional exports map:

| Environment | Entry | |---|---| | Bundlers (webpack, Vite, …) | ESM + WebAssembly ESM-integration (default condition) | | Node.js — require(), ESM import, CJS TS runners (tsx, ts-node) | CJS glue loading the wasm from the filesystem (node condition) — no loader hooks or flags |

Functions

| Function | Description | |----------|-------------| | solve_2d(json: string): string | Solve a 2D nesting problem | | solve_3d(json: string): string | Solve a 3D bin packing problem | | optimize_cutting_path(json: string): string | Optimize cutting path for placed parts | | version(): string | Get API version | | available_strategies(): string | List available strategies |

All functions use JSON string I/O.

Usage

2D Nesting

import { solve_2d } from '@iyulab/u-nesting';

const result = JSON.parse(solve_2d(JSON.stringify({
  geometries: [
    {
      id: "part-A",
      polygon: [[0,0], [100,0], [100,50], [0,50]],
      quantity: 3,
      allow_flip: false,
      rotations: [0, 90, 180, 270]
    },
    {
      id: "part-B",
      polygon: [[0,0], [60,0], [60,80], [0,80]],
      quantity: 2
    }
  ],
  boundary: { width: 500, height: 300 },
  config: {
    spacing: 2.0,
    strategy: "ga",
    population_size: 50,
    max_generations: 100,
    time_limit_ms: 5000
  }
})));

console.log(result);
// { success: true, placements: [...], utilization: 0.85, boundaries_used: 1, ... }

3D Bin Packing

import { solve_3d } from '@iyulab/u-nesting';

const result = JSON.parse(solve_3d(JSON.stringify({
  geometries: [
    { id: "box-1", dimensions: [10, 20, 15], quantity: 5 },
    { id: "box-2", dimensions: [8, 12, 10], quantity: 3, mass: 2.5 }
  ],
  boundary: {
    dimensions: [100, 100, 100],
    max_mass: 50.0,
    gravity: true,
    stability: true
  },
  config: {
    strategy: "ga",
    time_limit_ms: 3000
  }
})));

Cutting Path Optimization

import { solve_2d, optimize_cutting_path } from '@iyulab/u-nesting';

// First solve the nesting problem
const solveResult = JSON.parse(solve_2d(JSON.stringify({ /* ... */ })));

// Then optimize cutting path
const cutting = JSON.parse(optimize_cutting_path(JSON.stringify({
  geometries: [/* same geometries */],
  solve_result: solveResult,
  cutting_config: {
    kerf_width: 0.5,
    cut_speed: 100.0,
    rapid_speed: 500.0,
    exterior_direction: "cw",
    interior_direction: "ccw",
    time_limit_ms: 2000            // Bound the sequencing pass (see below)
  }
})));

optimize_cutting_path Request

interface CuttingRequest {
  geometries: Geometry[];          // Same shape as solve_2d geometries
  solve_result: SolveResult;       // The parsed result returned by solve_2d
  cutting_config?: {
    kerf_width?: number;           // Kerf compensation width (default: 0 = off)
    pierce_weight?: number;        // Pierce-count weight in cost (default: 10)
    max_2opt_iterations?: number;  // 2-opt iteration cap (default: 1000)
    time_limit_ms?: number;        // Wall-clock budget (ms) for the 2-opt phase.
                                   //   0 = unlimited. Default: 5000.
    rapid_speed?: number;          // For time estimation only (default: 1000)
    cut_speed?: number;            // For time estimation only (default: 100)
    exterior_direction?: string;   // "ccw" | "cw" | "auto" (default: "auto")
    interior_direction?: string;   // "ccw" | "cw" | "auto" (default: "auto")
    home_position?: [number, number]; // Head start/end point (default: [0,0])
    pierce_candidates?: number;    // Candidate pierce points per contour (default: 1)
    tolerance?: number;            // Geometric comparison tolerance (default: 1e-6)
  };
}

time_limit_ms (anytime bound). Cutting-path sequencing runs a nearest-neighbor construction followed by 2-opt improvement. The 2-opt neighborhood is O(n²) candidate moves per pass, so on large jobs (e.g. many identical parts filling a sheet) the iteration cap alone can run for seconds and block the calling thread — in the browser this freezes the whole tab. time_limit_ms caps that phase; when the budget is exceeded the best sequence found so far is returned. Cut order is a heuristic, so early termination never invalidates the result — it only trades some optimality for responsiveness. Set 0 to disable the wall-clock bound (native/batch callers only).

Input Schemas

solve_2d Request

interface Request2D {
  geometries: {
    id: string;
    polygon: [number, number][];       // Vertices (CCW)
    quantity?: number;                  // Default: 1
    allow_flip?: boolean;              // Default: false
    rotations?: number[];              // Allowed rotation angles in degrees
    holes?: [number, number][][];      // Interior holes
  }[];
  boundary: {
    width?: number;                    // Rectangle boundary
    height?: number;
    polygon?: [number, number][];      // Or custom polygon boundary
  };
  config?: {
    spacing?: number;                  // Part spacing (default: 0)
    margin?: number;                   // Boundary margin (default: 0)
    strategy?: string;                 // See available strategies
    population_size?: number;          // GA/BRKGA population (default: 50)
    max_generations?: number;          // GA/BRKGA generations (default: 100)
    crossover_rate?: number;           // Crossover rate (default: 0.8)
    mutation_rate?: number;            // Mutation rate (default: 0.1)
    time_limit_ms?: number;            // Time limit in ms
    target_utilization?: number;       // Stop early if reached
    multi_sheet?: boolean;             // Spill overflow onto extra sheets (default: false)
  };
}

Multi-Sheet Nesting

By default solve_2d packs into a single sheet; parts that do not fit become unplaced. Set config.multi_sheet: true to spill overflow onto additional sheets. Then:

• sheets_used reports how many sheets were needed.
• each placement's sheet_index selects its sheet.
• placement x/y are sheet-local — relative to that sheet's own origin — so you can render one panel per sheet without subtracting any offset.

const res = JSON.parse(solve_2d(JSON.stringify({
  geometries: [{ id: "part", polygon: [[0,0],[100,0],[100,100],[0,100]], quantity: 20 }],
  boundary: { width: 300, height: 300 },
  config: { strategy: "blf", multi_sheet: true }
})));
// res.sheets_used === 3, res.placements.length === 20, res.unplaced === []
// group placements by sheet_index to draw each sheet

Available 2D Strategies

| Strategy | Description | |----------|-------------| | blf | Bottom-Left Fill (fast, deterministic) | | nfp | NFP-Guided placement | | ga | Genetic Algorithm | | brkga | Biased Random-Key GA | | sa | Simulated Annealing | | gdrr | Guided Destroy-Repair-Refine | | alns | Adaptive Large Neighborhood Search |

Available 3D Strategies

| Strategy | Description | |----------|-------------| | blf | Bottom-Left Fill | | ep | Extreme Point | | ga | Genetic Algorithm | | brkga | Biased Random-Key GA | | sa | Simulated Annealing |

Response Schema

solve_2d Response

interface SolveResponse {
  version: string;
  success: boolean;
  error?: string;
  placements: {
    id: string;            // geometry id
    instance: number;      // 0-based copy index
    x: number;
    y: number;
    rotation: number;      // degrees
    sheet_index: number;   // 0-based sheet/bin index (see config.multi_sheet)
    flipped: boolean;      // mirrored
  }[];
  sheets_used: number;     // >1 only when config.multi_sheet is true
  utilization: number;
  total_requested: number; // Σ of every geometry's quantity (instance-level).
                           // unplaced instances = total_requested - placements.length
  unplaced: string[];      // deduplicated geometry ids (NOT per-instance), so
                           // unplaced.length under-reports the failed-instance count
  elapsed_ms: number;
}

solve_3d Response

interface Pack3DResponse {
  version: string;
  success: boolean;
  error?: string;
  placements: {
    id: string;            // geometry id
    instance: number;      // 0-based copy index
    bin_index: number;     // 0-based bin index
    x: number;
    y: number;
    z: number;             // depth/height position (min corner)
    orientation: string;   // axis permutation, e.g. "xyz", "xzy"
  }[];
  bins_used: number;
  utilization: number;
  total_requested: number; // Σ of every geometry's quantity (instance-level).
                           // unplaced instances = total_requested - placements.length
  unplaced: string[];      // deduplicated geometry ids (NOT per-instance), so
                           // unplaced.length under-reports the failed-instance count
  elapsed_ms: number;
}

Related

• u-geometry — Computational geometry primitives
• u-metaheur — Metaheuristic optimization framework