computational-geometry - CGAL/minkowski_sum_2 的不适合多边形问题

Question

出于嵌套目的，我需要计算两个多边形 A 和 B 的不适合多边形 (NFP)。 A 和 B 的 NFP 可以定义为 NFP(A,B) = A (+) -B，其中 (+) 是 Minkowski 和。我正在使用 C++ 和 CGAL 库，它提供了计算 Minkowski 和的函数。好吧，在这个简短的上下文描述之后，让我介绍一下我的问题。二维不规则嵌套问题有一些著名的基准实例，我打算在我的研究中使用它们。在名为 jakobs2 的实例中，有几对多边形完全吻合，如图所示:

jakobs2 实例中的精确匹配

我使用以下代码在 C++ 中创建了这些多边形:

#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));

并且，为了计算 NFP(A,B)，我使用了这个:

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

由 minkowski_sum_2 计算的变量 nfp_A_B 由以下几点描述:

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

这个点序列形成一个正方形。从 (2, -6) 到 (2, 2) 的线段应该包含在 NFP(A,B) 中，但实际上没有。我将不胜感激为使用 CGAL::minkowski_sum_2 进行 NFP 计算而提供的任何帮助，在这种情况下或在一般情况下(更好)。

Answer 1

Minkowski 求和运算的输出是一个正则化 多边形(或带孔的多边形)。 CGAL 的 2D Regularized Boolean Set-Operations 手册包含确切的定义。简而言之，如果 P 是非正则化多边形，则 P* = closure(interior(P)) 是正则化的。这意味着输出不能包含退化特征，例如孤立点和“天线”。 (您声称丢失的部分有时称为天线。)

您希望获得的功能不是开箱即用的。事实上，需要一个不同的接口(interface)来支持这个特性。但是，通过一些工作，您应该能够得到它。你需要做的是获取底层二维排列，然后遍历排列提取退化多边形。您将不得不深入研究代码。这是一个开始的提示。

有 3 个函数可实现 2D Minkowski 和:(i) 通过分解，(ii) 通过卷积，以及 (iii) 缩减卷积。我将从 (ii)(减少卷积)开始。在这里，我们计算卷积周期并将它们插入到二维排列中。然后，我们计算排列面的缠绕数，以确定哪些面是生成的多边形的一部分，哪些不是。你需要拦截这个排列，自己处理。