2D Arrangements

Introduction

Given a collection $$C of (possibly intersecting and not necessarily $$x-monotone) curves in the plane, we construct a collection $$C'' in two steps: First we decompose each curve in $$C into maximal $$x-monotone curves, thus obtaining the collection $$C'. We then 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. The arrangement of the curves in $$C is the planar map (see Chapter ) induced by the curves in $$C''.

Software Design

The class CGAL::Arrangement_2<Dcel,Traits,Base_node> is a data structure for maintaining 2D arrangements. The data structure maintains a planar map and curve hierarchy trees. There is a curve tree for each curve inserted into the arrangement (see below). The underlying combinatorial structure is determined by the Dcel template parameter, which should be a model of the ArrangementDcel_2 concept. The family of curves of the arrangement is determined by the Traits template parameter which should be a model of the ArrangementTraits_2 concept. The Base_node template parameter defines the attributes associated with each tree node of the hierarchy tree.

Curve Hierarchy Tree:  When constructing an arrangement we decompose each curve $$c in two steps obtaining the collections $$c' and $$c''. We regard these collections as levels in a hierarchy of curves where the union of the subcurves in each level is the original curve $$c. We store these collections in a special structure - a hierarchy tree. This structure usually consists of three levels, although in some cases they can consist of less (e.g., when inserting an $$x-monotone curve) or more (when the users define their own split functions see Section ). The levels are:

• Curve node level: the root of the tree - holds the original curve.
• Subcurve node level: inner nodes of the tree - hold decomposed subcurves of the original curve. In the default mode these are $$x-monotone curves.
• Edge node level: leaves of the tree - hold the curves corresponding to the edges of the planar map induced by the arrangement. These nodes will be built only in update mode (by default the arrangement is in update mode).

Figure  shows an example of a simple arrangement and its corresponding curve hierarchy.

Figure:  A simple arrangement of two polylines, and its corresponding hierarchy tree (the edges of the arrangement are numbered according to their order in the tree).

The hierarchy tree enables us to intersect the curves without loss of information. The original curve and the intermediate subcurves are stored in the tree and the user can traverse them. Furthermore, the users can define their own hierarchy by passing their own intersection sequence. This can be of use in some applications. For example, in an arrangement of spline curves the users might want to intersect a curve in the junction points before making the curve $$x-monotone.

Degeneracies  Like the planar map package (see Chapter ), the arrangement package can deal with $$x-degenerate input (including vertical segments). However, while in the planar map the input curves were assumed to be $$x-monotone and non-intersecting in their interiors, there are no such assumptions in the arrangement. A non $$x-monotone curve is partitioned into $$x-monotone subcurves, and curves are intersected in their points of intersection with other points before they are inserted into the map. Furthermore, overlapping curves are supported. If two curves overlap the traits intersection function returns the two endpoints of the common part. Circulators of the Overlap_circulator type (of Arrangement_2<Dcel,Traits,Base_node>) enables to traverse all overlapping edge_nodes that correspond to the same pair of halfedges in the map.

I/O functions:  I/O functions for reading a saved arrangement from the standard input, writing it to the standard output or drawing it to a graphic stream are also provided. Users of I/O functions for the arrangement package are required to define I/O operators for the curves defined in their Traits classes.

Update Mode:  For some algorithms, it is not necessary to build the whole planar map induced by the arrangement. For example, the lower envelope of an arrangement of $$x-monotone curves that intersect each other at most a fixed constant number of $$s times, can be found in near linear time [SA95, Hal97] even if the complexity of the planar map induced by it is quadratic. Therefore, building the planar map induced by the arrangement is not always desired. The users can therefore disable (or postpone) the building of the planar map. This is done by disabling the update mode using the set_update(bool) member function. When update mode is set to true, the planar map is updated - this is the default situation. When update mode is set to false, the hierarchy tree is built without its Edge_level, and the curves are not inserted into the planar map.

Segment Arrangements

The second template parameter of the arrangement class determines the so-called geometry of the arrangement, that is the family of curves we want to deal with. In order to deal with line segments we simply plug in on of the two segment traits classes supplied.

The Arr_segment_exact_traits<R> class is generic and allows flexibility in determining the kernel which is used. The Arr_leda_segments_exact_traits<R> is specialized to use LEDA's geometric rational kernel and works with LEDA's rational numbers. It has better performance.

Example of an Arrangement of Segments

The four numbers on each output lines is a representation of a segment. The first two numbers are the $$x and $$y coordinates of the first endpoint. The other two numbers are of the second endpoint. The way a curve is printed depends on the the output operator implemented for it.

//examples/Arrangement_2/example1.C
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arr_segment_exact_traits.h>
#include <CGAL/Arrangement_2.h>

// We use here double instead of leda_real 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 Traits::Curve                                 Curve;

typedef CGAL::Arr_base_node<Curve>                    Base_node;
typedef CGAL::Arr_2_default_dcel<Traits>              Dcel;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node >   Arr_2;

using namespace std;

int main() {
  
  Arr_2 arr;

  //insertion of the curves
  Arr_2::Curve_iterator cit=arr.insert(Curve(Point(0,0),Point(1,1)));
  cit=arr.insert(Curve(Point(0,1),Point(1,0))); 
  
  //traversal of the curves
  Arr_2::Edge_iterator eit;
  for (cit=arr.curve_node_begin(); cit!=arr.curve_node_end(); ++cit) {
    cout << "\nCurve level:\n" << cit->curve() << endl ;
    cout << "Edge level:\n";
    for (eit=cit->edges_begin(); eit!=cit->edges_end(); ++eit) {
      cout << eit->curve() << endl ;
    }
  }

  return 0;
}

The output of the program looks like this:

Curve level:
0 0 1 1
Edge level:
0 0 0.5 0.5
0.5 0.5 1 1

Curve level:
0 1 1 0
Edge level:
0 1 0.5 0.5
0.5 0.5 1 0

Example of Overlapping Segments

//examples/Arrangement_2/example2.C
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arr_segment_exact_traits.h>
#include <CGAL/Arrangement_2.h>

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

typedef Traits::Point                                 Point;
typedef Traits::Curve                                 Curve;

typedef CGAL::Arr_base_node<Curve>                    Base_node;
typedef CGAL::Arr_2_default_dcel<Traits> Dcel;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node >   Arr_2;

using namespace std;

int main() {
   Arr_2 arr;

   //insertion of the curves
   Arr_2::Curve_iterator cit=arr.insert(Curve(Point(0,0),Point(2,2)));
   cit=arr.insert(Curve(Point(1,1),Point(3,3))); 
  
   //traversal of the halfedges
   Arr_2::Halfedge_const_iterator hit;
   for (hit=arr.halfedges_begin(); hit!=arr.halfedges_end(); ++hit,++hit) {
     //we skip the adjacent twin halfedge
     Arr_2::Overlap_const_circulator occ=hit->overlap_edges();
     int count=0;
     do {
       count++;
     } while (++occ!=hit->overlap_edges());

   if (count == 1) 
     cout << "Edge " << occ->curve() << " is covered by a single edge.\n";
   else
     cout << "Edge " << occ->curve() << " is covered by " << count << " edges.\n";

   }

   return 0;
}

The output of the program looks like this:

Edge 0 0 1 1 is covered by a single edge.
Edge 1 1 2 2 is covered by 2 edges.
Edge 2 2 3 3 is covered by a single edge.

Arrangements with Circular Arcs

There is a traits class for circular arcs (Arr_circle_real_traits<NT>) and a traits class for both circular arcs and line segments (Arr_segment_circle_traits<NT>, which can be use, e.g., in motion planning applications. These traits classes expect a number type that supports the square root operation.

Example of an Arrangement of Circular Arcs

//examples/Arrangement_2/example3.C   
#include <CGAL/basic.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arr_circles_real_traits.h> 
#include <CGAL/Arrangement_2.h>

//#include <CGAL/leda_real.h>
//typedef leda_real                                     NT;

// We use here double instead of leda_real 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::Arr_circles_real_traits<NT>             Traits;

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

typedef CGAL::Arr_base_node<Curve>                    Base_node;
typedef CGAL::Arr_2_default_dcel<Traits>              Dcel;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node >   Arr_2;

using namespace std;

int main() {
   Arr_2 arr;  

   //2 ccw circles with radius 5 and center (0,0) and (6,0) resp.
   Arr_2::Curve_iterator cit=arr.insert(Curve(0,0,25));
   cit=arr.insert(Curve(6,0,25)); 

   //upward vertical ray shooting
   Arr_2::Locate_type lt;
#ifndef CGAL_NO_ASSERTIONS // in order to avoid warnings
   Arr_2::Halfedge_handle e=
#endif
     arr.vertical_ray_shoot(Point(-1,0),lt,true);

   CGAL_assertion(e->source()->point()==Point(3,4)); 
   CGAL_assertion(e->target()->point()==Point(-5,0));

   return 0;
}

Polyline Arrangements

There are two supplied traits classes for polyline (a.k.a., poly-segment) curves (Arr_polyline_traits<R, Container> and Arr_leda_polyline_traits<Container>).

Example of a Polyline Arrangement

For this simple example the built-in double number type will run correctly, it is not recommended in the general case. The traits are robust only when used with a number type such as LEDA real number type (requires LEDA to be installed in order to run).

//examples/Arrangement_2/example10.C

// Define shorter names to please linker (g++)
#define Arrangement_2 Ar
#define _In_place_list_iterator IPLI
#define Cartesian CRTS
#define Arr_polyline_traits APT

#include <CGAL/Cartesian.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_polyline_traits.h>

//#include <CGAL/leda_real.h>
//typedef leda_real                                     NT;

// We use here double instead of leda_real 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>                           Rep;
typedef CGAL::Arr_polyline_traits<Rep>                Traits;

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

typedef CGAL::Arr_base_node<Curve>                    Base_node;
typedef CGAL::Arr_2_default_dcel<Traits>              Dcel;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node >   Arr_2;

int main() {
   Arr_2 arr;
   Curve in_curve;

   // curve #1, not x monotone
   in_curve.push_back(Point(  0,  0));
   in_curve.push_back(Point( 10, 10));
   in_curve.push_back(Point(  0, 20));
   arr.insert(in_curve); 

   // curve #2, x monotone
   in_curve.clear();
   in_curve.push_back(Point(100,  0));
   in_curve.push_back(Point(150, 50));
   in_curve.push_back(Point(200,  0));
   arr.insert(in_curve);

   // curve #1 is broken into two edges. Point (10,10) turns into a vertex.
   Arr_2::Locate_type lt;
   arr.locate(Point(10, 10), lt);
   CGAL_assertion(lt == Arr_2::VERTEX);

   return 0;
}

User-defined Hierarchy

The default hierarchy structure can be extended to include more levels according to user defined split functions.

Example of a User-defined Hierarchy

The following example demonstrates the construction of an arrangement of two segments, using a user-defined hierarchy. We use a simple split function that splits a segment in its middle point. We insert the first segment using the user-defined function and the second segment with the regular function.

//examples/Arrangement_2/example4.C
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arr_segment_exact_traits.h>
#include <CGAL/Arrangement_2.h>
#include <vector>
#include <list>

// We use here double instead of leda_real 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 Traits::Curve                                  Curve;
typedef CGAL::Arr_base_node<Curve>                     Base_node;
typedef CGAL::Arr_2_default_dcel<Traits>               Dcel;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node >    Arr_2;

using namespace std;

//a simple function that splits a segment into 2
void my_split_f(const Curve& cv, list<Curve>& l) {
  Point s=cv.source(); //uses the knowledge of the curve functions
  Point t=cv.target();
  Point m1=s+(t-s)/2.0;
  l.push_back(Curve(s,m1));
  l.push_back(Curve(m1,t));
}

typedef void (*SPLIT_FUNC)(const Curve& cv, list<Curve>& l);

int main() {
   vector<SPLIT_FUNC> func_vec;
   func_vec.push_back(&my_split_f);
   Arr_2 arr;

   //insertion with user-defined function
   Arr_2::Curve_iterator cit=arr.insert(Curve(Point(0,0),Point(6,6)),
                                     func_vec.begin(),func_vec.end());

   //regular insertion                                  
   cit=arr.insert(Curve(Point(0,4),Point(6,4))); 
  
   //traversal of the curves
   Arr_2::Edge_iterator eit;
   for (cit=arr.curve_node_begin(); cit!=arr.curve_node_end(); ++cit) {
      cout << "\nCurve level:\n" << cit->curve() << endl ;
      cout << "Edge level:\n";
      for (eit=cit->edges_begin(); eit!=cit->edges_end(); ++eit) {
         cout << eit->curve() << endl ;
      }
   }

   return 0;
}

The output of the program looks like this:

Curve level:
0 0 6 6
Edge level:
0 0 3 3
3 3 4 4
4 4 6 6

Curve level:
0 4 6 4
Edge level:
0 4 4 4
4 4 6 4

Example of a User-defined Hierarchy with Function Objects

The following example demonstrates the use of a function object in a user-defined hierarchy. We define a base class for the function objects with a virtual operator(), that the function objects override (this kind of pattern is sometimes called an Action class (see for example [Str97, Chapter 25.5]). This enables us to use an inner state in our function as is done in the example.

In the example we define two levels of a hierarchy. The first level splits the inserted segment in the middle. The second layer splits every curve of the first layer in a ratio of $$1/3 : 2/3. Therefore, after an insertion of the segment $$(0,0) - (6,6) we will have four edges (eight halfedges) inside the arrangement, corresponding to the segments: $$(0,0) - (1,1), $$(1,1) - (3,3), $$(3,3) - (4,4) and $$(4,4) - (6,6).

//examples/Arrangement_2/example5.C
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arr_segment_exact_traits.h>
#include <CGAL/Arrangement_2.h>
#include <vector>
#include <list>

// We use here double instead of leda_real 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 Traits::Curve                                 Curve;
typedef CGAL::Arr_base_node<Curve>                    Base_node;
typedef CGAL::Arr_2_default_dcel<Traits>              Dcel;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node >   Arr_2;

using namespace std;

//a base class for split functions
struct Split_base {
  virtual void operator()(const Curve& cv, list<Curve>& l)=0;
};

struct Split_func : public Split_base {
  Split_func(double ratio) : r(ratio) {}
  void operator()(const Curve& cv, list<Curve>& l) {
     Point s=cv.source(); //uses the knowledge of the curve functions
     Point t=cv.target();
     Point m1=s+(t-s)/r;
     l.push_back(Curve(s,m1));
     l.push_back(Curve(m1,t));
   }     
private:
  double r;
};

int main() {
   std::vector<Split_base*> func_vec;
   func_vec.push_back(new Split_func(2.0));
   func_vec.push_back(new Split_func(3.0));
   Arr_2 arr;

   //insertion with user-defined function
   Arr_2::Curve_iterator cit=arr.insert(Curve(Point(0,0),Point(6,6)),
                                     func_vec.begin(),func_vec.end());

   CGAL_assertion(arr.number_of_halfedges()==8);                               

   CGAL_assertion(cit->number_of_sc_levels()==2);
   return 0;
}