CODEWITHSUNDEEP
computational-geometrycgal
Bruno Santos
Bruno Santos

Reputation: 1

About Boolean operation Difference

I'm facing a issue about difference boolean operation (Polygon A / Polygon B). When a polygon is not simple, the CGAL::difference() function has a crash. Look the example of a question that I facing.

#include <iostream>
#include <vector>
#include "print_utils.hpp"
/* The function print_polygon_with_holes taken from print_utils.h
 * component distributed by CGAL developers. This header was 
 * encontered at /cgal/Minkowski_sum_2/example/Minkowski_sum_2/ 
*/

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/convex_hull_2.h>

using Kernel                = CGAL::Exact_predicates_exact_constructions_kernel;
using FT                    = Kernel::FT;
using Point_2               = Kernel::Point_2;
using Segment_2             = Kernel::Segment_2;
using Polygon_2             = CGAL::Polygon_2<Kernel>;
using Polygon_with_holes_2  = CGAL::Polygon_with_holes_2<Kernel>;
using VertexIterator        = Polygon_2::Vertex_iterator;
using VectorOfPoints        = std::vector<Point_2>;
using Pwh_2_container       = std::vector<Polygon_with_holes_2>;

int main(void)
{
  Polygon_2 A;
  A.push_back(Point_2(12, 12));
  A.push_back(Point_2(10, 12));
  A.push_back(Point_2(8, 10));
  A.push_back(Point_2(8, 4));
  A.push_back(Point_2(8, 9));
  A.push_back(Point_2(6, 12));
  A.push_back(Point_2(4, 12));
  A.push_back(Point_2(2, 12));
  A.push_back(Point_2(0, 10));
  A.push_back(Point_2(0, 0));
  A.push_back(Point_2(0, -2));
  A.push_back(Point_2(2, -4));
  A.push_back(Point_2(4, -4));
  A.push_back(Point_2(14, -4));
  A.push_back(Point_2(16, -1));
  A.push_back(Point_2(16, 9));

  VectorOfPoints            ch_points_A;
  VectorOfPoints::iterator  ch_it;
  Polygon_2                 B;

  CGAL::convex_hull_2(A.vertices_begin(), A.vertices_end(), std::back_inserter(ch_points_A));

  for (ch_it = ch_points_A.begin(); ch_it != ch_points_A.end(); ++ch_it) {
    B.push_back(*ch_it);
  }

  Pwh_2_container diff;

  if (A.is_simple()) {
    CGAL::difference(B, A, std::back_inserter(diff));
  } else {
    std::cout << "The polygon A is not simple\n";
    exit(EXIT_FAILURE);
  }

  std::cout << "Printing the Difference A / B\n";
  for (auto p : diff) {
    print_polygon_with_holes(p);
  }

  return EXIT_SUCCESS;
}

Anyone has ideia why this happens?

I still don't have any ideas on how to avoid this situation.

Upvotes: 0

Views: 101

Answers (1)

Sneftel
Sneftel

Reputation: 41503

Your polygon A is degenerate, with overlapping collinear edges (see your third through fifth points). Looks like difference() doesn't handle that case. You'll need to clean up the degeneracies first. (Not a difficult task; just look for runs of three collinear points, and when you find such a run, remove the middle point).

Upvotes: 1

Related Questions