U-Nesting

2D/3D Spatial Optimization Engine - High-performance nesting and bin packing algorithms in Rust with C FFI support

U-Nesting provides domain-agnostic spatial optimization algorithms for 2D nesting and 3D bin packing problems:

• 2D Nesting - Optimal polygon placement on bounded surfaces
• 3D Bin Packing - Optimal volume arrangement in containers
• Genetic Algorithm - Metaheuristic optimization for complex layouts
• NFP/NFR Computation - Precise collision-free placement

U-Nesting is a pure computation engine with no domain-specific logic. Industry context (manufacturing, textile, logistics, etc.) is determined by consuming applications.

┌─────────────────────────────────────────┐
│         Consuming Applications          │
│  (Manufacturing, Textile, Logistics)    │
└─────────────────┬───────────────────────┘
                  │ Domain Context
                  ▼
┌─────────────────────────────────────────┐
│            U-Nesting Engine             │
│   Pure Geometry + Optimization Math     │
│      (Domain Agnostic)                  │
└─────────────────────────────────────────┘

• 🚀 High Performance - Written in Rust with parallel computation via Rayon
• 🎯 Domain Agnostic - Abstract models adaptable to any spatial optimization
• 📐 2D Support - Polygon nesting with NFP and holes (curves are supplied as polylines — flatten with a tolerance before submitting)
• 📦 3D Support - Box packing with physical constraints (gravity, stability, mass limits)
• 🔌 C FFI Support - Use from C#, Python, or any language with C bindings
• 📦 Zero Domain Dependencies - Pure mathematical optimization

A test dataset with 9 different polygon shapes and 50 total pieces on a 500×500 boundary:

Left: Original shapes | Right: Randomized input order

Optimization results using different algorithms on the same dataset (50 pieces, 500×500 boundary, 2 strips):

Algorithm	Result	Utilization	Time
GA (Genetic Algorithm)		70.6%	19.5s
GDRR (Goal-Driven Ruin & Recreate)		69.4%	30.5s
ALNS (Adaptive Large Neighborhood Search)		69.1%	30.2s
NFP (No-Fit Polygon Guided)		68.5%	5.0s
BRKGA (Biased Random-Key GA)		67.8%	23.5s
SA (Simulated Annealing)		64.1%	34.3s
BLF (Bottom-Left Fill)		60.0%	338ms

Note: Higher utilization = better material efficiency. Results may vary depending on piece shapes, quantities, and constraints. Run your own benchmarks to find the best algorithm for your specific use case.

These figures were captured before 0.11.0. Layouts and times differ from 0.11.0 on, which changed how placement follows the sheet's length, enforces spacing and margin, and honours time_limit_ms.

[dependencies]
u-nesting = "0.14"                             # 2D only (default)
u-nesting = { version = "0.14", features = ["3d"] } # 2D + 3D

[dependencies]
u-nesting = { git = "https://github.com/iyulab/u-nesting" }

use u_nesting::d2::{Boundary2D, Geometry2D, Nester2D};
use u_nesting::{Config, Solver, Strategy};

// Define geometries to place
let geometries = vec![
    Geometry2D::new("G1")
        .with_polygon(vec![(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)])
        .with_quantity(5)
        .with_rotations_deg(vec![0.0, 90.0, 180.0, 270.0]),
];

// Define boundary
let boundary = Boundary2D::rectangle(1000.0, 500.0);

// Configure and run
let config = Config::new()
    .with_strategy(Strategy::NfpGuided)
    .with_spacing(3.0)
    .with_margin(10.0);

let result = Nester2D::new(config).solve(&geometries, &boundary).unwrap();
assert_eq!(result.placements.len(), 5);
println!("Utilization: {:.1}%", result.utilization * 100.0);

use u_nesting::d3::{Boundary3D, Geometry3D, Packer3D};
use u_nesting::{Config, Solver, Strategy};

// Define geometries to place
let geometries = vec![
    Geometry3D::new("G1", 30.0, 20.0, 15.0)
        .with_quantity(10)
        .with_mass(2.5),
];

// Define boundary; gravity and stability are properties of the container
let boundary = Boundary3D::new(120.0, 80.0, 100.0)
    .with_max_mass(500.0)
    .with_gravity(true)
    .with_stability(true);

// Configure and run
let config = Config::new().with_strategy(Strategy::ExtremePoint);

let result = Packer3D::new(config).solve(&geometries, &boundary).unwrap();
assert_eq!(result.placements.len(), 10);
println!("Utilization: {:.1}%", result.utilization * 100.0);

u-nesting/
├── core/           # Shared abstractions
│   ├── traits.rs   # Geometry, Boundary, Solver
│   ├── ga.rs       # Genetic algorithm framework
│   ├── config.rs   # Common configuration
│   └── result.rs   # Unified result types
│
├── d2/             # 2D Module
│   ├── geometry.rs # Polygon, Point, Segment
│   ├── boundary.rs # 2D boundary definitions
│   ├── nfp.rs      # No Fit Polygon
│   ├── nester.rs   # Placement algorithms
│   └── io.rs       # Import/Export
│
├── d3/             # 3D Module
│   ├── geometry.rs # Box (Geometry3D)
│   ├── boundary.rs # 3D boundary definitions
│   ├── nfr.rs      # No Fit Region
│   ├── packer.rs   # Placement algorithms
│   ├── physics.rs  # Gravity, stability
│   └── io.rs       # Import/Export
│
└── ffi/            # C FFI interface

BLF, NFP, GA, BRKGA, SA, GDRR and ALNS (the optional exact MILP strategies are not covered here):

• spacing is the minimum distance between any two placed parts (it may be exceeded by at most 0.12 %, the allowance for rounded offsets). It does not apply to the boundary.
• margin is the minimum distance from any part to every boundary edge, including slanted edges of a polygon boundary and the edges of holes.
• Parts are placed inside the boundary polygon, never over a hole.
• Layouts advance along the boundary's longer side (the strip's length) and fill across the shorter one.
• time_limit_ms bounds the whole solve: the search strategies return the best layout found within it, plus the time of the bottom-left pass they are compared against.
• The search strategies (GA, BRKGA, SA, GDRR, ALNS) never return a layout that places fewer parts, or uses more length, than bottom-left fill on the same input — nor than greedy NFP placement, whenever that pass completes within the time limit (it runs first, inside the limit).

use u_nesting::{Config, Strategy};

// One `Config` serves 2D and 3D; every setting has a builder method.
let config = Config::new()
    .with_spacing(3.0)            // Minimum distance between geometries
    .with_margin(10.0)            // Minimum distance to the boundary edge
    .with_strategy(Strategy::GeneticAlgorithm)
    .with_time_limit(30_000)      // Whole solve, in milliseconds (0 = unlimited)
    .with_target_utilization(0.90)
    .with_seed(42);               // Reproducible runs

Rotation and mirroring are per geometry (Geometry2D::with_rotations_deg, with_flip), not part of the configuration.

use u_nesting::d3::geometry::OrientationConstraint;
use u_nesting::d3::{Boundary3D, Geometry3D};
use u_nesting::{Config, Strategy};

let config = Config::new()
    .with_margin(5.0)             // Boundary wall offset
    .with_strategy(Strategy::ExtremePoint)
    .with_time_limit(30_000);

// Physics lives on the container, orientation on each geometry.
let boundary = Boundary3D::new(120.0, 80.0, 100.0)
    .with_gravity(true)
    .with_stability(true);
let item = Geometry3D::new("crate", 30.0, 20.0, 15.0)
    .with_orientation(OrientationConstraint::Upright);

{
  "mode": "2d",
  "geometries": [
    {
      "id": "G1",
      "polygon": [[0,0], [100,0], [100,50], [0,50]],
      "quantity": 5,
      "rotations": [0, 90, 180, 270]
    }
  ],
  "boundary": { "width": 1000, "height": 500 },
  "config": { "spacing": 3.0, "strategy": "ga" }
}

{
  "mode": "3d",
  "geometries": [
    {
      "id": "G1",
      "dimensions": [30, 20, 15],
      "quantity": 10,
      "mass": 2.5
    }
  ],
  "boundary": { "dimensions": [120, 80, 100], "max_mass": 500 },
  "config": { "gravity": true, "stability": true }
}

extern int unesting_solve(const char* request_json, char** result_ptr);
extern void unesting_free_string(char* ptr);

// C# example
[LibraryImport("u_nesting")]
public static partial int unesting_solve(string request, out IntPtr result);

SolveResult {
    placements: Vec<Placement>,   // Position + orientation for each placed instance
    boundaries_used: usize,       // Number of boundaries needed
    utilization: f64,             // Area/volume efficiency (0.0 - 1.0)
    unplaced: Vec<String>,        // Deduplicated IDs of geometries that couldn't fit
    total_requested: usize,       // Σ quantity; unplaced instances = total_requested - placements.len()
    computation_time_ms: u64,
}

┌──────────────────────────────────────────────┐
│              U-Nesting Engine                │
├──────────────────────────────────────────────┤
│  Core: Traits, GA Framework, Config          │
├─────────────────────┬────────────────────────┤
│     2D Module       │       3D Module        │
├─────────────────────┼────────────────────────┤
│  Polygon, NFP       │  Box, NFR              │
│  BLF, GA Nester     │  EP, LAFF, GA Packer   │
└─────────────────────┴────────────────────────┘
          ▲                    ▲
          │                    │
┌─────────┴────────────────────┴───────────────┐
│           Consuming Applications             │
│  ┌─────────┐ ┌─────────┐ ┌─────────┐        │
│  │  Sheet  │ │  Mold   │ │Container│  ...   │
│  │  Metal  │ │  Design │ │ Loading │        │
│  └─────────┘ └─────────┘ └─────────┘        │
└──────────────────────────────────────────────┘

Licensed under either of:

• MIT license (LICENSE)

Contributions are welcome! Please read CONTRIBUTING.md for guidelines.

• u-numflow — Mathematical primitives
• u-metaheur — Metaheuristic optimization (GA, SA, ALNS, CP)
• u-geometry — Computational geometry
• u-schedule — Scheduling framework