2D多边形切分(2D Polygon Partition)

CGAL提供了一系列多边形切分算法，支持将单个多边形切分成若干个小的多边形，每个多边形之间互不交叉，总和等于原多边形大小。

1.Monotone Partitioning

1.1 什么是单调多边形(monotone polygon)

在几何形状中，如果与L垂直的每条线最多与多边形P相交两次，则称平面中的多边形P相对于直线L为单调的。类似地，如果与L垂直的每条线最多一次与C相交，则折线C相对于直线L称为单调。

1.2 Y Monotone Partition

对一个多边形进行Y单调切分就是要求切分后的子多边形都是Y单调多边形。CGAL提供了CGAL::y_monotone_partition_2函数用来实现平面多边形的Y单调分割。

template<class InputIterator , class OutputIterator , class Traits >
OutputIterator CGAL::y_monotone_partition_2(	
    InputIterator 	first,
    InputIterator 	beyond,
    OutputIterator 	result,
    const Traits & 	traits = Default_traits 
)

该函数实现了扫描线算法，算法时间复杂度为O(nlogn)，空间复杂度为O(n)，其中n是多边形中的节点的个数。该算法不保证分割的最优性，即切分得到的子多边形数目可能会大于最优子多边形的数目。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                      Traits;
typedef Traits::Point_2                                  Point_2;
typedef Traits::Polygon_2                                Polygon_2;
typedef std::list<Polygon_2>                          Polygon_list;

void make_polygon(Polygon_2& polygon) {
   polygon.push_back(Point_2(391, 374));
   polygon.push_back(Point_2(240, 431));
   polygon.push_back(Point_2(252, 340));
   polygon.push_back(Point_2(374, 320));
   polygon.push_back(Point_2(289, 214));
   polygon.push_back(Point_2(134, 390));
   polygon.push_back(Point_2(68, 186));
   polygon.push_back(Point_2(154, 259));
   polygon.push_back(Point_2(161, 107));
   polygon.push_back(Point_2(435, 108));
   polygon.push_back(Point_2(208, 148));
   polygon.push_back(Point_2(295, 160));
   polygon.push_back(Point_2(421, 212));
   polygon.push_back(Point_2(441, 303));
}

int main( ) {
   Polygon_2    polygon;
   Polygon_list partition_polys;
   make_polygon(polygon);
   CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                             polygon.vertices_end(),
                             std::back_inserter(partition_polys));
   std::list<Polygon_2>::const_iterator   poly_it;
   for (poly_it = partition_polys.begin(); poly_it != partition_polys.end(); poly_it++) {
      assert(CGAL::is_y_monotone_2((*poly_it).vertices_begin(),
                                   (*poly_it).vertices_end()));
   }
   assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
                                     polygon.vertices_end(),
                                     partition_polys.begin(),
                                     partition_polys.end()));
   return 0;
}

CGAL::is_y_monotone_2用于检测切分完成之后的多边形是否都是Y单调多边形；CGAL::partition_is_valid_2用于检验切分完成的多边形是否为合法的切分，一个合法的Y单调多边形切分满足1) 切分后多边形互不重叠；2）切分后的多边形都是Y单调多边形；3）切分后的多边形合并起来为原多边形。

程序编译:

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

切分的结果如下：

2. Convex Partitioning

CGAL提供了对多边形进行凸分割的方法，包含最优凸分割和近似最优凸分割。

近似最优凸分割(左)和最优凸分解(右)

最优凸分割可以通过CGAL::optimal_convex_partition_2实现。该函数实现了Greene于 1983 年提出的动态规划算法从而实现对多边形的最优分割空间算法，时间复杂度为O(n^4)，空间复杂度为O(n^3)，n为多边形的点个数。

template<class InputIterator, class OutputIterator, class Traits >
OutputIterator CGAL::optimal_convex_partition_2	(	InputIterator 	first,
InputIterator 	beyond,
OutputIterator 	result,
const Traits & 	traits = Default_traits 
)

简单多边形实现最优凸切分的实现如下：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>               Traits;
typedef Traits::Polygon_2                         Polygon_2;
typedef Traits::Point_2                           Point_2;
typedef std::list<Polygon_2>                      Polygon_list;

void make_polygon(Polygon_2& polygon) {
   polygon.push_back(Point_2(391, 374));
   polygon.push_back(Point_2(240, 431));
   polygon.push_back(Point_2(252, 340));
   polygon.push_back(Point_2(374, 320));
   polygon.push_back(Point_2(289, 214));
   polygon.push_back(Point_2(134, 390));
   polygon.push_back(Point_2( 68, 186));
   polygon.push_back(Point_2(154, 259));
   polygon.push_back(Point_2(161, 107));
   polygon.push_back(Point_2(435, 108));
   polygon.push_back(Point_2(208, 148));
   polygon.push_back(Point_2(295, 160));
   polygon.push_back(Point_2(421, 212));
   polygon.push_back(Point_2(441, 303));
}

int main() {
   Polygon_2             polygon;
   Polygon_list          partition_polys;
   make_polygon(polygon);
   CGAL::optimal_convex_partition_2(polygon.vertices_begin(),
                             polygon.vertices_end(),
                             std::back_inserter(partition_polys));
   assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
                                     polygon.vertices_end(),
                                     partition_polys.begin(),
                                     partition_polys.end()));
   return 0;
}

代码编译:

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

程序输出：

Polygon with 4 vertices
[391,374],[240,431],[252,340],[374,320],
Polygon with 3 vertices
[134,390],[68,186],[154,259],
Polygon with 3 vertices
[161,107],[435,108],[208,148],
Polygon with 3 vertices
[154,259],[161,107],[208,148],
Polygon with 5 vertices
[289,214],[134,390],[154,259],[208,148],[295,160],
Polygon with 5 vertices
[374,320],[289,214],[295,160],[421,212],[441,303],
Polygon with 3 vertices
[391,374],[374,320],[441,303],

函数approx_convex_partition_2实现了一个简单的凸分割近似算法，该算法首先对原多边形进行三角化，然后丢弃其中一些无用边从而实现对一个简单多边形的凸分割，该算法可以在O(n)时间和空间复杂度内对一个多边形进行凸分割，并且保证切分的多边形的数量不超过最优凸分割的多边形数量的四倍。

template<class InputIterator , class OutputIterator , class Traits >
OutputIterator CGAL::approx_convex_partition_2(
      InputIterator 	first,
      InputIterator 	beyond,
      OutputIterator 	result,
      const Traits & 	traits = Default_traits 
)

代码实现:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                         Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::Polygon_2                                   Polygon_2;
typedef std::list<Polygon_2>                                Polygon_list;

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

void make_polygon(Polygon_2& polygon) {
   polygon.push_back(Point_2(391, 374));
   polygon.push_back(Point_2(240, 431));
   polygon.push_back(Point_2(252, 340));
   polygon.push_back(Point_2(374, 320));
   polygon.push_back(Point_2(289, 214));
   polygon.push_back(Point_2(134, 390));
   polygon.push_back(Point_2( 68, 186));
   polygon.push_back(Point_2(154, 259));
   polygon.push_back(Point_2(161, 107));
   polygon.push_back(Point_2(435, 108));
   polygon.push_back(Point_2(208, 148));
   polygon.push_back(Point_2(295, 160));
   polygon.push_back(Point_2(421, 212));
   polygon.push_back(Point_2(441, 303));
}

int main() {
   Polygon_2             polygon;
   Polygon_list          partition_polys;
   make_polygon(polygon);
   CGAL::approx_convex_partition_2(polygon.vertices_begin(),
                             polygon.vertices_end(),
                             std::back_inserter(partition_polys));

   for (auto poly_it = partition_polys.begin(); poly_it != partition_polys.end(); poly_it++) {
      print_polygon(*poly_it);
   }

  assert(CGAL::convex_partition_is_valid_2(polygon.vertices_begin(),
                                     polygon.vertices_end(),
                                     partition_polys.begin(),
                                     partition_polys.end()));
   return 0;
}

代码编译：

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

程序输出：

Polygon with 4 vertices
[391,374],[240,431],[252,340],[374,320],
Polygon with 3 vertices
[134,390],[68,186],[154,259],
Polygon with 3 vertices
[289,214],[134,390],[154,259],
Polygon with 3 vertices
[161,107],[435,108],[208,148],
Polygon with 3 vertices
[154,259],[161,107],[208,148],
Polygon with 4 vertices
[289,214],[154,259],[208,148],[295,160],
Polygon with 4 vertices
[374,320],[289,214],[295,160],[421,212],
Polygon with 4 vertices
[391,374],[374,320],[421,212],[441,303],

此外还有CGAL::greene_approx_convex_partition_2的多边形切分函数，不再赘述。

template<class InputIterator , class OutputIterator , class Traits >
OutputIterator CGAL::greene_approx_convex_partition_2	(	InputIterator 	first,
InputIterator 	beyond,
OutputIterator 	result,
const Traits & 	traits = Default_traits 
)

参考材料

https://doc.cgal.org/latest/Partition_2/index.html

https://en.wikipedia.org/wiki/Monotone_polygon

1.Monotone Partitioning

1.1 什么是单调多边形(monotone polygon)

1.2 Y Monotone Partition

2. Convex Partitioning

参考材料

Recommend

使用 Meld 在 Linux 中以图形方式比较文件和文件夹 | Linux 中国

golang的chan特性

Android 自动化交互实践

市值超过巴菲特投资公司特斯拉成美国第六大上市企业

做空机构香橼做空Palantir 并给予其20美元目标价

方法 | 如何进行MVP验证？

复工120天后，影院如何度过七年来最冷的11月？

只要涉及到金钱的说谎都是诈骗吗？

Paw 黑五免费（我个人认为最好的 API 请求工具）

美团这是疯了吗？

About Joyk