If you give me a real good reason i might be willing to give you permission to use it under a different license for a specific application. Real good reasons include the following (non-exhausive): the greater good, educational purpose and money :)

libnfporb

Implementation of a robust no-fit polygon generation in a C++ library using an orbiting approach.

Please note: The paper this implementation is based on has several bad assumptions that required me to "improvise". That means the code doesn't reflect the paper anymore and is running way slower than expected.

Description

The no-fit polygon optimization makes it possible to check for overlap (or non-overlapping touch) of two polygons with only 1 point in polygon check (by providing the set of non-overlapping placements). This library implements the orbiting approach to generate the no-fit polygon: Given two polygons A and B, A is the stationary one and B the orbiting one, B is slid as tightly as possibly around the edges of polygon A. During the orbiting a chosen reference point is tracked. By tracking the movement of the reference point a third polygon can be generated: the no-fit polygon.

Once the no-fit polygon has been generated it can be used to test for overlap by only checking if the reference point is inside the NFP (overlap) outside the NFP (no overlap) or exactly on the edge of the NFP (touch).

Examples:

The polygons:

Orbiting:

The resulting NFP is red:

Polygons can have concavities, holes, interlocks or might fit perfectly:

The Approach

The approch of this library is highly inspired by the scientific paper Complete and robust no-fit polygon generation for the irregular stock cutting problem and by Svgnest

Note that is wasn't completely possible to implement it as suggested in the paper because it had several shortcomings that prevent complete NFP generation on some of my test cases. Especially the termination criteria (reference point returns to first point of NFP) proved to be wrong (see: test-case rect). Also tracking of used edges can't be performed as suggested in the paper since there might be situations where no edge of A is traversed (see: test-case doublecon).

By default the library is using floating point as coordinate type but by defining the flag "LIBNFP_USE_RATIONAL" the library can be instructed to use arbitrary precision.

Build

The library has two dependencies: Boost Geometry and libgmp. If you have problems with Boost try version 1.65 (though I am using 1.76 at the moment). You need to install those first before building.

git clone https://github.com/kallaballa/libnfp.git
cd libnfp
make
sudo make install

Code Example

//uncomment next line to use arbitrary precision (slow)
//#define LIBNFP_USE_RATIONAL

//uncomment to enable debug mode
//#define NFP_DEBUG

#include "../src/libnfporb.hpp"

int main(int argc, char** argv) {
  using namespace libnfporb;
  polygon_t pA;
  polygon_t pB;
  //read polygons from wkt files
  read_wkt_polygon(argv[1], pA);
  read_wkt_polygon(argv[2], pB);

  //generate NFP of polygon A and polygon B and check the polygons for validity. 
  //When the third parameters is false validity check is skipped for a little performance increase
  nfp_t nfp = generate_nfp(pA, pB, true);
  
  //write a svg containing pA, pB and NFP
  write_svg("nfp.svg", pA, pB, nfp);
  return 0;
}

Run the example program:

examples/nfp data/crossing/A.wkt data/crossing/B.wkt

References

• https://dspace.vutbr.cz/xmlui/handle/11012/191851 (Master thesis: Software for efficient use of material in 2D machining)
• https://dspace.cuni.cz/bitstream/handle/20.500.11956/148383/130316114.pdf?sequence=1 (Master thesis: Reálná aplikace uspořádávání mnohoúhelníků)
• https://github.com/tamasmeszaros/libnest2d (2D irregular bin packaging and nesting library written in modern C++)
• https://github.com/Naimad1CZ/Online2DIrregularBPP (2D irregular BPP algorithm)
• https://github.com/martinhansdk/Flatpack (An addin for Fusion 360 which provides a better way to export DXF files for laser cutting)
• https://github.com/Papooch/WasteOptimiser