| by YoungTimes | No comments

CGAL实现多边形凸分解

凹多边形的处理往往比较复杂,难以使用,所以我们往往需要将非凸多边形,甚至带空洞(Hole)的多边形拆解为凸多边形。

下图为带空洞的多边形(Polygon With Hole)。

图一:带空洞(Hole)的多边形

我们的目标是使用CGAL将其分解(decompose)为如下的多个凸多边形。

图二:带空洞(Hole)的多边形凸分解的结果

1. CGAL中的凸分解(Decompose)

CGAL中提供了Polygon和PolygonWithHole两大类凸分解的方法。

PolygonConvexDecomposition_2

CGAL::Small_side_angle_bisector_decomposition_2<Kernel,Container>
CGAL::Optimal_convex_decomposition_2<Kernel,Container>
CGAL::Hertel_Mehlhorn_convex_decomposition_2<Kernel,Container>
CGAL::Greene_convex_decomposition_2<Kernel,Container>
CGAL::Polygon_nop_decomposition_2<Kernel,Container>

PolygonWithHolesConvexDecomposition_2

CGAL::Polygon_vertical_decomposition_2<Kernel,Container>
CGAL::Polygon_triangulation_decomposition_2<Kernel,Container>

2. CGAL凸分解代码实现

以下代码用于实现从带空洞的多边形(图一)分解为凸多边形(图二)的效果。

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_vertical_decomposition_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 outP;
  Polygon_2 holesP[1];
  outP.push_back(Point_2(150, 250));
  outP.push_back(Point_2(150, 400));
  outP.push_back(Point_2(500, 400));
  outP.push_back(Point_2(500, 250));

  if (outP.orientation() != CGAL::COUNTERCLOCKWISE) {
      outP.reverse_orientation();
  }
  
  holesP[0].push_back(Point_2(240, 300));
  holesP[0].push_back(Point_2(240, 360));
  holesP[0].push_back(Point_2(400, 360));
  holesP[0].push_back(Point_2(400, 300));

  if (holesP[0].orientation() != CGAL::CLOCKWISE) {
      holesP[0].reverse_orientation();
  }
  
  Polygon_with_holes_2  P(outP, holesP, holesP + 1);
  std::cout << "P = ";
  print_polygon_with_holes(P);

  std::list<Polygon_2> decomposed_polygons;
  CGAL::Polygon_vertical_decomposition_2<Kernel> polygon_decompose;
  polygon_decompose(P, std::back_inserter(decomposed_polygons));
  std::cout << "decompose polygon:" << std::endl;
  for (const auto& decomposed_polygon : decomposed_polygons) {
      print_polygon(decomposed_polygon);
  }

  return 0;
}

程序编译:

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

程序输出:

P = Polygon_with_holes having 1 holes
Polygon with 4 vertices
[150,250],[500,250],[500,400],[150,400],
Polygon with 4 vertices
[240,300],[240,360],[400,360],[400,300],
decompose polygon:
Polygon with 4 vertices
[400,300],[240,300],[240,250],[400,250],
Polygon with 6 vertices
[240,400],[150,400],[150,250],[240,250],[240,300],[240,360],
Polygon with 6 vertices
[400,360],[400,300],[400,250],[500,250],[500,400],[400,400],
Polygon with 4 vertices
[400,400],[240,400],[240,360],[400,360],

参考材料

https://doc.cgal.org/latest/Minkowski_sum_2/classPolygonWithHolesConvexDecomposition__2.html
https://doc.cgal.org/latest/Minkowski_sum_2/classPolygonConvexDecomposition__2.html

发表评论