Marking (or coloring) CGAL objects

I am trying to use CGAL to do some simple 2D CSG operations. Below is an example of intersection of two polygons.

The actual problem is keeping track of the origin (color coded) of each segment in the resulting polygon.

I would like to know if this is possible, perhaps with some hacks on the CGAL itself. Any suggestion would be much appreciated.


source to share

1 answer

Unfortunately, there is no way to do this. However, this does not require too much (famous last words ...). You need to do two things described below. The first is supported by the API. The second is no, so you will need to fix the original file. A simple example is shown below. Note that the data you need, that is, the specification of the origin of each edge, goes into the data structure of the 2D structure. If you want to get polygons with this data, you need to extract it from the layout. You can get the title used in the example from Double Sided Book . pgn_print.h

  • Use an instance CGAL::Polygon_set_2<Kernel, Container, Dcel>

    where it Dcel

    is replaced with an expanded one Dcel

    whose half-element is expanded with a label indicating the start of the half-task (i.e. first polygon, second polygon, or both in case of overlap).

  • Download the header file Boolean_set_operations_2/Gps_base_functor.h. Specifically, add three functions to the body, called operators create_edge()

    , that label the resulting half-tasks according to their start:

  void create_edge(Halfedge_const_handle h1, Halfedge_const_handle h2,
                   Halfedge_handle h)

  void create_edge(Halfedge_const_handle h1, Face_const_handle f2,
                   Halfedge_handle h)

  void create_edge(Face_const_handle f1, Halfedge_const_handle h2,
                   Halfedge_handle h)


#include <list>
#include <vector>

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_set_2.h>

#include "pgn_print.h"

/*! Extend the arrangement halfedge */
template <typename X_monotone_curve_2>
class Arr_labeled_halfedge :
  public CGAL::Arr_halfedge_base<X_monotone_curve_2>
  unsigned m_label;

  Arr_labeled_halfedge() : m_label(0) {}
  unsigned label() const { return m_label; }
  void set_label(unsigned label) { m_label = label; }

  virtual void assign(const Arr_labeled_halfedge& he)
    m_label = he.m_label;

template <typename Traits>
class Arr_labeled_dcel :
  public CGAL::Arr_dcel_base<CGAL::Arr_vertex_base<typename Traits::Point_2>,
                             Arr_labeled_halfedge<typename Traits::
  Arr_labeled_dcel() {}

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                   Point_2;
typedef CGAL::Polygon_2<Kernel>                           Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>                Polygon_with_holes_2;
typedef std::vector<Point_2>                              Container;
typedef CGAL::Gps_segment_traits_2<Kernel, Container>     Traits_2;
typedef Arr_labeled_dcel<Traits_2>                        Dcel;
typedef CGAL::Polygon_set_2<Kernel, Container, Dcel>      Polygon_set_2;
typedef std::list<Polygon_with_holes_2>                   Pwh_list_2;
typedef Polygon_set_2::Arrangement_2                      Arrangement_2;
typedef Arrangement_2::Edge_const_iterator                Edge_const_iterator;

void print_result(const Polygon_set_2& S)
  std::cout << "The result contains " << S.number_of_polygons_with_holes()
            << " components:" << std::endl;

  Pwh_list_2 res;
  for (Pwh_list_2::const_iterator hit = res.begin(); hit != res.end(); ++hit) {
    std::cout << "--> ";

  const Arrangement_2& arr = S.arrangement();
  for (Edge_const_iterator it = arr.edges_begin(); it != arr.edges_end(); ++it) {
    std::cout << it->curve()
              << ", " << it->label()
              << std::endl;

int main()
  // Construct the two input polygons.
  Polygon_2 P;
  P.push_back(Point_2(0, 0));
  P.push_back(Point_2(5, 0));
  P.push_back(Point_2(3.5, 1.5));
  P.push_back(Point_2(2.5, 0.5));
  P.push_back(Point_2(1.5, 1.5));
  std::cout << "P = "; print_polygon(P);

  Polygon_2 Q;
  Q.push_back(Point_2(0, 2));
  Q.push_back(Point_2(1.5, 0.5));
  Q.push_back(Point_2(2.5, 1.5));
  Q.push_back(Point_2(3.5, 0.5));
  Q.push_back(Point_2(5, 2));
  std::cout << "Q = "; print_polygon(Q);

  // Compute the union of P and Q.
  Polygon_set_2 intersection_set;

  // Compute the intersection of P and Q.
  Polygon_set_2 union_set;

  return 0;




All Articles