Search code examples
cgal

Tagging (or coloring) CGAL objects

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

The actual problem is tracking down the origin (marked with color) of each segment in resulting polygon.

I would like to know if that is possible, maybe with some hacking on the CGAL itself. Any suggestion will be highly appreciated.

Solution

  • Unfortunately, there is no out-of-the-box way doing it. However, it doesn't require too much (famous last words...). You need to do two things described below. The first is supported by the API. The second is not, so you will need to patch a source file. A simple example is provided further bellow. Notice that the data you need, that is, the specification of the origin of each edge, ends up in a 2D arrangement data structure. If you want to obtain the polygons with this data, you need to extract them from the arrangement. You can obtain the header pgn_print.h, used in the example, from the 2D-Arrangement book.

    1. Use an instance of CGAL::Polygon_set_2<Kernel, Container, Dcel>, where the Dcel is substituted with an extended Dcel, the halfedge of which is extended with a label that indicates the origin of the halfedge (i.e., first polygon, second polygon, or both in case of an overlap).

    2. Patch the header file Boolean_set_operations_2/Gps_base_functor.h. In particular, add to the body of the three functions called create_edge() statements that set the label of the resulting halfedges according to their origin:

      void create_edge(Halfedge_const_handle h1, Halfedge_const_handle h2,
                   Halfedge_handle h)
  {
    h->set_label(3);
    h->twin()->set_label(3);
  }

  void create_edge(Halfedge_const_handle h1, Face_const_handle f2,
                   Halfedge_handle h)
  {
    h->set_label(1);
    h->twin()->set_label(1);
  }

  void create_edge(Face_const_handle f1, Halfedge_const_handle h2,
                   Halfedge_handle h)
  {
    h->set_label(2);
    h->twin()->set_label(2);
  }

    #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>
{
private:
  unsigned m_label;

public:
  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)
  {
    CGAL::Arr_halfedge_base<X_monotone_curve_2>::assign(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::
                                                  X_monotone_curve_2>,
                             CGAL::Gps_face_base>
{
public:
  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;
  S.polygons_with_holes(std::back_inserter(res));
  for (Pwh_list_2::const_iterator hit = res.begin(); hit != res.end(); ++hit) {
    std::cout << "--> ";
    print_polygon_with_holes(*hit);
  }

  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;
  intersection_set.insert(P);
  intersection_set.intersection(Q);
  print_result(intersection_set);

  // Compute the intersection of P and Q.
  Polygon_set_2 union_set;
  union_set.insert(P);
  union_set.join(Q);
  print_result(union_set);

  return 0;
}