U-Nesting

A high-performance 2D/3D spatial optimization engine for nesting and bin packing problems.

Features

• 2D Nesting: Optimal placement of irregular polygons on sheets
• 3D Bin Packing: Efficient box placement in containers
• Multiple Algorithms: BLF, NFP-guided, Genetic Algorithm, BRKGA, Simulated Annealing
• High Performance: Written in Rust with Python bindings
• Type Hints: Full type annotation support

Installation

pip install u-nesting

Quick Start

2D Nesting

import u_nesting

# Define polygons to nest
geometries = [
    {
        "id": "part1",
        "polygon": [[0, 0], [100, 0], [100, 50], [0, 50]],
        "quantity": 5,
        "rotations": [0, 90, 180, 270]
    },
    {
        "id": "triangle",
        "polygon": [[0, 0], [80, 0], [40, 60]],
        "quantity": 3
    }
]

# Define sheet boundary
boundary = {"width": 500, "height": 300}

# Configure solver
config = {
    "strategy": "nfp",      # Options: blf, nfp, ga, brkga, sa, gdrr, alns
    "spacing": 2.0,         # Gap between parts
    "time_limit_ms": 30000  # 30 second timeout
}

# Solve
result = u_nesting.solve_2d(geometries, boundary, config)

print(f"Utilization: {result['utilization']:.1%}")
print(f"Placed: {len(result['placements'])} items")
for p in result['placements']:
    print(f"  {p['geometry_id']}[{p['instance']}]: ({p['position'][0]:.1f}, {p['position'][1]:.1f})")

3D Bin Packing

import u_nesting

# Define boxes to pack
geometries = [
    {
        "id": "small",
        "dimensions": [20, 20, 20],
        "quantity": 10
    },
    {
        "id": "large",
        "dimensions": [40, 30, 25],
        "quantity": 5,
        "mass": 2.5  # Optional weight
    }
]

# Define container
boundary = {
    "dimensions": [200, 150, 100],
    "max_mass": 50.0,    # Optional mass limit
    "gravity": True,     # Stack from bottom
    "stability": True    # Require stable placement
}

# Configure solver
config = {
    "strategy": "ep",       # Extreme Point heuristic
    "time_limit_ms": 10000
}

# Solve
result = u_nesting.solve_3d(geometries, boundary, config)

print(f"Utilization: {result['utilization']:.1%}")
print(f"Containers used: {result['boundaries_used']}")

API Reference

solve_2d(geometries, boundary, config=None) -> dict

Solve a 2D nesting problem.

Parameters:

Keys are validated strictly: an unrecognized key in geometries, boundary or config raises ValueError naming it, rather than being ignored. A typo can therefore never silently fall back to a default. So does a value of the wrong type -- a count given as a fraction (2.5) included. A count outside its range (a negative one included) is a range refusal: a geometry's quantity below 1 comes back as code parameter_out_of_range with details parameter geometries[i].quantity and the geometry's id; a config count (population_size below 2, seed below 0, ...) raises ValueError naming the setting and its range.

What the solver refuses comes back in the result dict (success: False, code, details): an empty geometries list is empty_input (parameter geometries); a boundary side, dimension or max_mass of 0 or below is parameter_out_of_range naming it (boundary.width, boundary.height, boundary.dimensions[i], boundary.max_mass, with exclusive_min 0), and a setting is named by its path in config -- config.strategy for a strategy the dimension does not offer. A boundary given as both a rectangle and a polygon, or half of a rectangle, raises ValueError.

• geometries: List of geometry definitions
  • id (str): Unique identifier
  • polygon (list): Vertices as [[x, y], ...]
  • quantity (int): Number of copies (default: 1)
  • rotations (list): Allowed rotation angles in degrees — at least one; omit it for a fixed orientation (an empty list is refused)
  • allow_flip (bool): Allow horizontal flip
  • holes (list): Interior holes as list of polygons
• boundary: Sheet definition
  • width, height (float): Rectangle dimensions, OR
  • polygon (list): Custom boundary shape
• config: Solver configuration (optional)
  • strategy (str): "blf", "nfp", "ga", "brkga", "sa", "gdrr", "alns"
  • spacing (float): Gap between geometries
  • margin (float): Gap from boundary
  • time_limit_ms (int): Timeout in milliseconds
  • population_size (int): GA/BRKGA population, at least 2, run as given. Omitted, each search uses the size it is tuned for: 30 in 2D
  • max_generations (int): GA/BRKGA generation budget, at least 0, run as given. Omitted, 50 in 2D
  • seed (int): RNG seed of ga, brkga, sa, gdrr and alns. The same problem with the same seed returns the same layout when the run ends on its own budget rather than on the clock (a 2D search keeps a time budget of its own, 10-15 s, when time_limit_ms is 0)
  • multi_sheet (bool): Distribute overflow across multiple sheets (default: False). When True, parts that do not fit on one sheet spill onto extra sheets instead of becoming unplaced; boundaries_used reports the sheet count and each placement's boundary_index selects its sheet with sheet-local coordinates.

Returns: Dictionary with:

• success (bool): Whether solve succeeded
• placements (list): Placement results (instance-level)
• utilization (float): Area utilization ratio
• boundaries_used (int): Number of sheets used (>1 only when multi_sheet=True)
• total_requested (int): Σ of every geometry's quantity (instance-level total). Unplaced instance count = total_requested - len(placements)
• unplaced (list): Deduplicated IDs of items that couldn't be placed (not per-instance, so len(unplaced) under-reports the failed-instance count)
• computation_time_ms (int): Solve time
• error (str | None): Readable text when the solver refused the problem
• code (str | None): Stable reason for that refusal (invalid_geometry, duplicate_id, parameter_out_of_range, ...)
• details (dict | None): The values behind code (id, first, index, parameter, got, ...). A range gives each bounded side as min / max when the bound itself is accepted, or exclusive_min / exclusive_max when it is not

solve_3d(geometries, boundary, config=None) -> dict

Solve a 3D bin packing problem.

Parameters:

• geometries: List of box definitions
  • id (str): Unique identifier
  • dimensions (list): [width, depth, height]
  • quantity (int): Number of copies
  • mass (float): Weight, at least 0 (optional)
• boundary: Container definition
  • dimensions (list): [width, depth, height], each above 0
  • max_mass (float): Weight limit, above 0 (optional)
  • gravity (bool): Enable gravity constraint
  • stability (bool): Enable stability constraint
• config: Same as solve_2d but multi_sheet, which raises ValueError (one container, no sheets), and:
  • strategy: "blf", "ep", "ga", "brkga", "sa"
  • population_size / max_generations omitted: 100 / 500 for ga, 50 / 100 for brkga

Returns: Same structure as solve_2d

Strategy Selection Guide

Requirements

• Python 3.8+
• No additional dependencies

License

MIT License - see LICENSE for details.

Links

• GitHub Repository
• Issue Tracker
• Documentation