2D Planar Maps of Intersecting Curves

Introduction

2D Planar Map with Intersections:  Given a collection $$C of (possibly intersecting and not necessarily $$x-monotone curves in the plane, we construct a collection $$C'' in two steps, as follows: First, we decompose each curve in C into maximal x-monotone curves, thus obtaining the collection $$C'. Second, We decompose each curve in $$C' into maximal connected pieces not intersecting any other curve in $$C'. This way we obtain the collection $$C'' of $$x-monotone, pairwise interior disjoint curves. Constructing the planar map with intersection of the curves in $$C gives the planar map(see Chapter ) induced by the curves in $$C''.

The Planar Map with Intersections package extends the functionality of the Planar Map package by enabling simple insertion of intersecting not necessarily $$x-monotone curves. The Planar_map_with_intersections_2 class has different insertion functions but it uses the same data structures as the planar map. Therefore, almost any functionality of the planar map is also supported here (e.g., traversal of planar map features, point location queries and I/O operations are supported but infinite objects are not supported). However, the planar map with intersections needs additional intersection functions in the geometric traits class. Note that if one needs to build a planar map of $$x-monotone, pairwise interior disjoint curves, then it would be more efficient (in running time) and less demanding (in traits class functionality) to use the planar map class.

Degeneracies  Like the Planar Map package (see Chapter ), the Planar Map with Intersections package can deal with $$x-degenerate input (including vertical segments). However, while in the planar map the input curves were assumed to be non intersecting in their interiors, there is no such assumption when using planar map with intersections. Furthermore, overlapping curves are supported. If two curves overlap the traits intersection function returns the two endpoints of the common part.

Simple Example of a Segment Planar Map with Intersections

// examples/Pm_with_intersections/example1
// ---------------------------------------
#include <CGAL/Cartesian.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Arr_segment_exact_traits.h>
#include <CGAL/Planar_map_2.h>
#include <CGAL/Pm_with_intersections.h>

// We use here double instead of leda_rational to enable compilation 
// without LEDA.
// This is not recommended generally.
// Read more in the README file or in the manual.
typedef double                                        NT;
typedef CGAL::Cartesian<NT>                           R;
typedef CGAL::Arr_segment_exact_traits<R>             Traits;

typedef Traits::Point                                 Point;
typedef Traits::X_curve                               X_curve;

typedef CGAL::Pm_default_dcel<Traits>                          Dcel;
typedef CGAL::Planar_map_2<Dcel,Traits>                        Planar_map_2;
typedef CGAL::Planar_map_with_intersections_2<Planar_map_2>    Pmwx;

using namespace std;

int main() {
  
  Pmwx pm;
  X_curve cv1(Point(0,0),Point(1,1));
  X_curve cv2(Point(0,1),Point(1,0)); 

  //insertion of the curves
  cout << "Inserting the segments:" << endl;
  cout << cv1 << endl;
  pm.insert(cv1);
  cout << cv2 << endl << endl;
  pm.insert(cv2);
  
  //traversal of the curves
  cout << "Edges of the planar map:" << endl;

  Pmwx::Halfedge_iterator eit;
  for (eit = pm.halfedges_begin(); eit != pm.halfedges_end(); ++eit, ++eit) {
    cout << eit->source()->point();
    cout << " --- ";
    cout << eit->target()->point();
    cout << endl;
  }

  return 0;
}

The output of the program looks like this:

Inserting the segments:
0 0 1 1
0 1 1 0

Edges of the planar map:
0 0 --- 0.5 0.5
0.5 0.5 --- 1 1
0 1 --- 0.5 0.5
1 0 --- 0.5 0.5