No-Fit Polygon problem with CGAL/minkowski_sum_2

user_10365459 0
Viewed 908

I need to compute the No-Fit Polygon (NFP) of two polygons, A and B, for nesting purposes. The NFP of A and B can be defined as NFP(A,B) = A (+) -B, where (+) is the Minkowski sum. I'm using C++ and CGAL library, which provides functions to compute Minkowski sums. Well, after this small context description, let me introduce my problem. There are some well-known benchmark instances of the 2-D irregular nesting problems, and I intend to use them in my research. In the instance called jakobs2, there are some pairs of polygons that fit exactly together, as it is the case of those showed in the figure:

Exact fit case in jakobs2 instance

I've created those polygons in C++ with this code:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/minkowski_sum_2.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Point_2<Kernel> Point_2;
typedef CGAL::Polygon_2<Kernel, std::vector<Point_2>> Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel, std::vector<Point_2>> Polygon_with_holes_2;

(...)

Polygon_2 *A = new Polygon_2();
A->push_back(Point_2(0, 0));
A->push_back(Point_2(10, 0));
A->push_back(Point_2(10, 10));
A->push_back(Point_2(8, 10));
A->push_back(Point_2(8, 2));
A->push_back(Point_2(2, 2));
A->push_back(Point_2(2, 10));
A->push_back(Point_2(0, 10));

Polygon_2 *B = new Polygon_2();
B->push_back(Point_2(0, 0));
B->push_back(Point_2(6, 0));
B->push_back(Point_2(6, 6));
B->push_back(Point_2(4, 6));
B->push_back(Point_2(4, 2));
B->push_back(Point_2(2, 2));
B->push_back(Point_2(2, 6));
B->push_back(Point_2(0, 6));

Polygon_2 *minus_B = new Polygon_2();
minus_B->push_back(Point_2(0, 0));
minus_B->push_back(Point_2(-6, 0));
minus_B->push_back(Point_2(-6, -6));
minus_B->push_back(Point_2(-4, -6));
minus_B->push_back(Point_2(-4, -2));
minus_B->push_back(Point_2(-2, -2));
minus_B->push_back(Point_2(-2, -6));
minus_B->push_back(Point_2(0, -6));

And, to compute NFP(A,B), I used this:

Polygon_with_holes_2 nfp_A_B = CGAL::minkowski_sum_2(*A, *minus_B);

The variable nfp_A_B, computed by minkowski_sum_2, was described by these points:

(4, 10), (2, 10), (-4, 10), (-6, 10), (-6, 4), (-6, -6), (-4, -6),
(-2, -6), (0, -6), (6, -6), (10, -6), (10, 0), (10, 10)

This sequence of points forms a square. The line segment from (2, -6) to (2, 2) should be included in NFP(A,B), but it was not. I would appreciate any help provided to use CGAL::minkowski_sum_2 for NFP computation with exact fit in this case, or (better) in general case.

cgal computational-geometry
1 Answers

The output of the Minkowski sum operation is a regularized polygon (or polygon with holes). The manual of the 2D Regularized Boolean Set-Operations of CGAL contains the exact definition. In simple words, if P is a non-regularized polygon, then P* = closure(interior(P)) is regularized. It implies that the output cannot include degenerate features, such as isolated points and "antennas". (The segment that you claim is missing is sometimes referred to as an antenna.)

The feature that you were hoping to get is not available out-of-the-box. As a matter of fact, a different interface would be needed to support this feature. However, with some work, you should be able to get it. What you need to do is obtain the underlying 2D arrangement, and then traverse the arrangement to extract the degenerate polygon. You will have to dig into the code. Here is a hint to start with.

There are 3 functions that implement the 2D Minkowski sums: (i) by decomposition, (ii) by convolution, and by (iii) reduced convolution. I would start with (ii) (reduced convolution). Here, we compute the convolution cycles and insert them into a 2D arrangement. Then, we compute the winding numbers of the faces of the arrangement, to figure out which faces are part of the resulting polygon(s) and which are not. You need to intercept this arrangement, and process it yourself.

user_19154210
Related