Ошибка сегментации в CGAL при пересечении полигонов - PullRequest
Новая
       44

Ошибка сегментации в CGAL при пересечении полигонов

0 голосов
/ 20 ноября 2018

Я пишу код, в котором мне нужно очень часто вычислять площадь перекрытия двух полигонов (один всегда квадрат, другой простой, но в целом невыпуклый многоугольник).Однако, используя для этого CGAL, я иногда сталкиваюсь с ошибками сегментации.Следующий код предоставляет минимальный пример.Обратите внимание, что как только одна из координат точки перемещается на 0,001, все работает нормально. 

#include <CGAL/Cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2_algorithms.h>

typedef CGAL::Cartesian<double> K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon;
typedef CGAL::Polygon_with_holes_2<K> PolygonH;

int main()
{    
     // Rectangle
     Point pointsA[] = { Point(0.4,0.35), Point(0.4,0.4), Point(0.45,0.4), Point(0.5,0.35) };

     // Triangle
     Point pointsB[] = { Point(0.428,0.412), Point(0.387,0.389), Point(0.359,0.393) };

     // Convert to CGAL polygon
     Polygon polyA(pointsA, pointsA + 4);
     Polygon polyB(pointsB, pointsB + 3);

     // Intersection
     std::list<PolygonH> polyAB;
     CGAL::intersection(polyA, polyB, std::back_inserter(polyAB));
}

1 Ответ

0 голосов
/ 20 ноября 2018

Если первый многоугольник всегда выпуклый (как и большинство квадратов), и вы заботитесь только о области перекрытия, вы можете легко свернуть свое собственное решение.

Рассмотрите линию поддержки одной из сторонпервый многоугольник.Вы будете реализовывать отсечение по полуплоскости, допустим, что оно ограничено x = 0, WLOG.

Создайте пустой выходной многоугольник.Затем попробуйте все ребра второго многоугольника по очереди.Присвойте каждой вершине логическое условие x> = 0.Если условие отличается для обеих конечных точек, добавьте пересечение стороны с осью x = 0 к новому многоугольнику;затем, если условие верно для конечной конечной точки стороны, добавьте ее также.

В конце вы получите новый многоугольник, который является обрезанной версией оригинала.В случае, если обрезанный многоугольник должен быть отключен, алгоритм создаст связанный многоугольник с дополнительными связующими сторонами вдоль x = 0.Но что касается расчета площади, это вообще не имеет значения.

Повторите с четырьмя сторонами отсечения и рассчитайте площадь, используя формулу шнурка.

enter image description here

...