There are way better alternatives to libnfporb out by now that is why I'm going to archive this repository
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 :)
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.
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).
The polygons:
Orbiting:
The resulting NFP is red:
Polygons can have concavities, holes, interlocks or might fit perfectly:
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.
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
//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
- 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