使用CGAL对非简单多边形进行分割。

Question

假设我有一个非简单多边形，CGAL如何帮助我将其分割成一组简单多边形？

例如，给出由一系列2D点表示的多边形：

(1, 1) (1, -1) (-1, 1) (-1, -1) 

我希望获得两个多边形；

(1, 1) (1, -1) (0, 0)

并且。

(0, 0) (-1, 1) (-1, -1) 

可以用CGAL实现吗？

- Wei-Fan Chiang

Answer 1

这个问题似乎已经被放弃了...不管怎样，我添加了一个简单代码来回答它：

#include <iostream>
#include <vector>

#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Traits = CGAL::Arr_segment_traits_2<Kernel>;
using Arrangement = CGAL::Arrangement_2<Traits>;
using Point = Traits::Point_2;
using Segment = Traits::Segment_2;
using Polygon = CGAL::Polygon_2<Kernel>;

int main()
{
  // ------ create a segment chain
  Point const p1(1, 1), p2(1, -1), p3(-1, 1), p4(-1, -1);
  std::vector<Segment> const cv = {{p1, p2}, {p2, p3}, {p3, p4}, {p4, p1}};
  // ------ create the arrangement
  Arrangement arr;
  CGAL::insert(arr, cv.cbegin(), cv.cend());
  // ------ iterate the arrangement bounded faces and create simple polygons
  std::vector<Polygon> polygons;
  for (auto fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
  {
    if (not fit->is_unbounded())
    {
      Polygon poly;
      auto const heitBeg = fit->outer_ccb();
      auto heit = heitBeg;
      do {poly.push_back(heit->source()->point());} while (++heit != heitBeg);
      polygons.push_back(poly);
    }
  }
  // ------ print simple polygons
  auto polyN = 1;
  for (auto const& p: polygons)
  {
    std::cout << "Polygon #" << polyN++ << ": ";
    for (auto const& v: p.vertices()) std::cout << '(' << v << ") ";
    std::cout << std::endl;
  }
}

CGAL::insert 函数自动计算交点 (0,0)。输出结果为：

Polygon #1: (-0 -0) (-1 1) (-1 -1)
Polygon #2: (1 1) (-0 -0) (1 -1)

- HEKTO

Answer 2

您所需的两个多边形并不能组成原始外壳。如果您只想使用（0,0）作为其中一个顶点将原始集合分解为三角形，则可以执行以下操作：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Delaunay_mesh_vertex_base_2.h>
#include <CGAL/Delaunay_mesh_face_base_2.h>
#include <vector>    

typedef CGAL::Exact_predicates_inexact_constructions_kernel     K;
typedef K::Point_2                                              Point_2;
typedef CGAL::Delaunay_mesh_vertex_base_2<K>                    Vb;
typedef CGAL::Delaunay_mesh_face_base_2<K>                      Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb>            Tds;
typedef CGAL::Constrained_Delaunay_triangulation_2<K, Tds>      CDT;
typedef CDT::Vertex_handle                                      Vertex_handle;
typedef CDT::Face_iterator                                      Face_iterator;    

int main(int argc, char* argv[])
{
    // Create a vector of the points
    //
    std::vector<Point_2> points2D ;
    points2D.push_back(Point_2(  1,  1));
    points2D.push_back(Point_2(  1, -1));
    points2D.push_back(Point_2( -1,  1));
    points2D.push_back(Point_2( -1, -1));
    points2D.push_back(Point_2( 0, 0));

    size_t numTestPoints = points2D.size();

    // Create a constrained delaunay triangulation and add the points
    //
    CDT cdt;
    std::vector<Vertex_handle> vhs;
    for (unsigned int i=0; i<numTestPoints; ++i){
        vhs.push_back(cdt.insert(points2D[i]));
    }

    int i=0;
    for (Face_iterator fit = cdt.faces_begin()  ; fit != cdt.faces_end(); ++fit) {
        printf("Face %d is (%f,%f) -- (%f,%f) -- (%f,%f) \n",i++,
               fit->vertex(0)->point().x(),fit->vertex(0)->point().y(),
               fit->vertex(1)->point().x(),fit->vertex(1)->point().y(),
               fit->vertex(2)->point().x(),fit->vertex(2)->point().y() );

    }

    return 0 ;
}

这应该会给你输出如下：

Face 0 is (0.000000,0.000000) -- (1.000000,-1.000000) -- (1.000000,1.000000) 
Face 1 is (0.000000,0.000000) -- (1.000000,1.000000) -- (-1.000000,1.000000) 
Face 2 is (-1.000000,-1.000000) -- (0.000000,0.000000) -- (-1.000000,1.000000) 
Face 3 is (-1.000000,-1.000000) -- (1.000000,-1.000000) -- (0.000000,0.000000) 

- CobaltGray