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

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

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

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