2D Arrangements

Introduction

2D Arrangement:  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''.

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.

Update Mode:  For some algorithms, it is not needed to build the whole planar map induced by the arrangement. For example, the lower envelope of an arrangement of $$x-monotone curves which intersect each other at most a fixed constant $$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.

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. The Overlap_circulator enables to traverse all overlapping edge_nodes that correspond to the same pair of halfedges in the map.

Implementation

The arrangement class holds a planar map and a hierarchy tree. Vertices, halfedges and faces of the arrangement derive from those of the planar map (with the additional functionality of the arrangement), in the same way that the vertices, halfedges and faces of the topological map class derive from those of the Dcel class (see Chapter).

The hierarchy tree is implemented using the In_place_list class (see the chapter on STL Extensions in the Support Library Manual). Every level of a curve hierarchy is a list of tree nodes.The Curve_node and Edge_node of the hierarchy derive from Subcurve_node. This enables the polymorphic structure of the tree. The Subcurve_node is derived from the Base_node which is a template parameter of the arrangement. This enables to add attributes to the nodes of the hierarchy tree by adding them inside the Base_node.

Example Programs

Simple Example of a Segment Arrangement

//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>

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 ;
      }
   }
}

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

//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>

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_iterator hit;
   for (hit=arr.halfedges_begin(); hit!=arr.halfedges_end(); ++hit,++hit) {
     //we skip the adjacent twin halfedge
     Arr_2::Overlap_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.

Example of a Circle Arrangement

Figure:  The arrangement generated by the example program.

//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;
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;
   Arr_2::Halfedge_handle e=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;
}

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.

//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>

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;

//a simple functions 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);

using namespace std;

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 ;
      }
   }
}

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).

//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>

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;

//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;
};

using namespace std;

int main() {
   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);                                  
}

Arrangements

• Class declaration of Arrangement_2<Dcel,Traits,Base_node>.

• Class declaration of Subcurve_node.

• Class declaration of Curve_node.

• Class declaration of Edge_node.

• Class declaration of Vertex.

• Class declaration of Halfedge.

• Class declaration of Face.

Requirements for Arrangement Dcel Classes

The arrangement Dcel class requirements are identical to those of the planar map Dcel with additional functions for the Dcel Halfedge class which correspond to the additions listed above.

• Class declaration of Halfedge.

Model for an Arrangement Dcel Class

The Pm_dcel<V,H,F> is a model of the Dcel concept defined above. Its template parameters are the vertex, halfedge and face classes which conform to the requirements given above.

#include <CGAL/Pm_default_dcel.h>

Models for Dcel Vertex, Halfedge and Face

The Arr_2_vertex_base<Point> is a model for the Dcel vertex concept defined above. The Arr_2_halfedge_base<Base_node> is a model for the Dcel halfedge concept defined above. The Arr_2_face_base is a model for the Dcel face concept defined above.

#include <CGAL/Arr_2_bases.h>

The Default Dcel Structure

The Arr_2_default_dcel<Traits> is a model of the Dcel concept defined above. Its template parameter is the traits class defined below. It is a wrapper for Pm_dcel instantiated with Arr_2_vertex_base<Traits::Point>,
Arr_2_halfedge_base<Arr_base_node<Traits::X_curve> > and Arr_2_face_base.

#include <CGAL/Arr_2_default_dcel.h>

Requirements for Arrangement Traits Classes

• Class declaration of Arr_traits.

Models for an Arrangement Traits Class

Segment Traits Using the CGAL Kernel

#include <CGAL/Arr_segment_exact_traits.h>

• Class declaration of Arr_leda_segment_exact_traits.

Circle Traits

The Point type is Point_2<Cartesian<NT> >. The Curve and X_curve representation is a Circle_2<Cartesian<NT> > with two additional points corresponding to the source and target points. The copy and default constructor as well as the assignment and equality operators are provided for the curves. An operator<< for the curves is defined both for Window_stream. In addition, the following constructors and member functions are provided for the curves:

• Class declaration of Circ_curve.

#include <CGAL/Arr_circles_real_traits.h>

#include <CGAL/IO/Arr_circle_traits_Window_stream.h>

Requirement for Arrangement Base_node Class

The arrangement class is parameterized with the Base_node class which defines the base class for the objects inside the hierarchy tree. In this section we present the formal requirements for a Base_node class.

• Class declaration of Base_node.

Model for an Arrangement Base_node Class

The Arr_base_node<Curve> is a model of the Base_node concept defined above. Its template parameter is the curve class which should correspond to the traits' Curve class.

#include <CGAL/Arr_2_bases.h>