| by YoungTimes | No comments

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

除非注明，否则均为[半杯茶的小酒杯]原创文章，转载必须以链接形式标明本文链接

本文链接：http://www.banbeichadexiaojiubei.com/index.php/2020/11/28/2d%e5%a4%9a%e8%be%b9%e5%bd%a2%e5%88%87%e5%88%862d-polygon-partition/

相关文章:

  1. 任意简单多边形求差集(difference)
  2. 判断点在多边形内部、在多边形边界上还是在多边形外部
  3. 判断多边形为顺时针或者逆时针
  4. 判断点位于有向线段的左侧或者右侧
  5. 多边形求并集(Union)
  6. CGAL实现多边形凸分解
  7. CGAL计算多边形的对称差 (Symmetric difference)
  8. 计算几何-凸包(Convex Hull)
  9. 计算几何-线扫描算法计算矩形并集面积
  10. 计算几何-最近点对问题
« Prev