Skip to content
This repository has been archived by the owner on Mar 8, 2023. It is now read-only.

Latest commit

 

History

History
104 lines (72 loc) · 5.07 KB

README.md

File metadata and controls

104 lines (72 loc) · 5.07 KB

There are way better alternatives to libnfporb out by now that is why I'm going to archive this repository

License: GPL v3

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:

Start of NFP

Orbiting:

State 1 State 2 State 3 State 4

State 5 State 6 State 7 State 8

State 9

The resulting NFP is red:

nfp

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

concavities hole interlock jigsaw

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