Using CGAL to partition a non-simple polygon

Question

Suppose that I have a non-simple polygon, how CGAL can help me to partition it into a set of simple polygons?

For example, give a polygon represented by a sequence of 2D points:

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

I wish to acquire two polygons;

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

and

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

Is it doable for CGAL?

Answer 1

Your required two polygons do not make up the original hull. If you just want to break your original set into triangles using (0,0) as one of the vertices you can do this:

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

Which should give you output like this:

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) 

Answer 2

The question seems abandoned... Anyway, I'm adding a simple code to answer it:

#include <iostream>
#include <vector>

#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.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;

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());
  // ------ print the arrangement bounded faces 
  auto faceN = 1;
  for (auto fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
  {
    if (not fit->is_unbounded())
    {
      std::cout << "Face #" << faceN++ << ": ";
      auto const heitBeg = fit->outer_ccb();
      auto heit = heitBeg;
      do {std::cout << "[" << heit->curve() << "]";} while (++heit != heitBeg);
      std::cout << std::endl;
    }
  }
}

The function CGAL::insert automatically computes the intersection point (0,0). The output is:

Face #1: [-0 -0 -1 1][-1 1 -1 -1][-1 -1 -0 -0]
Face #2: [-0 -0 1 1][1 -1 -0 -0][1 1 1 -1]