Неполная проблема многоугольника с CGAL / minkowski_sum_2 - PullRequest
Новая
       67

Неполная проблема многоугольника с CGAL / minkowski_sum_2

0 голосов
/ 16 сентября 2018

Мне нужно вычислить полигон без подгонки (NFP) для двух полигонов, A и B, для целей вложения.NFP для A и B можно определить как NFP (A, B) = A (+) -B, где (+) - сумма Минковского.Я использую библиотеки C ++ и CGAL, которые предоставляют функции для вычисления сумм Минковского.Хорошо, после этого небольшого описания контекста, позвольте мне представить мою проблему.Есть несколько хорошо известных эталонных примеров нерегулярных двумерных задач, и я собираюсь использовать их в своих исследованиях.В экземпляре, называемом 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);

Переменная nfp_A_B, вычисленная minkowski_sum_2, была описана этими точками: 

(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 с точным соответствием в этом случае или (лучше) в общем случае.

1 Ответ

0 голосов
/ 17 сентября 2018

Результатом операции суммы Минковского является регуляризованный многоугольник (или многоугольник с отверстиями).Руководство по двумерным регуляризованным логическим операциям множеств CGAL содержит точное определение.Проще говоря, если P нерегуляризированный многоугольник, то P * = замыкание (внутренний (P)) регуляризовано.Это подразумевает, что выходные данные не могут включать вырожденные элементы, такие как изолированные точки и «антенны».(Сегмент, который, как вы утверждаете, отсутствует, иногда называется антенной.)

Функция, которую вы надеялись получить, недоступна из коробки.На самом деле, для поддержки этой функции потребуется другой интерфейс.Тем не менее, с некоторой работой, вы должны быть в состоянии получить ее.Что вам нужно сделать, это получить базовое 2D-расположение, а затем пройти по нему, чтобы извлечь вырожденный многоугольник.Вам придется копаться в коде.Вот подсказка для начала.

Существует 3 функции, которые реализуют двумерные суммы Минковского: (i) разложение, (ii) свертка и (iii) уменьшение свертки.Я бы начал с (ii) (уменьшенная свертка).Здесь мы вычисляем циклы свертки и вставляем их в 2D-схему.Затем мы вычисляем числа обмоток граней схемы, чтобы выяснить, какие грани являются частью результирующего многоугольника (ов), а какие нет.Вам необходимо перехватить эту договоренность и обработать ее самостоятельно.

...