Introduction

Libnest2D is a library and framework for the 2D bin packaging problem. Inspired from the SVGNest Javascript library the project is built from scratch in C++11. The library is written with a policy that it should be usable out of the box with a very simple interface but has to be customizable to the very core as well. The algorithms are defined in a header only fashion with templated geometry types. These geometries can have custom or already existing implementation to avoid copying or having unnecessary dependencies.

A default backend is provided if the user of the library just wants to use it out of the box without additional integration. This backend is reasonably fast and robust, being built on top of boost geometry and the polyclipping library. Usage of this default backend implies the dependency on these packages but its header only as well.

This software is currently under construction and lacks a throughout documentation and some essential algorithms as well. At this stage it works well for rectangles and convex closed polygons without considering holes and concavities.

Holes and non-convex polygons will be usable in the near future as well. The no fit polygon based placer module combined with the first fit selection strategy is now used in the PrusaSlicer application's arrangement feature. It uses local optimization techniques to find the best placement of each new item based on some features of the arrangement.

In the near future I would like to use machine learning to evaluate the placements and (or) the order if items in which they are placed and see what results can be obtained. This is a different approach than that of SVGnest which uses genetic algorithms to find better and better selection orders. Maybe the two approaches can be combined as well.

Integration

Using libnest2d in its current state implies the following dependencies:

• Clipper
• NLopt
• Boost Geometry

Integrating the library can be done in at least two ways. Use whichever suits your project the most.

1. The project source tree can be used as a subdirectory (or git submodule) in any other CMake based C++ project by using add_subdirectory() command in the parent level CMakeLists.txt file. This method ensures that the appropriate dependencies are detected or (optionally) downloaded and built if not found. This means that by default, if Clipper and NLopt are not installed, they will be downloaded into the CMake binary directory, built there and linked with your project if RP_ENABLE_DOWNLOADING is ON. Just add the target_link_library(<your_target> libnest2d_headeronly) line to your CMake build script. You can also compile the library with the selected dependencies into a static or shared library. To do this just disable the LIBNEST2D_HEADER_ONLY option in the CMake config.

2. Copying source files directly into a target project: The library can be header only and it is enough to just copy the content of the include directory or specify the location of these headers to the compiler. Be aware that in this case you are on your own regarding the geometry backend and optimizer selection. To keep things simple just define LIBNEST2D_GEOMETRIES_clipper and LIBNEST2D_OPTIMIZER_nlopt before including libnest2d.hpp. You will also need to link to these libraries manually.

3. (Recommended) Install the library after it was configured and "built" using cmake. An example how to do this in a bash command line in the checked out source dir:

   mkdir build
   cd build
   cmake .. -DLIBNEST2D_HEADER_ONLY=OFF -DCMAKE_INSTALL_PREFIX=<installdir>
   cmake --build . --target install

   Substitute <installdir> with your preferred location. If you don't have the required dependencies installed, you can add -DRP_ENABLE_DOWNLOADING=ON and make it download and build everything in the configure step. The built dependencies will be shared or static depending on BUILD_SHARED_LIBS. You can also specify the install location of the dependencies by setting RP_INSTALL_PREFIX variable. Alternatively you can (and should) install the dependencies first e.g. on Ubuntu:

   sudo apt install libboost-dev libpolyclipping-dev libnlopt-dev
   

Please note that the clipper backend still uses some algorithms from boost::geometry (header only). Later releases will probably get rid of the direct dependency.

The goal is to provide more geometry backends (e.g. boost only) and optimizer engines (e.g. optimlib) in the future. This would make it possible to use the already available dependencies in your project tree without including new ones.

Example

A simple example may be the best way to demonstrate the usage of the library.

#include <iostream>
#include <string>

// Here we include the libnest2d library
#include <libnest2d/libnest2d.hpp>

int main(int argc, const char* argv[]) {
    using namespace libnest2d;

    // Example polygons 
    std::vector<Item> input1(23,
    {
        {-5000000, 8954050},
        {5000000, 8954050},
        {5000000, -45949},
        {4972609, -568550},
        {3500000, -8954050},
        {-3500000, -8954050},
        {-4972609, -568550},
        {-5000000, -45949},
        {-5000000, 8954050},
    });
    std::vector<Item> input2(15,
    {
       {-11750000, 13057900},
       {-9807860, 15000000},
       {4392139, 24000000},
       {11750000, 24000000},
       {11750000, -24000000},
       {4392139, -24000000},
       {-9807860, -15000000},
       {-11750000, -13057900},
       {-11750000, 13057900},
    });

    std::vector<Item> input;
    input.insert(input.end(), input1.begin(), input1.end());
    input.insert(input.end(), input2.begin(), input2.end());

    // Perform the nesting with a box shaped bin
    size_t bins = nest(input, Box(150000000, 150000000));

    // Retrieve resulting geometries
    for(Item& r : input) {
        auto polygon = r.transformedShape();
        // render polygon...
    }

    return EXIT_SUCCESS;
}

It is worth to note that the type of the polygon carried by the Item objects is the type defined as a polygon by the geometry backend. In the example we use the clipper backend and clipper works with integer coordinates.

Of course it is possible to configure the nesting in every possible way. The nest function can take placer and selection algorithms as template arguments and their configuration as runtime arguments. It is also possible to pass a progress indication functor and a stop condition predicate to control the nesting process. For more details see the libnest2d.h header file.

Example output

Screenshot from Slic3r PE

For the record, Slic3r PE version 2.0 is now known as PrusaSlicer 2.0.

References

• SVGNest
• An effective heuristic for the two-dimensional irregular bin packing problem
• Complete and robust no-fit polygon generation for the irregular stock cutting problem
• Applying Meta-Heuristic Algorithms to the Nesting Problem Utilising the No Fit Polygon
• A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums