CGAL - можно ли рассчитать NFP полигонов с отверстиями

Question

Я планирую использовать библиотеку CGAL для расчета многоугольника без подгонки (NFP).Я видел, что пакет 2D Minkowski Sums в CGAL является отличным инструментом для этого.Однако мне нужно будет рассчитать NFP для очень разных типов полигонов, и я не уверен, что CGAL будет покрывать мои потребности, когда полигоны содержат дыры.Мои сомнения мотивированы следующим утверждением, найденным на их веб-сайте документации в главе 2D «Суммы Минковского»: «(...) Приложения некоторых операций в этом пакете ограничены полигонами, которые не содержат дыр. (Результирующие суммы могутно содержат дыры.) "

Кто-нибудь знает, какие операции ограничены полигонами без дырок?Кроме того, я был бы признателен за любой совет от любого, кто использовал CGAL для вычисления NFP для невыпуклых многоугольников.Большое спасибо.

Answer 1

Начиная с версии 4.9 CGAL, пакет "2D Minkowski Sum" поддерживает построение сумм Минковского многоугольников с отверстиями.Это построение может быть выполнено либо с помощью выпуклого разложения, либо с помощью методов приведенной свертки.Последний является стандартным и наиболее эффективным в большинстве случаев.Мы сохранили все старые методы, потому что они демонстрируют лучшую производительность в некоторых менее частых случаях.У вас не должно возникнуть проблем с вычислением NFP полигонов с дырками с помощью пакета.