Chapter 21
2D Planar Maps of Intersecting Curves

21.1   Introduction

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

The Planar Map with Intersections package extends the functionality of the Planar Map package by enabling simple insertion of intersecting and 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_2 class. 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, to maintain a planar map with intersections one obviously needs to support some additional functions in the geometric traits class, handling with intersections and $$x-monotonicity.

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_2 class instead.

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 also supported: If two curves overlap the traits intersection function must return the two endpoints of the common part.

21.1.1   A Simple Program

// file: examples/Pm_with_intersections/example1.C

#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Quotient.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Planar_map_2.h>
#include <CGAL/Pm_with_intersections.h>

typedef CGAL::Quotient<CGAL::MP_Float>                      NT;
typedef CGAL::Cartesian<NT>                                 Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>                  Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::X_monotone_curve_2                          X_monotone_curve_2;
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;

int main() {
  
  Pmwx pm;
  X_monotone_curve_2 cv1(Point_2(0, 0), Point_2(1, 1));
  X_monotone_curve_2 cv2(Point_2(0, 1), Point_2(1, 0)); 

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

  Pmwx::Halfedge_const_iterator eit;
  for (eit = pm.halfedges_begin(); eit != pm.halfedges_end(); ++eit, ++eit) {
    std::cout << eit->source()->point()
              << " --- " << eit->target()->point() << std::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

21.2   Architecture

The Planar_map_with_intersections_2<Planar_map_2<Dcel, Traits> > class is parameterized with the Planar_map_2 class it inherits from, which is parameterized with the Dcel and the Traits objects. The Dcel is a data structure that maintains a doubly-connected edge list and represents the underlying topology. The geometric functionality is provided by the Traits class, and is tailored to handle a specific family of curves. It encapsulates the number type used and the coordinate representation. This package contains traits classes that handle various types of curves (e.g., segments, polylines, conics, etc.).

Similar to some constructors of the Planar_map_2, (see Chapter ), some of the constructors of the Planar_map_with_intersections_2 class allow you to choose between various point-location strategies. While the default point-location strategy of the Planar_map_2 class is the trapezoid-ric strategy, which is based on a trapezoidal decomposition of the map, and requires constructing and maintening auxliary data structures, the default strategy of the Planar_map_with_intersections_2 class is the walk-along-a-line strategy, as the overhead of the former tends to be very large when no restrictions are applied on the input curves.

21.2.1   Operations

Aggregated Insert

A Planar Map with Intersections can be built incrementally by inserting one curve after the other into the map. However, for a large number of curves that intersect rather sparsely, it can be more efficient to use the aggregate insertion method, that inserts a set of curves to an empty map at once by performing the sweep-line algorithm on the set of input curves.

The aggregate insertion method is more efficient in many cases and it also has less requirements from the traits class, in comparison with the the incremental insertion function. Namely, the curves_compare_y_at_x_left() and the nearest_intersection_to_left() functions are not required, nor do the various reflection functions.

Example of Aggregate Insertion

The output of the program looks like this:

Non Intersecting Insertion Functions

In some cases the users insert curves to a planar map with intersections in an incremental manner, but have some knowledge regarding the location of several curves. In such cases, special insertion functions may be called in order to speed up the construction of the map:

• If it is known in advance that the current curve is $$x-monotone and does not intersect any one of the curves currently in the map in its interior, it is possible to insert this curve using the non_intersecting_insert() function. A similar function is also available for a range of $$x-monotone and interior-disjoint curves, that does not induce any intersection with the existing curves in the map.
• Sometimes the exact location of the $$x-monotone curve in the map is known. It may be inserted (1) within the interior of a given face, (2) with one given vertex as one of its endpoints, or (3) between to given vertices. The non_intersecting_insert_in_face_interior(), non_intersecting_insert_from_vertex() and non_intersecting_insert_at_vertices() functions serve for this purpose. For more details regrading these special insertion functions, as well as for an example for their usage, see section .

advanced

21.2.2   Change Notification

An insertion of an intersecting curve into a planar map may add several halfedges and modify several features of the map (i.e. split halfedges, split faces, etc.). The so-called Change Notification class provides this kind of flexibility. The modification methods accept an additional parameter, a class which is a model of the PlanarMapWithIntersectionsChangeNotification_2 concept. The change notification includes an associative function for each modification method. This function is called after each such modification.

The change notification class is useful in many cases. For example, one may add a color (or other extra data) to any halfedge of a planar map. An insertion of a new curve can split halfedges that were previously in the map. After such a split the color of the newly created halfedges should be updated according to the original color of the split halfedge. One can do this by implementing the split_edge function of the change notification class. This function will be called after each split of an halfedge in the map.

Example of Change Notification

The following example demonstrates the usage of the change notification concept during the construction of a planar map out of three segments - $$(0,1)-(1,0), $$(0,0)-(1,1) and $$(0,1)-(1,1). During the insertion we use My_notification instance to output the internal process of the construction of the planar map. We also count how many edges are in the map by incrementing a counter each time an edge is added (add_edge) or split (split_edge).

// file: examples/Pm_with_intersections/example2.C

#include "short_names.h"

#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Quotient.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Planar_map_2.h>
#include <CGAL/Pm_with_intersections.h>

typedef CGAL::Quotient<CGAL::MP_Float>                      NT;
typedef CGAL::Cartesian<NT>                                 Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>                  Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::X_monotone_curve_2                          X_monotone_curve_2;
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;
typedef Pmwx::Pmwx_change_notification Pmwx_change_notification;

class My_notification : public Pmwx_change_notification 
{
public:

  My_notification()
  {i = 0;}

  void add_edge(const  Traits::X_monotone_curve_2 &,
                Planar_map::Halfedge_handle, 
                bool /* left_to_right */, bool overlap = false)
  {
    (void) overlap;
    std::cout << "add_edge" << std::endl;
    i++;
  }

  void split_edge(Planar_map::Halfedge_handle /* orig_edge */, 
                  Planar_map::Halfedge_handle /* new_edge */,
                  const Traits::X_monotone_curve_2 &,
                  const Traits::X_monotone_curve_2 &)
  {
    std::cout << "split_edge" << std::endl;
    i++;
  }

  void split_face(Planar_map::Face_handle /* orig_face */, 
                  Planar_map::Face_handle /* new_face */)
  {
    std::cout << "split_face" << std::endl;
  }

  void add_hole(Planar_map::Face_handle /* in_face */, 
                Planar_map::Halfedge_handle /* new_hole */)
  {
    std::cout << "add_hole" << std::endl;
  }

  int i;
};

int main() {
  
  Pmwx pm;
  My_notification notif;

  //insertion of the curves
  X_monotone_curve_2 c1(Point_2(0, 1), Point_2(1, 0));
  X_monotone_curve_2 c2(Point_2(0, 0), Point_2(1, 1));
  X_monotone_curve_2 c3(Point_2(0, 1), Point_2(1, 1));

  std::cout << "inserting " << c1 << std::endl;
  pm.insert(c1, &notif);
  std::cout << "inserting " << c2 << std::endl;
  pm.insert(c2, &notif);
  std::cout << "inserting " << c3 << std::endl;
  pm.insert(c3, &notif);

  std::cout << "Total number of edges " << notif.i << std::endl;

  return 0;
}

The output of the program looks like this:

inserting 0 1 1 0
add_edge
add_hole
inserting 0 0 1 1
split_edge
add_edge
add_edge
inserting 0 1 1 1
add_edge
split_face
Total number of edges 5

advanced