kallaballa / libnfporb Goto Github PK

View Code? Open in Web Editor NEW

102.0 14.0 30.0 699 KB

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

License: GNU General Public License v3.0

Makefile 0.42% C++ 99.13% Shell 0.40% Python 0.05%

nesting bin-packing no-fit-polygon

libnfporb's Introduction

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 :)

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

libnfporb's People

Contributors

Stargazers

Watchers

libnfporb's Issues

Investigate libnfporb performance

The orbital approach is expected to be very efficient, at least this is the impression I got after reading papers. However, in my experiments it is at least 2 orders of magnitude slower than CGAL's reduced convolution method. It would be nice to investigate if the slowness is a defect of the algorithm, or we can improve the implementation.

I've sent the test data privately. It consists of 36 polygons numbered from 0 to 35.
On the polygon pair (2, 18) libnfporb hangs indefinitely.
The following pairs: (3, 14), (3, 16), (3, 17), (8, 17), (12, 14), (12, 16), (12, 17), (15, 20), (21, 24), (24, 25), and (28, 30) end up throwing an exception with a message "Unable to complete outer nfp loop: 1".

Here is the performance comparison on pairs where libnfporb is the slowest compared to CGAL:

Run on (16 X 3874.93 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x8)
  L1 Instruction 32 KiB (x8)
  L2 Unified 1280 KiB (x8)
  L3 Unified 24576 KiB (x1)
Load Average: 0.93, 0.71, 0.68
---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
benchmark_cgal/24/27    4523011 ns      4520737 ns          155
benchmark_cgal/24/31    2876381 ns      2874814 ns          244
benchmark_cgal/24/26    1987337 ns      1986189 ns          352
benchmark_cgal/24/33    2306633 ns      2305401 ns          297
benchmark_cgal/23/25    1619837 ns      1619050 ns          430
benchmark_orb/24/27  5694047455 ns   5692760057 ns            1
benchmark_orb/24/31  3049576536 ns   3048878609 ns            1
benchmark_orb/24/26  1877847975 ns   1877413520 ns            1
benchmark_orb/24/33  2259959241 ns   2259457033 ns            1
benchmark_orb/23/25  1518002236 ns   1517642500 ns            1

Please explain find_feasible.hpp

find_feasible.hpp

//discard immediately intersecting translations
std::vector<TranslationVector> vectors;
for (const auto& v : potentialVectors) {
	bool discarded = false;
	for (const auto& sp : touchEdges) {
            ……
        }
}

May I ask what happened in the second loop? I don't understand. Sometimes the program discards the correct potential vectors. I am trying to figure out the logical flow of this code and fix it.
Please!!

Edge case false positive degenerate case

When having those 2 polygons:
POLYGON((20 10,20 30,30 30,30 10,40 20,40 30,30 40,60 40,60 80,0 80,20 40,10 30,10 20))
POLYGON((50 30,50 20,60 20,60 30))
The resulting NFP consists of 1 big loop (correct) and 1 degenerate point (wrong).

I can see why it's selected - all vertices of polygon B (sliding polygon) are touching vertices of the polygon A, but everything else (except one edge) from polygon B is directly inside the polygon A.

removeCoLinear makes polygon invalid

Attached is colinear.zip which causes the error

terminate called after throwing an instance of 'std::runtime_error'
  what():  Polygon A is invalid: Geometry is defined as closed but is open

As far as I can tell it is because removeCoLinear removes some of the segments so the first and last point of the polygon end up to be different. Calling bg::correct() on the resulting polygon seems to fix it.

Regression tests

Would you accept a pull request that adds regression tests to the project?

I am thinking about simply adding the result of running the current examples in the data directory as reference files and have a test check against them. I'm assuming that you must have looked closely at all of those outputs so they constitute a pretty good set of correct results. Not only would it catch issues like the one with the non-working boost version, it would also help me greatly when making sure that the library works properly on Visual Studio.

I'm thinking about using catch2 as the test library as that is a very small single header only dependency.

Also, would you be opposed to me switching the build system from make to cmake? Cmake has the advantage of being cross platform.

history based loop prevention allows for oscillation

The current history based loop prevention still allows for some oscillation in the NFP traversal (e.g. test-case: crossing). At the moment that is mitigated by deleting those detours from the NFP in the very end by calling delete_consecutive_repeating_point_patterns, which works, but ultimately we should find a way to prevent it all together.

Why some results seem to miss a part?

Hi, I would like to know, why in some cases there is a line segment missing in NFP, e.g. in data/handcrafted/crossing:

(I would say that the result should be like this:)

However, this (the first image) NPF result is even in the golden.wkt file, so it's probably intended, but I don't know why - does it have something to do with floating point arithmetics?

The thing is that in my constructed test [I'm trying to change the code so it generates also Inner Fit Polygons (basically the thing that is calculated for holes of polygon A when computing NFP), and was constructing some cases to know if it's safe to compute only this] there should be a line segment in the "bottom part" (which is fulfilled) and also in the "upper part" (which isn't).

Polygon representation + NFP:
POLYGON((0 0,0 100,100 100,100 0), (30 30,30 5,95 5,95 85,30 85,30 60,50 60,50 50,40 55,40 35,50 40,50 30))
POLYGON((60 35,70 40,70 30,80 30,80 60,70 60,70 50,60 55))

"Should be:"

Here is a case without inner holes, with the same issue:
POLYGON((30 30,30 5,95 5,95 0,0 0,0 100,95 100,95 85,30 85,30 60,50 60,50 50,40 55,40 35,50 40,50 30))
60 35,70 40,70 30,80 30,80 60,70 60,70 50,60 55

PS: Anyway, thank you very much for creating this library! :)

Is it possible to get an example file without reading .wkt files?

Is it possible to get an example file without reading .wkt files?
But specifying them manually.

How to rotate polygon_t using boost rotate_transformer?

I tried to use the boost transformer to rotate a polygon:

namespace trans = boost::geometry::strategy::transform;
polygon_t p;
trans::rotate_transformer<boost::geometry::degree, coord_t, 2, 2> rotate(p);

I got error when compiling the code in visual studio:
Error C2665 'sin': none of the 3 overloads could convert all the argument types

I understand it was caused by no libnfporb::LongDouble version of cos. How can I fix this issue ?

generateNFP only returns singular points

Hello, kallaballa, I hope you are still active, I ran into an issue with this library where the function generateNFP does not return the no fit polygon, only some singular points. When I run your example code on the example geometry, I get this:

data/handcrafted/rect:

data/handcrafted/jigsaw:

The same happens when I try simple custom geometry

I'm on Windows 10, compiling with Visual Studio 2017, Boost version 1.72 if that helps.

I wanted to use it as a python extension for a scientific research project at my university, but this is really holding me back. Do you have any idea what could be the problem? Thanks!

Allow use under a different licence

I am considering writing a plugin for Autodesk Fusion 360 that would allow exporting a design as a DXF file ready to be fed to a laser cutter or CNC machine. In order to minimize the stock material used, I'd like to implement nesting with the help of libnfp. I am planning on making this plugin open source.

In this project, the GPL license of libnfp is an obvious issue:

I need to link my code both against libnfp and against the C++ API code of Autodesk Fusion 360, which has a proprietary license. Since I don't own the rights to Autodesk's code, I can't license that under GPL.
A C++ plugin to Autodesk Fusion 360 is a .dll file, which means that it will be dynamically linked to the Autodesk Fusion 360 executable to which I neither hold any rights nor have access to the source code for.

I'd like to discuss with you if you'd be willing to consider allowing me to use libnfp under a different license for this project. Would you accept "helping makers save material when building awesome stuff" as an acceptable "greater good"?

Big files cause a sever performance penalty

Here is my POLYGON data
POLYGON((55.3674 4.06366,58.0765 4.74094,59.939 6.60345,60.2777 6.43413,62.1402 7.78869,62.8175 7.78869,65.1879 9.31256,
66.7118 9.82052,68.5743 11.5137,69.0823 11.3444,69.7094 11.8147,71.0464 12.1233,72.9505 12.5241,75.0085 12.445,77.0403 1
2.3603,78.5642 11.3444,79.9187 11.1751,81.6119 9.82052,82.4585 9.82052,82.9665 9.31256,83.4744 9.31256,83.8131 8.80461,8
5.6756 8.12733,85.8449 7.61937,86.1835 7.78869,87.8767 6.77277,88.0037 6.79817,88.0461 6.77277,88.7782 6.91921,90.7119 6
.11351,90.8277 5.97455,91.2631 5.2489,92.279 5.2489,93.295 4.74094,94.8188 4.74094,95.6654 4.23298,98.7132 3.55571,98.80
99 3.57183,98.8825 3.55571,99.7659 3.70294,100.576 3.21707,103.623 3.21707,103.793 3.38639,104.019 3.49927,104.301 3.217
07,105.147 3.21707,105.768 3.52749,106.333 3.38639,106.366 3.42025,106.502 3.38639,106.812 3.69681,107.518 3.55571,107.6
1 3.5711,107.687 3.55571,111.751 4.23298,112.259 4.74094,114.968 5.2489,116.492 6.26482,117.508 6.26482,121.571 8.29665,
122.079 8.29665,124.111 9.48188,126.312 10.6671,126.331 10.7047,126.99 10.8364,126.99 11.3444,127.836 11.3444,132.408 13
.8842,134.948 15.7467,137.318 18.2865,138.673 18.9638,141.382 22.1808,141.72 23.0274,143.466 24.3079,143.583 24.382,143.
605 24.4093,144.26 24.8899,144.712 25.793,144.937 26.0752,144.876 26.1223,144.937 26.2445,137.487 32.0014,137.068 32.141
1,136.81 32.34,136.641 32.2836,136.471 32.34,135.625 33.5252,133.762 34.5411,132.069 36.065,130.715 36.573,126.651 39.28
21,124.28 41.1446,122.079 41.8219,121.802 42.0374,121.741 42.1605,121.588 42.2042,120.555 43.0071,119.539 43.0071,118.35
4 43.6844,115.476 44.1923,114.799 44.7003,112.428 44.7003,112.089 45.2083,109.719 45.3776,108.872 45.7162,106.333 45.800
9,103.962 45.8855,103.939 45.8807,103.793 45.8855,94.9881 44.023,89.4006 41.4832,88.0461 40.4673,86.8608 40.1287,85.1676
38.6048,84.9607 38.5296,84.4903 38.4355,84.4313 38.337,83.3051 37.9275,83.3051 37.5889,82.9665 37.3349,81.4426 36.573,8
0.2574 36.065,78.9028 35.0491,76.7017 34.0332,75.8551 34.0332,74.3312 33.0173,72.4687 33.0173,71.9607 32.5093,68.5743 32
.5093,64.8493 34.0332,64.3413 34.8798,62.9868 35.2184,62.8175 35.5571,59.2347 37.1148,58.2942 37.6373,56.722 38.6048,55.
8754 38.6048,55.1981 39.1128,52.997 39.6207,52.6583 40.1287,51.6424 40.6366,50.7958 40.6366,50.4572 41.1446,49.7799 41.1
446,49.1026 41.6526,44.023 43.0071,41.9065 43.1764,39.9594 43.3458,39.8933 43.3375,39.79 43.3458,37.0809 43.0071,36.573
42.3298,36.065 42.3298,35.7264 42.8378,35.5676 42.8219,35.5571 42.8378,34.8798 42.7531,34.0332 42.6685,33.6945 42.1605,3
2.5093 42.1605,31.3241 41.6526,30.9854 41.1446,28.9536 41.1446,27.505 40.3544,26.7525 40.1287,26.5831 40.1287,26.0752 39
.6207,24.8899 39.4514,21.6729 37.9275,19.9797 36.573,19.4717 36.573,18.6251 35.5571,15.2387 33.8639,14.3921 33.0173,10.8
364 30.9854,7.95801 28.4456,7.61937 28.4456,6.94209 27.4297,6.26482 27.2604,2.53979 23.5354,3.04775 23.3661,3.04775 23.0
274,1.69319 22.3502,1.52387 21.3342,0 20.149,0 19.8104,1.18524 19.1331,1.52387 18.6251,1.35455 18.1172,7.95801 11.5137,9
.98984 9.98984,12.8683 8.63529,14.2228 7.28073,15.5774 6.77277,18.7944 4.4023,19.641 4.23298,19.9797 3.72503,21.8422 2.8
7843,23.874 2.37047,24.2127 2.53979,26.4138 1.69319,27.2604 1.69319,28.107 1.18524,28.2763 1.18524,30.4775 1.01592,31.07
01 1.18524,31.3241 1.18524,31.4934 1.01592,31.1548 0.677278,32.5093 0.16932,32.6529 0.180363,32.6786 0.16932,34.7503 0.3
28679,36.065 0,40.4673 0,42.9301 0.492565,43.8537 0.338639,43.896 0.359804,44.023 0.338639,44.7003 0.677278,47.0708 0.67
7278,55.3674 4.06366))

The following is the output of my error after turning on NFP_DEBUG

Can you help me see what's the problem?

Cannot compile with boost 1.79

There is some conflict between boost::qvm and LongDouble:

make -C examples/  CXX=g++ NVCC="" NVCC_HOST_CXX="" NVCC_CXXFLAGS=""
make[1]: Entering directory '/home/user/libs-dev/libnfp/examples'
g++ -pthread -fno-strict-aliasing -std=c++1y -pedantic -Wall -march=native -g0 -O3 -fpic -I. -o nfp.o -c nfp.cpp
In file included from /home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/strategies.hpp:117,
                 from /home/user/libs-dev/boost_1_79_0/boost/geometry/geometry.hpp:60,
                 from /home/user/libs-dev/boost_1_79_0/boost/geometry.hpp:17,
                 from ../src/geometry.hpp:13,
                 from ../src/libnfporb.hpp:12,
                 from nfp.cpp:7:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp: In instantiation of ‘boost::geometry::strategy::transform::matrix_transform
er<CalculationType, 2, 2>::matrix_transformer(const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&) [with CalculationType = libnf
porb::LongDouble; ct = libnfporb::LongDouble]’:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:336:24:   required from ‘boost::geometry::strategy::transform::translate_tra
nsformer<CalculationType, 2, 2>::translate_transformer(const CalculationType&, const CalculationType&, const CalculationType&) [with CalculationType = libnfporb::LongDouble]’
../src/algo/trim_vector.hpp:22:87:   required from here
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:185:20: error: no matching function for call to ‘A<0, 0>(boost::geometry::st
rategy::transform::detail::matrix_transformer::matrix_transformer<libnfporb::LongDouble, 2, 2>::matrix_type&)’
  185 |         qvm::A<0,0>(this->m_matrix) = m_0_0;   qvm::A<0,1>(this->m_matrix) = m_0_1;   qvm::A<0,2>(this->m_matrix) = m_0_2;
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:27:
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp:21:1: note: candidate: ‘template<int R, int C, class M> typename boost::qvm::enable_if_c<boost::qvm::is_mat<M>:
:value, typename boost::qvm::mat_traits<M>::scalar_type>::type boost::qvm::A(const M&)’
   21 | A( M const & a )
      | ^
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp:21:1: note:   template argument deduction/substitution failed:
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp: In substitution of ‘template<int R, int C, class M> typename boost::qvm::enable_if_c<boost::qvm::is_mat<M>::va
lue, typename boost::qvm::mat_traits<M>::scalar_type>::type boost::qvm::A(const M&) [with int R = 0; int C = 0; M = boost::qvm::mat<libnfporb::LongDouble, 3, 3>]’:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:185:20:   required from ‘boost::geometry::strategy::transform::matrix_transf
ormer<CalculationType, 2, 2>::matrix_transformer(const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&) [with CalculationType = li
bnfporb::LongDouble; ct = libnfporb::LongDouble]’
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:336:24:   required from ‘boost::geometry::strategy::transform::translate_tra
nsformer<CalculationType, 2, 2>::translate_transformer(const CalculationType&, const CalculationType&, const CalculationType&) [with CalculationType = libnfporb::LongDouble]’
../src/algo/trim_vector.hpp:22:87:   required from here
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp:21:1: error: no type named ‘type’ in ‘struct boost::qvm::enable_if_c<false, libnfporb::LongDouble>’
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp: In instantiation of ‘boost::geometry::strategy::transform::matrix_transform
er<CalculationType, 2, 2>::matrix_transformer(const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&) [with CalculationType = libnf
porb::LongDouble; ct = libnfporb::LongDouble]’:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:336:24:   required from ‘boost::geometry::strategy::transform::translate_tra
nsformer<CalculationType, 2, 2>::translate_transformer(const CalculationType&, const CalculationType&, const CalculationType&) [with CalculationType = libnfporb::LongDouble]’
../src/algo/trim_vector.hpp:22:87:   required from here
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp:35:1: note: candidate: ‘template<int R, int C, class M> typename boost::qvm::enable_if_c<boost::qvm::is_mat<M>:
:value, typename boost::qvm::mat_traits<M>::scalar_type&>::type boost::qvm::A(M&)’
   35 | A( M & a )
      | ^
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp:35:1: note:   template argument deduction/substitution failed:
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp: In substitution of ‘template<int R, int C, class M> typename boost::qvm::enable_if_c<boost::qvm::is_mat<M>::va
lue, typename boost::qvm::mat_traits<M>::scalar_type&>::type boost::qvm::A(M&) [with int R = 0; int C = 0; M = boost::qvm::mat<libnfporb::LongDouble, 3, 3>]’:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:185:20:   required from ‘boost::geometry::strategy::transform::matrix_transf
ormer<CalculationType, 2, 2>::matrix_transformer(const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&) [with CalculationType = li
bnfporb::LongDouble; ct = libnfporb::LongDouble]’
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:336:24:   required from ‘boost::geometry::strategy::transform::translate_tra
nsformer<CalculationType, 2, 2>::translate_transformer(const CalculationType&, const CalculationType&, const CalculationType&) [with CalculationType = libnfporb::LongDouble]’
../src/algo/trim_vector.hpp:22:87:   required from here
/home/user/libs-dev/boost_1_79_0/boost/qvm/mat_access.hpp:35:1: error: no type named ‘type’ in ‘struct boost::qvm::enable_if_c<false, libnfporb::LongDouble&>’
In file included from /home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:28:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp: In instantiation of ‘boost::geometry::strategy::transform::matrix_transform
er<CalculationType, 2, 2>::matrix_transformer(const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&, const ct&) [with CalculationType = libnf
porb::LongDouble; ct = libnfporb::LongDouble]’:
/home/user/libs-dev/boost_1_79_0/boost/geometry/strategies/transform/matrix_transformers.hpp:336:24:   required from ‘boost::geometry::strategy::transform::translate_tra
nsformer<CalculationType, 2, 2>::translate_transformer(const CalculationType&, const CalculationType&, const CalculationType&) [with CalculationType = libnfporb::LongDouble]’
../src/algo/trim_vector.hpp:22:87:   required from here
/home/user/libs-dev/boost_1_79_0/boost/qvm/vec_access.hpp:21:1: note: candidate: ‘template<int I, class V> typename boost::qvm::enable_if_c<boost::qvm::is_vec<B>::value,
 typename boost::qvm::vec_traits<B>::scalar_type>::type boost::qvm::A(const V&)’
   21 | A( V const & a )
      | ^
/home/user/libs-dev/boost_1_79_0/boost/qvm/vec_access.hpp:21:1: note:   template argument deduction/substitution failed:
...

numerical error prevents discovery of the next slide vector

In the last frame of the animation you can see that B could slide in a little more before returning but findFeasibleTranslationVectors doesn't come up with a vector.

inner nfp without output

I found that the library can't generate the internal nfp directly so I constructed a polygon with a hole but the internal nfp is not generated when I test it . But I can generate using hole3 from test data
Below is my test data
pB.pdf
pA.pdf

what happened?

NFP of two identical squares incorrect

Given the following polygon:

POLYGON((0 0,10 0,10 10,0 10,0 0))

If this polygon is given to generateNFP() both as pA and pB then the result is

POLYGON((10 -10))
POLYGON((0 0))

I think this may be incorrect. I would have expected to get these four points:

POLYGON((-10 -10))
POLYGON((0 -10))
POLYGON((10 10))
POLYGON((-10 0))

Here I am assuming that the first point (0 0) is the reference point.

How to generate an inside nfp?

Given the polygon for a part and the polygon for a bin in which the part should be placed, how can I generate the nfp on the inside of the bin?

If I do

nfp_t nfp = generateNFP(bin, part, true);

Then it gives me the nfp for placing the part on the outside of the bin.

Runtime error: No touching points with certain simple geometry

In some obscure cases, the program throws a runtime error stating that "No touching points found". One example of such shape is:
POLYGON((181 180,181 331,31 331,31 31,181 31,181 180))
(It does not matter if it serves as A or B)
But as soon as I change it to
POLYGON((**180** 180,181 331,31 331,31 31,181 31,**180** 180))
It miraculously works and finds a valid NFP!

I tried to examine the code but I am of the impression that there must be some error in Boost.geometry, especially bg::intersects.

(Boost version 1.65)

Bad assumptions

Hi kallaballa, thanks a lot for your efforts coding this. I have a question regarding your note about the bad assumptions of the paper that inspired the NFP generator. If I'm not wrong, it is E.K. Burke et al. 2006. ¿Do you mean that it is necessary to make additional assumptions, on top of what can be read in the paper, to complete the NFP generator? Is the paper by Bennell & Song free of those types of issue? Thanks a lot!

The resulting polygon is shifted

Consider the following code:

    auto poly1 = libnfporb::polygon_t{};
    poly1.outer().push_back({12, 0});
    poly1.outer().push_back({0, 12});
    poly1.outer().push_back({-12, 0});
    poly1.outer().push_back({0, -12});

    auto poly2 = libnfporb::polygon_t{};
    poly2.outer().push_back({10, 10});
    poly2.outer().push_back({-10, 10});
    poly2.outer().push_back({-10, -10});
    poly2.outer().push_back({10, -10});

    auto nfp = generate_nfp(poly1, poly2, true);

Here is the result:

The green dot is the coordinates' origin. I would expect the NFP also to be located around the green dot.

Output of generateNFP() with a hole

I'm trying to understand how to use the output of generateNFP().

From the README, I was expecting, that generateNFP() would return the NFP in a form that would allow me to draw an image like the following:

However, this does not seem to be possible. The repository has the sample data data/handcrafted/hole which is very similar to the above situation. This generates the following NFP:

I have a few questions about this:

First of all, it seems like there are two points missing in the hole. Couldn't the small square also be located top left and bottom right?

Second, the returned type is a vector of rings, but each ring always seems to contain only a single point. How can I then distinguish the inner ring from the outer ring?

Lastly, if I treat the individual points as points in a polygon, the order in which they appear in the output gives me the following polygon:

To clarify, I don't need to distinguish the inner ring from the outer ring or have the points appear in any particular order (although this would be nice and make my application faster). It's just that the README had caused me to expect a certain kind of output. What I'm asking for is some documentation about the return value of generateNFP():

Why is it a vector of rings containing one point each?
Will the rings sometimes contain multiple points? What does it mean when they do?
Does the order of the rings and points carry any significance?
Which point is the reference point?

Thank you.

How to choose the reference point?

For different polyhedra, what is the principle of choosing a reference point?

What is the time complexity of generateNFP?

It could be useful to know the algorithmic complexity of generateNFP because it helps make informed decisions about how to best use it.

Running nfp without boost and libgmp

Hi,

In the project description it is written:
The library has two dependencies: Boost Geometry and libgmp. You need to install those first before building. Note that building is only required for the examples. The library itself is header-only.

Does it mean that it is possible to run your library in console application without boost and libgmp?
If Yes is it possible to get a source code without referencing these main libraries.

If not I would like to ask if the library is only contains of one file:
https://github.com/kallaballa/libnfporb/blob/master/src/libnfporb.hpp

out_of_range in vector indexing access

In Visual Studio 2017 I run into a situation where the second line of the following code in selectNextTranslationVector() causes an out_of_range exception:

if (i >= rA.size())
    next = rA[i % rA.size() + 1];
else
    next = rA[i];

In my case, rA.size() is 5 and i is 9. This ends up causing access to rA[5] which does not exist.

To reproduce the situation with gcc replace the lines (there are two occurrences of this code in selectNextTranslationVector() and another in searchStartTranslation()) with

next = rA.at(i % rA.size() + 1);

and run the tests.

How to generate the inner fit polygon?

it seems like there is a bug

testdata:
POLYGON((172 143, 142 117, 112 91, 82 65, 52 39, 52 31, 52 23, 52 15, 52 06, 314 06, 576 06, 837 06, 1099 06, 1099 15, 1099 23, 1099 31, 1099 39, 1069 65, 1039 91, 1009 117, 979 143, 964 118, 944 98, 919 83, 892 75, 734 53, 576 46, 417 53, 259 75, 259 75, 232 83, 207 98, 187 118, 172 143))

boost version

Could you please list out the version of boost?

unable to complete outer loop

Running testgen.sh ends with an error:

#### Running case data/generated/Z.wkt data/generated/2.wkt: ./testgen.sh: line 16: 11971 Aborted                 build/examples/nfp $file1 $file2 &>> testgen.log
Fail

testgen.log contains the following message:

terminate called after throwing an instance of 'std::runtime_error'
  what():  Unable to complete outer nfp loop