namespace CGAL {
/*!

\mainpage User Manual
\anchor Chapter_2D_Arrangements
\anchor chapterArrangement_on_surface_2
\cgalAutoToc

\authors Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman

\section arr_secintro Introduction

Given a set \f$ \cal C\f$ of planar curves, the <I>arrangement</I>
\f$ \cal A(\cal C)\f$ is the subdivision of the plane into zero-dimensional,
one-dimensional and two-dimensional cells, called <I>vertices</I>, <I>edges</I> and <I>faces</I>, respectively induced by the curves in \f$ \cal C\f$.
Arrangements are ubiquitous in the computational-geometry
literature and have many applications;
see, e.g., \cgalCite{as-aa-00}, \cgalCite{cgal:h-a-04}.

The curves in \f$ \cal C\f$ can intersect each other (a single curve may also
be self-intersecting or may be comprised of several disconnected branches)
and are not necessarily \f$ x\f$-monotone.\cgalFootnote{A continuous planar curve \f$ C\f$ is <I>\f$ x\f$-monotone</I> if every vertical line intersects it at most once. For example, a non-vertical line segment is always \f$ x\f$-monotone and so is the graph of any continuous function \f$ y = f(x)\f$. For convenience, we treat vertical line segments as <I>weakly \f$ x\f$-monotone</I>, as there exists a single vertical line that overlaps them. A circle of radius \f$ r\f$ centered at \f$ (x_0, y_0)\f$ is not \f$ x\f$-monotone, as the vertical line \f$ x = x_0\f$ intersects it at \f$ (x_0, y_0 - r)\f$ and at \f$ (x_0, y_0 + r)\f$.}
We construct a collection \f$ \cal C''\f$ of
\f$ x\f$-monotone subcurves that are pairwise disjoint in their interiors
in two steps as follows. First, we decompose each curve in \f$ \cal C\f$
into maximal \f$ x\f$-monotone subcurves (and possibly isolated points),
obtaining the collection \f$ \cal C'\f$. Note that an \f$ x\f$-monotone curve cannot
be self-intersecting. Then, we decompose each curve in \f$ \cal C'\f$ into
maximal connected subcurves not intersecting any other
curve (or point) in \f$ \cal C'\f$. The collection \f$ \cal C''\f$ may also
contain isolated points, if the curves of \f$ \cal C\f$ contain such
points. The arrangement induced by the collection \f$ \cal C''\f$ can be
conveniently embedded as a planar graph, whose vertices are associated
with curve endpoints or with isolated points, and whose edges are
associated with subcurves. It is easy to see that
\f$ \cal A(\cal C) = \cal A(\cal C'')\f$. This graph can be represented using a
<I>doubly-connected edge list</I> data-structure (\sc{Dcel} for short),
which consists of containers of vertices, edges and faces and
maintains the incidence relations among these objects.

The main idea behind the \sc{Dcel} data-structure is to represent
each edge using a pair of directed <I>halfedges</I>, one going from
the \f$ xy\f$-lexicographically smaller (left) endpoint of the curve toward
its the \f$ xy\f$-lexicographically larger (right) endpoint, and the other,
known as its <I>twin</I> halfedge, going in the opposite direction. As each
halfedge is directed, we say it has a <I>source</I> vertex and a <I>target</I>
vertex. Halfedges are used to separate faces, and to
connect vertices (with the exception of <I>isolated vertices</I>, which
are unconnected).

If a vertex \f$ v\f$ is the target of a halfedge \f$ e\f$, we say that \f$ v\f$
and \f$ e\f$ are <I>incident</I> to each other. The halfedges incident
to a vertex \f$ v\f$ form a circular list oriented in a clockwise order
around this vertex. (An isolated vertex has no incident halfedges.)

Each halfedge \f$ e\f$ stores a pointer to its <I>incident face</I>,
which is the face lying to its left. Moreover, every halfedge is
followed by another halfedge sharing the same incident face, such
that the target vertex of the halfedge is the same as the source
vertex of the next halfedge. The halfedges are therefore connected
in circular lists, and form chains, such that all edges of a chain
are incident to the same face and wind along its boundary. We call
such a chain a <I>connected component of the boundary</I> (or <I>CCB</I> for short).

The unique CCB of halfedges winding in a counterclockwise orientation
along a face boundary is referred to as the <I>outer CCB</I> of the
face. For the time being let us consider only arrangements of
bounded curves, such that exactly one unbounded face exists in every
arrangement. The unbounded face does not have an outer boundary. Any
other connected component of the boundary of the face is called a
<I>hole</I> (or <I>inner CCB</I>), and can be represented as a circular
chain of halfedges winding in a clockwise orientation around it.
Note that a hole does not necessarily correspond to a single face,
as it may have no area, or alternatively it may consist of several
connected faces. Every face can have several holes contained in its
interior (or no holes at all). In addition, every face may contain
isolated vertices in its interior. See \cgalFigureRef{arr_figseg_dcel}
for an illustration of the various \sc{Dcel} features. For more details
on the \sc{Dcel} data structure see \cgalCite{bkos-cgaa-00} Chapter 2.

\cgalFigureBegin{arr_figseg_dcel,arr_segs.png}
An arrangement of interior-disjoint line segments with some of the \sc{Dcel} records that represent it. The unbounded face \f$ f_0\f$ has a single connected component that forms a hole inside it, and this hole is comprised if several faces. The half-edge \f$ e\f$ is directed from its source vertex \f$ v_1\f$ to its target vertex \f$ v_2\f$. This edge, together with its twin \f$ e'\f$, correspond to a line segment that connects the points associated with \f$ v_1\f$ and \f$ v_2\f$ and separates the face \f$ f_1\f$ from \f$ f_2\f$. The predecessor \f$ e_{\rm prev}\f$ and successor \f$ e_{\rm next}\f$ of \f$ e\f$ are part of the chain that form the outer boundary of the face \f$ f_2\f$. The face \f$ f_1\f$ has a more complicated structure as it contains two holes in its interior: One hole consists of two adjacent faces \f$ f_3\f$ and \f$ f_4\f$, while the other hole is comprised of two edges. \f$ f_1\f$ also contains two isolated vertices \f$ u_1\f$ and \f$ u_2\f$ in its interior.
\cgalFigureEnd

The \f$ x\f$-monotone curves of an arrangement are embedded in an
rectangular two-dimensional area called the parameter
space.\cgalFootnote{The term parameter space stems from a major extension the arrangement package is going through to support arrangements embedded on certain two-dimensional parametric surfaces in three-dimensions (or higher).} The parameter space is
defined as \f$ X \times Y\f$, where \f$ X\f$ and \f$ Y\f$ are open, half-open, or
closed intervals with endpoints in the compactified real line
\f$ \mathbb{R} \cup \{-\infty,+\infty\}\f$. Let \f$ b_l\f$, \f$ b_r\f$, \f$ b_b\f$, and
\f$ b_t\f$ denote the endpoints of \f$ X\f$ and \f$ Y\f$, respectively. We
typically refer to these values as the left, right, bottom, and top
sides of the boundary of the parameter space. If the parameter space
is, for example, the entire compactified plane, which is currently
the only option supported by the package, \f$ b_l = b_b = -\infty\f$ and
\f$ b_r = b_t = +\infty\f$.

The rest of this chapter is organized as follows: In
Section \ref arr_secarr_class we review in detail the interface
of the `Arrangement_2` class-template, which is the central
component in the arrangement package. In
Section \ref arr_secqueries we show how queries on an arrangement
can be issued. In Section \ref arr_secgl_funcs we
review some important free (global) functions that operate on
arrangements, the most important ones being the free
insertion-functions. Section \ref arr_sectraits contains detailed
descriptions of the various geometric traits classes included in
the arrangement package. Using these traits classes it is possible
to construct arrangements of different families of curves. In
Section \ref arr_secnotif we review the notification mechanism
that allows external classes to keep track of the changes that an
arrangement instance goes through. Section \ref arr_secex_dcel
explains how to extend the \sc{Dcel} records, to store extra data
with them, and to efficiently update this data.
In Section \ref arr_secoverlay we introduce the fundamental
operation of overlaying two arrangements.
Section \ref arr_secarr_with_hist describes the
`Arrangement_with_history_2` class-template that extends the
arrangement by storing additional history records with its curves.
Finally, in Section \ref arr_secio we review the arrangement
input/output functions.

\section arr_secarr_class The Main Arrangement Class

The class `Arrangement_2<Traits,Dcel>` is the main class in
the arrangement package. It is used to represent planar
arrangements and it provides the interface needed to construct them,
traverse them, and maintain them. An arrangement is defined by
a geometric <I>traits</I> class that determines the family of planar
curves that form the arrangement, and a \sc{Dcel} class, which
represents the <I>topological structure</I> of the planar subdivision.
It supplies a minimal set of geometric operations (predicates and
constructions) required to construct and maintain the arrangement
and to operate on it.

The design of the arrangement package is guided by the need to
separate between the representation of the arrangements and the
various geometric algorithms that operate on them, and by the need to
separate between the topological and geometric aspects of the planar
subdivision. The separation is exhibited by the two template
parameters of the `Arrangement_2` template:
<UL>

<LI>The `Traits` template-parameter should be instantiated with a
  model of the `ArrangementBasicTraits_2` concept and optionally
  additional geometry traits concepts. A model of the
  `ArrangementBasicTraits_2` concept defines the types of \f$
  x\f$-monotone curves and two-dimensional points, namely
  `X_monotone_curve_2` and `Point_2`, respectively, and supports basic
  geometric predicates on them.

  In the first sections of this chapter we always use
  `Arr_segment_traits_2` as our traits class, to construct
  arrangements of line segments. However, the arrangement package
  contains several other traits classes that can handle other types of
  curves, such as polylines (continuous piecewise-linear curves),
  conic arcs, and arcs of rational functions. We exemplify the usage
  of these traits classes in Section \ref arr_sectraits.
<LI>The `Dcel` template-parameter should be instantiated with a class
  that is a model of the `ArrangementDcel` concept. The value of this
  parameter is `Arr_default_dcel<Traits>` by default.  However, in
  many applications it is necessary to extend the \sc{Dcel} features;
  see Section \ref arr_secex_dcel for further explanations and
  examples.
</UL>

\subsection Arrangement_on_surface_2ASimpleProgram A Simple Program

\image html triangle.png
\image latex triangle.png

The simple program listed below constructs a planar map of three line
segments forming a triangle. The constructed arrangement is instantiated
with the `Arr_segment_traits_2` traits class to handle segments only.
The resulting arrangement consists of two faces, a bounded triangular face
and the unbounded face.
The program is not very useful as it is, since it ends immediately
after the arrangement is constructed. We give more enhanced examples
in the rest of this chapter.

\code{.cpp}
#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Quotient.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

typedef CGAL::Quotient<CGAL::MP_Float> Number_type;
typedef CGAL::Cartesian<Number_type> Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef Traits_2::Point_2 Point_2;
typedef Traits_2::X_monotone_curve_2 Segment_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;

int main()
{
  Arrangement_2 arr;
  Segment_2 cv[3];
  Point_2 p1 (0, 0), p2 (0, 4), p3 (4, 0);

  cv[0] = Segment_2 (p1, p2);
  cv[1] = Segment_2 (p2, p3);
  cv[2] = Segment_2 (p3, p1);
  CGAL::insert (arr, &cv[0], &cv[3]);
  return (0);
}
\endcode

\subsection arr_ssectraverse Traversing the Arrangement

The simplest and most fundamental arrangement operations are the
various traversal methods, which allow users to systematically go
over the relevant features of the arrangement at hand.

As mentioned above, the arrangement is represented as a \sc{Dcel},
which stores three containers of vertices, halfedges and faces. Thus,
the `Arrangement_2` class supplies iterators for these
containers. For example, the methods `vertices_begin()` and
`vertices_end()` return `Arrangement_2::Vertex_iterator`
objects that define the valid range of arrangement vertices. The value
type of this iterator is `Arrangement_2::Vertex`. Moreover, the
vertex-iterator type is equivalent to
`Arrangement_2::Vertex_handle`, which serves as a pointer to a
vertex. As we show next, all functions related to arrangement features
accept handle types as input parameters and return handle types as
their output.

In addition to the iterators for arrangement vertices, halfedges
and faces, the arrangement class also provides `edges_begin()`
and `edges_end()` that return
`Arrangement_2::Edge_iterator` objects for traversing the
arrangement edges. Note that the value type of this iterator is
`Arrangement_2::Halfedge`, representing one of the twin
halfedges that represent the edge.

All iterator, circulator\cgalFootnote{A <I>circulator</I> is used to traverse a circular list, such as the list of halfedges incident to a vertex - see below.} and handle types also have non-mutable
(<I>const</I>) counterparts. These non-mutable iterators are useful
to traverse an arrangement without changing it. For example,
the arrangement has a
non-constant member function called `vertices_begin()` that
returns a `Vertex_iterator` object and another const member
function that returns a `Vertex_const_iterator` object. In fact,
all methods listed in this section that return an iterator, a
circulator or a handle have non-mutable counterparts. It should be
noted that, for example, `Vertex_handle` can be readily converted
into a `Vertex_const_handle`, but not vice-verse.

Conversion of a non-mutable handle to a corresponding mutable
handle are nevertheless possible, and can be performed using the
static function `Arrangement_2::non_const_handle()` (see, e.g.,
Section \ref arr_ssecpl). There are
three variant of this function, one for each type of handle.

\subsection arr_sssectr_vertex Traversal Methods for an Arrangement Vertex

A vertex is always associated with a geometric entity, namely with
a `Point_2` object, which can be obtained by the `point()`
method of the `Vertex` class nested within `Arrangement_2`.

\todo With doxygen it is enough to prefix a method with the
right scope to get the right link in the manual. So we could write:
\"A vertex is always associated with a geometric entity, namely with
an `Arrangement_2::Point_2` object, which can be obtained by the
`Arrangement_2::Vertex::point()` method.\"




The `is_isolated()` method determines whether a vertex is isolated
or not. Recall that the halfedges incident to a non-isolated vertex,
namely the halfedges that share a common target vertex, form a circular
list around this vertex. The `incident_halfedges()` method returns
a circulator of type `Arrangement_2::Halfedge_around_vertex_circulator`
that enables the traversal of this circular list in a clockwise
direction. The value type of this circulator is `Halfedge`.

The following function prints all the neighbors of a given
arrangement vertex (assuming that the `Point_2` type can be
inserted into the standard output using the `<<` operator). The
arrangement type is the same as in the simple example above.

\code
void print_neighboring_vertices (Arrangement_2::Vertex_const_handle v)
{
  if (v->is_isolated()) {
    std::cout << "The vertex (" << v->point() << ") is isolated" << std::endl;
   return;
  }

  Arrangement_2::Halfedge_around_vertex_const_circulator first, curr;
  first = curr = v->incident_halfedges();

  std::cout << "The neighbors of the vertex (" << v->point() << ") are:";
  do {
    // Note that the current halfedge is directed from u to v:
    Arrangement_2::Vertex_const_handle u = curr->source();
    std::cout << " (" << u->point() << ")";
  } while (++curr != first);
  std::cout << std::endl;
}
\endcode

In case of an isolated vertex, it is possible to obtain the face
that contains this vertex using the `face()` method.

\subsection arr_sssectr_halfedge Traversal Methods for an Arrangement Halfedge

Each arrangement edge, realized as a pair of twin halfedges,
is associated with an `X_monotone_curve_2` object, which
can be obtained by the `curve()` method of the `Halfedge`
class nested in the `Arrangement_2` class.

The `source()` and `target()` methods return handles to
the halfedge source and target vertices respectively. We can
obtain a handle to the twin halfedge using the `twin()`
method. From the definition of halfedges, it follows that if
`he` is a halfedge handle, then:
<UL>
<LI>`he->curve()` is equivalent to `he->twin()->curve()`,
<LI>`he->source()` is equivalent to `he->twin()->target()`, and
<LI>`he->target()` is equivalent to `he->twin()->source()`.
</UL>

Every halfedge has an incident face that lies to its left, which
can be obtained by the `face()` method. Recall that a
halfedge is always one link in a connected chain of halfedges that
share the same incident face, known as a <I>CCB</I>. The
`prev()` and `next()` methods return handles to the
previous and next halfedges in the CCB respectively.

As the CCB is a circular list of halfedges, it is only natural to
traverse it using a circulator. The `ccb()` method returns a
`Arrangement_2::Ccb_halfedge_circulator` object for the
halfedges along the CCB.

The function `print_ccb()` listed below prints all \f$ x\f$-monotone
curves along a given CCB (assuming that the `Point_2` and the
`X_monotone_curve_2` types can be inserted into the standard output
using the `<<` operator).

\code
void print_ccb (Arrangement_2::Ccb_halfedge_const_circulator circ)
{
  Ccb_halfedge_const_circulator curr = circ;
  std::cout << "(" << curr->source()->point() << ")";
  do {
    Arrangement_2::Halfedge_const_handle he = curr->handle();
    std::cout << " [" << he->curve() << "] "
              << "(" << he->target()->point() << ")";
  } while (++curr != circ);
  std::cout << std::endl;
}
\endcode

\subsection arr_sssectr_face Traversal Methods for an Arrangement Face

An arrangement of bounded curves always has a single unbounded face.
The function `unbounded_face()` returns a handle to this face.
(Note that an empty arrangement contains nothing <I>but</I> the
unbounded face.)

Given a `Face` object, we can use the `is_unbounded()`
method to determine whether it is unbounded. Bounded faces have an
outer CCB, and the `outer_ccb()` method returns a circulator
for the halfedges along this CCB. Note that the halfedges along
this CCB wind in a counterclockwise orientation around the outer
boundary of the face.

A face can also contain disconnected components in its interior,
namely holes and isolated vertices:
<UL>
<LI>The `holes_begin()` and `holes_end()` methods return
`Arrangement_2::Hole_iterator` iterators that define the range
of holes inside the face. The value type of this iterator is
`Ccb_halfedge_circulator`, defining the CCB that winds in a
clockwise orientation around a hole.
<LI>The `isolated_vertices_begin()` and
`isolated_vertices_end()` methods return
`Arrangement_2::Isolated_vertex_iterator` iterators that
define the range of isolated vertices inside the face. The value
type of this iterator is `Vertex`.
</UL>

The function `print_face()` listed below prints the outer and
inner boundaries of a given face, using the function `print_ccb()`,
which was introduced in the previous subsection.

\code
void print_face (Arrangement_2::Face_const_handle f)
{
  // Print the outer boundary.
  if (f->is_unbounded())
    std::cout << "Unbounded face. " << std::endl;
  else {
    std::cout << "Outer boundary: ";
    print_ccb (f->outer_ccb());
  }

  // Print the boundary of each of the holes.
  Arrangement_2::Hole_const_iterator hi;
  int index = 1;
  for (hi = f->holes_begin(); hi != f->holes_end(); ++hi, ++index) {
    std::cout << " Hole #" << index << ": ";
    print_ccb (*hi);
  }

  // Print the isolated vertices.
  Arrangement_2::Isolated_vertex_const_iterator iv;
  for (iv = f->isolated_vertices_begin(), index = 1;
       iv != f->isolated_vertices_end(); ++iv, ++index){
    std::cout << " Isolated vertex #" << index << ": "
              << "(" << iv->point() << ")" << std::endl;
  }
}
\endcode

\subsection arr_sssectr_ex Additional Example

The function listed below prints the current setting of a given
arrangement. This concludes the preview of the various traversal
methods.\cgalFootnote{The file `arr_print.h`, which can be found under the examples folder, includes this function and the rest of the functions listed in this section. Over there they are written in a more generic fashion, where the arrangement type serves as a template parameter for these functions, so different instantiations of the `Arrangement_2<Traits,Dcel>` template can be provided to the same function templates.}

\code
void print_arrangement (const Arrangement_2& arr)
{
  // Print the arrangement vertices.
  Vertex_const_iterator vit;
  std::cout << arr.number_of_vertices() << " vertices:" << std::endl;
  for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
    std::cout << "(" << vit->point() << ")";
    if (vit->is_isolated())
       std::cout << " - Isolated." << std::endl;
    else
       std::cout << " - degree " << vit->degree() << std::endl;
  }

  // Print the arrangement edges.
  Edge_const_iterator eit;
  std::cout << arr.number_of_edges() << " edges:" << std::endl;
  for (eit = arr.edges_begin(); eit != arr.edges_end(); ++eit)
    std::cout << "[" << eit->curve() << "]" << std::endl;

  // Print the arrangement faces.
  Face_const_iterator fit;
  std::cout << arr.number_of_faces() << " faces:" << std::endl;
  for (fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
    print_face (fit);
}
\endcode

\subsection arr_ssecmodify Modifying the Arrangement

In this section we review the various member functions of the
`Arrangement_2` class that allow users to modify the
topological structure of the arrangement by introducing new edges
or vertices, modifying them, or removing them.

The arrangement member-functions that insert new curves into the
arrangement, thus enabling the construction of a planar subdivision, are
rather specialized, as they require a-priori knowledge on the location of
the inserted curve. Indeed, for most purposes it is more convenient to
construct an arrangement using the free (global) insertion-functions.

\subsection arr_sssecmf_insert_cv Inserting Non-Intersecting x-Monotone Curves

The most important functions that allow users to modify the
arrangement, and perhaps the most frequently used ones, are the
specialized insertion functions of \f$ x\f$-monotone curves whose
interior is disjoint from any other curve in the existing
arrangement and do not contain any vertex of the arrangement. In
addition, these function require that the location of the curve in the
arrangement is known.

The motivation behind these rather harsh restrictions on the nature of
the inserted curves is the decoupling of the topological arrangement
representation from the various algorithms that operate on it. While
the insertion of an \f$ x\f$-monotone curve whose interior is disjoint
from all existing arrangement features is quite straightforward (as we
show next), inserting curves that intersect with the curves already
inserted into the arrangement is much more complicated and requires
the application of non-trivial geometric algorithms.  These insertion
operations are therefore implemented as free functions that operate on
the arrangement and the inserted curve(s); see Section \ref arr_secgl_funcs
for more details and examples.
\cgalFootnote{You may skip to Section \ref arr_secgl_funcs, and return to this subsection at a later point in time.}


\cgalFigureBegin{arr_figex_1,insert.png}
 The various specialized insertion procedures. The inserted \f$ x\f$-monotone curve is drawn with a light dashed line, surrounded by two solid arrows that represent the pair of twin half-edges added to the \sc{Dcel}. Existing vertices are shown as black dots while new vertices are shown as light dots. Existing half-edges that are affected by the insertion operations are drawn as dashed arrows. (a) Inserting a curve as a new hole inside the face \f$ f\f$. (b) Inserting a curve from an existing vertex \f$ u\f$ that corresponds to one of its endpoints. (c) Inserting an \f$ x\f$-monotone curve whose endpoints are the already existing vertices \f$ u_1\f$ and \f$ u_2\f$. In our case, the new pair of half-edges close a new face \f$ f'\f$, where the hole \f$ h_1\f$, which used to belong to \f$ f\f$, now becomes an enclave in this new face.
\cgalFigureEnd


When an \f$ x\f$-monotone curve is inserted into an existing arrangement, such
that the interior of this curve is disjoint from any arrangement feature,
only the following three scenarios are possible, depending on the status
of the endpoints of the inserted subcurve:

<OL>
<LI>In case both curve endpoints do not correspond to any existing
arrangement vertex we have to create two new vertices
corresponding to the curve endpoints and connect them using a pair
of twin halfedges. This halfedge pair initiates a new hole inside
the face that contains the curve in its interior.</LI>
<LI>If exactly one endpoint corresponds to an existing arrangement
vertex (we distinguish between a vertex that corresponds to the left
endpoint of the inserted curve and a vertex corresponding to its right
endpoint), we have to create a new vertex that corresponds to the other
endpoint of the curve and to connect the two vertices by a pair of
twin halfedges that form an "antenna" emanating from the boundary
of an existing connected component (note that if the existing vertex
used to be isolated, this operation is actually equivalent to forming
a new hole inside the face that contains this vertex).</LI>
<LI>If both endpoints correspond to existing arrangement
vertices, we connect these vertices using a pair of twin halfedges.
(If one or both vertices are isolated this case reduces to one of
the two previous cases respectively.) The two following subcases may
occur:
<UL>
<LI>Two disconnected components are merged into a single connected
component (as is the case with the segment \f$s_1\f$ in the figure to the
left).</LI>
<LI>A new face is created, a face that splits from an existing
arrangement face. In this case we also have to examine the holes and
isolated vertices in the existing face and move the relevant ones
inside the new face (as is the case with the segment \f$s_2\f$ in the
figure to the left).</LI>
</UL>
</LI>
</OL>

\image html connect_comp.png
\image latex connect_comp.png

The `Arrangement_2` class offers insertion functions named
`insert_in_face_interior()`, `insert_from_left_vertex()`,
`insert_from_right_vertex()` and `insert_at_vertices()`
that perform the special insertion procedures listed above. The
first function accepts an \f$ x\f$-monotone curve \f$ c\f$ and an arrangement
face \f$ f\f$ that contains this curve in its interior. The other
functions accept an \f$ x\f$-monotone curve \f$ c\f$ and handles to the existing
vertices that correspond to the curve endpoint(s). Each of the four
functions returns a handle to one of the twin halfedges that have
been created, where:
<UL>
<LI>`insert_in_face_interior(c, f)` returns a halfedge directed
from the vertex corresponding to the left endpoint of `c`
toward the vertex corresponding to its right endpoint.
<LI>`insert_from_left_vertex(c, v)` and
`insert_from_right_vertex(c, v)` returns a halfedge whose
source is the vertex \f$ v\f$ that and whose target is the new vertex
that has just been created.
<LI>`insert_at_vertices(c, v1, v2)` returns a halfedge directed
from \f$ v_1\f$ to \f$ v_2\f$.
</UL>

\cgalFigureBegin{arr_figex_2,ex_1.png}
The arrangement of the line segments \f$ s_1, \ldots, s_5\f$ constructed in `edge_insertion.cpp`. The arrows mark the direction of the halfedges returned from the various insertion functions.
\cgalFigureEnd

The following program demonstrates the usage of the four insertion
functions. It creates an arrangement of five line segments, as
depicted in \cgalFigureRef{arr_figex_1}.\cgalFootnote{Notice that in all figures in the rest of this chapter the coordinate axes are drawn only for illustrative purposes and are <I>not</I> part of the arrangement.} As the arrangement is very
simple, we use the simple Cartesian kernel of \cgal with integer
coordinates for the segment endpoints. We also use the
`Arr_segment_traits_2` class that enables the efficient
maintenance of arrangements of line segments; see more details on
this traits class in Section \ref arr_sectraits. This example, as
many others in this chapter, uses some print-utility functions from
the file `print_arr.h`; these functions are also listed in
Section \ref arr_ssectraverse.

\cgalExample{Arrangement_on_surface_2/edge_insertion.cpp}

Observe that the first line segment is inserted in the interior of
the unbounded face. The other line segments are inserted
using the vertices created by the insertion of previous segments.
The resulting arrangement consists of three faces, where the two
bounded faces form together a hole in the unbounded face.

\subsection arr_sssecmf_iso_verts Manipulating Isolated Vertices

Isolated points are in general simpler geometric entities than
curves and indeed the member functions that manipulate them are
easier to understand.

The function `insert_in_face_interior(p, f)` inserts an
isolated point \f$ p\f$, located in the interior of a given face \f$ f\f$,
into the arrangement and returns a handle to the arrangement
vertex it has created and associated with \f$ p\f$. Naturally, this
function has a precondition that \f$ p\f$ is really an isolated point,
namely it does not coincide with any existing arrangement vertex
and does not lie on any edge. As mentioned in
Section \ref arr_ssectraverse, it is possible to obtain the face
containing an isolated vertex handle \f$ v\f$ by calling `v->face()`.

The function `remove_isolated_vertex(v)` receives a handle to
an isolated vertex and removes it from the arrangement.

\cgalFigureBegin{arr_figex_3,ex_2.png}
An arrangement of line segments containing three isolated vertices, as constructed in `isolated_vertices.cpp`. The vertices \f$ u_2\f$ and \f$ u_3\f$ are eventually removed from the arrangement.
\cgalFigureEnd


The following program demonstrates the usage of the arrangement
member-functions for manipulating isolated vertices. It first
inserts three isolated vertices located inside the unbounded face, then
it inserts four line segments that form a rectangular hole inside the
unbounded face (see \cgalFigureRef{arr_figex_2} for an
illustration). Finally, it traverses the vertices and removes those
isolated vertices that are still contained in the unbounded face
(\f$ u_2\f$ and \f$ u_3\f$ in this case):

\cgalExample{Arrangement_on_surface_2/isolated_vertices.cpp}

\subsection arr_sssecmf_halfedges Manipulating Halfedges

In the previous subsection we showed how to introduce new isolated
vertices in the arrangement. But how does one create a vertex that
lies on an existing arrangement edge (more precisely, on an
\f$ x\f$-monotone curve that is associated with an arrangement edge)?

It should be noted that such an operation involves the splitting
of a curve at a given point in its interior, while the traits
class used by `Arrangement_2` does not necessarily have the
ability to perform such a split operation. However, if users have
the ability to split an \f$ x\f$-monotone curve into two at a given point
\f$ p\f$ (this is usually the case when employing a more sophisticated
traits class; see Section \ref arr_sectraits for more details)
they can use the `split_edge(e, c1, c2)` function, were
\f$ c_1\f$ and \f$ c_2\f$ are the two subcurves resulting from splitting the
\f$ x\f$-monotone curve associated with the halfedge \f$ e\f$ at some point
(call it \f$ p\f$) in its interior. The function splits the halfedge pair into two
pairs, both incident to a new vertex \f$ v\f$ associated with \f$ p\f$, and
returns a handle to a halfedge whose source equals \f$ e\f$'s source
vertex and whose target is the new vertex \f$ v\f$.

The reverse operation is also possible. Suppose that we have a
vertex \f$ v\f$ of degree \f$ 2\f$, whose two incident halfedges, \f$ e_1\f$ and
\f$ e_2\f$, are associated with the curves \f$ c_1\f$ and \f$ c_2\f$. Suppose
further that it is possible to merge these two curves into a single
continuous \f$ x\f$-monotone curve \f$ c\f$. Calling `merge_edge(e1, e2, c)`
will merge the two edges into a single edge associated with the curve
\f$ c\f$, essentially removing the vertex \f$ v\f$ from the arrangement.

Finally, the function `remove_edge(e)` removes the edge \f$ e\f$
from the arrangement. Note that this operation is the reverse of
an insertion operation, so it may cause a connected
component to split into two, or two faces to merge into one, or a
hole to disappear. By default, if the removal of `e` causes one
of its end-vertices to become isolated, we remove this vertex as well.
However, users can control this behavior and choose to keep the
isolated vertices by supplying additional Boolean flags to
`remove_edge()` indicating whether the source and the target vertices
are to be removed should they become isolated.

\cgalFigureBegin{arr_figex_4,ex_3.png}
An arrangement of line segments as constructed in `edge_manipulation.cpp`. Note that the edges \f$ e_7\f$ and \f$ e_8\f$ and the vertices \f$ w_1\f$ and \f$ w_2\f$, introduced in step (b) are eventually removed in step (c).
\cgalFigureEnd

In the following example program we show how the edge-manipulation
functions can be used. The program works in three
steps, as demonstrated in \cgalFigureRef{arr_figex_3}. Note that
here we still stick to integer coordinates, but as we work on a
larger scale we use an unbounded integer number-type (in this
case, the `Gmpz` type taken from the <span class="textsc">Gmp</span> library)
instead of the built-in `int` type.\cgalFootnote{As a rule of thumb, one can use a bounded integer type for representing line segments whose coordinates are bounded by \f$ \lfloor\sqrt[3]{M}\rfloor\f$, where \f$ M\f$ is the maximal representable integer value. This guarantees that no overflows occur in the computations carried out by the traits class, hence all traits-class predicates always return correct results.}
In case the <span class="textsc">Gmp</span> library is not installed (as indicated by
the `CGAL_USE_GMP` flag defined in `CGAL/basic.h`), we
use `MP_Float`, a number-type included in \cgal's support
library that is capable of storing floating-point numbers with
unbounded mantissa. We also use the standard Cartesian
kernel of \cgal as our kernel. This is recommended when the
kernel is instantiated with a more complex number type, as we
demonstrate in other examples in this chapter.

\cgalExample{Arrangement_on_surface_2/edge_manipulation.cpp}

Note how we use the halfedge handles returned from
`split_edge()` and `merge_edge()`. Also note the insertion
of the isolated vertex \f$ v_6\f$ located inside the triangular face (the
incident face of \f$ e_7\f$). This vertex seizes from being isolated, as it
is gets connected to other vertices.

In this context, we should mention the two member functions
`modify_vertex(v, p)`, which sets \f$ p\f$ to be the point
associated with the vertex \f$ v\f$, and `modify_edge(e, c)`, which
sets \f$ c\f$ to be the \f$ x\f$-monotone curve associated with the halfedge
\f$ e\f$. These functions have preconditions that \f$ p\f$ is
geometrically equivalent to `v->point()` and \f$ c\f$ is equivalent
to `e->curve()` (i.e., the two curves have the same graph),
respectively, to avoid the invalidation of the geometric structure of
the arrangement. At a first glance it may seen as these two functions
are of little use. However, we should keep in mind that there may be
extraneous data (probably non-geometric) associated with the point
objects or with the curve objects, as defined by the traits class. With
these two functions we can modify this data; see more details in
Section \ref arr_sectraits.

In addition, we can use these functions to replace a geometric
object (a point or a curve) with an equivalent object that has a
more compact representation. For example, we can replace the point
\f$ (\frac{20}{40}, \frac{99}{33})\f$ associated with some vertex \f$ v\f$,
by \f$ (\frac{1}{2}, 3)\f$.

\subsection arr_sssecadv_insert Advanced Insertion Functions

\image html pred_around_vertex.png
\image latex pred_around_vertex.png

\cgalAdvancedBegin
Assume that the specialized insertion function
`insert_from_left_vertex(c,v)` is invoked for a curve \f$ c\f$,
whose left endpoint is already associated with a non-isolated
vertex \f$ v\f$. Namely, \f$ v\f$ has already several incident halfedges. It
is necessary in this case to locate the exact place for the
new halfedge mapped to the inserted new curve \f$ c\f$ in the circular
list of halfedges incident to \f$ v\f$. More precisely, it is sufficient
to locate one of the halfedges `pred` directed toward \f$ v\f$ such
that \f$ c\f$ is located between `pred` and `pred->next()` in
clockwise order around \f$ v\f$, in order to complete the insertion
(see \cgalFigureRef{arr_figex_1} for an illustration). This may
take \f$ O(d)\f$ time where \f$ d\f$ is the degree of the vertex. However,
if the halfedge `pred` is known in advance, the insertion can
be carried out in constant time.

The `Arrangement_2` class provides the advanced versions of
the specialized insertion functions for a curve \f$ c\f$ - namely we have
`insert_from_left_vertex(c,pred)` and
`insert_from_right_vertex(c,pred)` that accept a halfedge `pred`
as specified above, instead of a vertex \f$ v\f$. These functions are
more efficient, as they take constant time and do not perform any
geometric operations. Thus, they should be used when the halfedge
`pred` is known. In case that the vertex \f$ v\f$ is isolated or
that the predecessor halfedge for the new inserted curve is not
known, the simpler versions of these insertion functions should be
used.

Similarly, there exist two overrides of the
`insert_at_vertices()` function: One that accept the two
predecessor halfedges around the two vertices \f$ v_1\f$ and \f$ v_2\f$ that
correspond to the curve endpoints, and one that accepts a handle
for one vertex and a predecessor halfedge around the other
vertex.


\cgalFigureBegin{arr_figex_5,ex_4.png}
An arrangement of line segments, as constructed in `special_edge_insertion.cpp`. Note that \f$ p_0\f$ is initially inserted as an isolated point and later on connected to the other four vertices.
\cgalFigureEnd

The following program shows how to construct the arrangement
depicted in \cgalFigureRef{arr_figex_4} using the specialized
insertion functions that accept predecessor halfedges:

\cgalExample{Arrangement_on_surface_2/special_edge_insertion.cpp}

It is possible to perform even more refined operations on an
`Arrangement_2` instance given specific topological information.
As most of these operations are very fragile and perform no precondition
testing on their input in order to gain efficiency, they are not included
in the public interface of the arrangement class. Instead, the
`Arr_accessor<Arrangement>` class allows access to these internal
arrangement operations - see more details in the Reference Manual.
\cgalAdvancedEnd

\section arr_secqueries Issuing Queries on an Arrangement

One of the most important query types defined on arrangements is
the <I>point-location</I> query: Given a point, find the arrangement
cell that contains it. Typically, the result of a point-location
query is one of the arrangement faces, but in degenerate situations
the query point can be located on an edge or it may coincide with a
vertex.

Point-location queries are common in many applications, and also
play an important role in the incremental construction of arrangements
(and more specifically in the free insertion-functions described in
Section \ref arr_secgl_funcs). Therefore, it is crucial to have the
ability to answer such queries effectively.

\subsection arr_ssecpl Point-Location Queries

The `Arrangement_2` class template does not support point-location
queries directly, as the arrangement representation is decoupled from
the geometric algorithms that operate on it. The <I>2D Arrangements</I>
package includes a set of classe templates that are capable of
answering such queries; all are models of the concept
`ArrangementPointLocation_2`. Each model employs a different
algorithm or <I>strategy</I> for answering queries. A model of this
concept must define the `locate()` member function, which accepts
an input query-point and returns an object that represents the
arrangement cell that contains this point. This object is is type
`Arr_point_location_result<Arrangement_2>::%Type`---a discriminated
union container of the bounded types `Vertex_const_handle`,
`Halfedge_const_handle`, or `Face_const_handle`. Depending on
whether the query point is located inside a face, on an edge, or on a
vertex, the appropriate handle can be obtained with <I>value retrieval</I>
by `boost::get` as demonstrated in the example below.

Note that the handles returned by the `locate()` functions are
non-mutable (`const`). If necessary, such handles may
be cast to mutable handles using the `non_const_handle()` methods
`Arrangement_2::non_const_handle()` provided by the
`Arrangement_2` class.

An object `pl` of any point-location class must be attached to an
`Arrangement_2` object `arr` before it is used to answer
point-location queries on `arr`. This attachment can be performed
when `pl` is constructed or at a later time using the
`pl.init(arr)` call.

The function template listed below accepts a point-location object,
the type of which is a model of the `ArrangementPointLocation_2`
concept, and a query point. The function template issues a
point-location query for the given point, and prints out the result.
It is defined in the header file `point_location_utils.h`.

\anchor lst_pl
\code
template <typename PointLocation>
void locate_point(const PointLocation& pl,
                  const typename PointLocation::Arrangement_2::Point_2& q)
{
  typedef PointLocation                                 Point_location;
  typedef typename Point_location::Arrangement_2        Arrangement_2;
  typename CGAL::Arr_point_location_result<Arrangement_2>::Type obj =
    pl.locate(q);

  // Print the result.
  print_point_location<Arrangement_2>(q, obj);
}
\endcode

The function template `locate_point()` calls an instance of the
function template `print_point_location()`, which inserts the
result of the query into the standard output-stream. It is listed
below, and defined in the header file `point_location_utils.h`.
Observe how the function `boost::get()` is used to cast the
resulting object into a handle to an arrangement feature. The
point-location object `pl` is assumed to be already attached
to an arrangement.

\code
template <typename Arrangement_>
void
print_point_location
(const typename PointLocation::Arrangement_2::Point_2& q
 typename CGAL::Arr_point_location_result<Arrangement_>::Type obj)
{
  typedef Arrangement_                                  Arrangement_2;

  typedef typename Arrangement_2::Vertex_const_handle   Vertex_const_handle;
  typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Arrangement_2::Face_const_handle     Face_const_handle;

  const Vertex_const_handle*   v;
  const Halfedge_const_handle* e;
  const Face_const_handle*     f;

  std::cout << "The point (" << q << ") is located ";
  if (f = boost::get<Face_const_handle>(&obj)) // located inside a face
    std::cout << "inside "
              << (((*f)->is_unbounded()) ? "the unbounded" : "a bounded")
              << " face." << std::endl;
  else if (e = boost::get<Halfedge_const_handle>(&obj)) // located on an edge
    std::cout << "on an edge: " << (*e)->curve() << std::endl;
  else if (v = boost::get<Vertex_const_handle>(&obj)) // located on a vertex
    std::cout << "on " << (((*v)->is_isolated()) ? "an isolated" : "a")
              << " vertex: " << (*v)->point() << std::endl;
  else CGAL_error_msg("Invalid object.");
}
\endcode

\subsection arr_sssecpl_strat Choosing a Point-Location Strategy

Each of the various point-location class templates employs a different
algorithm or <I>strategy</I>\cgalFootnote{The term <I>strategy</I>
is borrowed from the design-pattern taxonomy \cgalCite{cgal:ghjv-dpero-95},
Chapter 5. A <I>strategy</I> provides the means to define a family of
algorithms, each implemented by a separate class. All classes that implement
the various algorithms are made interchangeable, letting the algorithm in use
vary according to the user choice.} for answering queries:
<UL>
<LI> `Arr_naive_point_location<Arrangement>` employs the
  <I>naive</I> strategy. It locates the query point naively,
  exhaustively scanning all arrangement cells.

<LI> `Arr_walk_along_line_point_location<Arrangement>` employs
  the <I>walk-along-a-line</I> (or <I>walk</I> for short) strategy.
  It simulates a traversal, in reverse order, along an imaginary
  vertical ray emanating from the query point. It starts from the
  unbounded face of the arrangement and moves downward toward the
  query point until it locates the arrangement cell containing it.

<LI>`Arr_landmarks_point_location<Arrangement,Generator>`
  uses a set of <I>landmark</I> points, the location of which in the
  arrangement is known. It employs the <I>landmark</I> strategy. Given a
  query point, it uses a nearest-neighbor search-structure (a
  <span class="textsc">Kd</span>-tree is used by default) to find the
  nearest landmark, and then traverses the straight-line segment
  connecting this landmark to the query point.

  There are various ways to select the landmark set in the
  arrangement. The selection is governed by the `Generator`
  template parameter. The default generator class, namely
  `Arr_landmarks_vertices_generator`, selects all the vertices of
  the attached arrangement as landmarks. Additional generators that
  select the set in other ways, such as by sampling random
  points or choosing points on a grid, are also available; see the
  Reference Manual for more details.

  The landmark strategy requires that the type of the attached
  arrangement be an instance of the `Arrangement_2<Traits,Dcel>`
  class template, where the `Traits` parameter is substituted with
  a geometry-traits class that models the
  `ArrangementLandmarkTraits_2` concept, which refines the basic
  `ArrangementBasicTraits_2` concept; see
  Section \ref arr_sssectr_lanmarks_concept for details. Most traits
  classes included in the <I>2D Arrangement</I> package are models of
  this refined concept.

<LI>`Arr_trapezoid_ric_point_location<Arrangement>` implements an
  improved variant of Mulmuley's point-location algorithm
  \cgalCite{m-fppa-90}; see also \cgalCite{bkos-cgaa-00}, Chapter 6.
  The (expected) query-time is logarithmic. The arrangement faces
  are decomposed into simpler cells each of constant complexity, known
  as <I>pseudo-trapezoids</I>, and a search structure (a directed acyclic
  graph) is constructed on top of these cells, facilitating the search
  of the pseudo trapezoid (hence the arrangement cell) containing a
  query point in expected logarithmic time. The trapezoidal map and
  the search structure are built by a randomized incremental construction
  algorithm (RIC).

</UL>

The first two strategies do not require any extra data. The class
templates that implement them store a pointer to an arrangement object
and operate directly on it. Attaching such point-location objects to
an existing arrangement has virtually no running-time cost at all, but
the query time is linear in the size of the arrangement (the
performance of the walk strategy is much better in practice, but
its worst-case performance is linear). Using these strategies is
therefore recommended only when a relatively small number of
point-location queries are issued by the application, or when the
arrangement is constantly changing (That is, changes in the arrangement
structure are more frequent than point-location queries).

On the other hand, the landmarks and the trapezoid RIC strategies
require auxiliary data structures on top of the arrangement, which
they need to construct once they are attached to an arrangement
object and need to keep up-to-date as this arrangement changes.
The data structure needed by the landmarks strategy can be constructed
in \f$ O(N \log N) \f$ time, where \f$ N \f$ is the overall number of edges in
the arrangement, but the constant hidden in the \f$ O() \f$ notation for the
trapezoidal map RIC strategy is much larger. Thus, construction needed
by the landmark algorithm is in practice significantly faster than the
construction needed by the trapezoidal map RIC strategy. In addition,
although both resulting data structures are asymptotically linear in
size, using a <span class="textsc">Kd</span>-tree as the nearest-neighbor search-structure that
the landmark algorithm stores significantly reduces memory consumption.
The trapezoidal map RIC algorithm has expected logarithmic query time,
while the query time for the landmark strategy may be as large as
linear. In practice however, the query times of both strategies are
competitive. For a detailed experimental comparison
see \cgalCite{cgal:hh-eplca-05}.

Updating the auxiliary data structures of the trapezoidal map RIC
algorithm is done very efficiently. On the other hand, updating the
nearest-neighbor search-structure of the landmark algorithm may consume
more time when the arrangement changes frequently, especially when
a <span class="textsc">Kd</span>-tree is used, as it must be rebuilt each time the arrangement
changes. It is therefore recommended that the
`Arr_landmarks_point_location` class template be used when the
application frequently issues point-location queries on an arrangement
that only seldom changes. If the arrangement is more dynamic and is
frequently going through changes, the `Arr_trapezoid_ric_point_location`
class template should be the selected point-location strategy.

\subsection arr_sssecpl_ex An Example

\cgalFigureBegin{arr_figex_8,ex_5.png}
The arrangement of line segments, as constructed in `point_location_example.cpp`, `vertical_ray_shooting.cpp`, and `batched_point_location.cpp`. The arrangement vertices are drawn as small discs, while the query points \f$ q_1, \ldots, q_6\f$ are marked with crosses.
\cgalFigureEnd

The program listed below constructs a simple arrangement of five line
segments that form a pentagonal face, with a single isolated
vertex in its interior, as depicted in \cgalFigureRef{arr_figex_5}.
Notice that we use the same arrangement structure in the next
three example programs. The arrangement construction is performed by
the function `construct_segment_arr()` defined in the header file
`point_location_utils.h`. (Its listing is omitted here.) The
program employs the naive and the landmark strategies to issue
several point-location queries on this arrangement.

\cgalExample{Arrangement_on_surface_2/point_location_example.cpp}

Note that the program uses the `locate_point()` function template
to locate a point and nicely print the result of each query; see
\ref lst_pl "here".

\subsection arr_ssecray_shoot Vertical Ray Shooting

Another important query issued on arrangements is the vertical
ray-shooting query: Given a query point, which arrangement feature
do we encounter by a vertical ray shot upward (or downward) from this
point? In the general case the ray hits an edge, but it is possible
that it hits a vertex, or that the arrangement does not have any
vertex or edge lying directly above (or below) the query point.

All point-location classes listed in the previous section are also
models of the `ArrangementVerticalRayShoot_2` concept. That is,
they all have member functions called `ray_shoot_up(q)` and
`ray_shoot_down(q)` that accept a query point `q`. These functions
output an object of type type
`Arr_point_location_result<Arrangement_2>::%Type`---a discriminated
union container of the bounded types `Vertex_const_handle`,
`Halfedge_const_handle`, or `Face_const_handle`. The latter type
is used for the unbounded face of the arrangement, in case there is no
edge or vertex lying directly above (or below) `q`.

The function template `vertical_ray_shooting_query()` listed
below accepts a vertical ray-shooting object, the type of which
models the `ArrangementVerticalRayShoot_2` concept. It exports
the result of the upward vertical ray-shooting operation from a
given query point to the standard output-stream. The ray-shooting
object `vrs` is assumed to be already attached to an arrangement.
The function template is defined in the header file
`point_location_utils.h.

\code
template <typename RayShoot>
void shoot_vertical_ray(const RayShoot& vrs,
                       const typename RayShoot::Arrangement_2::Point_2& q)
{
  typedef RayShoot                                      Vertical_ray_shooting;

  // Perform the point-location query.
  typename Vertical_ray_shooting::result_type obj = vrs.ray_shoot_up(q);

  // Print the result.
  typedef typename Vertical_ray_shooting::Arrangement_2 Arrangement_2;
  typedef typename Arrangement_2::Vertex_const_handle   Vertex_const_handle;
  typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Arrangement_2::Face_const_handle     Face_const_handle;

  const Vertex_const_handle*   v;
  const Halfedge_const_handle* e;
  const Face_const_handle*     f;

  std::cout << "Shooting up from (" << q << ") : ";
  if (v = boost::get<Vertex_const_handle>(&obj))         // we hit a vertex
    std::cout << "hit " << (((*v)->is_isolated()) ? "an isolated" : "a")
              << " vertex: " << (*v)->point() << std::endl;
  else if (e = boost::get<Halfedge_const_handle>(&obj))  // we hit an edge
    std::cout << "hit an edge: " << (*e)->curve() << std::endl;
  else if (f = boost::get<Face_const_handle>(&obj)) \{    // we hit nothing
    CGAL_assertion((*f)->is_unbounded());
    std::cout << "hit nothing." << std::endl;
  else CGAL_error();
}
\endcode

The program below uses the function template listed above to
perform vertical ray-shooting queries on an arrangement. The
arrangement and the query points are exactly the same as in
`point_location.cpp`; see \cgalFigureRef{arr_figex_5}.

\cgalExample{Arrangement_on_surface_2/vertical_ray_shooting.cpp}

The number type we use in this example is \cgal's built-in
`MP_Float` type, which is a floating-point number with an
unbounded mantissa and a 32-bit exponent. It supports construction
from an integer or from a machine `float` or `double` and
performs additions, subtractions and multiplications in an exact
number.

\subsection arr_ssecbatched_pl Batched Point-Location

Suppose that at a given moment our application has to issue a
relatively large number \f$ m\f$ of point-location queries on a
specific arrangement object. Naturally, It is possible to define
a point-location object and use it to issue separate queries on
the arrangement. However, as explained in Section \ref arr_ssecpl
choosing a simple point-location strategy (either the naive or
the walk strategy) means inefficient queries, while the more
sophisticated strategies need to construct auxiliary structures
that incur considerable overhead in running time.

Alternatively, the <I>2D Arrangement</I> package includes a free
`locate()` function that accepts an arrangement and a range of
query points as its input and sweeps through the arrangement to
locate all query points in one pass. The function outputs the query
results as pairs, where each pair consists of a query point
and a discriminated union container, which represents the
cell containing the point; see Section \ref arr_ssecpl. The output
pairs are sorted in increasing $xy$-lexicographical order of the
query point.

The batched point-location operation is carried out by sweeping the
arrangement. Thus, it takes \f$ O((m+N)\log{(m+N)}) \f$  time, where \f$ N \f$
is the number of edges in the arrangement. Issuing separate queries
exploiting a point-location strategy with logarithmic query time
per query, such as the trapezoidal map RIC strategy (see
Section \ref arr_sssecpl_strat), is asymptotically more
efficient. However, experiments show that when the number \f$ m \f$ of
point-location queries is of the same order of magnitude as \f$ N\f$,
the batched point-location operation is more efficient in practice.
One of the reasons for the inferior performance of the alternative
(asymptotically faster) procedures is the necessity to construct
and maintain complex additional data structures.

The program below issues a batched point-location query, which
is essentially equivalent to the six separate queries performed in
`point_location_example.cpp`; see Section \ref arr_ssecpl.

\cgalExample{Arrangement_on_surface_2/batched_point_location.cpp}

\section arr_secgl_funcs Free Functions in the Arrangement Package

In Section \ref arr_secarr_class we reviewed in details the
`Arrangement_2` class, which represents two-dimensional
subdivisions induced by planar curves, and mentioned that its
interface is minimal in the sense that the member functions hardly
perform any geometric algorithms and are mainly used for
maintaining the topological structure of the subdivision. In this
section we explain how to utilize the free (global) functions that operate
on arrangements. The implementation of these operations typically require
non-trivial geometric algorithms or load some extra requirements on
the traits class.

\subsection arr_ssecinc_insert Incremental Insertion Functions

\subsection arr_sssecinsert_non_x Inserting Non-Intersecting Curves

In Section \ref arr_secarr_class we explained how to construct
arrangements of \f$ x\f$-monotone curves that are pairwise disjoint in
their interior, when the location of the segment endpoints in the
arrangement is known. Here we relax this constraint, and allow the
location of the inserted \f$ x\f$-monotone curve endpoints to be arbitrary,
as it may be unknown at the time of insertion. We retain, for the moment,
the requirement that the interior of the inserted curve is disjoint from
all existing arrangement edges and vertices.

The free function `insert_non_intersecting_curve(arr, c, pl)`
inserts the \f$ x\f$-monotone curve \f$ c\f$ into the arrangement `arr`,
with the precondition that the interior of \f$ c\f$ is disjoint from
all `arr`'s existing edges and vertices. The third argument
`pl` is a point-location object attached to the arrangement,
which is used for performing the insertion. It locates both curve
endpoints in the arrangement, where each endpoint is expected to
either coincide with an existing vertex or lie inside a face.
It is possible to invoke one of the specialized insertion functions
(see Section \ref arr_secarr_class), based on the query results, and
insert \f$ c\f$ at its proper position.\cgalFootnote{The `insert_non_intersecting_curve()` function, as all other functions reviewed in this section, is a function template, parameterized by an arrangement class and a point-location class (a model of the `ArrangementPointLocation_2` concept).} The insertion operation
thus hardly requires any geometric operations on top on the ones
needed to answer the point-location queries. Moreover, it is
sufficient that the arrangement class is instantiated with a
traits class that models the `ArrangementBasicTraits_2`
concept (or the `ArrangementLandmarkTraits_2` concept, if the
landmark point-location strategy is used), which does not have to
support the computation of intersection points between curves.

The variant `insert_non_intersecting_curve(arr, c)` is also
available. Instead of accepting a user-defined point-location
object, it defines a local instance of the walk point-location
class and uses it to insert the curve.

\subsection arr_sssecinsert_x_mon Inserting x-Monotone Curves

The `insert_non_intersecting_curve()` function is very
efficient, but its preconditions on the input curves are still
rather restricting. Let us assume that the arrangement is
instantiated with a traits class that models the refined
`ArrangementXMonotoneTraits_2` concept and supports
intersection computations (see Section \ref arr_sectraits for
the exact details). Given an \f$ x\f$-monotone curve, it is sufficient
to locate its left endpoint in the arrangement and to trace its
<I>zone</I>, namely the set of arrangement features crossing the curve,
until the right endpoint is reached. Each time the new curve \f$ c\f$
crosses an existing vertex or an edge, the curve is split into
subcurves (in the latter case, we have to split the curve
associated with the existing halfedge as well) and associate new
edges with the resulting subcurves. Recall that an edge is represented
by a pair of twin halfedges, so we split it into two halfedge pairs.

The free function `insert(arr, c, pl)` performs
this insertion operation. It accepts an \f$ x\f$-monotone curve \f$ c\f$,
which may intersect some of the curves already in the arrangement
`arr`, and inserts it into the arrangement by computing its zone.
Users may supply a point-location object `pl`, or use the default
walk point-location strategy (namely, the variant
`insert(arr, c)` is also available). The
running-time of this insertion function is proportional to the
complexity of the zone of the curve \f$ c\f$.

\cgalAdvancedBegin
In some cases users may have a prior knowledge of the location of the
left endpoint of the \f$ x\f$-monotone curve `c` they wish to insert,
so they can perform the insertion without issuing any point-location
queries. This can be done by calling
`insert(arr, c, obj)`, where `obj` is an
object represents the location of `c`'s left endpoint in the
arrangement - namely it wraps a `Vertex_const_handle`, a
`Halfedge_const_handle` or a `Face_const_handle` (see
also Section \ref arr_ssecpl).
\cgalAdvancedEnd

\subsection arr_sssecinsert_gen Inserting General Curves

So far all our examples were of arrangements of line segments,
where the `Arrangement_2` template was instantiated with the
`Arr_segment_traits_2` class. In this case, the fact that
`insert()` accepts an \f$ x\f$-monotone curve does not
seem to be a restriction, as all line segments are \f$ x\f$-monotone
(note that we consider vertical line segments to be <I>weakly</I>
\f$ x\f$-monotone).

Suppose that we construct an arrangement of circles. A circle is
obviously not \f$ x\f$-monotone, so we cannot insert it in the same way we
inserted \f$ x\f$-monotone curves. \cgalFootnote{Note that a key operation performed by `insert()` is to locate the left endpoint of the curve in the arrangement. A circle, however, does not have any endpoints!} However, it is possible to subdivide each circle
into two \f$ x\f$-monotone circular arcs (its upper half and its lower
half) and to insert each \f$ x\f$-monotone arc separately.

The free function `insert()` also supports general curve and
not necessarily \f$ x\f$-monotone curves. In this case it requires that the
traits class used by the arrangement `arr` to be a model of the
concept `ArrangementTraits_2`, which refines the
`ArrangementXMonotoneTraits_2` concept. It has to define an
additional `Curve_2` type (which may differ from the
`X_monotone_curve_2` type), and support the subdivision of curves
of this new type into \f$ x\f$-monotone curves (see the exact details in
Section \ref arr_sectraits). The `insert(arr, c, pl)`
function performs the insertion of the curve \f$ c\f$, which does not need
to be \f$ x\f$-monotone, into the arrangement by subdividing it (if needed)
into \f$ x\f$-monotone subcurves and inserting each one separately. Users
may supply a point-location object `pl`, or use the default walk
point-location strategy by calling `insert(arr, c)`.

\subsection arr_sssecinsert_point Inserting Points

The arrangement class enables us to insert a point as an isolated
vertex in a given face. The free function
`insert_point(arr, p, pl)` inserts a vertex into `arr` that
corresponds to the point `p` at an arbitrary location. It uses
the point-location object `pl` to locate the point in the
arrangement (by default, the walk point-location strategy is used),
and acts according to the result as follows:
<UL>
<LI>If `p` is located inside a face, it is inserted as an
isolated vertex inside this face.
<LI>If `p` lies on an edge, the edge is split to create a
vertex associated with `p`.
<LI>Otherwise, `p` coincides with an existing vertex and
we are done.
</UL>
In all cases, the function returns a handle to the vertex
associated with `p`.

The arrangement `arr` should be instantiated with a traits class
that models the `ArrangementXMonotoneTraits_2` concept, as the
insertion operation may involve splitting curves.

\subsection arr_sssecinsert_ex An Example

\cgalFigureBegin{arr_figex_10,ex_8.png}
An arrangement of five intersecting line segments, as constructed in `incremental_insertion.cpp` and `aggregated_insertion.cpp`. The segment endpoints are marked by black disks and the arrangement vertices that correspond to intersection points are marked by circles. The query point \f$ q\f$ is marked with a cross and the face that contains it is shaded.
\cgalFigureEnd


The program below constructs an arrangement of intersecting
line-segments. We know that \f$ s_1\f$ and \f$ s_2\f$ do not intersect, so
we use `insert_non_intersecting_curve()` to insert them into the
empty arrangement. The rest of the segments are inserted using
`insert()`. The resulting arrangement consists
of \f$ 13\f$ vertices, \f$ 16\f$ edges, and \f$ 5\f$ faces, as can be seen in
\cgalFigureRef{arr_figex_8}.

In the earlier examples, all arrangement vertices corresponded to
segment endpoints. In this example we have additional vertices that
correspond to intersection points between two segments. The
coordinates of these intersection points are rational numbers, if
the input coordinates are rational (or integer). Therefore,
the `Quotient<int>` number type is used to represent the
coordinates:

\cgalExample{Arrangement_on_surface_2/incremental_insertion.cpp}

\subsection arr_ssseczone Other Zone Related Functions

In this section we have described so far free functions that
insert curves and points to a given arrangement. Now we will describe
functions that don't insert curves or points to an arrangement nor do
they change the arrangement, but they are closely related to the
incremental insertion functions as they also use the zone algorithm.

The free function `do_intersect()` checks if a given curve or \f$ x\f$-monotone
curve intersects an existing arrangement's edges or vertices.
If the give curve is not an \f$ x\f$-monotone curve then the function
subdivides the given curve into \f$ x\f$-monotone subcurves and isolated
vertices . Each subcurve is in turn checked for intersection.
The function uses the zone algorithm to check if the curve intersects
the arrangement. First, the curve's left endpoint is located. Then,
its zone is computed starting from its left endpoint location. The
zone computation terminates when an intersection with an arrangement's
edge/vertex is found or when the right endpoint is reached.
A given point-location object is used for locating the left endpoint
of the given curve in the existing arrangement. By default, the function
uses the "walk along line" point-location strategy - namely an
instance of the class
`Arr_walk_along_line_point_location`.
If the given curve is \f$ x\f$-monotone then the traits
class must model the `ArrangementXMonotoneTraits_2` concept. If
the curve is not \f$ x\f$-monotone curve then the traits class must
model the `ArrangementTraits_2` concept.

The `zone()` function computes the zone of a given \f$ x\f$-monotone
curve in a given arrangement. Meaning, it outputs all the arrangement's
elements (vertices, edges and faces) that the \f$ x\f$-monotone curve
intersects in the order that they are
discovered when traversing the \f$ x\f$-monotone curve from left to right.
The function uses a given point-location object to locate the left
endpoint of the given \f$ x\f$-monotone curve. By default, the function
uses the "walk along line" point-location strategy.
The function requires that the traits class will model the
`ArrangementXMonotoneTraits_2` concept.

\subsection arr_ssecagg_insert Aggregated Insertion Functions

Let us assume that we have to insert a set of \f$ m\f$ input curves into an
arrangement. It is possible to do this incrementally,
inserting the curves one by one, as shown in the previous section.
However, the arrangement package provides three free functions that
aggregately insert a range of curves into an arrangement:
<UL>
<LI>`insert_non_intersecting_curves(arr, begin, end)` inserts
a range of \f$ x\f$-monotone curves given by the input iterators
`[begin, end)` into an arrangement `arr`. The \f$ x\f$-monotone
curves should be pairwise disjoint in their interior and also
interior-disjoint from all existing edges and vertices of `arr`.
<LI>`insert(arr, begin, end)` inserts a range of general
(not necessarily \f$ x\f$-monotone) curves of type `Curve_2` or
`X_monotone_curve_2` that may intersect one another, given by
the input iterators `[begin, end)`, into the arrangement
`arr`.
</UL>

We distinguish between two cases: (i) The given arrangement
`arr` is empty (has only an unbounded face), so we have to
construct it from scratch. (ii) We have to insert \f$ m\f$ input curves
to a non-empty arrangement `arr`.

In the first case, we sweep over the input curves, compute
their intersection points and construct the \sc{Dcel} that represents
their planar arrangement. This process is performed in
\f$ O\left((m + k)\log m\right)\f$ time, where \f$ k\f$ is the total number
of intersection points. The running time is asymptotically better
than the time needed for incremental insertion, if the arrangement
is relatively sparse (when \f$ k\f$ is bounded by \f$ \frac{m^2}{\log
m}\f$), but in practice it is recommended to use this aggregated
construction process even for dense arrangements, since the
sweep-line algorithm needs less geometric operations compared to
the incremental insertion algorithms and hence typically runs
much faster in practice.

Another important advantage the aggregated insertion functions
have is that they do not issue point-location queries. Thus, no
point-location object needs to be attached to the arrangement. As
explained in Section \ref arr_ssecpl, there is a trade-off
between construction time and query time in each of the
point-location strategies, which affects the running times of the
incremental insertion process. Naturally, this trade-off is irrelevant
in case of aggregated insertion as above.

The example below shows how to construct the arrangement of
line segments depicted in \cgalFigureRef{arr_figex_8} and built
incrementally in `incremental_insertion.cpp`, as shown in the previous
section. We use the aggregated insertion function
`insert()` as we deal with line segments.
Note that no point-location object needs to be defined and attached to the
arrangement:

\cgalExample{Arrangement_on_surface_2/aggregated_insertion.cpp}

In case we have to insert a set of \f$ m\f$ curves into an existing
arrangement, where we denote the number of edges in the arrangement by \f$ N\f$.
As a rule of thumb, if \f$ m = o(\sqrt{N})\f$, we insert the curves one by
one. For larger input sets, we use the aggregated insertion procedures.

\cgalFigureBegin{arr_figex_unb1,ex_10.png}
An arrangement of intersecting line segments, as constructed in `global_insertion.cpp`. The segments of \f$ {\mathcal S}_1\f$ are drawn in solid lines and the segments of \f$ {\mathcal S}_2\f$ are drawn in dark dashed lines. Note that the segment \f$ s\f$ (light dashed line) overlaps one of the segments in \f$ {\mathcal S}_1\f$.
\cgalFigureEnd

In the example below we aggregately construct an arrangement of a set
\f$ {\mathcal S}_1\f$ containing five line segments. Then we insert a single
segment using the incremental insertion function. Finally, we add a set
\f$ {\mathcal S}_2\f$ with five more line segments in an aggregated fashion.
Notice that the line segments of \f$ {\mathcal S}_1\f$ are pairwise
interior-disjoint, so we use `insert_non_intersecting_curves()`.
\f$ {\mathcal S}_2\f$ also contain pairwise interior-disjoint segments,
but as they intersect the existing arrangement, we have to use
`insert()` to insert them. Also note that the
single segment \f$ s\f$ we insert incrementally overlaps an existing
arrangement edge:

\cgalExample{Arrangement_on_surface_2/global_insertion.cpp}

The number type used in the example above,
`Quotient<MP_Float>`, is comprised of a numerator and a
denominator of type `MP_Float`, namely floating-point numbers
with unbounded mantissa. This number type is therefore capable of
exactly computing the intersection points as long as the segment
endpoints are given as floating-point numbers.

\subsection arr_ssecgl_remove Removing Vertices and Edges

The free functions `remove_vertex()` and `remove_edge()` handle
the removal of vertices and edges from an arrangement. The difference
between these functions and the member functions of the `Arrangement_2`
template having the same name is that they allow the merger of two curves
associated with adjacent edges to form a single edge. Thus, they require
that the traits class that instantiates the arrangement instance is a model
of the refined `ArrangementXMonotoneTraits_2` concept (see
Section \ref arr_sectraits).

The function `remove_vertex(arr, v)` removes the vertex
`v` from the given arrangement `arr`, where `v` is
either an isolated vertex or is a <I>redundant</I> vertex -
namely, it has exactly two incident edges that are associated with
two curves that can be merged to form a single \f$ x\f$-monotone curve.
If neither of the two cases apply, the function returns an
indication that it has failed to remove the vertex.

The function `remove_edge(arr, e)` removes the edge `e`
from the arrangement by simply calling `arr.remove_edge(e)`
(see Section \ref arr_ssecmodify). In addition, if either of the
end vertices of `e` becomes isolated or redundant after the removal
of the edge, it is removed as well.

\image html h_shape.png
\image latex h_shape.png

The following example demonstrates the usage of the free removal
functions. In creates an arrangement of four line segment forming
an H-shape with a double horizontal line. Then it removes the two
horizontal edges and clears all redundant vertices, such that the
final arrangement consists of just two edges associated with the
vertical line segments:

\cgalExample{Arrangement_on_surface_2/global_removal.cpp}

\section arr_secunbounded Arrangements of Unbounded Curves

Previous sections dealt only with arrangements of line segments,
namely of bounded curves. Such arrangements always have one unbounded
face that contains all other arrangement features. This section
explains how to construct arrangements of unbounded curves, such as
lines and rays.

\subsection arr_ssecunb_basic Basic Manipulation and Traversal Methods

Consider the arrangement induced by the two lines \f$ y = x\f$ and
\f$ y = -x\f$. These two lines intersect at the origin, such that the
arrangement contains a single vertex \f$ v = (0,0)\f$, with four infinite
rays emanating from it. Each ray corresponds to an arrangement edge,
and these edges subdivide the plane into four unbounded faces.
Consider a halfedge pair that represents one of the edges. The source
vertex of one of these halfedges is \f$ v\f$ and its target is at infinity,
while the other has its source at infinity and \f$ v\f$ is its target.

If `e` is an object of the nested type
`Arrangement_2::Halfedge`, then the predicates
`e.source_at_infinity()` and `e.target_at_infinity()` indicate
whether the halfedge represents a curve with an infinite end.
In general there is no need to access the source (or the target) of a
halfedge if it lies at infinity, since this vertex is not associated
with any valid point. Similarly, calling `arr.number_of_vertices()`
for an arrangement object `arr` counts only the vertices
associated with finite points, and ignores vertices at infinity
(and the range `[vertices_begin(), vertices_end())` contains only
finite vertices). The method `arr.number_of_vertices_at_infinity()`
counts the number of vertices at infinity.

As mentioned above, arrangements of unbounded curves usually have more
than one unbounded face. The function `arr.number_of_unbounded_faces()`
returns the number of unbounded arrangement faces
(Thus, `arr.number_of_faces() - arr.number_of_unbounded_faces()`
is the number of bounded faces).
The functions `arr.unbounded_faces_begin()` and
`arr.unbounded_faces_end()` return iterators of type
`Arrangement_2::Unbounded_face_iterator` that specify the range
of unbounded faces. Naturally, the value-type of this iterator is
`Arrangement_2::Face`.

The specialized insertion functions listed in
Section \ref arr_sssecmf_insert_cv can also be used for inserting
\f$ x\f$-monotone unbounded curves, provided that they are interior-disjoint
from any subcurve that already exists in the arrangement. For example,
if you wish to insert a ray \f$ r\f$ emanating from \f$ (0,0)\f$ in the direction
of \f$ (1,0)\f$, to the arrangement of \f$ y = -x\f$ and \f$ y = x\f$, you can use
the function `arr.insert_from_left_vertex()`, as the left
endpoint of \f$ r\f$ is already associated with an arrangement vertex.
Other edge-manipulation functions can also be applied on edges
associated with unbounded curves.

\cgalFigureBegin{arr_figunb_dcel,ex_unb1.png}
An arrangement of unbounded linear objects, as constructed in unbounded_non_intersecting.cpp.
\cgalFigureEnd

The following example demonstrates the use of the insertion function
for pairwise interior-disjoint unbounded curves. In this example
we use the traits class `Arr_linear_traits_2<Kernel>` to
instantiate the `Arrangement_2` template. This traits class is
capable of representing line segments as well as unbounded linear
curves (namely lines and rays). Observe that objects of the type
`X_monotone_curve_2` defined by this traits class are
constructible from `Line_2`, `Ray_2`, and `Segment_2`
objects, as defined in the instantiated kernel.

The first three curves are inserted using the special insertion
functions for \f$ x\f$-monotone curves whose location in the arrangement
is known. Notice that inserting an unbounded curve in the interior
of an unbounded face, or from an existing vertex that represents the
bounded end of the curve, may cause an unbounded face to split (this
is never the case when inserting a bounded curve - compare with
Section \ref arr_sssecmf_insert_cv). Then, three additional rays are
inserted incrementally, using the insertion function for \f$ x\f$-monotone
curves whose interior is disjoint from all arrangement features.
Finally, the program prints the size of the arrangement (compare to
the illustration in \cgalFigureRef{arr_figex_unb1}) and the outer
boundaries of its six unbounded faces:

\cgalExample{Arrangement_on_surface_2/unbounded_non_intersecting.cpp}

\subsection arr_ssecunb_global Free Functions

In principle, all queries and operations that relate to arrangements
of bounded curves can also be applied to arrangements of unbounded
curves. For example, it is possible to issue point-location and
vertical ray-shooting queries (see also Section \ref arr_secqueries)
on arrangements of lines, where the only restriction is that the query
point has finite coordinates.\cgalFootnote{Currently, all point-location strategies except the trapezoidal RIC point-location strategy are capable of handling arrangements of unbounded curves.}

In the following example we show how an arrangement of unbounded lines
is utilized to solve the following problem: Given a set of points, does
the set contain at least three collinear points? In this example a set
of input points is read from a file. The file `points.dat` is
used by default. It contains definitions of \f$ 100\f$ points randomly
selected on the grid \f$ [-10000,10000]\times[-10000,10000]\f$. We
construct an arrangement of the dual lines, where the line \f$ p^{*}\f$
dual to the point \f$ p = (p_x, p_y)\f$ is given by the equation
\f$ y = p_x*x - p_y\f$, and check whether three (or more) of the dual lines
intersect at a common point, by searching for a (dual) vertex, whose
degree is greater than \f$ 4\f$. If such a vertex exists, then there are at
least three dual lines that intersect at a common point, which implies
that there are at least three collinear points.

\cgalExample{Arrangement_on_surface_2/dual_lines.cpp}

Note that there are no three collinear points among the points defined
in the input file `points.dat`. In the second part of the example
the existence of collinearity is forced and verified as follows. A line
dual to the midpoint of two randomly selected points is introduced,
and inserted into the arrangement. This operation is followed by a
test that verifies that a vertex of degree greater than \f$ 4\f$
exists. This implied that collinearity indeed exists as explained above.

\subsection arr_ssecunb_rep Representation of Unbounded Arrangements
\cgalAdvancedBegin

\cgalFigureBegin{typenormal,unb_dcel.png}
A \sc{Dcel} representing an arrangement of four lines. Halfedges are drawn as thin arrows. The vertices \f$ v_1, \ldots, v_8\f$ lie at infinity, and are not associated with valid points. The halfedges that connect them are fictitious, and are not associated with concrete curves. The face denoted \f$ f_0\f$ (lightly shaded) is the fictitious "unbounded face" which lies outside the bounding rectangle (dashed) that bounds the actual arrangement. The four fictitious vertices \f$ v_{\rm bl}, v_{\rm tl}, v_{\rm br}\f$ and \f$ v_{\rm tr}\f$ represent the four corners of the bounding rectangle.
\cgalFigureEnd


Given a set \f$ \cal C\f$ of unbounded curves, a simple approach for
representing the arrangement induced by \f$ \cal C\f$ would be to clip the
unbounded curves using an axis-parallel rectangle that contains all
finite curve endpoints and intersection points between curves in
\f$ \cal C\f$. This process would result in a set \f$ \cal C\f$ of bounded curves
(line segments if \f$ \cal C\f$ contains lines and rays), and it would be
straightforward to compute the arrangement induced by this set.
However, we would like to operate directly on the unbounded curves
without having to preprocess them. Therefore, we use an implicit
bounding rectangle embedded in the \sc{Dcel} structure.
\cgalFigureRef{arr_figunb_dcel} shows the arrangement of four lines
that subdivide the plane into eight unbounded faces and two bounded
ones. Notice that in this case the unbounded faces have outer
boundaries, and the halfedges along these outer CCBs are drawn as
arrows. The bounding rectangle is drawn with a dashed line. The
vertices \f$ v_1,v_2,\ldots,v_8\f$, which represent the unbounded ends of
the four lines, and lie on the bounding rectangle, actually exist at
infinity, and the halfedges connecting them are <I>fictitious</I>, and
represent portions of the bounding rectangle. Note that the outer CCBs
of the unbounded faces contain fictitious halfedges. The twins of these
halfedges form together one connected component that corresponds to
the entire bounding rectangle, which forms a single hole in a face
\f$ f_0\f$. We say that \f$ f_0\f$ is <I>fictitious</I>, as it does
not correspond to a real two-dimensional cell of the arrangement.

Observe that there are four extra vertices at infinity that do not lie
on any curve; they are denoted as \f$ v_{\rm bl}, v_{\rm tl},
v_{\rm br}\f$, and \f$ v_{\rm tr}\f$, and represent the bottom-left, top-left,
bottom-right, and top-right corners of the bounding rectangle,
respectively. Similarly, there are fictitious halfedges that lie on
the top, the bottom, the left, or the right edge of the bounding
rectangle. When the arrangement is empty, there are exactly
four pairs of fictitious halfedges, that divide the plane into two
faces, namely a fictitious face lying outside of the bounding
rectangle and a single unbounded face bounded by the bounding rectangle.

Summarizing the above, there are four types of arrangement vertices,
which differ from one another by their location with respect to the
bounding bounding rectangle:
<OL>
<LI>A vertex, associated with a point in \f$ \mathbb{R}^2\f$ whose
coordinates are bounded. Such a vertex always lies inside the
bounding rectangle.
<LI> \anchor typeunbounded A vertex that represents an unbounded end of an \f$ x\f$-monotone curve
that is defined at \f$ x = -\infty\f$ or at \f$ x = \infty\f$. In case of
a horizontal line or a curve with a horizontal asymptote, the
\f$ y\f$-coordinate of the curve end may be finite (see for example the
vertices \f$ v_2\f$ and \f$ v_7\f$ in \cgalFigureRef{arr_figunb_dcel}), but in
general the curve end also goes to \f$ y = \pm\infty\f$ (see for instance
the vertices \f$ v_1\f$, \f$ v_3\f$, \f$ v_6\f$ and \f$ v_8\f$ in
\cgalFigureRef{arr_figunb_dcel}). For our convenience, we will always
take a "tall" enough bounding rectangle and treat such vertices as
lying on either the left or right rectangle edges (that is, if a curve
is defined at \f$ x = -\infty\f$, its left end will be represented by
a vertex on the left edge of the bounding rectangle, and if it is
defined at \f$ x = \infty\f$, its right end will be represented by a
vertex of the right edge).
<LI>A \anchor typeunboundedvertical vertex that represent the unbounded end of a vertical line or of a
curve with a vertical asymptote (finite \f$ x\f$-coordinate and an
unbounded \f$ y\f$-coordinate). Such a vertex always lies on one of the
horizontal edges of the bounding rectangle (either the bottom one if
\f$ y = -\infty\f$, or the top one if \f$ y = \infty\f$). The vertices \f$ v_4\f$
and \f$ v_5\f$ in \cgalFigureRef{arr_figunb_dcel} are of this type.
<LI>The \anchor typefictitious fictitious vertices that represent the four corners of the
bounding bounding rectangle.
</OL>

A vertex (at infinity) of Type \ref typeunbounded or
Type \ref typeunboundedvertical above always has
three incident edges: one concrete edge that is associated with an
unbounded portion of an \f$ x\f$-monotone curve, and two fictitious edges
connecting the vertex to its neighboring vertices at infinity.
Fictitious vertices (of type 4 above) have exactly two incident edges.
See Section \ref arr_sectraits on how the traits-class interface
helps imposing the fact that we never have more than one curve
incident to any true vertex at infinity.

The nested types defined in the `Arrangement_2` class support the
following methods, in addition to the ones listed in
Section \ref arr_ssectraverse :
<UL>
<LI>The `Vertex` class provides three-valued predicates
`parameter_space_in_x()` and `parameter_space_in_y()`, which
return the location of the geometric embedding of the vertex in the
parameter space. In particular, the former returns
`ARR_LEFT_BOUNDARY`, `ARR_INTERIOR`, or
`ARR_RIGHT_BOUNDARY`, and the latter returns
`ARR_BOTTOM_BOUNDARY`, `ARR_INTERIOR`, or
`ARR_TOP_BOUNDARY`. As the package currently supports only the
case where the parameter space is the compactified plane, the former
returns `ARR_INTERIOR` if the \f$ x\f$-coordinate associated with the
vertex is finite, `ARR_LEFT_BOUNDARY` if it is \f$ -\infty\f$, and
`ARR_RIGHT_BOUNDARY` if it is \f$ \infty\f$. The latter returns
`ARR_INTERIOR` if the \f$ y\f$-coordinate associated with the vertex
is finite, `ARR_BOTTOM_BOUNDARY` if it is \f$ -\infty\f$, and
`ARR_TOP_BOUNDARY` if it is \f$ \infty\f$. The Boolean predicate
`is_at_open_boundary()` is also provided. You can access the
point associated with a vertex only if it is not a vertex at an open
boundary (recall that a vertex at an open boundary is not associated
with a `Point_2` object).
<LI>The nested `Halfedge` class provides the Boolean predicate
`is_fictitious()`. The \f$ x\f$-monotone curve associated with
a halfedge can be accessed by the `curve()` method only if the
halfedge is not fictitious.
<LI>The nested `Face` class provides the Boolean predicate
`f.is_fictitious()`. The method `outer_ccb()` has the
precondition that the face is not fictitious. Note that non-fictitious
unbounded faces always have valid CCBs (although this CCB may
comprise only fictitious halfedge in case the arrangement contains
only bounded curves).
</UL>

The method `arr.number_of_edges()` does not count the number of
fictitious edges, (which is always
`arr.number_of_vertices_at_infinity() + 4`), and the iterators
returned by `arr.edges_begin()` and `arr.edges_end()` specify
a range of non-fictitious edges. Similarly, `arr.number_of_faces()`
does not count the fictitious face. However, the
`Ccb_halfedge_circulator` of the outer boundary of an
unbounded face or the `Halfegde_around_vertex_circulator` of a vertex
at infinity do traverse fictitious halfedges. For example, it is possible
to traverse the outer boundaries of the unbounded arrangement edges
using the following procedure:

\code
  Arrangement_2::Unbounded_face_const_iterator fit;
  Arrangement_2::Ccb_halfedge_const_circulator first, curr;
  Arrangement_2::Halfedge_const_handle he;
  int k = 1;

  for (fit = arr.unbounded_faces_begin();
       fit != arr.unbounded_faces_end(); ++fit, k++) {
    std::cout << "Unbounded face no. " << k << ": ";
    curr = first = fit->outer_ccb();
    if (! curr->source()->is_at_infinity())
      std::cout << "(" << curr->source()->point() << ")";
    do {
      he = curr;
      if (! he->is_fictitious())
        std::cout << " [" << he->curve() << "] ";
      else
        std::cout << " [ ... ] ";

      if (! he->target()->is_at_infinity())
        std::cout << "(" << he->target()->point() << ")";

      ++curr;
    } while (curr != first);
    std::cout << std::endl;
}
\endcode
\cgalAdvancedEnd

\section arr_sectraits Traits Classes

As mentioned in the introduction of this chapter, the traits class
encapsulates the definitions of the geometric entities and
implements the geometric predicates and constructions needed by
the `Arrangement_2` class and by its peripheral algorithms. We also
mention throughout the chapter that there are different levels of
requirements from the traits class, namely the traits class can model
different concept refinement-levels.

\subsection arr_sssectr_concepts The Hierarchy of Traits-Class Concepts

\subsection arr_sssectr_basic_concept The Basic Concept

A model of the basic concept, `ArrangementBasicTraits_2`,
needs to define the types `Point_2` and
`X_monotone_curve_2`, where objects of the first type are
the geometric mapping of arrangement vertices, and objects of the
latter type are the geometric mapping of edges. Such a model has to
support in addition the following set of operations:
<DL>
<DT><B>`Compare_x_2`:</B><DD> Compares the \f$ x\f$-coordinates of two points.
<DT><B>`Compare_xy_2`:</B><DD> Compares two points lexicographically, by
their \f$ x\f$-coordinates and then (in case of equality) by their
\f$ y\f$-coordinates.
<DT><B>`Construct_min_vertex_2`,`Construct_max_vertex_2`:</B><DD>
Returns the left endpoint (similarly, the right endpoint) of
an \f$ x\f$-monotone curve.
<DT><B>`Compare_y_at_x_2`:</B><DD> Given an \f$ x\f$-monotone curve \f$ c\f$ and a
point \f$ p\f$ that lies in its \f$ x\f$-range, this predicate determines
whether \f$ p\f$ lies below, above or on \f$ c\f$.
<DT><B>`Compare_y_at_x_right_2`:</B><DD>
Given two \f$ x\f$-monotone curves \f$ c_1\f$ and \f$ c_2\f$ that share a common
left endpoint \f$ p\f$, this predicate determines whether \f$ c_1\f$ lies
above or under \f$ c_2\f$ immediately to the right of \f$ p\f$, or whether the
two curves coincide there.
<DT><B>`Equal_2`:</B><DD> Checks two points and two curves for equality
(two curves are equal if their graph is the same).
<DT><B>`Is_vertical_2`:</B><DD>
Determines whether an \f$ x\f$-monotone curve is vertical.
</DL>

Each model of the concept `ArrangementBasicTraits_2`
needs to define a tag named `Has_left_category`. It determines
whether the traits class supports the following predicate:
<DL>
<DT><B>`Compare_y_at_x_left_2`:</B><DD>
Given two \f$ x\f$-monotone curves \f$ c_1\f$ and \f$ c_2\f$ that share a common
right endpoint \f$ p\f$, this predicate determines whether \f$ c_1\f$ lies
above or under \f$ c_2\f$ immediately to the left of \f$ p\f$, or whether the
two curves coincide there.
</DL>
This predicate is optional, as it can be answered using the
other traits-class primitives, and we wish to alleviate the
need to implement an extra method that is not absolutely
necessary. However, as implementing the predicate directly
may prove to be more efficient, the traits-class
implementer may choose to provide it.

The basic set of predicates is sufficient for constructing
arrangements of \f$ x\f$-monotone curves that do not reach or approach the
boundary of the parameter space. The nature of the input curves, i.e.,
whether some of them are expected to reach or approach the left, right,
bottom, or top side of the boundary of the parameter space, must be
conveyed by the traits class. This is done through the definition of
four additional nested types, namely `Left_side_category`,
`Right_side_category`, `Bottom_side_category`, and
`Top_side_category`. Each of those types must be convertible to
the type `Arr_oblivious_side_tag` for the class to be a model of
the concept `ArrangementBasicTraits_2`.

\subsection arr_sssectr_lanmarks_concept The Landmarks Concept

The type of an arrangement associated with the landmark point-location
strategy (see Section \ref arr_ssecpl) must be an instance of the
`Arrangement_2<Traits,Dcel>` class template, where the `Traits`
parameter is substituted with a model of the concept
`ArrangementLandmarkTraits_2`. (Naturally, it can also model
either the `ArrangementXMonotoneTraits_2` concept or the
`ArrangementTraits_2` concept.) The `ArrangementLandmarkTraits_2`
concept refines the two concepts `ArrangementApproximateTraits_2` and
`ArrangementConstructXMonotoneCurveTraits_2`. Each of these two
concepts, in turn, refines the concept `ArrangementBasicTraits_2`.

A model of the `ArrangementApproximateTraits_2` concept must define a
fixed precision number type (typically the double-precision
floating-point `double`) and support the additional below (in addition
to fulfilling the requirements listed by the `ArrangementBasicTraits_2`
concept).
<DL>
<DT><B>`Approximate_2`:</B>
<DD> Given a point `p`, approximate the \f$ x\f$ and \f$ y\f$-coordinates of
`p` using the fixed precision number type. We use this operation for
approximate computations---there are certain operations in the search
for the location of the point that need not be exact and we can
perform them faster than other operations.
</DL>

A model of the `ArrangementConstructXMonotoneCurveTraits_2` concept
support the operation below (in addition to fulfilling the requirements
listed by the `ArrangementBasicTraits_2` concept).
<DL>
<DT><B>`Construct_x_monotone_curve_2`:</B>
<DD> Given two points \f$ p_1\f$ and \f$ p_2\f$, this predicate constructs an
\f$ x\f$-monotone curve connecting \f$ p_1\f$ and \f$ p_2\f$.
</DL>

\subsection arr_sssectr_xmon_concept Supporting Intersecting x-Monotone Curves

A traits class that models the `ArrangementXMonotoneTraits_2`
concept, which refines the `ArrangementBasicTraits_2`
concept, has to support the following functions:
<DL>
<DT><B>`Intersection_2`:</B><DD>
Computes all intersection points and overlapping sections of
two given \f$ x\f$-monotone curves. If possible, computes also the
multiplicity of each intersection point.\cgalFootnote{If the two curves intersect at a point \f$ p\f$ but have different tangents, \f$ p\f$ is of multiplicity 1. If the tangents are also equal but the their curvatures are not the same, \f$ p\f$ is of multiplicity 2, etc.}
Knowing the multiplicity of an intersection point is not required,
but it can speed up the arrangement construction.
<DT><B>`Split_2`:</B><DD> Splits an \f$ x\f$-monotone curve \f$ c\f$ into two subcurves
at a point \f$ p\f$ lying in the interior of \f$ c\f$.
<DT><B>`Are_mergeable_2`:</B><DD> Given two \f$ x\f$-monotone curve \f$ c_1\f$ and
\f$ c_2\f$ that share a common endpoint, this predicate determines
whether \f$ c_1\f$ and \f$ c_2\f$ are <I>mergeable</I>, that is, whether they
can be merged to form a single continuous \f$ x\f$-monotone curve of the
type supported by the traits class.
<DT><B>`Merge_2`:</B><DD> Merges two mergeable \f$ x\f$-monotone curves.
</DL>
Using a model of the `ArrangementXMonotoneTraits_2`, it is
possible to construct arrangements of sets of \f$ x\f$-monotone curves
(and points) that may intersect one another.

\subsection arr_sssectr_full_concept Supporting Arbitrary Curves

The concept `ArrangementTraits_2` refines the
`ArrangementXMonotoneTraits_2` concept by adding the notion
of a general, not necessarily \f$ x\f$-monotone (and not necessarily
continuous) curve. A model of this concept must define the
`Curve_2` type and support the subdivision of a curve into a
set of continuous \f$ x\f$-monotone curves and isolated points using
the predicate `Make_x_monotone_2`. For example, the curve
\f$ C:\ (x^2 + y^2)(x^2 + y^2 - 1) = 0\f$ is the unit circle (the loci
of all points for which \f$ x^2 + y^2 = 1\f$) with the origin \f$ (0,0)\f$
as a singular point in its interior. \f$ C\f$ should therefore be
divided into two circular arcs (the upper part and the lower part
of the unit circle) and a single isolated point.

Note that the refined model `ArrangementTraits_2` is required
only when using the free `insert()` functions (see
Section \ref arr_secgl_funcs), which accept a `Curve_2` object
in the incremental version, or a range of `Curve_2` objects in the
aggregated version. In all other cases it is sufficient to use a model
of the `ArrangementXMonotoneTraits_2` concept.

\subsection Arrangement_on_surface_2SupportingUnbounded Supporting Unbounded Curves

An arrangement that supports unbounded \f$ x\f$-monotone curves maintains
an implicit bounding rectangle in the \sc{Dcel} structure; see
Section \ref arr_ssecunb_rep. The unbounded ends of vertical rays,
vertical lines, and curves with vertical asymptotes are represented
by vertices that lie on the bottom or top sides of this bounding
rectangle. These vertices are not associated with points, but are
associated with (finite) \f$ x\f$-coordinates. The unbounded ends of all
other curves are represented by vertices that lie on the left or
right sides of this bounding rectangle. These vertices are not
associated with points either. Edges connect these vertices and the
four vertices that represents the corners of this bounding rectangle
to form the rectangle.

Several predicates are required to handle \f$ x\f$-monotone curves that
approach infinity and thus approach the boundary of the parameter
space. These predicates are sufficient to handle not only curves
embedded in an unbounded parameter space, but also curves embedded
in a bounded parameter space with open boundaries. Let \f$ b_l\f$ and
\f$ b_r\f$ denote the \f$ x\f$-coordinates of the left and right boundaries of
the parameter space, respectively. Let \f$ b_b\f$ and \f$ b_t\f$ denote the
\f$ y\f$-coordinates of the bottom and top boundaries of the parameter
space, respectively. Recall that currently the general code of the
arrangement only supports the case where the parameter space is the
entire compactified plane, thus \f$ b_l = b_b = -\infty\f$ and
\f$ b_r = b_t = +\infty\f$. Nonetheless, when the parameter space is
bounded, it is the exact geometric embedding of the implicit bounding
rectangle. In the following we assume that an \f$ x\f$ monotone
curve \f$ C\f$ can be considered as a parametric curve \f$ C(t) = (X(t),Y(t))\f$
defined over a closed, open, or half open interval with endpoints \f$ 0\f$
and \f$ 1\f$.

Models of the concept `ArrangementOpenBoundaryTraits_2` handle
curves that approach the boundary of the parameter space. This concept
refines the concept `ArrangementBasicTraits_2`. The arrangement
template instantiated with a traits class that models this concept
can handle curves that are unbounded in any direction. If some curves
inserted into an arrangement object are expected to be unbounded, namely,
there exists \f$ d \in \{0,1\}\f$ such that
\f$ \lim_{t \rightarrow d}X(t) = \pm\infty\f$ or
\f$ \lim_{t \rightarrow d}y(t) = \pm\infty\f$
holds for at least one input curve \f$ C(t) = (X(t),Y(t))\f$, the arrangement
template must be instantiated with a model of the
`ArrangementOpenBoundaryTraits` concept.\cgalFootnote{We intend to enhance the arrangement template to handle curves confined to a bounded yet open parameter space. A curve that reaches the boundary of the parameter space in this case is bounded and open.}

All the four types `Left_side_category`,
`Right_side_category`, `Bottom_side_category`, and
`Top_side_category` nested in a model of the concept
`ArrangementOpenBoundaryTraits` must be convertible to
`Arr_open_side_tag`.\cgalFootnote{The tags `Arr_oblivious_side_tag` and `Arr_open_side_tag` are only two out of a larger number of options for the side categories included in major extension the code is going through.}
For example, the `Arr_rational_function_traits_2` traits-model supports
unbounded curves; see Section \ref arr_ssectr_ratfunc. Thus, all
four nested types are defined as `Arr_open_side_tag`.
Adversely, all four types nested in the `Arr_segment_traits_2`
traits-model (see Section \ref arr_ssectr_segs) are defined as
`Arr_oblivious_side_tag`, as segments are always
bounded.\cgalFootnote{We intend to introduce more concepts that require only a subset of the categories to be convertible to `Arr_open_side_tag`.}

A model of the concept `ArrangementOpenBoundaryTraits_2` must provide
the additional predicates listed below.
\f$ x\f$-coordinates and \f$ y\f$-coordinates are differently handled. This
asymmetry is brought on by the various algorithms applied to
arrangements, the input and output arguments of which are \f$ x\f$-monotone
curves. Indeed, all curves maintained by any arrangement are
continuous weakly \f$ x\f$-monotone curves. A non \f$ x\f$-monotone curve is
divided into \f$ x\f$-monotone sub curves (and perhaps points) before it
is inserted into an arrangement. This asymmetry is also reflected in
the additional predicates listed below.

<DL>
<DT><B>`Parameter_space_in_x_2`:</B><DD>
Given a parametric \f$ x\f$-monotone curve \f$ C(t) = (X(t),Y(t))\f$ and an
enumerator that specifies either the minimum end or the maximum end
of the curve, and thus maps to a parameter value \f$ d \in \{0,1\}\f$,
this predicate determines the location of the curve end along the
\f$ x\f$-dimension. Formally, the predicate determines whether
\f$ \lim_{t \rightarrow d} X(t)\f$ evaluates to \f$ b_l\f$, \f$ b_r\f$, or a value
in between.
<DT><B>`Compare_y_near_boundary_2`:</B><DD>
Given two \f$ x\f$-monotone curves \f$ C_1\f$ and \f$ C_2\f$ and an enumerator \f$ i\f$
that specifies either the minimum ends or the maximum ends of the
two curves, this predicate compares the \f$ y\f$-coordinates of the
curves near their respective ends. That is, the predicate compares
the \f$ y\f$-coordinates of the vertical projection of a point \f$ p\f$ onto
\f$ C_1\f$ and onto \f$ C_2\f$. If the enumerator \f$ i\f$ specifies the minimum
ends, the curves must approach the left boundary-side. In this case
\f$ p\f$ is located far to the left, such that the result is invariant
under a translation of \f$ p\f$ farther to the left. If \f$ i\f$ specifies the
maximum ends, the curves must approach the right boundary-side. In
that case \f$ p\f$ is located far to the right in a similar manner.
<DT><B>`Parameter_space_in_y_2`:</B><DD>
Given a parametric \f$ x\f$-monotone curve \f$ C(t) = (X(t),Y(t))\f$ and an
enumerator that specifies either the minimum end or the maximum end
of the curve, and thus maps to a parameter value \f$ d \in \{0,1\}\f$,
this predicate determines the location of the curve end along the
\f$ y\f$-dimension. Formally, the predicate determines whether
\f$ \lim_{t \rightarrow d} Y(t)\f$ evaluates to \f$ b_b\f$, \f$ b_t\f$, or a value
in between.
<DT><B>`Compare_x_at_limit_2`:</B><DD>
Two versions of this predicate are provided:
(i) Given a point \f$ p\f$, a parametric \f$ x\f$-monotone curve
\f$ C(t) = (X(t),Y(t))\f$, and an enumerator that specifies either the
minimum end or the maximum end of the curve, and thus maps to a
parameter value \f$ d \in \{0,1\}\f$, this predicate compares the
\f$ x\f$-coordinate of \f$ p\f$ and \f$ \lim_{t \rightarrow d} X(t)\f$. If the
parameter space is unbounded, a precondition assures that \f$ C\f$
has a vertical asymptote at its \f$ d\f$-end; that is
\f$ \lim_{t \rightarrow d} X(t)\f$ is finite.
(ii) Given two parametric \f$ x\f$-monotone curves
\f$ C_1(t) = (X_1(t),Y_1(t))\f$ and \f$ C_2(t) = (X_2(t),Y_2(t))\f$ and two
enumerators that specify either the minimum end or the maximum
end of each curve, and thus map to parameter values
\f$ d_1\in \{0,1\}\f$ and \f$ d_2 \in \{0,1\}\f$ for \f$ C_1\f$ and for \f$ C_2\f$,
respectively, this predicate compares
\f$ \lim_{t \rightarrow d_1} X_1(t)\f$ and \f$ \lim_{t \rightarrow d_2} X_2(t)\f$.
If the parameter space is unbounded, a precondition assures that
\f$ C_1\f$ and \f$ C_2\f$ have vertical asymptote at their respective ends;
that is \f$ \lim_{t \rightarrow d_1} X_1(t)\f$ and
\f$ \lim_{t \rightarrow d_2} X_2(t)\f$ are finite.
<DT><B>`Compare_x_near_limit_2`:</B><DD>
Given two \f$ x\f$-monotone curves \f$ C_1\f$ and \f$ C_2\f$ and an enumerator \f$ i\f$
that specifies either the minimum ends or the maximum ends of the
two curves, this predicate compares the \f$ x\f$-coordinates of the
curves near their respective ends. That is, the predicate compares
the \f$ x\f$-coordinates of the horizontal projection of a point \f$ p\f$
onto \f$ C_1\f$ and onto \f$ C_2\f$. If the parameter space is unbounded, a
precondition assures that \f$ C_1\f$ and \f$ C_2\f$ have vertical asymptote
at their respective ends. Furthermore, both curves approach the
same boundary-side, either the bottom or the top, at their
respective ends. If both curves approach the bottom boundary-side,
\f$ p\f$ is located far to the bottom, such that the result is invariant
under a translation of \f$ p\f$ farther to the bottom. If both curves
approach the top boundary-side, \f$ p\f$ is located far to the top in a
similar manner. Another precondition assures that the
\f$ x\f$-coordinates of the limits of the curves at their respective
ends are equal. That is, the predicate `Compare_x_at_limit_2`
applied to \f$ C_1\f$, \f$ C_2\f$, and \f$ i\f$ evaluates to `EQUAL`.
</DL>

In the rest of this section we review the traits classes
included in the public distribution of \cgal, that handle line
segments, polylines, conic arcs, rational functions, and arcs of
B&eacute;zier and algebraic curves.
The last subsection overviews
decorators for geometric traits classes distributed with \cgal,
which extend other geometric traits-class by attaching auxiliary
data with the geometric objects.

\subsection arr_ssectr_segs Traits Classes for Line Segments and Linear Objects

The `Arr_segment_traits_2<Kernel>` class used so far in most
example programs in this chapter is a model of the concepts
`ArrangementTraits_2`, `ArrangementLandmarkTraits_2`,
and `ArrangementDirectionalXMonotoneTraits_2`; the later
enables Boolean set operations. It is parameterized by a
geometric kernel and uses the `Kernel::Point_2` type as it
point type. However, neither the `Curve_2` nor the
`X_monotone_curve_2` types are identical to the
`Kernel::Segment_2` type. A kernel segment is typically
represented by its two endpoints, and these may have a large bit-size
representation, if the segment is intersected and split several
times (in comparison with the representation of its original
endpoints). The large representation may significantly slow down the
various traits-class operations involving such a segment. In contrast,
the `Arr_segment_traits_2` represents a segment using
its supporting line and the two endpoints, such that most computations
are performed on the supporting line, which never changes as the
segment is split. It also caches some additional information with
the segment to speed up various predicates.
An `X_monotone_curve_2` object can still be constructed from two
endpoints or from a kernel segment. Moreover, an
`X_monotone_curve_2` instance can also be casted or assigned to a
`Kernel::Segment_2` object. The two types are thus fully
convertible to one another.

The `Arr_segment_traits_2<Kernel>` class is very efficient for
maintaining arrangements of a large number of intersecting line
segments, especially if it is instantiated with the appropriate
geometric kernel. Using `Exact_predicates_exact_constructions_kernel`
as the kernel type, which is the default, is generally a good choice;
the coordinates of the segment endpoints are represented as exact
rational numbers, and this ensures the robustness and correctness of
any computation.\cgalFootnote{Many of the example programs in the rest
of the chapter include a header file named `arr_rational_nt.h`, which
defines a type named `Number_type` as either `Gmpq` or
`Quotient<MP_Float>`, depending on whether <span
class="textsc">Gmp</span> is installed or not.}

An instance of the `Arr_segment_traits_2<Kernel>` class
template can be very efficient for constructing arrangements induced
by line segments with a large number of intersections. Efficiency is
affected by the substituted geometric kernel. Using
`Cartesian<Gmpq>` as the kernel type is in general not a
bad choice; the coordinates of the segment endpoints are represented
as multi-precision rational-numbers, and this ensures the correctness
of all computations regardless of the input. Computations on
multi-precision number types, such as `Gmpq`, typically
take longer than computations on machine-precision
floating-point. However, in almost all cases it is possible to
expedite the computation using numerical filtering; see
`Kernel_2` and `Kernel_3`. If the input set of line segments do
not have degeneracies; namely, no two segments in the set share a
common endpoint, and no three segments intersect at a common point, or
at least, degeneracies exist but their number is relatively small,
then filtered computation incurs only negligible overhead compared to
floating-point arithmetic, which is error-prone. Indeed, in almost all
examples and applications given in this manual, a predefined filtered
kernel is used to instantiate the line-segment traits class, namely
`Exact_predicates_exact_constructions_kernel`. Furthermore, this kernel
is used as a default kernel in case the user did not provide one.

\cgalFigureBegin{arr_figpredef_kernels,fan_grids.png,Europe.png}
(a) An arrangement of \f$ 104\f$ line segments from the input file `fan_grids.dat`. (b) An arrangement of more than \f$ 3000\f$ interior disjoint line segments, defined in the input file `Europe.dat`.
\cgalFigureEnd

In the following example we use the predefined
`Exact_predicates_exact_constructions_kernel` for instantiating our
segment-traits class. This kernel use interval arithmetic to filter the
exact computations. The program reads a set of line segments with integer
coordinates from a file and computes their arrangement. By default it
opens the `fan_grids.dat` input-file, located in the examples folder,
which contains \f$ 104\f$ line segments that form four "fan-like" grids and
induce a dense arrangement, as illustrated in
\cgalFigureRef{arr_figpredef_kernels} (a):

\cgalExample{Arrangement_on_surface_2/predefined_kernel.cpp}

The arrangement package also offers a simpler alternative
segment-traits class. The traits class
`Arr_non_caching_segment_basic_traits_2<Kernel>` models
the `ArrangementBasicTraits_2` concept. It uses
`Kernel::Point_2` as its point type and
`Kernel::Segment_2` as its \f$ x\f$-monotone curve type. As this
traits class does not support intersecting and splitting segments,
the kernel representation is sufficient. It is still less
efficient than `Arr_segment_traits_2` for constructing
arrangements of pairwise disjoint line segments in many cases, as
it performs no caching at all, but using this traits class may be
preferable as it reduces the memory consumption a bit, since no extra
data is stored with the line segments.

The class `Arr_non_caching_segment_traits_2<Kernel>` inherits
from `Arr_non_caching_segment_basic_traits_2<Kernel>` and
extends it to be a model of the concepts `ArrangementTraits_2`,
`ArrangementLandmarkTraits_2`,and
`ArrangementDirectionalXMonotoneTraits_2`. It may thus be used to
construct arrangement of intersecting line segments, but as explained
above, for efficiency reasons it is recommended to use it only when
the arrangement is very sparse and contains hardly any intersection
points.

In the following example we read an input file containing a set of
line segments that are pairwise disjoint in their interior. As the
segments do not intersect, no new points are constructed and we can
instantiate the `Arr_non_caching_segment_traits_basic_2<Kernel>`
class-template with the predefined
`Exact_predicates_inexact_constructions_kernel`. Note that we use
the `insert_non_intersecting_curves()` function to construct the
arrangement.
By default, the example opens the `Europe.dat` input-file,
located in the examples folder, which contains more than \f$ 3000\f$ line segments
with floating-point coordinates that form the map of Europe, as depicted in
\cgalFigureRef{arr_figpredef_kernels} (b):

\cgalExample{Arrangement_on_surface_2/predefined_kernel_non_intersecting.cpp}

The `Arr_linear_traits_2<Kernel>` class used for demonstrating the
construction of arrangements of unbounded curves is capable of handling
bounded and unbounded linear objects, namely lines, rays and line
segments. It is parameterized by a geometric kernel and such that
its nested `Point_2` type is the same as the kernel point. The
`Curve_2` (and `X_monotone_curve_2`) type it defines is
constructible from a `Kernel::Line_2`, a `Kernel::Ray_2` or
from a `Kernel::Segment_2` object. Just like the default
segment-traits class, the linear-traits class also use caching
techniques to speed up its predicates and constructions.

\subsection arr_ssectr_polylines The Polyline and Polycurve Traits Classes

Polylines are continuous piecewise linear curves. Polylines are of
particular interest, as they can be used to approximate more complex
curves in the plane. At the same time they are easier to handle in
comparison to higher-degree algebraic curves, as rational arithmetic
is sufficient to carry out computations on polylines, and to construct
arrangements of polylines in an exact and robust manner.

The `Arr_polyline_traits_2<SubcurveTraits_2>` class template handles
polylines. It models the concepts `ArrangementTraits_2`,
and `ArrangementDirectionalXMonotoneTraits_2`. The type that
substitutes the template parameter `SubcurveTraits_2` when
`Arr_polyline_traits_2<SubcurveTraits_2>` is instantiated must be a
geometry-traits class that models the following concepts:

- `ArrangementTraits_2`,
- `ArrangementDirectionalXMonotoneTraits_2`,
- `ArrangementConstructXMonotoneCurveTraits_2`.

We refer to the type that substitutes the template parameter
`SubcurveTraits_2` as the <em>subcurve traits</em> hereafter.
If, in addition, the subcurve traits also models the concept
`ArrangementApproximateTraits_2` then the instantiated
`Arr_polyline_traits_2<SubcurveTraits>` type models the concept
`ArrangementApproximateTraits_2` as well. (By definition, modeling the
concepts `ArrangementApproximateTraits_2` and
`ArrangementConstructXMonotoneCurveTraits_2` implies modeling the
concept `ArrangementLandmarkTraits_2`.) The same holds for the
`ArrangementOpenBoundaryTraits_2` concept as well.
Modeling the `ArrangementConstructXMonotoneCurveTraits_2` concept
implies that the subcurve traits must support the construction of a
unique (\f$x\f$-monotone) segment given two input points. Roughly
speaking, it means that each operation defined by the subcurve traits
must handle linear curves.

An instance of the polyline traits class-template inherits its nested
point type, i.e., `Point_2`, from the subcurve traits, and defines the
nested types `Curve_2` and `X_monotone_curve_2`, which are used to
represent polylines and \f$x\f$-monotone polylines, respectively.  A
polyline of the nested type `Curve_2` is stored as a vector of
`SubcurveTraits_2::Curve_2` objects, and an \f$x\f$-monotone polyline
of the nested type `X_monotone_curve_2` is stored as a vector of
`SubcurveTraits_2::X_monotone_curve_2` objects.  The nested
`X_monotone_curve_2` type inherits from the nested type `Curve_2`.  By
default, `Arr_segment_traits_2` is used as the subcurve traits (in
case where the `SubcurveTraits_2` parameter is omitted). In this case
the nested types `SubcurveTraits_2::Curve_2` and
`SubcurveTraits_2::X_monotone_curve_2` are identical types
representing line segments.

A polyline can be constructed given one of the following inputs:

- <b>A range of <em>points</em></b>, where two succeeding points in the
  range represent the endpoints of a segment of the polyline.

- <b>A range of <em>segments</em></b>. Note that , if the types
`SubcurveTraits_2::Curve_2` and `SubcurveTraits_2::X_monotone_curve_2` are
not the same, then when `Make_x_monotone_2` is invoked the segments
that compose the polyline will be broken into \f$x\f$-monotone
parts.

- <b>A pair of points \a or a single segment</b>. In this case a polyline
  that consists of a single segment is constructed.

Note that degenerate polylines are not supported. That is, it is
impossible to construct a polyline that contains a segment of length
zero, or an isolated point. Finally, a polyline is
<b><em>continuous</em></b> and <b><em>well-oriented</em></b>; that is,
the target of the \f$i\f$th segment is the source of the \f$i+1\f$st
segment. For example, the general polyline

\image html generic-polyline.png
\image latex generic-polyline.pdf

can be represented by one of the following two

\image html well-oriented-polyline.png
\image latex well-oriented-polyline.pdf

Also, note, that a single polyline can be split into several
\f$ x\f$-monotone polylines, and that the number of intersection
points (or overlapping sections) between two polylines can also
be large.

\cgalAdvancedBegin

Technically speaking, it is possible to construct a general polyline
that is neither well-oriented nor continuous. However, it is
impossible to use such polylines for the purpose of computing an
arrangement.

\cgalAdvancedEnd

You can traverse over the range of defining segments of a given
polyline. The \a first and \a past-the-end iterators can be obtained
through the access functions of the polyline `begin_segments()` and
`end_segments()`, respectively. The vertices of an \f$ x\f$-monotone
curve are always stored in a strongly monotonic lexicographical order.
In other words, \f$x\f$-monotone polylines can be directed \a either
left-to-right \a or right-to-left. If the macro
#CGAL_ALWAYS_LEFT_TO_RIGHT is set to 1, then the \f$x\f$-monotone
polylines are always directed from left-to-right (only proposed for
backward compatibility).

The polyline-traits class does not perform any geometric operations
directly. Instead, it solely relies on the functionality of the
segment traits. For example, when we need to determine the position of
a point with respect to an \f$x\f$-monotone polyline, we use binary
search to locate the relevant segment that contains the point in its
\f$x\f$-range. Then, we compute the position of the point with respect
to this segment. Thus, operations on \f$x\f$-monotone polylines of
size \f$m\f$ typically take \f$O(\log m)\f$ time.

You are free to choose the underlying segment traits class. Your
decision could be based, for example, on the number of expected
intersection points; see Section \ref arr_ssectr_segs. Moreover, it
is possible to substitute the `SubcurveTraits_2` template parameter
with a traits class that handles segments with some additional data
attached to each individual segment; see Section
\ref arr_ssecmeta_tr. This makes it possible to associate different
data objects with the different segments that compose a polyline.

\cgalFigureBegin{arr_figex_12,ex_12.png} An arrangement of three
polylines, as constructed in `polylines.cpp`. Disks mark vertices
associated with polyline endpoints, while circles mark vertices that
correspond to intersection points. Note that \f$ \pi_2\f$ is split
into three \f$ x\f$-monotone polylines, and that \f$ \pi_1\f$ and \f$
\pi_3\f$ have two overlapping sections. \cgalFigureEnd

The following example program constructs an arrangement of three
polylines, as depicted in \cgalFigureRef{arr_figex_12}. Note that
most points defining the polylines are not associated with arrangement
vertices. The arrangement vertices are either the endpoints of
each \f$ x\f$-monotone polyline or the intersection points between two
polylines:

\cgalExample{Arrangement_on_surface_2/polylines.cpp}

The traits class `Arr_polycurve_traits_2<GeometryTraits_2>` handles
piecewise curves that are not necessarily linear, such as conic arcs,
circular arcs, Bezier curves, or line segments. We call such a
compound curve a <em>polycurve</em>. Similar to a polyline, a
polycurve is a chain of subcurves, where each two neighboring
subcurves in the chain share a common endpoint; that is, the polycurve
is continuous. As a matter of fact, most characteristics of the
`Arr_polyline_traits_2<GeometryTraits_2>` traits class apply also to
the `Arr_polycurve_traits_2<GeometryTraits_2>` traits class. The only
difference between the two, is that the latter is not a model of the
concept `ArrangementConstructXMonotoneCurveTraits_2`, and as such, it
is not able to construct a subcurve from two points. As a consequence,
it does not support the operations that (i) construct a polycurve from
a sequence of point, and (ii) push a point at the back or at the front
of a non-empty polycurve.

\subsection arr_ssectr_circ_seg A Traits Class for Circular Arcs and Line Segments

Circles and circular arcs are the simplest form of non-linear curves.
We handle circles whose centers have rational coordinates and whose
squared radii is also rational. If we denote the circle center by \f$ (x_0,y_0)\f$
and its radius by \f$ r\f$, then the equation of the circle - that is,
\f$ (x - x_0)^2 + (y - y_0)^2 = r^2\f$ - has rational coefficients.
The intersection points of two such circles are therefore solutions
of a quadratic equation with rational coefficients, or algebraic numbers
of degree \f$ 2\f$. The same applies for intersection points between such a
rational circle and a line, or a line segment, with rational coefficients
(a line whose equation is \f$ ax + by + c = 0\f$, where \f$ a\f$, \f$ b\f$ and \f$ c\f$ are
rational). Such numbers can be expressed as \f$ \alpha + \beta\sqrt{\gamma}\f$,
where \f$ \alpha\f$, \f$ \beta\f$ and \f$ \gamma\f$ are all rational numbers.

Arrangement of circular arcs and of line segment are very useful, as they
occur in many applications. For example, when dilating a polygon by some
radius we obtain a shape whose boundary is comprised of line segments,
which correspond to dilated polygon edges, and circular arcs, which
result from dilated polygon vertices. Using the arrangement of the
boundary curves it is possible, for example, to compute the union of a set
of dilated polygons.

The `Arr_circle_segment_traits_2<Kernel>` class-template is designed
for efficient handling of arrangements of circular arcs and line segments.
It is a model of the concepts `ArrangementTraits_2` and
`ArrangementDirectionalXMonotoneTraits_2`; the later enables
Boolean set operations. Note that it is not a model of
`ArrangementLandmarkTraits_2` concept, so it is impossible to
use the landmark point-location strategy. The traits class template
is parameterized by a geometric kernel, and can handle arrangements of
segments of `Kernel::Circle_2` objects (full circles are also supported)
or of `Kernel::Line_2` objects - namely circular arcs and line segments.
It is important to observe that the nested `Point_2` type defined by the
traits class, whose coordinates are typically algebraic numbers of degree 2,
is <I>not</I> the same as the `Kernel::Point_2` type, which is capable of
representing a point with rational coordinates. The coordinates of a
point are represented using the nested `CoordNT` number-type.

\cgalFigureBegin{arr_figex_13,ex_13.png}
An arrangement of three circles constructed in `circles.cpp`. Each circle is split into two \f$ x\f$-monotone circular arcs, whose endpoints are drawn as disks. Circles mark vertices that correspond to intersection points. The vertex \f$ v_{\rm max}\f$ is a common intersection point of all three circles.
\cgalFigureEnd


In the following example an arrangement of three full circles is
constructed, as shown in \cgalFigureRef{arr_figex_13}. Then, the vertex
of maximal degree is searched for. The geometric mapping of this
vertex is the point \f$ (4,3)\f$, as all three circles intersect at this point
and the associated vertex has six incident edges:

\cgalExample{Arrangement_on_surface_2/circles.cpp}

The `Curve_2` type nested in `Arr_circle_segment_traits_2` can be
used to represent circles, circular arcs, or line segments. Curve objects
can therefore be constructed from a `Kernel::Circle_2` object or from
a `Kernel::Segment_2` object. A circular arc is typically defined by
a supporting circle and two endpoints, where the endpoints are instances
of the `Point_2` type, with rational or irrational coordinates. The
orientation of the arc is determined by the orientation of the supporting
circle. Similarly, we also support the construction of lines segments given
their supporting line (of type `Kernel::Line_2`) and two endpoints, which
may have irrational coordinates (unlike the `Kernel::Segment_2` type).

Note that the `Kernel::Circle_2` type represents a circle whose
<I>squared radius</I> is rational, where the radius itself may be irrational.
However, if the radius is known to be rational, it is advisable to use it,
for efficiency reasons. It is therefore also possible to construct a circle,
or a circular arc specifying the circle center (a `Kernel::Point_2`), its
rational radius, and its orientation. Finally, we also support the construction
of a circular arcs that is defined by two endpoints and an arbitrary midpoint
that lies on the arc in between its endpoint. In this case, all three points
are required to have rational coordinates (to be kernel points).

The following example demonstrates the usage of the various construction
methods for circular arcs and line segments. Note the usage of the constructor
of `CoordNT (alpha, beta, gamma)`, which creates a degree-\f$ 2\f$ algebraic
number whose value is \f$ \alpha + \beta\sqrt{\gamma}\f$.

\cgalExample{Arrangement_on_surface_2/circular_arcs.cpp}

It is also possible to construct \f$ x\f$-monotone curve objects, which represent
\f$ x\f$-monotone circular arcs or line segments, using similar constructors.
Construction from a full circle is obviously not supported. See the Reference
Manual for more details.

The traits class-template
`Arr_circular_line_arc_traits_2<CircularKernel>` offered by the
arrangement package also handles circular arcs and line segments. It
is an alternative to the `Arr_circle_segment_traits_2<Kernel>`
class-template. These two class templates, while serve similar
purposes, are based on different concepts, and posses different
characteristics. You are encouraged to experiment with both, compare
their performance, and use the most suitable for your case.

\subsection arr_ssectr_conic A Traits Class for Conic Arcs

A <I>conic curve</I> is an algebraic curve of degree 2. Namely, it
is the locus of all points \f$ (x,y)\f$ satisfying the equation \f$ C:\ r
x^2 + s y^2 + t xy + u x + v y + w = 0\f$, where the six
coefficients \f$ \langle r, s, t, u, v, w \rangle\f$ completely
characterize the curve. The sign of the expression \f$ \Delta_{C} = 4
r s - t^2\f$ determines the type of curve:
<UL>
<LI>If \f$ \Delta_{C} > 0\f$ the curve is an ellipse. A circle is a
special case of an ellipse, where \f$ r = s\f$ and \f$ t = 0\f$.
<LI>If \f$ \Delta_{C} = 0\f$ the curve is a parabola - an unbounded
conic curve with a single connected branch. When \f$ r = s = t = 0\f$
we have a line, which can be considered as a degenerate parabola.
<LI>If \f$ \Delta_{C} < 0\f$ the curve is a hyperbola. That is, it
is comprised of two disconnected unbounded branches.
</UL>

As the arrangement package is suitable for bounded curves, we
consider bounded segments of conic curves, referred to as <I>conic arcs</I>. A conic arc \f$ a\f$ may be either (i) a full ellipse, or
(ii) defined by the tuple \f$ \langle C, p_s, p_t, o \rangle\f$, where
\f$ C\f$ is a conic curve and \f$ p_s\f$ and \f$ p_t\f$ are two points on \f$ C\f$
(namely \f$ C(p_s) = C(p_t) = 0\f$) that define the <I>source</I> and
<I>target</I> of the arc, respectively. The arc is formed by
traversing \f$ C\f$ from the source to the target going in the
orientation specified by \f$ o\f$, which is typically clockwise or
counterclockwise orientation (but may also be collinear in case of
degenerate conic curves).

We always assume that the conic coefficients \f$ \langle r, s,
t, u, v, w \rangle\f$ are rational. When dealing with linear curves
(line segments and polylines), similar assumptions guarantee that
all intersection points also have rational coordinates, such that
the arrangement of such curves can be constructed and maintained
using only rational arithmetic. Unfortunately, this does not hold
for conic curves, as the coordinates of intersection points of two
conic curves with rational coefficients are in general algebraic
numbers of degree \f$ 4\f$.\cgalFootnote{Namely, they are roots of polynomials with integer coefficients of degree \f$ 4\f$. However, in some special cases, for example when handling only circles and circular arcs, the coordinates of the intersection points are only of degree \f$ 2\f$, namely they are solutions of quadratic equations.}
In addition, conic arcs may not necessarily be \f$ x\f$-monotone, and
must be split at points where the tangent to the arc is vertical.
In the general case, such points typically have coordinates that
are algebraic numbers of degree \f$ 2\f$.
It is therefore clear that we have to use different number types
to represent the conic coefficients and the point coordinates.
Note that as arrangement vertices induced by intersection points
and points with vertical tangents are likely to have algebraic
coordinates, we also allow the original endpoints of the input arcs
\f$ p_s\f$ and \f$ p_t\f$ to have algebraic coordinates.

The `Arr_conic_traits_2<RatKernel, AlgKernel, NtTraits>` class
template is designed for efficient handling of arrangements of
bounded conic arcs. The template has three parameters, defined as
follows:
<UL>
<LI>The `RatKernel` class is a geometric kernel, whose field
type is an exact rational type. It is used to define basic
geometric entities (e.g., a line segment or a circle) with rational
coefficients. Typically we use one of the standard \cgal kernels,
instantiated with the number type `NtTraits::Rational` (see
below).
<LI>The `AlgKernel` class is a geometric kernel whose field
type is an exact algebraic type. It is used to define points with
algebraic coordinates. Typically we use one of the standard
\cgal kernels, instantiated with the number type
`NtTraits::Algebraic` (see below).
<LI>The `NtTraits` class (the number-type traits class)
encapsulates all the numeric operations needed for performing the
geometric computation carried out by the geometric traits class.
It defines the `Integer`, `Rational` and `Algebraic`
number-types, and supports several operations on these types, such
as conversion between number types, solving quadratic equations
and extracting the real roots of a polynomial with integer
coefficients. It is highly recommended to use the
`CORE_algebraic_number_traits` class, which is included in the
arrangement package. It relies on the exact number types
implemented in the <span class="textsc">Core</span> library and performs exact
computations on the number types it defines.
</UL>

The `Arr_conic_traits_2` models the `ArrangementTraits_2` and
`ArrangementLandmarkTraits_2` concepts. (It supports
the landmark point-location strategy). Its `Point_2` type is
derived from `AlgKernel::Point_2`, while the `Curve_2`
type represents a bounded, not necessarily \f$ x\f$-monotone, conic arc.
The `X_monotone_curve_2` type is derived from `Curve_2`,
but its constructors are to be used only by the traits class.
You should therefore construct only `Curve_2` objects and
insert them into the arrangement using the `insert()`
or `insert()` functions.

Conic arcs can be constructed from full ellipses or by specifying
a supporting curve, two endpoints and an orientation. However,
several constructors of `Curve_2` are available to allow for some
special cases, such as circular arcs or line segments. The
`Curve_2` (and the derived `X_monotone_curve_2`) classes
also support basic access functions such as `source()`,
`target()` and `orientation()`.

\subsection Arrangement_on_surface_2ExamplesforArrangements Examples for Arrangements of Conics

\cgalFigureBegin{arr_figex_14,ex_14.png}
An arrangement of mixed conic arcs, as constructed in conics.cpp
\cgalFigureEnd


The following example demonstrates the usage of the various
constructors for conic arcs. The resulting arrangement is depicted
in \cgalFigureRef{arr_figex_14}. Especially noteworthy are the
constructor of a circular arc that accepts three points and the
constructor that allows specifying approximate endpoints, where the
exact endpoints are given explicitly as intersections of
the supporting conic with two other conic curves. Also note that as the
preconditions required by some of these constructors are rather
complicated (see the Reference Manual for the details), a
precondition violation does not cause the program to terminate -
instead, an <I>invalid</I> arc is created. We can verify the validity
of an arc by using the `is_valid()` method. Needless to say, inserting
invalid arcs into an arrangement is not allowed.

\cgalExample{Arrangement_on_surface_2/conics.cpp}

The last example in this section demonstrates how the conic-traits
class can handle intersection points with multiplicity. The
supporting curves of the two arcs, a circle centered at
\f$ (0,\frac{1}{2})\f$ with radius \f$ \frac{1}{2}\f$, and the hyperbola \f$ y
= \frac{x^2}{1-x}\f$,\cgalFootnote{This curve can also be written as \f$ C: x^2 + xy - y = 0\f$. It is a hyperbola since \f$ \Delta_{C} = -1\f$.}
intersect at the origin such that the intersection point has
multiplicity \f$ 3\f$ (note that they both have the same horizontal
tangent at \f$ (0,0)\f$ and the same curvature \f$ 1\f$). In addition, they
have another intersection point at \f$ (\frac{1}{2},\frac{1}{2})\f$ of
multiplicity \f$ 1\f$:

\cgalExample{Arrangement_on_surface_2/conic_multiplicities.cpp}

\subsection arr_ssectr_ratfunc A Traits Class for Arcs of Rational Functions

The traits class
`Arr_rational_function_traits_2<AlgebraicKernel_d_1>` handles
bounded and unbounded arcs of rational functions, referred to as
<I>rational arcs</I> (in particular, such an arc may correspond to the
entire graph of a rational function), and enables the construction and
maintenance of arrangements of such arcs. Rational functions, and
polynomial functions in particular, are not only interesting in their
own right, they are also very useful for approximating or
interpolating more complicated curves; see,
e.g., [\cgalCite{cgal:ptvf-nrcpp-02} Chapter 3.

`Arr_rational_function_traits_2<AlgebraicKernel_d_1>` is a model
of the concepts `ArrangementTraits_2`,
`ArrangementOpenBoundaryTraits_2`, and
`ArrangementDirectionalXMonotoneTraits_2`; the later enables
Boolean set operations. Note that it is not a model of
`ArrangementLandmarkTraits_2` concept, so it is impossible to use
the landmark point-location strategy with this traits class.

A rational function \f$ y = \frac{P(x)}{Q(x)}\f$ is defined by two
polynomials \f$ P\f$ and \f$ Q\f$ of arbitrary degrees. If \f$ Q(x) = 1\f$ then
the function is a simple polynomial function. Usually the domain is
\f$ \mathbb{R}\f$ but the function may also be restricted to a bounded interval
\f$ [x_{\rm min}, x_{\rm max}]\f$ or defined over a ray
\f$ (-\infty, x_{\rm max}]\f$ or \f$ [x_{\rm min}, \infty)\f$. Rational
functions are represented by the nested type `Curve_2`.
A rational arc is always \f$ x\f$-monotone in the mathematical
sense. However, it is not necessarily continuous, as it may have
singularities. An arc that has singularities must
be split into continuous portions before being inserted into the
arrangement. Arbitrary rational functions are represented by the
nested type `Curve_2` and continuous portions of rational
functions are represented by the nested type
`X_monotone_curve_2`. Constructors for both types are provided by
the traits. A `Curve_2` may be split up into several
`X_monotone_curve_2` using `Make_x_monotone_2`.

Using the `Arr_rational_function_traits_2<AlgebraicKernel_d_1>`
class template it is possible to construct and maintain arrangement
of rational arcs. The template parameter of the traits must be a model
of the concept `AlgebraicKernel_d_1`. A rational function is
represented as the quotient of two polynomials \f$ P\f$ and \f$ Q\f$ of type
`AlgebraicKernel_d_1::Polynomial_1` and an \f$ x\f$-interval over which
the polynomials are defined. The type of the polynomial coefficients,
namely `AlgebraicKernel_d_1::Coefficient`, cannot be algebraic.
Moreover, it is recommended that this type is not made rational either,
since using rational, as opposed to integral, coefficients does not
extend the range of the rational arcs and is typically less efficient.
The type of the interval bounds, namely
`AlgebraicKernel_d_1::Bound`, however, can be algebraic. A point is
represented by a rational function and its \f$ x\f$-coordinate, which is of
type `AlgebraicKernel_d_1::Algebraic_real_1`. Note that an explicit
representation of the \f$ y\f$-coordinate is only computed upon request, as
it can be a rather costly operation.

The constructed rational functions are cached by the traits class. The
cache is local to each traits class object. It is therefore necessary
to construct curves using only the constructor objects provided by
member functions of the traits class.
Moreover, a curve must only be used by the traits class object that
was used to construct it. The cache is automatically cleaned up from
time to time. The amortized clean up costs are constant. In addition,
there is also a separate member function that cleans up the cache on
demand.

The curve constructors have an additional advantage. They conveniently
enable the provision of two polynomials that define a rational arc
using rational coefficients. For example, let \f$ P\f$ and \f$ Q\f$ denote two
polynomials with integral coefficients that define a rational arc at
interest, and let \f$ P'\f$ and \f$ Q'\f$ denote two polynomials with rational
coefficients that define the same rational arc; that is, the quotients
\f$ P/Q\f$ and \f$ P'/Q'\f$ are identical. You can construct the rational arc
providing the coefficients of \f$ P'\f$ and \f$ Q'\f$ to the constructor. In this
case the constructor normalizes the coefficients and stores the desired
polynomials \f$ P\f$ and \f$ Q\f$.

\cgalFigureBegin{arr_figex_16,ex_16.png}
An arrangement of four arcs of rational functions, as constructed in rational_functions.cpp.
\cgalFigureEnd

The following example demonstrates the construction of an
arrangement of rational arcs depicted in
\cgalFigureRef{arr_figex_16}. Note the usage of the two
constructors, for polynomial arcs and for rational arcs:

\cgalExample{Arrangement_on_surface_2/rational_functions.cpp}

\cgalFigureBegin{arr_figex_unb_rat,ex_unb_rat.png}
An arrangement of six arcs of rational functions, as constructed in unbounded_rational_functions.cpp
\cgalFigureEnd

The following example demonstrates the construction of an
arrangement of six rational arcs - four unbounded arcs and two
bounded ones - as depicted in \cgalFigureRef{arr_figex_unb_rat}. Note
the usage of the constructors of an entire rational function and of
an infinite "ray" of such a function. Also observe that the hyperbolas
\f$ y = \pm\frac{1}{x}\f$ and \f$ y = \pm\frac{1}{2x}\f$ never intersect, although
they have common vertical and horizontal asymptotes, so very "thin"
unbounded faces are created between them:

\cgalExample{Arrangement_on_surface_2/unbounded_rational_functions.cpp}

\subsection arr_ssectr_bez A Traits Class for Planar B&eacute;zier Curves

A planar <I>B&eacute;zier curve</I> \f$ B\f$ is a parametric curve defined by a sequence
of <I>control points</I> \f$ p_0, \ldots, p_n\f$ as follows:

\f{eqnarray*}{
B(t) = \left(X(t), Y(t)\right)
= \ccSum{k=0}{n}{p_k \cdot \frac{n!}{k! (n-k)!} \cdot
t^k (1-t)^{n-k}}\ .
\f}

where \f$ t \in [0, 1]\f$. The degree of the curve is therefore \f$ n\f$ -
namely, \f$ X(t)\f$ and \f$ Y(t)\f$ are polynomials of degree \f$ n\f$. B&eacute;zier curves
have numerous applications in computer graphics and solid modelling. They
are used, for example, in free-form sketches and for defining the true-type
fonts.

Using the `Arr_Bezier_curve_traits_2<RatKernel, AlgKernel, NtTraits>`
class template it is possible to construct and maintain arrangements of
B&eacute;zier curves that are given by rational control points (a sequence
of objects of the `RatKernel::Point_2` type). We can handle curves
of arbitrary degree (in general, a sequence of \f$ n+1\f$ control points define a
B&eacute;zier curve of degree \f$ n\f$). The template parameters are the same ones
used by the `Arr_conic_traits_2` class template, and here it is also
recommended to use the `CORE_algebraic_number_traits` class, with
Cartesian kernels instantiated with the `Rational` and `Algebraic`
number-types defined by this class.

As mentioned above, we assume that the coordinates of all control
points that define a B&eacute;zier curve are rational numbers, so both \f$ X(t)\f$
and \f$ Y(t)\f$ are polynomials with rational coefficients. The intersection
points between curves are however algebraic numbers, and their exact
computation is time-consuming. The traits class therefore contains a layer
of geometric filtering that performs all computation in an approximate
manner whenever possible. Thus, it resorts to exact computations only when
the approximate computation fails to produce an unambiguous result.
Note that most arrangement vertices are therefore associated with approximated
points. You cannot access the coordinates of such points and obtain them as
algebraic numbers, and only access to the approximate coordinates is possible.
See the Reference Manual for the exact interface of the `Point_2`,
`Curve_2` and `X_monotone_curve_2` defined by the traits class.

The `Arr_Bezier_curve_traits_2` is a model of the
`ArrangementTraits_2` concept (but not of the
`ArrangementLandmarkTraits_2` concept, so it is impossible
to use the landmark point-location strategy for arrangements of
rational arcs).

\cgalFigureBegin{arr_figex_bez,Bezier_arr.png}
An arrangement of ten B&eacute;zier curves of degree \f$ 5\f$, as constructed in `Bezier_curves.cpp`.
\cgalFigureEnd


The following example reads a set of B&eacute;zier curves from an input
file, where each file is specified by an integer stating its number
of control points, followed by the sequence of control points, given
in integer or rational coordinates. By default, the program uses
the `Bezier.dat` file, which contains ten curves of degree \f$ 5\f$
each; their resulting arrangement is depicted in
\cgalFigureRef{arr_figex_bez}.

\cgalExample{Arrangement_on_surface_2/Bezier_curves.cpp}

\subsection arr_ssectr_alg A Traits Class for Planar Algebraic Curves of Arbitrary Degree

An algebraic curve \f$ C\f$ in the plane is defined as the (real) zero locus
of a polynomial \f$ f(x,y)\f$ in two variables. The curve is uniquely defined
by \f$ f\f$ (although several polynomials might define the same curve).
We call \f$ f\f$ a <I>defining polynomial</I> of \f$ C\f$.

We consider arrangements induced by algebraic curves
or by (weakly) \f$ x\f$-monotone segments for algebraic curves
(Such a segment is not necessarily the maximal possible
(weakly) x-monotone segment; see below.)
When talking about algebraic curves,
we use the term "segment" for a continuous, possibly non-linear subset
of an algebraic curve - see the definition below.
There are no restrictions on the algebraic curve, that means,
we support unbounded curves, vertical curves or segments, and isolated points.

The `Arr_algebraic_segment_traits_2<Coefficient>` class template
is a model of the `ArrangementTraits_2` concept (but not of the
`ArrangementLandmarkTraits_2` concept, so it is impossible
to use the landmark point-location strategy for arrangements of
algebraic curves).
The template argument `Coefficient` determines
the type of the scalar coefficients of the polynomial.
Currently supported types are `leda_integer`, `CORE::BigInt`,
and any instance of `Sqrt_extension<A,B>`
instantiated with one of the integral types above.

The traits class defines a type `Curve_2` for algebraic curves.
Such a type can be constructed by the `Construct_curve_2` functor,
which accepts an instance of `Polynomial_2` as an argument.
This polynomial type is also available by the traits class
and constitutes a valid model
of the concept `Polynomial_d` with two variables (see ??).

\cgalFigureBegin{arr_figex_alg_curves,algebraic_curves.png}
An arrangement of algebraic curves of degrees \f$ 1\f$, \f$ 2\f$, \f$ 3\f$, and \f$ 6\f$, as constructed in `algebraic_curves.cpp`.
\cgalFigureEnd

The following examples computes the arrangement induced by the four curves
in \cgalFigureRef{arr_figex_alg_curves}

\cgalExample{Arrangement_on_surface_2/algebraic_curves.cpp}

We first give a precise definition of segments of algebraic curves.
A point \f$ p\f$ on a curve \f$ C_f\subset\mathbb{R}^2\f$
(with \f$ f\f$ its defining equation) is called
<I>semi-regular</I>, if locally around \f$ p\f$, \f$ C_f\f$ can be written as
a function graph of some continuous function in \f$ x\f$ or in \f$ y\f$
(we also say that \f$ p\f$ is parameterizable in \f$ x\f$ or \f$ y\f$, respectively).
The only two cases of non-semi-regular points are isolated points, and
self-intersections.
A <I>segment</I> of a curve is a closed and continuous point set
such that each interior point is semi-regular.
It follows that a weakly \f$ x\f$-monotone segment is either a completely vertical
segment, or a segment whose interior points are all parameterizable in \f$ x\f$.

The traits class allows to construct weakly \f$ x\f$-monotone segments of a curve
using the `Construct_x_monotone_segment_2` functor.
The `X_monotone_curve_2` type of the traits class represents
weakly \f$ x\f$-monotone segments of a curve; however,
segments may need to be further subdivided into several (sub-)segments,
for technical reasons. Therefore, `Construct_x_monotone_segment_2`
constructs a sequence of `X_monotone_curve_2` objects, whose union
represents the weakly \f$ x\f$-monotone segment that was queried.
We call a segment <I>terminal</I> if it can be represented
by the type `X_monotone_curve_2`.

\cgalAdvancedBegin
The subdivision of segments is due to the internal representation of
\f$ x\f$-monotone segments, which is based on a vertical decomposition.
We assume the defining polynomial \f$ f\f$ of the curve \f$ C\f$
to be <I>square-free</I>, that means, it contains no divisor \f$ g^2\f$ of total
degree greater than zero. We define a <I>(complex) critical point</I>
\f$ p\in\mathbb{C}^2\f$ by
\f[ f(p)=0=\frac{\partial f}{\partial y}(p). \f]
An \f$ x\f$-coordinate \f$ \alpha\in\mathbb{R}\f$ is <I>critical</I>
if either some critical point has \f$ x\f$-coordinate \f$ \alpha\f$,
or if the leading coefficient of \f$ f\f$, considered as a polynomial in \f$ y\f$,
vanishes. In particular, vertical lines of and isolated point of \f$ C\f$
can only take place at critical \f$ x\f$-coordinates.
Between two consecutive critical \f$ x\f$-coordinates, the curve decomposes
into a finite number of \f$ x\f$-monotone segments (the same is true on the left
of the leftmost, and on the right of the rightmost critical \f$ x\f$-coordinate).
The type `X_monotone_curve_2` is only able to represent such segments
(and sub-segments of them). See \cgalFigureRef{arr_figcylindrical_decomposition}
for an example of a decomposition into terminal segments. Formally,
a terminal segment is a weakly \f$ x\f$-monotone segment that is either vertical, or
its \f$ x\f$-range contains no critical point in its interior.
\cgalAdvancedEnd

\cgalFigureBegin{arr_figcylindrical_decomposition,cylindrical_decomposition.png}
The critical \f$ x\f$-coordinates of an algebraic curve (dashed lines), and its decomposition into terminal segments (in different colors). The segment from \f$ p\f$ to \f$ q\f$ consists of the union of three terminal segments.
\cgalFigureEnd


Coordinates of points are represented by the type `Algebraic_real_1`,
which is defined in the traits class.
This type is taken from a model of the `AlgebraicKernel_1` concept,
which is also available by the type `Algebraic_kernel_1`.
One can use this model to create algebraic numbers as roots of univariate
polynomials, and process them, for instance,
compare them, or approximate them to any precision. See the documentation
of `AlgebraicKernel_1` for more information.
One can construct an object of type `Point_2` by a triple
(\f$ x_0\f$,cv,i), which means that the \f$ i\f$-th point (counted from below)
in the fiber of cv at the \f$ x\f$-coordinate \f$ x_0\f$ is constructed.
This is also how points are presented internally.
In the example displayed in \cgalFigureRef{arr_figcylindrical_decomposition},
if \f$ x_1\f$ denotes the \f$ x\f$-coordinate of \f$ p\f$, and \f$ cv\f$ represents the algebraic
curve, then \f$ p\f$ could be represented by \f$ (x_1,cv,3)\f$. If \f$ x_2\f$
is the \f$ x\f$-coordinate of \f$ q\f$,
then \f$ (x_2,cv,1)\f$ is a valid representation of \f$ q\f$.
Although the \f$ y\f$-coordinate of an object of type `Point_2` can be queried,
we recommend to be careful with that option, since computing an explicit
representation of the \f$ y\f$-coordinate as an `Algebraic_real_1` object
can become rather expensive.

\cgalFigureBegin{arr_figex_alg_segments,algebraic_segments.png}
An arrangement of algebraic segments (solid lines), as constructed in `algebraic_segments.cpp`. The supporting curves are drawn in dashed lines.
\cgalFigureEnd

The following code exemplifies various methods to construct
algebraic segments. The computed arrangement is displayed in
\cgalFigureRef{arr_figex_alg_segments}.

\cgalExample{Arrangement_on_surface_2/algebraic_segments.cpp}

\subsection arr_ssecmeta_tr Traits-Class Decorators

Geometric traits-class decorators allow you to attach auxiliary
data to curves and to points. The data is automatically manipulated
by the decorators and distributed to the constructed geometric entities.
Note that additional information can alternatively be maintained by extending
the vertex, halfedge, or face types provided by the \sc{Dcel} class used
by the arrangement; see the details in Section \ref arr_secex_dcel.

The arrangement package includes a generic traits-class decorator
template named
`Arr_curve_data_traits_2<BaseTraits, XMonotoneCurveData, Merge, CurveData, Convert>`.
This decorator is used to attach a data field to curves and to
\f$ x\f$-monotone curves. It is parameterized by a base-traits class, which is
one of the geometric traits classes described in the previous subsections, or
a user-defined traits class. The curve-data decorator derives itself from the
base-traits class, and in particular inherits its `Point_2` type.
In addition:
<UL>
<LI>`Curve_2` is derived from the basic `BaseTraits::Curve_2`
class, extending it by an extra field of type `CurveData`.
<LI>`X_monotone_curve_2` is derived from the basic
`BaseTraits::X_monotone_curve_2` class, extending it by an extra field of
type `XMonotoneCurveData`.
</UL>
Note that the `Curve_2` and `X_monotone_curve_2` are not
the same, even if the `BaseTraits::Curve_2` and
`BaseTraits::X_monotone_curve_2` are (as in the case of the
segment-traits class for example). The extended curve types support the
additional methods `data()` and `set_data()` for
accessing and modifying the data field.

You can create an extended curve (or an extended \f$ x\f$-monotone curve)
from a basic curve and a curve-data object. When curves are
inserted into an arrangement, they may be split, and the
decorator handles their data fields automatically:
<UL>
<LI>When a curve is subdivided into \f$ x\f$-monotone subcurves, its
data field of type `CurveData` is converted to an `XMonotoneCurveData`
object \f$ d\f$ using the `Convert` functor. The object \f$ d\f$ is automatically
associated with each of the resulting \f$ x\f$-monotone subcurves.

Note that by default, the `CurveData` type is identical to the
`XMonotoneCurveData` type (and the conversion functor `Convert`
is trivially defined). Thus, the data field associated with the original
curve is just duplicated and stored with the \f$ x\f$-monotone subcurves.
<LI>When an \f$ x\f$-monotone curve is split into two, the decorator
class automatically copies its data field to both resulting subcurves.
<LI>When intersecting two \f$ x\f$-monotone curves \f$ c_1\f$ and \f$ c_2\f$, the
result may include overlapping sections, represented as
\f$ x\f$-monotone curves. In this case the data fields of \f$ c_1\f$ and \f$ c_2\f$
are merged into a single `XMonotoneCurveData` object,
using the `Merge` functor, which is supplied as a
parameter to the traits class-template. The resulting object is
assigned to the data field of the overlapping subcurves.
<LI>Merging two \f$ x\f$-monotone curves is allowed only when (i) the two
curves are geometrically mergeable - that is, the base-traits class
allows to merge them - and (ii) the two curves store the same data field.
</UL>

The `Arr_consolidated_curve_data_traits_2<BaseTraits, Data>` decorator
specializes the generic curve-data decorator. It extends the basic
`BaseTraits::Curve_2` by a single `Data` field, and the basic
`BaseTraits::X_monotone_curve_2` with a <I>set</I> of (distinct) data
objects. The `Data` type is required to support the equality operator,
used to ensure that each set contains only distinct data objects with no
duplicates.
When a curve with a data field \f$ d\f$ is subdivided into \f$ x\f$-monotone subcurves,
each subcurve is associated with a set \f$ S = \{ d \}\f$. In case of an overlap
between two \f$ x\f$-monotone curves \f$ c_1\f$ and \f$ c_2\f$ with associated data sets
\f$ S_1\f$ and \f$ S_2\f$, respectively, the overlapping subcurve is associated with
the consolidated set \f$ S_1 \cup S_2\f$.

\subsection Arrangement_on_surface_2Examples Examples

\cgalFigureBegin{arr_figex_17,ex_17.png}
An arrangement of six red and blue segments, as constructed in `consolidated_curve_data.cpp`. Disks correspond to red-blue intersection points, while circles mark the endpoints of red-blue overlaps.
\cgalFigureEnd

In the following example, we use `Arr_segment_traits_2` as our
base-traits class, attaching an additional <I>color</I> field to
the segments using the consolidated curve-data traits class. A
color may be either <I>blue</I> or <I>red</I>. Having constructed
the arrangement of colored segments, as depicted in
\cgalFigureRef{arr_figex_17}, we detect the vertices that have incident
edges mapped to both blue and red segments. Thus, they correspond
to red-blue intersection points. We also locate the edge that
corresponds to overlaps between red and blue line segments:

\cgalExample{Arrangement_on_surface_2/consolidated_curve_data.cpp}

\cgalFigureBegin{arr_figex_18,ex_18.png}
An arrangement of four polylines, named A-D, as constructed in `generic_curve_data.cpp`.
\cgalFigureEnd

In the following example, we use `Arr_polyline_traits_2` as
our base-traits class, attaching an additional <I>name</I> field to
each polyline using the generic curve-data traits class. In case of
overlaps, we simply concatenate the names of the overlapping
polylines. Also notice how we replace the curve associated with
the edges that correspond to overlapping polylines with
geometrically equivalent curves, but with a different data fields:

\cgalExample{Arrangement_on_surface_2/generic_curve_data.cpp}

The third example we give in this section is based on `dual_lines.cpp`
given in Section \ref arr_ssecunb_global. It constructs the arrangement
of the dual lines for a set of point given in an input file (by default we
use `coll_points.dat`, which contains \f$ 50\f$ points randomly selected
on the grid \f$ [-100,100]\times[-100,100]\f$; the file contains two distinct
triplets of collinear points). Here we use the generic curve-data
decorator to attach the index of the primal point to each of the lines.
Doing so, we can go over the incident edges of each vertex whose degree is
greater than \f$ 4\f$ and report the subsets collinear points (if we have a vertex
of degree \f$ d\f$, we actually need to go over \f$ \frac{d}{2}\f$ edges, as each
incident line contributes exactly \f$ 2\f$ edges). Note that in this case the
dual line cannot overlap, so we use a dummy merge functor to instantiate
the curve-data traits:

\cgalExample{Arrangement_on_surface_2/dual_with_data.cpp}

\section arr_secnotif The Notification Mechanism

For some applications it is essential to know exactly what
happens inside a specific arrangement-instance. For example, when
a new curve is inserted into an arrangement, it might be desired to keep
track of the faces that are split due to this insertion operation.
Other important examples are the point-location strategies that
require auxiliary data-structures (see Section \ref arr_ssecpl),
which must be notified on various local changes in the arrangement,
in order to keep their data structures up-to-date. The arrangement
package offers a mechanism that uses <I>observers</I>
(see \cgalCite{cgal:ghjv-dpero-95}) that can be
attached to an arrangement instance and receive notifications
about the changes this arrangement goes through.

The `Arr_observer<Arrangement>` class-template is
parameterized with an arrangement class. It stores a pointer to an
arrangement object, and is capable of receiving notifications <I>just before</I> a structural change occurs in the arrangement and
<I>immediately after</I> such a change takes place.
`Arr_observer` serves as a base class for other observer
classes and defines a set of virtual notification functions,
with default empty implementations.

The set of functions can be divided into three categories, as
follows:
<OL>
<LI>Notifiers of changes that affect the entire topological structure
of the arrangement. This category consists of two pairs that
notify the observer of the following changes:
<UL>
<LI>The arrangement is cleared.
<LI>The arrangement is assigned with the contents of another
arrangement.
</UL>
<LI>Pairs of notifiers of a local change that occurs in the
topological structure. Most notifier functions belong to this
category. The relevant local changes include:
<UL>
<LI>A new vertex is constructed and associated with a point.
<LI>An edge\cgalFootnote{The term "edge" refers here to a pair of twin half-edges.} is constructed and associated with an \f$ x\f$-monotone
curve.
<LI>An edge is split into two edges.
<LI>An existing face is split into two faces, as a consequence of the
insertion of a new edge.
<LI>A hole is created in the interior of a face.
<LI>Two holes are merged to form a single hole, as a consequence of the
insertion of a new edge.
<LI>A hole is moved from one face to another, as a consequence of
a face split.
<LI>Two edges are merged into one edge.
<LI>Two faces are merged into one face, as a consequence of the
removal of an edge that used to separate them.
<LI>One hole is split into two, as a consequence of the deletion of an
edge that used to connect the two components.
<LI>A vertex is removed.
<LI>An edge is removed.
<LI>A hole is deleted from the interior of a face.
</UL>
<LI>Notifiers about a change applied by a free (global) function.
This category consists of a single pair of notifiers, namely
`before_global_change()` and `after_global_change()`. Neither of
these functions is invoked by methods of the `Arrangement_2` class.
Instead, they are called by the free functions themselves. It is implied
that no point-location queries (or any other queries for that matter)
are issued between the calls to the notification functions above.
</OL>
See the Reference Manual for a detailed specification of the
`Arr_observer` class along with the exact prototypes of all
notification functions.

Each arrangement object stores a (possibly empty) list of pointers to
`Arr_observer` objects, and whenever one of the structural
changes listed in the first two categories above is about to take
place, the arrangement object performs a <I>forward</I> traversal
on this list and invokes the appropriate function of each
observer. After the change takes place the observer list is
traversed in a <I>backward</I> manner (from tail to head), and the
appropriate notification function is invoked for each observer.
This allows the nesting of observer objects.

Concrete arrangement-observer classes should inherit from
`Arr_observer`. When an observer is constructed, it is attached to
a valid arrangement supplied to the observed constructor, or alternatively
the observer can be attached to the arrangement at a later time.
When this happens, the observer instance inserts itself into the
observer list of the associated arrangement and starts receiving
notifications whenever this arrangement changes thereafter. Naturally,
the observer object unregisters itself by removing itself from
this list just before it is destroyed.

The trapezoidal RIC and the landmark point-location strategies
both use observers to keep their auxiliary data structures
up-to-date. Besides them, users can define their own observer
classes, by inheriting from the base observer class and overriding
the relevant notification functions, as required by their
applications.

\cgalFigureBegin{arr_figex_19,ex_19.png}
An arrangement of five line segments, as constructed in `observer.cpp`. The halfedge \f$ e_v\f$ (dashed) is eventually removed, so that the final arrangement consists of four faces (one unbounded and three bounded ones).
\cgalFigureEnd

The following example shows how to define and use an observer
class. The observer in the example keeps track of the arrangement
faces, and prints a message whenever a face is split into two due
to the insertion of an edge, and whenever two faces merge into one
due to the removal of an edge. The layout of the arrangement is
depicted in \cgalFigureRef{arr_figex_19} :

\cgalExample{Arrangement_on_surface_2/observer.cpp}

Observers are especially useful when the \sc{Dcel} records are
extended and store additional data, as they help updating this
data on-line. See Section \ref arr_secex_dcel for more details
and examples.

\section arr_secex_dcel Extending the DCEL

For many applications of the arrangement package it is necessary to
store additional information (perhaps of non-geometric nature) with
the arrangement cells. As vertices are associated with `Point_2`
objects and edges (halfedge pairs) are associated with
`X_monotone_curve_2` objects, both defined by the traits class,
it is possible to extend the traits-class type by using a traits-class
decorator, as explained in Section \ref arr_ssecmeta_tr, which may
be a sufficient solution for some applications.
However, the \sc{Dcel} faces are not associated with any geometric object,
so it is impossible to extend them using a traits-class decorator.
Extending the \sc{Dcel} face records comes handy is such cases. As a matter
of fact, it is possible to conveniently extend all \sc{Dcel} records
(namely vertices, halfedges and faces), which can also be advantageous
for some applications.

All examples presented so far use the default `Arr_default_dcel<Traits>`.
This is done implicitly, as this class serves as a default parameter for
the `Arrangement_2` template. The default \sc{Dcel} class just associates
points with vertices and \f$ x\f$-monotone curves with halfedge, but nothing more.
In this section we show how to use alternative \sc{Dcel} types to extend the
desired \sc{Dcel} records.

\subsection arr_ssecex_dcel_face Extending the DCEL Faces

The `Arr_face_extended_dcel<Traits, FaceData>` class-template
is used to associate auxiliary data field of type `FaceData` to
each face record in the \sc{Dcel}.

When an `Arrangement_2` object is parameterized by this
\sc{Dcel} class, its nested `Face` type is extended with the access function
`data()` and with the modifier `set_data()`. Using these extra
functions it is straightforward to access and maintain the auxiliary
face-data field.

Note that the extra data fields must be maintained by the application
programmers. They may choose to construct their arrangement, and
only then go over the faces and attach the appropriate data fields to
the arrangement faces. However, in some cases the face data can only
be computed when the face is created (split from another face, or merged
with another face). In such cases one can use an arrangement observer
tailored for this task, which receives updates whenever a face is
modified and sets its data field accordingly.

\cgalFigureBegin{arr_figex_20,ex_20.png}
An arrangement of six line segments, as constructed in `face_extension.cpp` and `dcel_extension.cpp` (in `dcel_extension.cpp` we treat the segments as directed, so they are drawn as arrows directed from the source to the target). The indices associated with the halfedges in `face_extension.cpp` are shown in brackets.
\cgalFigureEnd


The next example constructs an arrangement that contains seven bounded
faces induced by six line segments (see \cgalFigureRef{arr_figex_20}). An
observer gets notified each time a new face \f$ f\f$ is created and it associates
\f$ f\f$ with a running index, (where the index of the unbounded face
is 0). As a result, the faces are numbered according to their creation
order, as one can easily verify by examining the insertion order of the
segments:\cgalFootnote{For simplicity, the particular observer used must be attached to an empty arrangement. It is not difficult however to modify the program to handle the general case of attaching a similar observer to a non-empty arrangement.}

\cgalExample{Arrangement_on_surface_2/face_extension.cpp}

\subsection arr_ssecex_dcel_all Extending All DCEL Records

The `Arr_extended_dcel<Traits, VertexData, HalfedgeData, FaceData>`
class-template is used to associate auxiliary data fields of
types `VertexData` `HalfedgeData`, and `FaceData` to
each \sc{Dcel} vertex, halfedge, and face record types, respectively.

When an `Arrangement_2` object is injected with this
\sc{Dcel} class, each one of its nested `Vertex`, `Halfedge` and
`Face` classes is extended by the access function `data()`
and by the modifier `set_data()`.

The next example shows how to use a \sc{Dcel} with extended vertex,
halfedge, and face records. In this example each vertex is associated
with a color, which may be blue, red, or white, depending on whether the
vertex is isolated, represents a segment endpoint, or whether it
represents an intersection point. Each halfedge is associated with
Boolean flag indicating whether its direction is the same as the
direction of its associated segment (in this example segments are
treated as directed objects). Each face is also extended to store the
size of its outer boundary.

The constructed arrangement, depicted in \cgalFigureRef{arr_figex_20}, is
similar to the arrangement constructed in the previous example.
Note that all auxiliary data fields are set during the construction phase.
Also note that the data fields are properly maintained when the arrangement
is copied to another arrangement instance:

\cgalExample{Arrangement_on_surface_2/dcel_extension.cpp}

\cgalAdvancedBegin
The various \sc{Dcel} classes presented in this section are perfectly
sufficient for most applications based on the arrangement package.
However, users may also use their own implementation of a \sc{Dcel} class
to instantiate the `Arrangement_2` class-template, in case they need
special functionality from their \sc{Dcel}. Such a class must be a model of the
concept `ArrangementDcel`, whose exact specification is listed in the
Reference Manual.
\cgalAdvancedEnd

\section arr_secoverlay Overlaying Arrangements

Assume that we are given two geographic maps represented as
arrangements with some data objects attached to their faces,
representing some geographic information - for example, a map of
the annual precipitation in some country and a map of the vegetation
in the same country. It is interesting to overlay the two maps to
locate, for example, the regions where there is a pine forest and
the annual precipitation is between 1000mm and 1500mm.

Computing the overlay of two planar arrangement is also useful for
supporting Boolean set operations on polygons (or generalized polygons,
see, e.g., \cgalCite{cgal:behhms-cbcab-02}).

The function `overlay (arr_a, arr_b, ovl_arr, ovl_traits)` accepts
two input arrangement instances `arr_a` and `arr_b`, and constructs
their overlay instance `ovl_arr`. All three arrangements must use the
same geometric primitives. More precisely, let `arr_a` be of
type `Arrangement_2<Traits_A,Dcel_A>`, `arr_b` be of type
`Arrangement_2<Traits_B,Dcel_B>` and the resulting `ovl_arr` be of type
`Arrangement_2<Traits_R,Dcel_R>`. All types nested in geometry
traits `Traits_A`, e.g., `Point_2` and
`X_monotone_curve_2`, must be convertible to the corresponding
types nested in geometry traits `Traits_R`. The same holds for all
types nested in geometry traits `Traits_B`.
The `ovl_traits` parameter is
an instance of an <I>overlay traits-class</I>, which enables the creation of
`Dcel_R` records in the overlaid arrangement from the \sc{Dcel} features
of `arr_a` and `arr_b` that they correspond to.

In principle, we distinguish between three levels of overlay:
<DL>
<DT><B>Simple overlay:</B><DD>
An overlay of two arrangements that store no additional data
with their \sc{Dcel} records. That is, they are defined using the default
\sc{Dcel} class `Arr_default_dcel`. Typically, the overlaid
arrangement in this case stores no extra data with its \sc{Dcel} records as
well (or if it does, the additional data fields cannot be computed by
the overlay operation), so by overlaying the two arrangement we just
compute the arrangement of all curves that induce `arr_a` and `arr_b`.
Note that the same result can be obtained using the standard insertion
operations, but users may choose to use overlay computation in order to
achieve better running times.

The `Arr_default_overlay_traits` class should be used as an overlay
traits-class for such simple overlay operations.
<DT><B>Face overlay:</B><DD>
An overlay of two arrangements that store additional data
fields with their faces (e.g., the geographic-map example
given in the beginning of this section). The resulting overlaid arrangement
typically also stores extraneous data fields with its faces, where the
data field that is attached to an overlaid face can be computed from the
data fields of the two faces (in `arr_a` and `arr_b`) that induce
the overlaid face.

The `Arr_face_overlay_traits` class should be used as an overlay
traits-class for face-overlay operations. It operates on arrangement, whose
\sc{Dcel} representation is based on the `Arr_face_extended_dcel`
class-template (see Section \ref arr_ssecex_dcel_face). The face-overlay
traits-class is parameterized by a functor that is capable of combining two
face-data fields of types `Dcel_A::Face_data` and
`Dcel_B::Face_data`, and computing the output `Dcel_R::Face_data`
object. The overlay traits-class uses this functor to properly construct
the overlaid faces.
<DT><B>Full overlay:</B><DD>
An overlay of two arrangements that store additional data
fields with all their \sc{Dcel} records. That is, their \sc{Dcel} classes
are instantiations of the `Arr_extended_dcel` class-template (see
Section \ref arr_ssecex_dcel_all), where the resulting arrangement
also extends it \sc{Dcel} records with data fields computed on the basis
of the overlapping \sc{Dcel} features of the two input arrangements.
</DL>

In the following subsections we give some examples for the simple and the
face-overlay operations and demonstrate how to use the auxiliary overlay
traits-classes. For the full overlay operations users need to implement
their specialized overlay traits-class, which models the `OverlayTraits`
concept. The details of this concept are given in the Reference Manual.

\subsection arr_ssecsimp_ovl Example for a Simple Overlay

\cgalFigureBegin{arr_figex_22,ex_22.png}
Overlaying two simple arrangements of line segments, as done in `overlay.cpp` and `ex_face_extension_overlay.cpp`. In `face_extension_overlay.cpp` the two bounded faces are considered as <I>marked</I>, and the octagonal face which is the intersection of the two marked faces is denoted by \f$ f_0\f$.
\cgalFigureEnd

The next program constructs two simple arrangements, as depicted in
\cgalFigureRef{arr_figex_22} and computes their overlay:

\cgalExample{Arrangement_on_surface_2/overlay.cpp}

\subsection arr_ssecface_ovl Examples for a Face Overlay

The following example shows how to compute the intersection of two polygons
using the `overlay()` function. It uses a face-extended \sc{Dcel} class
to define our arrangement class. The \sc{Dcel} extends each face with a Boolean
flag. A polygon is represented as a <I>marked</I> arrangement face, (whose
flag is set). The example uses a face-overlay traits class, instantiated with
a functor that simply performs a logical <I>and</I> operations on Boolean flags.
As a result, a face in the overlaid arrangement is marked only when it
corresponds to an overlapping region of two marked cells in the input
arrangements. Namely, it is part of the intersection of the two polygons.

The example computes the intersection between a square and a rhombus, (which is
actually also a square). The resulting polygon is an octagon, denoted
by \f$ f_0\f$ in \cgalFigureRef{arr_figex_22} :

\cgalExample{Arrangement_on_surface_2/face_extension_overlay.cpp}

The next example demonstrates the face overlay of two arrangements that
have unbounded faces as well. The first arrangement is formed by the two lines
\f$ y = x\f$ and \f$ y = -x\f$, that subdivide the plane into four unbounded faces,
denoted \f$ A\f$, \f$ B\f$, \f$ C\f$ and \f$ D\f$. The second arrangement comprises four line
segments that form a square-shaped face. When we overlay the two arrangements,
each of the four faces \f$ A\f$, \f$ B\f$, \f$ C\f$ and \f$ D\f$ is split into an unbounded
face (indexed 1) and a bounded face (indexed 2):

\cgalExample{Arrangement_on_surface_2/overlay_unbounded.cpp}

\section arr_secarr_with_hist Storing the Curve History

As stated at the beginning of this chapter (Section \ref arr_secintro),
when one constructs an arrangement induced by a set \f$ \cal C\f$ of arbitrary
planar curves, she or he constructs a collection \f$ \cal C''\f$ of \f$ x\f$-monotone
subcurves of \f$ \cal C\f$ that are pairwise disjoint in their interior, and these
subcurves are associated with the arrangement edges (more precisely, with the
\sc{Dcel} halfedges). Doing so, the connection between the originating input
curves and the arrangement edges is lost. This loss might be acceptable for
some applications. However, in many practical cases it is important to
determine the input curves that give rise to the final subcurves.

The `Arrangement_with_history_2<Traits,Dcel>` class-template extends
the `Arrangement_2` class by keeping an additional container of input
curves representing \f$ \cal C\f$, and by maintaining a cross-mapping between these
curves and the arrangement edges they induce. The traits class that is
used for instantiating the template should be a model of the
`ArrangementTraits_2` concept (see Section \ref arr_sssecinsert_gen).
That is, it should define the `Curve_2` type (and not just the
`X_monotone_curve_2` type). The `Dcel` parameter should model the
`ArrangementDcel` concept. Users can use the default \sc{Dcel} class or
an extended \sc{Dcel} class according to their needs.

\subsection arr_ssecarrwh_traverse Traversing an Arrangement with History

The `Arrangement_with_history_2` class extends the `Arrangement_2`
class, thus all the iterator and circulator types that are defined by the
arrangement class are also available in `Arrangement_with_history_2`.
The reader is referred to Section \ref arr_ssectraverse for a comprehensive
review of these functions.

As mentioned above, the `Arrangement_with_history_2` class maintains
a container of input curves, which can be accessed using curve handles.
The member function `number_of_curves()` returns the number of input
curves stored in the container, while `curves_begin()` and
`curves_end()` return `Arrangement_with_history_2::Curve_iterator`
objects that define the valid range of curves that induce the arrangement.
The value type of this iterator is `Curve_2`. Moreover, the curve-iterator
type is equivalent to `Arrangement_with_history_2::Curve_handle`, which
is used for accessing the stored curves. Conveniently, the corresponding
constant-iterator and constant-handle types are also defined.

As mentioned in the previous paragraph, a `Curve_handle` object `ch`
serves as a pointer to a curve stored in an arrangement-with-history instance
`arr`. Using this handle, it is possible to obtain the number of
arrangement edges this curve induces by calling
`arr.number_of_induced_edges(ch)`. The functions
`arr.induced_edges_begin(ch)` and
`arr.induced_edges_end(ch)` return iterators of type
`Arrangement_with_history_2::Induced_edges_iterator` that define the
valid range of edges induced by `ch`. The value type of these iterators
is `Halfedge_handle`. It is thus possible to traverse all arrangement
edges induced by an input curve.

It is also important to be able to perform the inverse mapping. Given an
arrangement edge, we would like to be able to determine which input curve
induces it. In case the edge represents an overlap of several curves, we
should be able to trace all input curves that overlap over this edge.
The `Arrangement_with_history_2` class is extended by several member
functions that enable such an inverse mapping. Given a halfedge handle `e`
in an arrangement with history `arr`, then
`arr.number_of_originating_curves(e)` returns the number of curves that
induce the edge (which should be 1 in non-degenerate cases, and 2 or more
in case of overlaps), while `arr.originating_curves_begin(e)` and
`arr.originating_curves_end(e)` return
`Arrangement_with_history_2::Originating_curve_iterator` objects that
define the range of curves that induce `e`. The value type of these
iterator is `Curve_2`.

It is possible to overlay two `Arrangement_with_history_2` instances
instantiated by the same traits class. In this case, the resulting
arrangement will store a consolidated container of input curves, and
automatically preserve the cross-mapping between the arrangement edges
and the consolidated curve set. Users can employ an overlay-traits class
to maintain any type of auxiliary data stored with the \sc{Dcel} features
(see Section \ref arr_secoverlay).

\subsection arr_ssecmodif_traverse Modifying an Arrangement with History

As the `Arrangement_with_history_2` class extends the `Arrangement_2`
class, it inherits the fundamental modification operations, such as
`assign()` and `clear()`, from it. The vertex-manipulation functions
are also inherited and supported (see Sections \ref arr_sssecmf_iso_verts
and \ref arr_sssecinsert_point for the details). However, there are some
fundamental differences between the interfaces of the two classes, which we
highlight in this subsection.

The most significant difference between the arrangement-with-history class
and the basic arrangement class is the way they handle their input curves.
`Arrangement_with_history_2` always stores the `Curve_2` objects
that induce it, thus it is impossible to insert \f$ x\f$-monotone curves into
an arrangement with history. The free `insert_non_intersecting_curve()`
and `insert()` that receives \f$ x\f$-monotone curve (as well as
their aggregated versions) are therefore not available for
arrangement-with-history instances and only the free
`insert()` and `insert()` functions that receive
`Curve_2` (the incremental insertion function and the aggregated
insertion function) are supported - see also
Section \ref arr_sssecinsert_gen. Notice however that while the
incremental insertion function `insert(arr,c)` for an
`Arrangement_2` object `arr` does not have a return value, the
corresponding arrangement-with-history function returns a
`Curve_handle` to the inserted curve.

As we are able to keep track of all edges induced by an input curve, we also
provide a free function that removes a curve from an arrangement. By calling
`remove(arr,ch)`, where `ch` is a valid curve handle, the given curve
is deleted from the curve container, and all edges induced solely by
this curve (i.e., excluding overlapping edges) are removed from the
arrangement. The function returns the number of edges that have been removed.

In some cases, users may need to operate directly on the arrangement edges.
We first mention that the specialized insertion functions (see
Section \ref arr_sssecmf_insert_cv) are not supported, as they accept
\f$ x\f$-monotone curves. Insertion can only be performed via the free
insertion-functions. The other edge-manipulation functions
(see Section \ref arr_sssecmf_halfedges) are however available, but have
a different interface that does not use \f$ x\f$-monotone curves:
<UL>
<LI>Invoking `split_edge(e,p)` splits the edge `e` at a given point
`p` that lies in its interior.
<LI>Invoking `merge_edge(e1,e2)` merges the two given edges. There is
a precondition that `e1` and `e2` shared a common end-vertex of degree
2, and that the \f$ x\f$-monotone subcurves associated with these edges are
mergeable.
<LI>It is possible to remove an edge by simply invoking
`remove_edge(e)`.
</UL>
In all cases, the maintenance of cross-pointers for the appropriate input
curves will be done automatically.

It should be noted that it is possible to attach observers to an
arrangement-with-history instance in order to get detailed notifications of
the changes the arrangements undergoes (see Section \ref arr_secnotif for
the details).

\subsection arr_ssecarr_hist_ex Examples

\cgalFigureBegin{arr_figex_24,ex_24.png}
An arrangement with history as constructed in `curve_history.cpp`. Note that \f$ s_1\f$ and \f$ s_3\f$ overlap over two edges. The point-location query points are drawn as lightly shaded dots.
\cgalFigureEnd

In the following example we construct a simple arrangement of six line
segments, as depicted in \cgalFigureRef{arr_figex_24}, while maintaining
the curve history. The example demonstrates the usage of the special
traversal functions. It also shows how to issue point-location queries
on the resulting arrangement, using the auxiliary function
`locate_point()` defined in the header file
`point_location_utils.h`; see also Section \ref arr_ssecpl.

\cgalExample{Arrangement_on_surface_2/curve_history.cpp}

\cgalFigureBegin{arr_figex_25,ex_25.png}
An arrangement with history of nine circle as constructed in `edge_manipulation_curve_history.cpp`. Note the vertical tangency points of \f$ C_0\f$, marked as dark dots, which subdivide this circle into an upper half and a lower half, each consists of 9 edges. The large circle \f$ C_0\f$ is eventually removed from the arrangement, with all 18 edges it induces.
\cgalFigureEnd

The following example demonstrates the usage of the free `remove()`
function. We construct an arrangement of nine circles, while keeping a handle
to each inserted circle. We then remove the large circle \f$ C_0\f$, which induces
\f$ 18\f$ edges, as depicted in \cgalFigureRef{arr_figex_25}. The example also shows
how to use the `split_edge()` and `merge_edge()` functions when
operating on an arrangement-with-history instance:

\cgalExample{Arrangement_on_surface_2/edge_manipulation_curve_history.cpp}

\section arr_secio Input/Output Streams

In some cases, one would like to save an arrangement object
constructed by some application, so that later on it can be
restored. In other cases one would like to create nice drawings that
represent arrangements constructed by some application. These
drawings can be hard printed or displayed on a computer screen.

\subsection arr_ssecio_stream Input/Output Stream

Consider an arrangement that represents a very complicated geographical
map, and assume that there are various applications that need to answer
point-location queries on this map. Naturally, you can store the set of
curves that induces the arrangement, but this implies that you would need
to construct the arrangement from scratch each time you need to reuse it.
A more efficient solution is to write the arrangement to a file in a format
that other applications can read.

This package provides an <I>inserter</I> (the `<<` operator) and an
<I>extractor</I> (the `>>` operator) for the
`Arrangement_2<Traits,Dcel>` class that inserts and an arrangement
object into an output stream and extracts an arrangement object from an
input stream respectively. The arrangement is written using a simple
predefined ASCII format that encodes the arrangement topology, as well
as all geometric entities associated with vertices and edges.

The ability to use the input/output operators, requires that the
`Point_2` type and the `X_monotone_curve_2` type defined by the
traits class both support the `<<` and `>>` operators. The
`Arr_conic_traits_2` class (see Section \ref arr_ssectr_conic), the
`Arr_rational_function_traits_2` class (see Section \ref arr_ssectr_ratfunc),
and the `Arr_linear_traits_2` class (see Section \ref arr_ssectr_segs)
currently do not provide these operators for the geometric types they define.
Thus, only arrangements of line segments or of polylines can be written or
read.

The following example constructs the arrangement depicted in
\cgalFigureRef{arr_figex_5} and writes it to an output file. It also
demonstrates how to re-read the arrangement from a file:

\cgalExample{Arrangement_on_surface_2/io.cpp}

\subsection arr_ssecarr_io_aux_data Arrangements with Auxiliary Data

\cgalAdvancedBegin
The inserter and extractor both ignore any auxiliary data stored with
the arrangement features. Thus, they are ideal for arrangements
instantiated using the `Arr_default_dcel` class.
However, as explained in Section \ref arr_secex_dcel, one can easily
extend the arrangement faces by using the `Arr_face_extended_dcel`
template, or extend all \sc{Dcel} records by using the `Arr_extended_dcel`
template. In such cases, it might be crucial that the auxiliary data fields
are written to the file and read from there.

The arrangement package includes the free functions
`write(arr, os, formatter)`, which writes the arrangement `arr`
to an output stream `os`, and `read(arr, os, formatter)`, which
reads the arrangement `arr` from an input stream `is`. Both
operations are performed using a `formatter` object, which defines
the I/O format. The package contains three formatter classes:
<UL>
<LI>`Arr_text_formatter<Arrangement>` defines a simple textual
I/O format for the arrangement topology and geometry, disregarding any
auxiliary data that may be associated with the arrangement features.
This is the default formatter used by the arrangement inserter and the
arrangement extractor, as defined above.
<LI>`Arr_face_extended_text_formatter<Arrangement>` operates on
arrangements whose \sc{Dcel} representation is based on the
`Arr_face_extended_dcel<Traits,FaceData>` class (see
Section \ref arr_ssecex_dcel_face). It supports reading and writing
the auxiliary data objects stored with the arrangement faces provided
that the `FaceData` class supports an inserter and an extractor.
<LI>`Arr_extended_dcel_text_formatter<Arrangement>` operates on
arrangements whose \sc{Dcel} representation is based on the
`Arr_extended_dcel<Traits,VertexData,HalfedgeData,FaceData>` class
(see Section \ref arr_ssecex_dcel_all). It supports reading and writing
the auxiliary data objects stored with the arrangement vertices, edges
and faces, provided that the `VertexData`, `HalfedgeData` and
`FaceData` classed all have inserters and extractors.
</UL>

The following example constructs the same arrangement as the
example `dcel_extension` does
(see Section \ref arr_ssecex_dcel_all), depicted in
\cgalFigureRef{arr_figex_20}, and writes it to an output file. It also
demonstrates how to re-read the arrangement from a file:

\cgalExample{Arrangement_on_surface_2/dcel_extension_io.cpp}

You may develop your own own formatter classes - models of the
`ArrangementInputFormatter` and `ArrangementOutputFormatter`
concepts, as defined in the Reference Manual.
Doing so, you can define other I/O formats, such as an XML-based
format or a binary format.
\cgalAdvancedEnd

\subsection arr_ssecarr_io_hist Arrangements with Curve History

Section \ref arr_secarr_with_hist introduces the
`Arrangement_with_history_2<Traits,Dcel>` class, which saves the
set of curves inducing an arrangement and maintains the relations between
these curves and the edges they induce. Naturally, when reading or writing
an arrangement-with-history instance we would like this information to be
saved to the output stream or restored from the input stream alongside
with the basic arrangement structure.

The arrangement package supplies an inserter and an extractor for the
`Arrangement_with_history_2<Traits,Dcel>` class. The arrangement is
represented using a simple predefined ASCII format. An object of the
`Arrangement_with_history_2<Traits,Dcel>` type can be saved and
restored, as long as the `Curve_2` type defined by the traits
class - as well as the `Point_2` type and the `X_monotone_curve_2`
types - support the `<<` and`>>` operators.

The following example constructs the same arrangement as example
`curve_history` does
(see Section \ref arr_ssecarr_hist_ex), depicted in
\cgalFigureRef{arr_figex_24}, and writes it to an output file. It also
demonstrates how to re-read the arrangement-with-history from a file:

\cgalExample{Arrangement_on_surface_2/io_curve_history.cpp}

\cgalAdvancedBegin
The arrangement package also includes the free functions
`write(arr, os, formatter)` and `read(arr, os, formatter)` that
operate on a given arrangement-with-history instance `arr`.
Both functions are parameterized by a `formatter` object, which define
the I/O format. The package contains a template called,
`Arr_with_hist_text_formatter<ArranagmentFormatter>`, which extends
an arrangement formatter class (see Section \ref arr_ssecarr_io_aux_data)
and defines a simple textual input/output format.
\cgalAdvancedEnd

\section arr_secbgl Adapting to Boost Graphs

<span class="textsc">Boost</span>\cgalFootnote{See also <span class="textsc">Boost</span>'s homepage at: <TT>www.boost.org</TT>.}
is a collection of portable \cpp libraries that extend the Standard Template Library (<span class="textsc">Stl</span>). The <span class="textsc">Boost</span> Graph Library (<span class="textsc">bgl</span>), which one of the libraries in the collection, offers an
extensive set of generic graph algorithms parameterized through templates.
As our arrangements are embedded as planar graphs, it is only
natural to extend the underlying data structure with the interface that the
<span class="textsc">bgl</span> expects, and gain the ability to perform the operations that the <span class="textsc">bgl</span> supports, such as shortest-path computation. This section describes how apply
the graph algorithms implemented in the <span class="textsc">bgl</span> to `Arrangement_2` instances.

An instance of `Arrangement_2` is adapted to a <span class="textsc">Boost</span> graph through the
provision of a set of free functions that operate on the arrangement features
and conform with the relevant BGL concepts. Besides the straightforward
adaptation, which associates a vertex with each \sc{Dcel} vertex and an edge
with each \sc{Dcel} halfedge, the package also offer a <I>dual</I> adaptor, which
associates a graph vertex with each \sc{Dcel} face, such that two vertices are
connected, iff there is a \sc{Dcel} halfedge that connects the two corresponding
faces.

\subsection arr_ssecbgl_primal The Primal Arrangement Representation

Arrangement instances are adapted to <span class="textsc">Boost</span> graphs by specializing the
\link BGLArgtGT `boost:graph_traits` \endlink template for `Arrangement_2` instances. The
graph-traits states the graph concepts that the arrangement class models
(see below) and defines the types required by these concepts.

In this specialization the `Arrangement_2` vertices correspond to the
graph vertices, where two vertices are adjacent if there is at least one
halfedge connecting them. More precisely, `Arrangement_2::Vertex_handle`
is the graph-vertex type, while `Arrangement_2::Halfedge_handle` is the
graph-edge type. As halfedges are directed, we consider the graph to be
directed as well. Moreover, as several interior-disjoint \f$ x\f$-monotone curves
(say circular arcs) may share two common endpoints, inducing an arrangement
with two vertices that are connected with several edges, we allow parallel
edges in our <span class="textsc">Boost</span> graph.

Given an `Arrangement_2` instance, we can efficiently traverse its
vertices and halfedges. Thus, the arrangement graph is a model of the concepts
`VertexListGraph` and `EdgeListGraph` introduced by the <span class="textsc">bgl</span>.
At the same time, we use an iterator adapter of the circulator over the
halfedges incident to a vertex (`Halfedge_around_vertex_circulator` - see
Section \ref arr_sssectr_vertex), so it is possible to go over the ingoing
and outgoing edges of a vertex in linear time. Thus, our arrangement graph
is a model of the concept `BidirectionalGraph` (this concept refines
`IncidenceGraph`, which requires only the traversal of outgoing edges).

It is important to notice that the vertex descriptors we use are
`Vertex_handle` objects and <I>not</I> vertex indices. However, in order
to gain more efficiency in most <span class="textsc">bgl</span> algorithm, it is better to have them
indexed \f$ 0, 1, \ldots, (n-1)\f$, where \f$ n\f$ is the number of vertices. We
therefore introduce the `Arr_vertex_index_map<Arrangement>` class-template,
which maintains a mapping of vertex handles to indices, as required by the
<span class="textsc">bgl</span>. An instance of this class must be attached to a valid arrangement
vertex when it is created. It uses the notification mechanism (see
Section \ref arr_secnotif) to automatically maintain the mapping of vertices
to indices, even when new vertices are inserted into the arrangement or
existing vertices are removed.

In most algorithm provided by the <span class="textsc">bgl</span>, the output is given by
<I>property maps</I>, such that each map entry corresponds to a vertex.
For example, when we compute the shortest paths from a given source vertex
\f$ s\f$ to all other vertices we can obtain a map of distances and a map of
predecessors - namely for each \f$ v\f$ vertex we have its distance from \f$ s\f$
and a descriptor of the vertex that precedes \f$ v\f$ in the shortest path from \f$ s\f$.

If the vertex descriptors are simply indices, boost supplies tools to
easily represent property maps using vectors.
`Arr_vertex_index_map<Arrangement>` class allows create such
indices, and together with `boost::vector_property_map<Type, IndexMap>`
allows for an efficient mapping of `Vertex_handle` objects to
properties of type `Type`. Note however that unlike the
`Arr_vertex_index_map` class, the vertex property-map class is not
kept synchronized with the number of vertices in the arrangement, so it
should not be reused in calls to <span class="textsc">bgl</span> functions in case the arrangement
is modified in between these calls.

\cgalFigureBegin{arr_figex_bgl,ex_bgl.png}
An arrangement of 7 line segments, as constructed by `bgl_primal_adapter.cpp` and `bgl_dual_adapter.cpp`. The breadth-first visit times for the arrangement faces, starting from the unbounded face \f$ f_0\f$, are shown is brackets.
\cgalFigureEnd

In the following example we construct an arrangement of 7 line segments,
as shown in \cgalFigureRef{arr_figex_bgl},
then use Dijkstra's shortest-paths algorithm from the <span class="textsc">bgl</span> to compute
the graph distance of all vertices from the leftmost vertex in the
arrangement \f$ v_0\f$. Note the usage of the `boost::vector_property_map<Type, IndexMap>` and
the `Arr_vertex_property_map` classes. The latter one, instantiated by
the type `double` is used to map vertices to their distances from \f$ v_0\f$.

\cgalExample{Arrangement_on_surface_2/bgl_primal_adapter.cpp}

\subsection arr_ssecbgl_dual The Dual Arrangement Representation

It is possible to give a dual graph representation for an arrangement instance,
such that each arrangement face corresponds to a graph vertex and two vertices
are adjacent iff the corresponding faces share a common edge on their
boundaries. This is done by specializing the
`boost:graph_traits` template for `Dual<Arrangement_2>` instances,
where `Dual<Arrangement_2>` is a template specialization that gives a
dual interpretation to an arrangement instance.

In dual representation, `Arrangement_2::Face_handle`
is the graph-vertex type, while `Arrangement_2::Halfedge_handle` is the
graph-edge type. We treat the graph edges as directed, such that a halfedge
`e` is directed from \f$ f_1\f$, which is its incident face, to \f$ f_2\f$, which
is the incident face of its twin halfedge. As two arrangement faces may
share more than a single edge on their boundary, we allow parallel
edges in our <span class="textsc">Boost</span> graph. As is the case in the primal graph, the dual
arrangement graph is also a model of the concepts `VertexListGraph`,
`EdgeListGraph` and `BidirectionalGraph` (thus also of
`IncidenceGraph`).

Since we use `Face_handle` objects as the vertex descriptors, we define
the `Arr_face_index_map<Arrangement>` class-template, which maintains an
efficient mapping of face handles to indices.
Like vertices, `boost::vector_property_map<Type, IndexMap>` can be
used for associating arbitrary data with the arrangement faces.

In the following example we construct the same arrangement as in
example `bgl_primal_adapter.cpp` (see \cgalFigureRef{arr_figex_bgl}),
and perform breadth-first search on the graph faces, starting from the
unbounded face. We extend the \sc{Dcel} faces
with an unsigned integer, marking the discover time of the face
using `boost` visitors and a property-map class that directly accesses
the extended data of the faces:

\cgalExample{Arrangement_on_surface_2/bgl_dual_adapter.cpp}

\section arr_sectips How To Speed Up Your Computation

Before the specific tips, we remind you that compiling programs with
debug flags disabled and with optimization flags enabled significantly
reduces the running time.

<OL>
<LI>When the curves to be inserted into an arrangement are \f$ x\f$-monotone
and pairwise disjoint in their interior to start with, then it is more
efficient (in running time) and less demanding (in traits-class
functionality) to use the non-intersection insertion-functions instead
of the general ones; e.g., `insert()`.

<LI>When the curves to be inserted into an arrangement are segments that
are pairwise disjoint in their interior, it is more efficient to use
the traits class `Arr_non_caching_segment_traits_2` rather then
the default one (`Arr_segment_traits_2`).

If the segments may intersect each other, the default traits class
`Arr_segment_traits_2` can be safely used with the somehow limited
number type `Quotient<MP_float>`.

On rare occasions the traits class `Arr_non_caching_segment_traits_2`
exhibits slightly better performance than the default one
(`Arr_segment_traits_2`
even when the segments intersect each other, due to the small overhead
of the latter (optimized) traits class. (For example, when the so
called <span class="textsc">Leda</span> rational kernel is used).

<LI>Prior knowledge of the combinatorial structure of the arrangement can
be used to accelerate operations that insert \f$ x\f$-monotone curves,
whose interior is disjoint from existing edges and vertices of the
arrangement. The specialized insertion functions, i.e.,
`insert_in_face_interior()`, `insert_from_left_vertex()`,
`insert_from_right_vertex()`, and `insert_at_vertices()`
can be used according to the available information. These functions
hardly involve any geometric operations, if at all. They accept
topologically related parameters, and use them to operate directly on
the \sc{Dcel} records, thus saving algebraic operations, which are
especially expensive when high-degree curves are involved.

A polygon, represented by a list of segments along its boundary, can
be inserted into an empty arrangement as follows. First, one segment
is inserted using `insert_in_face_interior()` into the unbounded
face. Then, a segment with a common end point is inserted using either
`insert_from_left_vertex()` or `insert_from_right_vertex()`,
and so on with the rest of the segments except for the last, which is
inserted using `insert_at_vertices()`, as both endpoints of which
are the mapping of known vertices.

<LI>The main trade-off among point-location strategies, is between time
and storage. Using the naive or walk strategies, for example, takes
more query time but does not require preprocessing or maintenance of
auxiliary structures and saves storage space.

<LI>If point-location queries are not performed frequently, but other
modifying functions, such as removing, splitting, or merging edges
are, then using a point-location strategy that does not require the
maintenance of auxiliary structures, such as the naive or walk
strategies, is preferable.

<LI>There is a trade-off between two modes of the trapezoidal RIC strategy
that enables the user to choose whether preprocessing should be
performed or not. If preprocessing is not used, the creation of the
structure is faster. However, for some input sequences the structure
might be unbalanced and therefore queries and updates might take
longer, especially, if many removal and split operations are
performed.

<LI>When the curves to be inserted into an arrangement are available in
advance (as opposed to supplied on-line), it is advised to use the
more efficient aggregate (sweep-based) insertion over the incremental
insertion; e.g., `insert()`.

<LI>The various traits classes should be instantiated with an exact number
type to ensure robustness, when the input of the operations to be
carried out might be degenerate, although inexact number types could
be used at the user's own risk.

<LI>Maintaining short bit-lengths of coordinate representations may
drastically decrease the time consumption of arithmetic operations on
the coordinates. This can be achieved by caching certain information
or normalization (of rational numbers). However, both solutions should
be used cautiously, as the former may lead to an undue space
consumption, and indiscriminate normalization may considerably slow
down the overall process.

<LI>Geometric functions (e.g., traits methods) dominate the time
consumption of most operations. Thus, calls to such function should be
avoided or at least their number should be decreased, perhaps at the
expense of increased combinatorial-function calls or increased space
consumption. For example, repetition of geometric-function calls could
be avoided by storing the results obtained by the first call, and
reusing them when needed.
</OL>

\section Arrangement_on_surface_2Design Design and Implementation History

The code of this package is the result of a long development process.
Initially (and until version 3.1), the code was spread among several
components, namely, `Topological_map`, `Planar_map_2`,
`Planar_map_with_intersections_2` and `Arrangement_2`, that were
developed by Ester Ezra, Eyal Flato, Efi Fogel, Dan Halperin, Iddo
Hanniel, Idit Haran, Shai Hirsch, Eugene Lipovetsky, Oren Nechushtan,
Sigal Raab, Ron Wein, Baruch Zukerman, and Tali Zvi.

In version 3.2, as part of the ACS project, the packages have gone
through a major re-design, resulting in an improved and unified
<I>2D Arrangements</I> package.
The code of the new package was restructured and developed by
Efi Fogel, Idit Haran, Ron Wein, and Baruch Zukerman. This
version included for the first time a new geometry-traits
class that handles circular and linear curves, and is based
on the circular kernel. The circular kernel was developed
by Monique Teillaud, Sylvain Pion, and Julien Hazebrouck.

Version 3.3 features arrangements of unbounded curves for the first
time. The design and development of this feature required yet another
restructuring of the entire package. All this was done by Eric
Berberich, Efi Fogel, Dan Halperin, Ophir Setter, and Ron
Wein. Michael Hemmer helped tuning up parts of the geometry-traits
concept related to unbounded curves.

Version 3.7 introduced a geometry-traits class
that handles planar algebraic curves of arbitrary degree.
It was developed by Eric Berberich and Michael Kerber.

Version 3.9 introduced a new geometry-traits class that handles
rational arcs. It was developed by Oren Salzman and Michael Hemmer.
It replaced an old traits, which handled the same family of
curves, developed by Ron Wein.

Version 4.1 introduces a revised implementation of the point location class
via a randomized incremental construction of the trapezoidal map.
The old class was implemented by Oren Nechushtan, while the revamp
was done by Michal Kleinbort and Michael Hemmer. The new class adds support
for unbounded curves and can now guarantee logarithmic query time in all
cases.

*/
} /* namespace CGAL */
