任意简单多边形求差集(difference)

在日常开发中会遇到从一个多边形扣除掉部分区域的需求，如下图所示：

图1：多变形集合 图2：多边形差集

CGAL提供了CGAL::difference函数用于实现多边形差集的功能。函数原型如下：

OutputIterator difference(const Type1 & p1, const Type2 & p2, OutputIterator oi)

其中type1和type2支持的类型如下：

Type1 Type2 Polygon_2 Polygon_2 Polygon_2 Polygon_with_holes_2 Polygon_with_holes_2 Polygon_2 Polygon_with_holes_2 Polygon_with_holes_2 General_polygon_2 General_polygon_2 General_polygon_2 General_polygon_with_holes_2 General_polygon_with_holes_2 General_polygon_2 General_polygon_with_holes_2 General_polygon_with_holes_2

计算差集的代码如下:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <list>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                   Point_2;
typedef CGAL::Polygon_2<Kernel>                           Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>                Polygon_with_holes_2;
typedef std::list<Polygon_with_holes_2>                   Pwh_list_2;

template<class K>
void print_point(CGAL::Point_2<K> const& p) {
  std::cout << "[" << p.x() << "," << p.y() << "]," ;
}

template<class K, class C>
void print_polygon(CGAL::Polygon_2<K,C> const& poly) {
  typedef CGAL::Polygon_2<K,C> Polygon ;

  std::cout << "Polygon with " << poly.size() << " vertices" << std::endl ;

  for (typename Polygon::Vertex_const_iterator vi = poly.vertices_begin() ; vi != poly.vertices_end(); ++vi) {
    print_point(*vi); 
  }

  std::cout << std::endl ;
}

template<class K, class C>
void print_polygon_with_holes(CGAL::Polygon_with_holes_2<K,C> const& polywh) {
  typedef CGAL::Polygon_with_holes_2<K,C> PolygonWithHoles ;

  std::cout << "Polygon_with_holes having " << polywh.number_of_holes() << " holes" << std::endl ;

  print_polygon(polywh.outer_boundary());

  for (typename PolygonWithHoles::Hole_const_iterator hi = polywh.holes_begin() ; hi != polywh.holes_end() ; ++ hi)
    print_polygon(*hi);
}

int main () {
  Polygon_2 P;
  P.push_back(Point_2(0, 0));
  P.push_back(Point_2(0, 200));
  P.push_back(Point_2(300, 200));
  P.push_back(Point_2(300, 0));

  if (P.orientation() != CGAL::COUNTERCLOCKWISE) {
      P.reverse_orientation();
  }

  Polygon_2 Q;
  Q.push_back(Point_2(60, 60));
  Q.push_back(Point_2(60, 250));
  Q.push_back(Point_2(130, 250));
  Q.push_back(Point_2(130, 60));

  if (Q.orientation() != CGAL::COUNTERCLOCKWISE) {
      Q.reverse_orientation();
  }

  Pwh_list_2 differenceR;
  CGAL::difference(P, Q, std::back_inserter(differenceR));

  for (auto it = differenceR.begin(); it != differenceR.end(); ++it) {
    std::cout << "--> ";
    print_polygon_with_holes (*it);
  }

  return 0;
}

代码编译:

g++ difference.cpp -std=c++11  -Wall -pedantic -lCGAL -lCGAL_Core -lmpfr -lgmp -pthread  && ./a.out

程序输出:

--> Polygon_with_holes having 0 holes
Polygon with 8 vertices
[0,0],[300,0],[300,200],[130,200],[130,60],[60,60],[60,200],[0,200]

上述代码实现的效果如下:

参考材料

https://doc.cgal.org/latest/Boolean_set_operations_2/group__boolean__difference.html