sparrow

 

Sparrows are master weavers, crafting nests with intricate patterns. They utilize geometry and symmetry to ensure structural integrity and stability. By incorporating precise angles, lengths, and weaving patterns, these birds achieve a balance between strength and efficiency. (read more)

State-of-the-art nesting heuristic for 2D irregular strip packing

sparrow can be used to solve 2D irregular strip packing problems, also commonly referred to as nesting problems. This optimization algorithm builds on jagua-rs: a collision detection engine for 2D irregular cutting & packing problems.

This repository accompanies the paper: “An open-source heuristic to reboot 2D nesting research”.

sparrow in action

Nested by sparrow

Requirements

• Rust ≥ 1.90

Usage

General usage:

cargo run --release  -- \
    -i [path to input JSON, or a solution JSON] \
    -t [timelimit in seconds (default is 600s)]

The optimization process contains two distinct phases: exploration & compression. By default 80% of the timelimit is spent exploring and 20% is spent compressing. Pressing ‘Ctrl + C’ immediately moves the algorithm to the next phase, or terminates it.

All CLI options:

-i, --input <INPUT>              Path to the input JSON file, or a solution JSON file for warm starting
-t, --global-time <GLOBAL_TIME>  Set a global time limit (in seconds)
-e, --exploration <EXPLORATION>  Set the exploration phase time limit (in seconds)
-c, --compression <COMPRESSION>  Set the compression phase time limit (in seconds)
-x, --early-termination          Enable early termination of the optimization process
-s, --rng-seed <RNG_SEED>        Fixed seed for the random number generator
--workers <WORKERS>           Number of worker threads used by the separator
-h, --help                       Print help

Concrete example:

cargo run --release -- \
    -i data/input/swim.json

Live visualization

sparrow can show the search in a terminal dashboard alongside a live browser view of the current solution. The dashboard reports the current phase, progress, throughput, and logs. It continuously updates the SVG used by live_viewer.html:

cargo run --release --features=tui -- \
    -i data/input/swim.json

For the browser viewer without the dashboard, open live_viewer.html and enable the live_svg feature:

cargo run --release --features=live_svg -- \
    -i data/input/swim.json

Input

This repository uses the same JSON format as jagua-rs to represent instances.

sparrow 0.3.0 uses jagua-rs 1.0.0 from crates.io. This release changes the input format: every item requires orientation.rotation: {"mode":"discrete","angles":[0,180]}, {"mode":"stepped","step":90}, or {"mode":"continuous"}. Item IDs may be non-consecutive and are preserved in output. Set min_item_separation on the input instance; omission means zero. The CLI and solver configuration no longer override it. Legacy orientation fields and item holes are rejected. See the 1.0.0 release notes. These are also available in Oscar Oliveira’s OR-Datasets repository.

See jagua-rs README for details on the input format.

Output

Solutions are exported as SVG files in the output folder. The final SVG solution is saved as output/final_{name}.svg.

The SVG files serve both as a visual and exact representation of the solution. All original shapes and their exact transformations applied to them are defined within the SVG:

    ...
    <g id="items">
        <defs>
            <g id="item_0">...</g>
        </defs>
        <use transform="translate(1289.9116 1828.7717), rotate(-90)" xlink:href="#item_0">...</use>
    </g>
    ...

The SVG spec defines that the transformations are applied from right to left. So here the item is always first rotated and then translated.

By default, a range of intermediate (and infeasible) solutions will be exported in output/sols_{name}. To disable this and export only a single final solution, compile with the only_final_svg feature:

cargo run --release --features=only_final_svg -- \
    -i data/input/swim.json

The final solution is saved both in SVG and JSON format in output/final_{name}.svg and output/final_{name}.json, respectively.

Targeting maximum performance

This crate is highly optimized and is floating-point heavy. To enable the maximum performance, make sure target-cpu=native compiler flag is set, switch to the nightly toolchain (required for SIMD support) and enable the simd feature:

  export RUSTFLAGS='-C target-cpu=native'
  export RUSTUP_TOOLCHAIN=nightly
  cargo run --release --features=simd,only_final_svg -- \
      -i data/input/swim.json

Testing

A suite of debug_assert!() checks are included throughout the codebase to verify the correctness of the heuristic. These assertions are omitted in release builds to maximize performance, but are active in test builds. Some basic integration tests are included that run the heuristic on a few example instances while all assertions are active:

  cargo test

Alternatively you can enable all debug_assert!() checks in release builds by running the tests with the debug-release profile:

cargo run --profile debug-release -- \
    -i data/input/swim.json

Experiments

All solutions from the comparative experiments in the paper can be found at data/experiments. The accompanying README details how to perform an exact reproduction of any benchmark run.

Related Projects

• sparrow/studio: an interactive browser interface for sparrow
• spyrrow: a Python wrapper of sparrow
• sparrow-3d: a 3D adaptation of sparrow

Development

This repo is meant to remain a faithful representation of the algorithm described in the paper. However, I am open to pull requests containing bug fixes and speed/performance improvements as long as they do not alter the algorithm too significantly.

Feel free to fork the repository if you want to experiment with different heuristics or want to expand the functionality.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgements

 

This project began development at the CODeS research group of NUMA - KU Leuven and was funded by Research Foundation - Flanders (FWO) (grant number: 1S71222N) until October 2025.

Since then, I have continued the development and maintenance of the project independently. If you find sparrow useful and would like to support its continued development and maintenance, you can do so through GitHub Sponsors or Buy Me a Coffee.