U-Nesting

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

Overview

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

Design Philosophy

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)                  │
└─────────────────────────────────────────┘

Features

• 🚀 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

Demo

Sample Dataset

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

Algorithm Comparison

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

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.

Installation

From crates.io

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

From GitHub

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

Quick Start

2D 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);

3D Bin Packing

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);

Core Concepts

Module Structure

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

Algorithms

2D Algorithms

What the 2D heuristic and search strategies guarantee

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

3D Algorithms

Configuration

2D Configuration

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.

3D 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);

FFI Interface

JSON Request (2D)

{
  "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" }
}

JSON Request (3D)

{
  "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 }
}

C Interface

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);

Result Structure

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,
}

Performance

2D Benchmarks (GA, 500 generations)

3D Benchmarks (Extreme Point)

Architecture

┌──────────────────────────────────────────────┐
│              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 │        │
│  └─────────┘ └─────────┘ └─────────┘        │
└──────────────────────────────────────────────┘

License

Licensed under either of:

• MIT license (LICENSE)

Contributing

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

Related

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