时间戳

首页 > 解决方案 > CGAL/minkowski_sum_2 的不适合多边形问题

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

问题描述

出于嵌套目的，我需要计算两个多边形 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 计算提供的任何帮助。

标签： computational-geometrycgal

解决方案

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

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

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

推荐阅读