kallaballa / libnfporb Goto Github PK
View Code? Open in Web Editor NEWImplementation of a robust no-fit polygon generation in a C++ library using an orbiting approach
License: GNU General Public License v3.0
Implementation of a robust no-fit polygon generation in a C++ library using an orbiting approach
License: GNU General Public License v3.0
Is it possible to get an example file without reading .wkt files?
But specifying them manually.
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:
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!
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
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!!
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:
...
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()
:
Thank you.
Could you please list out the version of boost?
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'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"?
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.
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 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.
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?
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.
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.
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.
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))
It could be useful to know the algorithmic complexity of generateNFP
because it helps make informed decisions about how to best use it.
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
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.
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 ?
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);
The green dot is the coordinates' origin. I would expect the NFP also to be located around the green dot.
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
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)
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))
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! :)
For different polyhedra, what is the principle of choosing a reference point?
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.