关于布尔运算的区别

Question

我面临着关于差异布尔运算（多边形A /多边形B）的问题。当多边形不简单时，CGAL::difference() 函数会崩溃。看看我面临的一个问题的例子。

#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;
}

有人知道为什么会发生这种情况吗？

我仍然不知道如何避免这种情况。

Answer 1

您的多边形 A 是退化的，具有重叠的共线边缘（请参见第三点到第五点）。看起来

difference()

无法处理这种情况。您需要首先清理退化。 （这不是一项困难的任务；只需寻找三个共线点的运行，当找到这样的运行时，删除中间点）。