cgal Documentation

\section Alpha_shapes_2Examples Examples

\subsection I1_SectClassicAS2D Example for Basic Alpha Shapes

The basic alpha shape requires a Delaunay triangulation as
underlying triangulation Dt. The Delaunay triangulation class is
parameterized with a geometric and a triangulation data structure traits.

For the geometric traits class we can use a \cgal kernel.

For the triangulation data structure traits, we have to
choose the vertex and face classes needed for alpha shapes,
namely Alpha_shape_vertex_base_2<Gt, Vb> and Alpha_shape_face_base_2<Gt,Fb>.
The parameter Vb and Fb must be filled by classes that are models of the
TriangulationVertexBase_2 and TriangulationFaceBase_2 concepts. The classes
Triangulation_vertex_base_2<Gt> and Triangulation_face_base_2<Gt> fit these
requirements.

The example below illustrates how to construct a basic alpha shape.
Note that Triangulation_vertex_base_2<Gt> and Triangulation_face_base_2<Gt>
are the default parameters for Vb and Fb in the classes
Alpha_shape_vertex_base_2<Gt, Vb> and Alpha_shape_face_base_2<Gt,Fb>. They
are thus omitted in the code below.
\cgalExample{Alpha_shapes_2/ex_alpha_shapes_2.cpp}

\subsection I1_SectWeightedAS2D Example for Weighted Alpha Shapes

A weighted alpha shape requires a regular triangulation as
underlying triangulation Dt.
Here again, we can use the vertex and face Alpha_shape_vertex_base_2<Gt, Vb>
and Alpha_shape_face_base_2<Gt,Fb>, but for weighted alpha shapes, Vb and Fb
must be models of the concepts RegularTriangulationVertexBase_2 and
RegularTriangulationFaceBase_2. The classes Regular_triangulation_vertex_base_2<Gt>
Regular_triangulation_face_base_2<Gt> fit these requirements.

Note that there is no special weighted alpha shape class.

The example below illustrates how to construct a weighted alpha shape.
\cgalExample{Alpha_shapes_2/ex_weighted_alpha_shapes_2.cpp}

\subsection AlphaShape_2DExampleForPeriodicAlphaShapes Example for Periodic Alpha Shapes
The following example shows how to use a periodic Delaunay
triangulation as underlying triangulation for the alpha shape computation.

In order to define the original domain and to benefit from the
built-in heuristic optimizations of the periodic triangulation computation,
it is recommended to first construct the triangulation and
then construct the alpha shape from it. The alpha
shape constructor that takes a point range can be used as well but in
this case the original domain cannot be specified and the default unit
cube will be chosen and no optimizations will be used.

It is also recommended to switch the triangulation to 1-sheeted
covering if possible. Note that a periodic triangulation in 9-sheeted
covering space is degenerate. In this case, an exact constructions
kernel needs to be used to compute the alpha shapes. Otherwise, the
results will suffer from round-off problems.

\cgalExample{Alpha_shapes_2/ex_periodic_alpha_shapes_2.cpp}

/
} / namespace CGAL */

Alpha Shapes 2 Doc Alpha Shapes 2 PackageDescription (`Alpha_shapes_2/doc/Alpha_shapes_2/PackageDescription.txt`) Copy Section

/// \defgroup PkgAlphaShapes2Ref Reference Manual
/// \defgroup PkgAlphaShapes2Concepts Concepts
/// \ingroup PkgAlphaShapes2Ref

/*!
\addtogroup PkgAlphaShapes2Ref

\cgalPkgDescriptionBegin{2D Alpha Shapes,PkgAlphaShapes2}
\cgalPkgPicture{alpha-detail.png}
\cgalPkgSummaryBegin
\cgalPkgAuthor{Tran Kai Frank Da}
\cgalPkgDesc{This package offers a data structure encoding the whole family of alpha-complexes related to a given 2D Delaunay or regular triangulation. In particular, the data structure allows to retrieve the alpha-complex for any alpha value, the whole spectrum of critical alpha values and a filtration on the triangulation faces (this filtration is based on the first alpha value for which each face is included on the alpha-complex).}
\cgalPkgManuals{Chapter_2D_Alpha_Shapes,PkgAlphaShapes2Ref}
\cgalPkgSummaryEnd
\cgalPkgShortInfoBegin
\cgalPkgSince{2.1}
\cgalPkgDependsOn{\ref PkgTriangulation2}
\cgalPkgBib{cgal:d-as2}
\cgalPkgLicense{\ref licensesGPL "GPL"}
\cgalPkgDemo{2D Alpha Shapes,alpha_shapes_2.zip}
\cgalPkgShortInfoEnd
\cgalPkgDescriptionEnd

This chapter presents a framework for alpha shapes. The description is based on
the articles \cgalCite{em-tdas-94}, \cgalCite{e-was-92}. Alpha shapes are
the generalization of the convex hull of a point set. Let \f$ S\f$ be a finite set of
points in \f$ \mathbb{R}^d\f$, \f$ d = 2,3\f$ and \f$ \alpha\f$ a parameter with \f$ 0 \leq \alpha \leq
\infty\f$. For \f$ \alpha = \infty\f$, the \f$ \alpha\f$-shape is the convex hull of \f$ S\f$. As
\f$ \alpha\f$ decreases, the \f$ \alpha\f$-shape shrinks and develops cavities, as soon as
a sphere of radius \f$ \sqrt{\alpha}\f$ can be put inside.
Finally, for \f$ \alpha = 0\f$, the \f$ \alpha\f$-shape is the set \f$ S\f$ itself.

We distinguish two versions of alpha shapes, one is based on the Delaunay
triangulation and the other on its generalization, the regular triangulation,
replacing the natural distance by the power to weighted points. The metric used
determines an underlying triangulation of the alpha shape and thus, the version
computed.
The basic alpha shape (cf. \ref I1_SectClassicAS2D) is associated with the Delaunay triangulation
(cf. Section \ref Section_2D_Triangulations_Delaunay "Delaunay Triangulations").
The weighted alpha shape (cf. \ref I1_SectWeightedAS2D ) is associated with the regular triangulation
(cf. Section \ref Section_2D_Triangulations_Regular "Regular Triangulations").

There is a close connection between alpha shapes and the underlying
triangulations. More precisely, the \f$ \alpha\f$-complex of \f$ S\f$ is a
subcomplex of this triangulation of \f$ S\f$, containing the \f$ \alpha\f$-exposed
\f$ k\f$-simplices, \f$ 0 \leq k \leq d\f$. A simplex is \f$ \alpha\f$-exposed, if there is an
open disk (resp. ball) of radius \f$ \sqrt{\alpha}\f$ through the vertices of the
simplex that does not contain any other point of \f$ S\f$, for the metric used in
the computation of the underlying triangulation. The corresponding
\f$ \alpha\f$-shape is defined as the underlying interior space of the
\f$ \alpha\f$-complex.

In general, an \f$ \alpha\f$-complex is a non-connected and non-pure polytope,
meaning that a \f$ k\f$-simplex, with \f$ 0 \leq k \leq d-1\f$, is not necessarily
adjacent to a \f$ (k+1)\f$-simplex.

The \f$ \alpha\f$-shapes of \f$ S\f$ form a discrete family, even though they
are defined for all real numbers \f$ \alpha\f$ with \f$ 0 \leq \alpha
\leq \infty\f$. Thus, we can represent the entire family of \f$ \alpha\f$-shapes
of \f$ S\f$ by the underlying triangulation of \f$ S\f$. In this representation
each \f$ k\f$-simplex of the underlying triangulation is associated with an
interval that specifies for which values of \f$ \alpha\f$ the \f$ k\f$-simplex
belongs to the \f$ \alpha\f$-shape. Relying on this result, the family of
\f$ \alpha\f$-shapes can be computed efficiently and relatively
easily. Furthermore, we can select an appropriate \f$ \alpha\f$-shape from a
finite number of different \f$ \alpha\f$-shapes and corresponding
\f$ \alpha\f$-values.

\cgalClassifedRefPages

\cgalCRPSection{Concepts}

• AlphaShapeTraits_2
• WeightedAlphaShapeTraits_2
• AlphaShapeFace_2
• AlphaShapeVertex_2

\cgalCRPSection{Classes}

• CGAL::Alpha_shape_2<Dt>
• CGAL::Alpha_shape_vertex_base_2<AlphaShapeTraits_2>
• CGAL::Alpha_shape_face_base_2<AlphaShapeTraits_2, TriangulationFaceBase_2>

*/

Alpha Shapes 2 Doc Alpha Shapes 2 Examples (`Alpha_shapes_2/doc/Alpha_shapes_2/examples.txt`) Copy Section

/*!
\example Alpha_shapes_2/ex_alpha_shapes_2.cpp
\example Alpha_shapes_2/ex_periodic_alpha_shapes_2.cpp
\example Alpha_shapes_2/ex_weighted_alpha_shapes_2.cpp
\example Alpha_shapes_2/ex_alpha_projection_traits.cpp
*/

Alpha Shapes 3 Doc Alpha Shapes 3 Alpha Shapes 3 (`Alpha_shapes_3/doc/Alpha_shapes_3/Alpha_shapes_3.txt`) Copy Section

namespace CGAL {
/*!

\mainpage User Manual
\anchor Chapter_3D_Alpha_Shapes
\cgalAutoToc
\authors Tran Kai Frank Da, Sébastien Loriot, and Mariette Yvinec

\image html alphashape.png
\image latex alphashape.png

Assume we are given a set \f$ S\f$ of points in 2D or 3D and we would like to
have something like "the shape formed by these points". This is
quite a vague notion and there are probably many possible
interpretations, the alpha shape being one of them. Alpha shapes
can be used for shape reconstruction from a dense unorganized set of
data points. Indeed, an alpha shape is demarcated by a frontier,
which is a linear approximation of the original shape \cgalCite{bb-srmua-97t}.

As mentioned in Edelsbrunner's and Mücke's paper \cgalCite{em-tdas-94},
one can intuitively think of an alpha shape as the
following. Imagine a huge mass of ice-cream making up the space \f$ \mathbb{R}^3\f$
and containing the points as "hard" chocolate pieces. Using one of
those sphere-formed ice-cream spoons, we carve out all parts of the
ice-cream block we can reach without bumping into chocolate pieces,
thereby even carving out holes in the inside (e.g. parts not reachable
by simply moving the spoon from the outside). We will eventually end
up with a (not necessarily convex) object bounded by caps, arcs and
points. If we now straighten all "round" faces to triangles and line
segments, we have an intuitive description of what is called the
alpha shape of \f$ S\f$. The drawing above provides an example
of this process in 2D (where our ice-cream spoon is simply a circle).

Alpha shapes depend on a parameter \f$ \alpha\f$ after which they are named.
In the ice-cream analogy above, \f$ \alpha\f$ is the squared radius of the
carving spoon. A very small value will allow us to eat up all the
ice-cream except the chocolate points themselves. Thus, we already see
that the alpha shape degenerates to the point-set \f$ S\f$ for
\f$ \alpha \rightarrow 0\f$. On the other hand, a huge value of \f$ \alpha\f$
will prevent us even from moving the spoon between two points since
it is too large and we will never spoon up the ice-cream lying in the
inside of the convex hull of \f$ S\f$. Hence, the alpha shape becomes
the convex hull of \f$ S\f$ as \f$ \alpha \rightarrow \infty\f$.

\cgal offers 2D and 3D alpha shapes. The GUDHI library offers a
dD Alpha complex.

\section Alpha_shapes_3Definitions Definitions

We distinguish two versions of alpha shapes. Basic alpha shapes
are based on the Delaunay triangulation. Weighted alpha shapes
are based on its generalization, the regular triangulation
(cf. Section \ref Triangulation3secclassRegulartriangulation "Regular Triangulations"),
replacing the Euclidean distance by the power to weighted points.

Let us consider the basic case with a Delaunay triangulation.
We first define the alpha complex of the set of points \f$ S\f$.
The alpha complex is a subcomplex
of the Delaunay triangulation.
For a given value of \f$ \alpha\f$, the alpha complex includes
all the simplices in the Delaunay triangulation which have
an empty circumscribing sphere with squared radius equal or smaller than \f$ \alpha\f$.
Here "empty" means that the open sphere does not include any points of \f$ S\f$.
The alpha shape is then simply the domain covered by the simplices
of the alpha complex (see \cgalCite{em-tdas-94}).

In general, an alpha complex is a disconnected and non-pure complex,
meaning in particular that the alpha complex may have
singular faces. For \f$ 0 \leq k \leq d-1\f$,
a \f$ k\f$-simplex of the alpha complex is said to be
singular if it is not a facet of a \f$ (k+1)\f$-simplex of the complex.
\cgal provides two versions of alpha shapes. In the general mode,
the alpha shapes correspond strictly to the above definition.
The regularized mode provides a regularized version of the alpha shapes.
It corresponds to the domain covered by a regularized version
of the alpha complex where singular faces are removed
(See \cgalFigureRef{figgenregex} for an example).

\cgalFigureBegin{figgenregex,gen-reg-ex.png}
Comparison of general and regularized alpha-shape. Left: Some points are taken on the surface of a torus, three points being taken relatively far from the surface of the torus; Middle: The general alpha-shape (for a large enough alpha value) contains the singular triangle facet of the three isolated points; Right: The regularized version (for the same value of alpha) does not contain any singular facet.
\cgalFigureEnd

The alpha shapes of a set of points
\f$ S\f$ form a discrete family, even though they
are defined for all real numbers \f$ \alpha\f$.
The entire family of alpha shapes can be represented
through the underlying triangulation of \f$ S\f$. In this representation
each \f$ k\f$-simplex of the underlying triangulation is associated with an
interval that specifies for which values of \f$ \alpha\f$ the \f$ k\f$-simplex
belongs to the alpha complex. Relying on this fact, the family of
alpha shapes can be computed efficiently and relatively
easily. Furthermore, we can select the optimal value
of \f$ \alpha\f$ to get an alpha shape including all data points
and having less than a given number of connected components.
Also, the alpha-values allows to define a filtration on the
faces of the triangulation of a set of points.
In this filtration, the faces of the triangulation are output
in increasing order of the alpha value
for which they appear
in the alpha complex. In case of equal alpha values,
lower dimensional faces are output first.

The definition is analog in the case of weighted alpha shapes.
The input set is now a set of weighted points (which can be regarded
as spheres) and the underlying triangulation
is the regular triangulation of this set.
Two spheres, or two weighted points, with centers \f$ C_1, C_2\f$
and radii \f$ r_1, r_2 \f$ are said to be orthogonal iff
\f$ C_1C_2 ^2 = r_1^2 + r_2^2\f$ and suborthogonal
iff \f$ C_1C_2 ^2 < r_1^2 + r_2^2\f$.
For a given value of \f$ \alpha\f$,
the weighted alpha complex is formed with the simplices of the
regular triangulation such that there is a sphere
orthogonal to the weighted points associated
with the vertices of the simplex and suborthogonal to all the other
input weighted points. Once again the alpha shape is then defined as
the domain covered by the alpha complex and comes in general and
regularized versions.

\section Alpha_Shape_3Functionality Functionality

\subsection AlphaShape_3DFamilyOfAlphaShapes Family of Alpha Shapes

The class Alpha_shape_3<Dt,ExactAlphaComparisonTag> represents the whole
family of alpha shapes for a given set of points.
The class includes the underlying triangulation Dt
of the set, and associates to each \f$ k\f$-face of this triangulation
an interval specifying
for which values of \f$ \alpha\f$ the face belongs to the
alpha complex.
The second template parameter, ExactAlphaComparisonTag, is a tag that,
when set to CGAL::Tag_true, triggers exact comparisons between alpha values.

The class provides functions to set and
get the current \f$ \alpha\f$-value, as well as an iterator that enumerates
the \f$ \alpha\f$ values where the alpha shape changes.

Additionally, the class has a filtration member function that, given
an output iterator with Object
as value type, outputs the faces of the triangulation
according to the
order of apparition in the alpha complex when alpha increases.

Finally, it provides a function to determine
the smallest value \f$ \alpha\f$
such that the alpha shape satisfies the following two properties:

1. All data points are either on the boundary or in the interior of the regularized version of the alpha shape (no singular faces).
2. The number of components is equal or less than a given number.

The current implementation is static, that is after its construction
points cannot be inserted or removed.

\subsection AlphaShape_3DAlphaShapeForAFixedAlpha Alpha Shape for a Fixed Alpha

Given a value of alpha, the class Fixed_alpha_shape_3<Dt> represents one
alpha shape for a given set of points.
The class includes the underlying triangulation Dt
of the set, and associates to each \f$ k\f$-face of this triangulation
a classification type. This class is dynamic, that is after its construction
points can be inserted or removed.

\subsection AlphaShape_3DClassificationAndIterators Classification and Iterators

Both classes provide member functions to classify for a (given) value
of \f$ \alpha\f$ the different faces of the triangulation as
EXTERIOR, SINGULAR, REGULAR or
INTERIOR with respect
to the alpha shape. A \f$ k\f$-face on the boundary of the alpha complex
is said to be: REGULAR if it is a subface of the alpha-complex which
is a subface of a \f$ (k+1)\f$-face of the alpha complex, and SINGULAR otherwise.
A \f$ k\f$-face of the alpha complex which is not on the boundary of the alpha complex
is said to be INTERIOR. See \cgalFigureRef{figclassif} for a 2D illustration.

\cgalFigureBegin{figclassif,classif.png} Classification of simplices, a 2D example. Left: The 2D
Delaunay triangulation of a set of points; Right:
Classification of simplices for a given alpha (the squared radius of
the red circle). INTERIOR, REGULAR and SINGULAR simplices are
depicted in black, green and blue respectively. EXTERIOR simplices
are not depicted. The vertex s and the edge tu are SINGULAR
since all higher dimension simplices they are incident to are
EXTERIOR. The facet pqr is EXTERIOR because the squared radius
of its circumscribed circle is larger than alpha.
\cgalFigureEnd

The classes provide also output iterators to get for a given alpha value
the vertices, edges, facets and cells of the different types
(EXTERIOR, SINGULAR, REGULAR or
INTERIOR).

\subsection AlphaShape3DIO Input/Output
It is possible to export a 3D alpha shape to a std::ostream
using the operator<<, see the documentation of the class Alpha_shape_3 for more information.

\section AlphaShape3D_ConceptAndModels Concepts and Models

We currently do not specify concepts for the underlying triangulation
type. Models that work for a family of alpha-shapes are the instantiations
of the classes Delaunay_triangulation_3 and
Periodic_3_Delaunay_triangulation_3 (see
example \ref AlphaShape_3DExampleForPeriodicAlphaShapes).
A model that works for a fixed alpha-shape are the instantiations
of the class Delaunay_triangulation_3.
Models that work for a weighted alpha-shape are the instantiations
of the classes Regular_triangulation_3 and
Periodic_3_regular_triangulation_3.
The triangulation needs a geometric traits class
and a triangulation data structure as template parameters.

\subsection AlphaShape3D_ConceptAndModelsAlphaShapes Alpha Shapes

For the class Alpha_shape_3<Dt,ExactAlphaComparisonTag>, the requirements of
the traits class are described in the concepts AlphaShapeTraits_3
in the non-weighted case and WeightedAlphaShapeTraits_3 in the weighted case.
All \cgal kernels are models of both concepts.

The triangulation data structure of the triangulation
has to be a model of the concept TriangulationDataStructure_3
whose vertex and cell classes are model of the concepts
AlphaShapeVertex_3 and AlphaShapeCell_3.
The classes Alpha_shape_vertex_base_3<Gt> and Alpha_shape_cell_base_3<Gt>
are models of these concepts and can be used for all type of alpha shapes,
provided that the template parameters Vb and Fb are appropriately chosen,
as we shall see in the following section.

\subsection AlphaShape3D_ConceptAndModelsFixedAlphaShapes Fixed Alpha Shapes

For the class Fixed_alpha_shape_3<Dt>, the requirements of
the traits class are described in the concepts FixedAlphaShapeTraits_3
in the non-weighted case and FixedWeightedAlphaShapeTraits_3 in the weighted case.
All \cgal kernels are models of both concepts.
The triangulation data structure of the triangulation
has to be a model of the concept TriangulationDataStructure_3
whose vertex and cell classes are model of the concepts
FixedAlphaShapeVertex_3 and FixedAlphaShapeCell_3.
The package provides models Fixed_alpha_shape_vertex_base_3<Gt>
and Fixed_alpha_shape_cell_base_3<Gt>, respectively.

\subsection AlphaShape3D_ConceptAndModelsTDS Triangulation data structure

Additional requirements are put when using weighted or
periodic triangulations as underlying triangulation:

\section Alpha_shapes_3AlphaShape3OrFixedAlphaShape3 Alpha_shape_3 vs. Fixed_alpha_shape_3

The class Alpha_shape_3<Dt,ExactAlphaComparisonTag> represents the whole family
of alpha shapes for a given set of points while the class Fixed_alpha_shape_3<Dt>
represents only one alpha shape (for a fixed alpha). When using the same kernel,
Fixed_alpha_shape_3<Dt> is a lighter version. It is thus naturally much more efficient
when the alpha-shape is needed for a single given value of alpha.
In addition, note that the class Alpha_shape_3<Dt,ExactAlphaComparisonTag>
requires constructions (squared radius of simplices) while the
class Fixed_alpha_shape_3<Dt> uses only predicates.
This implies that a certified construction of one (several)
alpha-shape, using the Alpha_shape_3<Dt,ExactAlphaComparisonTag> requires a kernel
with exact predicates and exact constructions (or setting ExactAlphaComparisonTag to Tag_true)
while using a kernel with exact predicates is sufficient for the class Fixed_alpha_shape_3<Dt>.
This makes the class Fixed_alpha_shape_3<Dt> even more efficient in this setting.
In addition, note that the Fixed version is the only one of the
two that supports incremental insertion and removal of points.

We give the time spent while computing the alpha shape of a protein (considered
as a set of weighted points) featuring 4251 atoms (using gcc 4.3 under Linux with -O3
and -DNDEBUG flags, on a 2.27GHz Intel(R) Xeon(R) E5520 CPU):
Using Exact_predicates_inexact_constructions_kernel, building
the regular triangulation requires 0.09s, then the class Fixed_alpha_shape_3<Dt>
required 0.05s while the class Alpha_shape_3<Dt,ExactAlphaComparisonTag> requires 0.35s
if ExactAlphaComparisonTag is Tag_false (and 0.70s with Tag_true).
Using Exact_predicates_exact_constructions_kernel, building
the regular triangulation requires 0.19s and then the class Alpha_shape_3<Dt,ExactAlphaComparisonTag>
requires 0.90s.

\section Alpha_shapes_3Examples Examples

\subsection AlphaShape_3DExampleForBasicAlphaShapes Example for Basic Alpha-Shapes

This example builds a basic alpha shape using a Delaunay triangulation
as underlying triangulation.

\cgalExample{Alpha_shapes_3/ex_alpha_shapes_3.cpp}

\subsection AlphaShape_3DBuildingBasicAlphaShapesForManyPoints Building Basic Alpha Shapes for Many Points

When many points are input in the alpha shape, say more than 10 000,
it may pay off to use a Delaunay triangulation with the Fast_location
policy as underlying triangulation in order to speed up point location
queries (cf. Section \ref Triangulation3seclocpol "The Location Policy Parameter").

\cgalExample{Alpha_shapes_3/ex_alpha_shapes_with_fast_location_3.cpp}

\subsection AlphaShape_3DExampleforWeightedAlphaShapes Example for Weighted Alpha-Shapes

The following examples build a weighted alpha shape requiring a
regular triangulation as underlying triangulation.
The alpha shape is built in GENERAL mode.

\cgalExample{Alpha_shapes_3/ex_weighted_alpha_shapes_3.cpp}

\subsection AlphaShape_3DExampleForFixedWeightedAlphaShapes Example for Fixed Weighted Alpha-Shapes

Same example as previous but using a fixed value of alpha.

\cgalExample{Alpha_shapes_3/ex_fixed_weighted_alpha_shapes_3.cpp}

\subsection AlphaShape_3DBuildingAnAlphaShapesWithExactComparisonsOfAlphaValues Building an Alpha Shapes with Exact Comparisons of Alpha Values

On some platforms, the alpha shapes of the set of points of this example
cannot be computed when using a traits with inexact constructions. To be able to compute
them with a traits with inexact constructions, the tag
ExactAlphaComparisonTag is set to Tag_true.
\cgalExample{Alpha_shapes_3/ex_alpha_shapes_exact_alpha.cpp}

\subsection AlphaShape_3DExampleForPeriodicAlphaShapes Example for Periodic Alpha Shapes

The following example shows how to use a periodic Delaunay
triangulation (Chapter \ref Chapter_3D_Periodic_Triangulations "3D Periodic Triangulations") as underlying
triangulation for the alpha shape computation. Usage of a weighted Delaunay periodic
triangulation is presented in the example: \ref Alpha_shapes_3/ex_weighted_periodic_alpha_shapes_3.cpp "ex_weighted_periodic_alpha_shapes_3.cpp".

In order to define the original domain and to benefit from the
built-in heuristic optimizations of the periodic triangulation computation,
it is recommended to first construct the triangulation and
then construct the alpha shape from it. The alpha
shape constructor that takes a point range can be used as well but in
this case the original domain cannot be specified and the default unit
cube will be chosen and no optimizations will be used.

It is also recommended to switch the triangulation to 1-sheeted
covering if possible. Note that a periodic triangulation in 27-sheeted
covering space is degenerate. In this case, an exact constructions
kernel needs to be used to compute the alpha shapes. Otherwise, the
results will suffer from round-off problems.

\cgalExample{Alpha_shapes_3/ex_periodic_alpha_shapes_3.cpp}

/
} / namespace CGAL */

Alpha Shapes 3 Doc Alpha Shapes 3 PackageDescription (`Alpha_shapes_3/doc/Alpha_shapes_3/PackageDescription.txt`) Copy Section

/// \defgroup PkgAlphaShapes3Ref Reference Manual
/// \defgroup PkgAlphaShapes3Concepts Concepts
/// \ingroup PkgAlphaShapes3Ref
/*!
\addtogroup PkgAlphaShapes3Ref
\cgalPkgDescriptionBegin{3D Alpha Shapes,PkgAlphaShapes3}
\cgalPkgPicture{alpha_shapes_3_small.png}
\cgalPkgSummaryBegin
\cgalPkgAuthors{Tran Kai Frank Da, Sébastien Loriot, and Mariette Yvinec}
\cgalPkgDesc{This package offers a data structure encoding either one alpha-complex or the whole family of alpha-complexes related to a given 3D Delaunay or regular triangulation. In the latter case, the data structure allows to retrieve the alpha-complex for any alpha value, the whole spectrum of critical alpha values and a filtration on the triangulation faces (this filtration is based on the first alpha value for which each face is included on the alpha-complex). }
\cgalPkgManuals{Chapter_3D_Alpha_Shapes,PkgAlphaShapes3Ref}
\cgalPkgSummaryEnd
\cgalPkgShortInfoBegin
\cgalPkgSince{2.3}
\cgalPkgDependsOn{\ref PkgTriangulation3}
\cgalPkgBib{cgal:dy-as3}
\cgalPkgLicense{\ref licensesGPL "GPL"}
\cgalPkgDemo{3D Alpha Shapes,alpha_shape_3.zip}
\cgalPkgShortInfoEnd
\cgalPkgDescriptionEnd

Alpha shapes definition is based on an underlying
triangulation that may be a Delaunay triangulation
in case of basic alpha shapes or a regular triangulation
(cf. Section \ref Triangulation3secclassRegulartriangulation "3D Regular Triangulation")
in case of weighted alpha shapes.

Let us consider the basic case with a Delaunay triangulation.
We first define the alpha complex of the set of points \f$ S\f$.
The alpha complex is a subcomplex
of the Delaunay triangulation.
For a given value of \f$ \alpha\f$, the alpha complex includes
all the simplices in the Delaunay triangulation which have
an empty circumscribing sphere with squared radius equal or smaller than \f$ \alpha\f$.
Here "empty" means that the open sphere
do not include any points of \f$ S\f$.
The alpha shape is then simply the domain covered by the simplices
of the alpha complex (see \cgalCite{em-tdas-94}).

In general, an alpha complex is a non-connected and non-pure complex.
This means in particular that the alpha complex may have
singular faces. For \f$ 0 \leq k \leq d-1\f$,
a \f$ k\f$-simplex of the alpha complex is said to be
singular if it is not a facet of a \f$ (k+1)\f$-simplex of the complex

The alpha shapes of a set of points
\f$ S\f$ form a discrete family, even though they
are defined for all real numbers \f$ \alpha\f$.
The entire family of alpha shapes can be represented
through the underlying triangulation of \f$ S\f$. In this representation,
each \f$ k\f$-simplex of the underlying triangulation is associated with an
interval that specifies for which values of \f$ \alpha\f$ the \f$ k\f$-simplex
belongs to the alpha complex. Relying on this fact, the family of
alpha shapes can be computed efficiently and relatively
easily. Furthermore, we can select the optimal value
of \f$ \alpha\f$ to get an alpha shape including all data points
and having less than a given number of connected components.

The definition is analog in the case of weighted alpha shapes.
The input set is now a set of weighted points (which can be regarded
as spheres) and the underlying triangulation
is the regular triangulation of this set.
Two spheres, or two weighted points, with centers \f$ C_1, C_2\f$
and radii \f$ r_1, r_2 \f$ are said to be orthogonal iff
\f$ C_1C_2 ^2 = r_1^2 + r_2^2\f$ and suborthogonal
iff \f$ C_1C_2 ^2 < r_1^2 + r_2^2\f$.
For a given value of \f$ \alpha\f$
the weighted alpha complex is formed with the simplices of the
regular triangulation triangulation
such that there is a sphere orthogonal to the weighted points associated
with the vertices of the simplex and suborthogonal to all the other
input weighted points. Once again the alpha shape is then defined as
the domain covered by a the alpha complex.

CGAL provides two versions to compute alpha shapes.
The first one gives access to an explicit classification of all the simplices for a fixed alpha value.
The second one gives access to the entire family of alpha shapes of a set of points.
This latter version comes with two modes. In the general mode,
the alpha shapes correspond strictly to the definition previously made.
The regularized mode provides a regularized version of the alpha shapes
corresponding to the domain covered by a regularized version
of the alpha complex where singular faces are removed.

\cgalClassifedRefPages

\cgalCRPSection{Concepts}

• AlphaShapeTraits_3
• WeightedAlphaShapeTraits_3
• AlphaShapeCell_3
• AlphaShapeVertex_3
• FixedAlphaShapeTraits_3
• FixedWeightedAlphaShapeTraits_3
• FixedAlphaShapeCell_3
• FixedAlphaShapeVertex_3

\cgalCRPSection{Classes}

• CGAL::Alpha_status<NT>

• CGAL::Alpha_shape_3<Dt,ExactAlphaComparisonTag>

• CGAL::Alpha_shape_vertex_base_3

• CGAL::Alpha_shape_cell_base_3

• CGAL::Fixed_alpha_shape_3<Dt>

• CGAL::Fixed_alpha_shape_vertex_base_3

• CGAL::Fixed_alpha_shape_cell_base_3

*/

Alpha Shapes 3 Doc Alpha Shapes 3 Examples (`Alpha_shapes_3/doc/Alpha_shapes_3/examples.txt`) Copy Section

/*!
\example Alpha_shapes_3/ex_alpha_shapes_3.cpp
\example Alpha_shapes_3/ex_alpha_shapes_exact_alpha.cpp
\example Alpha_shapes_3/ex_alpha_shapes_with_fast_location_3.cpp
\example Alpha_shapes_3/ex_fixed_weighted_alpha_shapes_3.cpp
\example Alpha_shapes_3/ex_periodic_alpha_shapes_3.cpp
\example Alpha_shapes_3/ex_weighted_alpha_shapes_3.cpp
\example Alpha_shapes_3/ex_weighted_periodic_alpha_shapes_3.cpp
\example Alpha_shapes_2/ex_alpha_projection_traits.cpp
*/

Alpha Wrap 2 Doc Alpha Wrap 2 PackageDescription (`Alpha_wrap_2/doc/Alpha_wrap_2/PackageDescription.txt`) Copy Section

/// \defgroup PkgAlphaWrap2Ref Reference Manual

/// \defgroup PkgAlphaWrap2Concepts Concepts
/// \ingroup PkgAlphaWrap2Ref

/// \defgroup AW2_free_functions_grp Free Functions
/// Functions to create a wrap from point clouds, segment soups, and polygons with holes.
/// \ingroup PkgAlphaWrap2Ref

/*!
\addtogroup PkgAlphaWrap2Ref
\cgalPkgDescriptionBegin{2D Alpha Wrapping,PkgAlphaWrap2}
\cgalPkgPicture{alpha_wrap_2.png}
\cgalPkgSummaryBegin
\cgalPkgAuthors{Pierre Alliez, David Cohen-Steiner, Michael Hemmer, Cédric Portaneri, and Mael Rouxel-Labbé}
\cgalPkgDesc{This component takes a polygon soup, a 2D segment soup, and/or a 2D point set as input,
and generates a valid (watertight, intersection-free and 1-manifold) multi-polygon that
strictly encloses the input. The algorithm proceeds by shrink-wrapping
and refining a 2D Delaunay triangulation starting from a loose bounding box of the input.
Two user-defined parameters, alpha and offset, offer control over the maximum size
of cavities where the shrink-wrapping process can enter, and the tightness
of the final polygon(s) to the input, respectively. Once combined, these parameters
provide a means to trade fidelity to the input for complexity of the output.}
\cgalPkgManuals{Chapter_2D_Alpha_wrapping,PkgAlphaWrap2Ref}
\cgalPkgSummaryEnd
\cgalPkgShortInfoBegin
\cgalPkgSince{6.2}
\cgalPkgDependsOn{\ref PkgTriangulation2 and \ref PkgPolygonRepair}
\cgalPkgBib{cgal:achpr-aw2}
\cgalPkgLicense{\ref licensesGPL "GPL"}
\cgalPkgDemo{2D Alpha wrap demo,alpha_wrap_2.zip}
\cgalPkgShortInfoEnd
\cgalPkgDescriptionEnd

\cgalClassifedRefPages

\cgalCRPSection{Concepts}

• AlphaWrapTraits_2

\cgalCRPSection{Functions}

• \link AW2_free_functions_grp CGAL::alpha_wrap_2() \endlink
  */

Alpha Wrap 2 Doc Alpha Wrap 2 Alpha Wrap 2 (`Alpha_wrap_2/doc/Alpha_wrap_2/alpha_wrap_2.txt`) Copy Section

namespace CGAL {

/*!

\mainpage User Manual
\anchor Chapter_2D_Alpha_wrapping
\cgalAutoToc

\authors Pierre Alliez, David Cohen-Steiner, Michael Hemmer, Cédric Portaneri, Mael Rouxel-Labbé

\section aw2_introduction Introduction

Various tasks in geometric modeling and processing require 2D objects represented as valid polygons,
where "valid" refers to polygons that are closed, intersection-free (simple), orientable, and 1-manifold.
Such representations offer well-defined notions of interior/exterior and geodesic neighborhoods.

2D data are usually acquired through measurements, possibly followed by reconstruction,
designed by humans, or generated through imperfect automated processes.
As a result, they can exhibit a wide variety of defects including gaps, missing data,
self-intersections, degeneracies such as zero-area structures, and non-manifold features.

Given the large repertoire of possible defects, many methods and data structures have been proposed
to repair specific defects (see for example the package \ref PkgPolygonRepair), usually with the goal
of guaranteeing specific properties in the repaired 2D model.
Reliably repairing all types of defects is an ill-posed problem as many valid solutions exist
for a given 2D model with defects.
In addition, the input model can be overly complex with unnecessary geometric details,
spurious topological structures, nonessential inner components, or excessively fine discretizations.
For applications such as collision avoidance, path planning, or simulation,
getting an approximation (i.e., a silhouette) of the input can be more relevant than repairing it.
Approximation herein refers to an approach capable of filtering out inner structures,
fine details and cavities, as well as wrapping the input within a user-defined offset margin.

Given an input 2D geometry, we address the problem of computing a conservative approximation,
where conservative means that the output is guaranteed to strictly enclose the input.
We seek unconditional robustness in the sense that the output polygon should be valid (oriented,
1-manifold, and without self-intersections), even for raw input with many defects
and degeneracies.
The default input is a soup of 2D segments, but the generic interface leaves the door open
to other types of finite 2D primitives such as point sets.

\cgalFigureAnchor{aw2_inputs_fig}

\cgalFigureCaptionBegin{aw2_inputs_fig}
(Left) Shrink-wrapping output from a segment soup with many intersections and gaps.
(Center & Right) Possible input degeneracies: non-manifold vertices and zero-area structures.
The algorithm handles these cases by wrapping an offset of the input.
\cgalFigureCaptionEnd

\section aw2_definition Approach

Many approaches have been devised to enclose a 2D model within a polygon, featuring different balances
between the runtime and quality (i.e., tightness) of the approximation.
Within the simplest cases, an axis-aligned or oriented bounding box clearly satisfies some desired properties;
however, the approximation error is uncontrollable and often very large.
Computing the convex hull of the input also matches some of the desired properties
and improves the quality of the result, albeit at the price of increasing the runtime.
However, the approximation remains crude, especially in the case of several components.

The convex hull is, in fact, a special case of alpha shapes (\ref PkgAlphaShapes2).
Mathematically, the alpha shape is a subcomplex of the Delaunay triangulation, with simplicies
being part of the complex depending on the size of their minimal (empty) Delaunay ball.
Intuitively, constructing 2D alpha shapes can be thought of as carving 2D space with an empty ball
of user-defined radius alpha.
Alpha shapes yield provable, good piecewise-linear approximations of a shape \cgalCite{bb-srmua-97t},
but are defined on point sets, whereas we wish to deal with more general input data, such as segment soups.
Even after sampling the segment soup, alpha shapes do not guarantee to be conservative for any alpha.
Finally, inner structures are also carved within the interior, instead of being filtered out.

Inspired by alpha shapes, we replace the above notion of carving by shrink-wrapping:
we iteratively construct a subcomplex of a 2D Delaunay triangulation by starting from
a simple 2D Delaunay triangulation enclosing the input, and then iteratively removing eligible triangles
that lie on the boundary of the complex.
In addition, the underlying triangulation---and thus the complex incidentally---is refined
as shrinking proceeds.
Thus, instead of carving from the convex hull of the input data as in alpha shapes, we construct
an entirely new polygon through a Delaunay refinement-like algorithm. The refinement algorithm inserts Steiner points
on the boundary of an offset surface, defined as a level set of the unsigned distance field to the input.

This process both prevents the creation of inner structures within the output and avoids superfluous computations.
In addition, detaching our wrap construction from the geometry and discretization of the input has several advantages:
(1) the underlying data is not restricted to a specific format (polygon soups, segment soups, point sets, etc.)
as all that is required is answering three basic geometric queries: (a) the distance between a point
and the input, (b) the projection of a query point onto the input, (c) an intersection test
between a triangle and the input, and (2) The user has more freedom to trade tightness
to the input for final polygon complexity, as constructing a conservative approximation on a large offset
of the input requires fewer polygon edges.

\subsection aw2_algorithm Algorithm

Initialization. The algorithm is initialized by inserting the four corner vertices
of a loose bounding box into a 2D Delaunay triangulation.
In the 2D Delaunay triangulation of \cgal, all edges are adjacent to two triangle faces.
Each edge of the boundary of the Delaunay triangulation, which coincides with one edge
of the convex hull of the triangulation vertices, is adjacent to a so-called infinite triangle face,
an abstract face connected to the so-called infinite vertex to ensure the aforementioned double-edge adjacency.
Initially, all infinite faces are tagged as outside, and all finite triangle faces are tagged as inside.

Shrink-wrapping. The shrink-wrapping algorithm proceeds by traversing the faces
of the Delaunay triangulation from outside to inside, flood-filling from one face to its adjacent face,
and tagging the adjacent face as outside whenever possible (the term "possible" is specified later).
Flood filling is implemented via a priority queue of Delaunay triangle edges representing
the traversal between the two adjacent faces of the edge, from outside to inside.
These edges are referred to as gates in the following.

Given an outside face and its adjacent inside face, the common edge (i.e., a gate) is said
to be alpha-traversable if its circumradius is larger than the user-defined parameter alpha,
where circumradius refers to the radius of the relating segment's Delaunay ball.
Intuitively, cavities smaller than alpha are not accessible as their gates are not alpha-traversable.

Initialized by the alpha-traversable gates on the convex hull, the priority queue contains only
alpha-traversable gates and is sorted by decreasing order of the circumradius of the gate.
Traversal can be seen as a continuous process that advances along dual Voronoi edges of the gates,
with a pencil of empty balls circumscribing the gate.

\cgalFigureAnchor{aw2_pencil_fig}

\cgalFigureCaptionBegin{aw2_pencil_fig}
(Left) Pencil of empty circles (blue) circumscribing a Delaunay edge (green) in a 2D Delaunay triangulation (black).
From the top triangle circumcenter c1 to the bottom triangle circumcenter c2, the dual Voronoi edge denoted by e (doted red) is the trace of centers of the largest circles that are empty of Delaunay vertex.
(Right) The graph corresponding to the left example. The x-axis corresponds to the position of empty circle centers located on the Voronoi edge e, from c1 to c2. The y-axis is the radius value of the corresponding empty circles. In this case, the minimum radius of this pencil of empty circle is located at the midpoint of the green Delaunay edge.
In our algorithm, a gate (green Delaunay edge) is said to be not alpha-traversable when the minimum radius of the pencil of empty circle is smaller than alpha.
\cgalFigureCaptionEnd

When traversing from an outside face \f$ f_o \f$ to an inside face \f$ f_i \f$ through an alpha-traversable edge \f$ e \f$,
two criteria are tested to prevent the wrapping process from colliding with the input:

(1) We check for an intersection between the dual Voronoi edge of \f$ e \f$, i.e., the segment between
the circumcenters of the two incident faces, and the offset surface, defined as the level set
of unsigned distance field to the input.
If one or several intersections exists, the first intersection point, along the dual Voronoi edge
oriented from outside to inside is inserted into the triangulation as a Steiner point.

(2) If the dual Voronoi edge does not intersect the offset surface but the neighboring face \f$ f_i \f$
intersects the input, we compute the projection of the circumcenter of \f$ f_i \f$
onto the offset surface, and insert it into the triangulation as a Steiner point (which destroys \f$ f_i \f$).

After each of the above Steiner point insertions, all new incident faces are tagged as inside,
and the newly alpha-traversable gates are pushed into the priority queue.

If none of the above two criteria are met, the neighboring face \f$ f_i \f$ is traversed and tagged as outside.
Alpha-Traversable edges of \f$ f_i \f$ that are separating inside from outside faces are pushed as new gates into the priority queue.

Once the queue empties---a process that is guaranteed as edges (and their circumradii) become smaller
due to the insertion of new Steiner points---the construction phase terminates.
The output (multi)polygon is extracted from the Delaunay triangulation as the set of edges
separating inside from outside faces.

The figure below depicts the steps of the algorithm.

\cgalFigureAnchor{aw2_steps_fig}

\cgalFigureCaptionBegin{aw2_steps_fig}
Steps of the shrink-wrapping algorithm in 2D.
The algorithm is initialized by inserting the corners of the loose bounding box of the input (red)
into a Delaunay triangulation, and all finite triangles are tagged inside (grey).
The current gate (green edge) popped out from the queue is alpha-traversable. The triangle adjacent
to the gate is tagged outside when it does not intersect the input, and new alpha-traversable gates
are pushed to the queue. When the adjacent triangle intersects the input, a new Steiner point (large green disc)
is computed and inserted into the triangulation, all neighboring triangles are tagged inside,
new alpha-traversable gates are pushed to the queue, and traversal is resumed.
Grey edges depict the Delaunay triangulation. Blue edges depict the Voronoi diagram.
Pink circles depict the empty circle of radius alpha. The output edges (dark blue) separate inside from outside triangles.
\cgalFigureCaptionEnd

\subsection aw2_guarantees Guarantees

The algorithm is proven to terminate and to produce a set of 1-manifold, simple polygons
that strictly enclose the input data.
The key element to the proof is that we wrap from outside to inside and never allow a face
that intersects the input to be flagged outside.
Furthermore, both criteria that lead to refinement of the triangulation insert Steiner points
that are guaranteed to break the faces in need of refinement and reduce the neighbor edges' circumradii.

Because the main refinement criterion is the insertion of an intersection between a dual Voronoi edge
and an offset of the input, or the projection of a Voronoi vertex onto the offset of the input,
the algorithm has similarities to popular meshing algorithms based on Delaunay filtering
and refinement (see \ref PkgMesh3).

\section aw2_interface Interface

Our algorithm takes as input a set of segments in 2D, provided either as a segment soup or
as a set of polygons, and two user-defined scalar parameters: the alpha and the offset values.
It proceeds by shrink-wrapping and refining a 2D Delaunay triangulation starting from a loose bounding box of the input.
The parameter alpha refers to the size of cavities or holes that cannot be traversed during wrapping,
and hence to the final level of detail, as alpha acts like a sizing field in a common Delaunay
refinement algorithm (\ref PkgMesh3).
The parameter offset refers to the distance between the vertices of the refined triangulation
and the input, so that a large offset translates into a loose enclosing of the input.
This second parameter offers a means to control the trade-off between tightness and complexity.

The main entry point of the component is the global function CGAL::alpha_wrap_2() that generates the alpha wrap;
this function takes as input a point set, a polyline soup, or a polygon soup.
There is no prerequisite on the input connectivity so that it can take inputs
with islands, self-intersections, or overlaps, as well as combinatorial or geometrical degeneracies.

The underlying traits class must be a model of the AlphaWrapTraits_2 concept. It should use
a floating point number type as inexactness is inherent to the algorithm since there is no closed
form description of new vertices on the offset surface.

The output is a multi polygon, i.e., a set of polygons, whose type is chosen by the user,
under the constraint that it must be a model of the MultipolygonWithHoles_2 concept.

A three-dimensional version of this package is also available: \ref PkgAlphaWrap3.

\section aw2_parameters Choosing Parameters

The two parameters of the algorithm impact both the level of detail and complexity of the output wrap.

\subsection aw2_alpha Alpha

The main parameter, alpha, controls whether a Delaunay edge is traversable during shrink-wrapping.
Alpha's main purpose is to control the size
of the empty balls used during wrapping, and thus to determine which features will appear in the output:
indeed, an edge is alpha-traversable if its circumradius is larger than alpha; hence, the algorithm
can only shrink-wrap through straits or holes with diameters larger than alpha.
A second, less direct consequence is that as long as an edge has a circumradius larger than alpha,
the incident inside face will be visited and possibly refined.
Therefore, when the algorithm terminates, all edges have a circumradius smaller than alpha.
This parameter thus also behaves like a sizing criterion on the edges of the output.

\cgalFigureAnchor{aw2_alpha_param_fig}

\cgalFigureCaptionBegin{aw2_alpha_param_fig}
Impact of the alpha parameter on the output.
(Left) The input segment soup, generated from an SVG file. The input
has many self-intersections, non-manifold vertices, superfluous geometric details
and spurious topological structures.
(Middle & Right) This component approximates the input conservatively and produces valid polygons
with different complexity and fidelity to the input, depending on the alpha parameter.
The smaller the alpha, the deeper the shrink-wrapping process will enter cavities.
The alpha parameter is decreasing from left to right, to respectively 1/20, 1/100, and 1/500 of the longest diagonal of the input bounding box.
A large alpha will produce an output less complex but less faithful to the input.
\cgalFigureCaptionEnd

\subsection aw2_offset Offset

The second parameter, the offset distance, controls the distance from the input and thus the definition
of the offset isosurface onto which the vertices of the output polygon are located.
This parameter controls the tightness of the result, which has, in turn, a few consequences.
Firstly, locating vertices away from the input enables the algorithm to generate
a less complex result, especially in convex areas. A trivial example of this behavior would be a very dense
circle-shaped polygon, for which an as-tight-as-possible envelope would also need to be very dense.
Secondly, the farther the isosurface is from the input, the more new points are inserted
through the first criterion (i.e., through intersection with dual Voronoi edge, see Section \ref aw2_algorithm);
thus, the quality of the output improves in terms of angles of the triangle elements.
Finally, and depending on the value of the alpha parameter, a large offset can also offer defeaturing capabilities.
However, using a small offset parameter will tend to better preserve sharp features as projection
Steiner points tend to project onto convex sharp features.

\cgalFigureAnchor{aw2_steiner_fig}

\cgalFigureCaptionBegin{aw2_steiner_fig}
Steiner points.
The projection Steiner points (green) are computed by projecting the triangle circumcenter onto the offset.
The intersection Steiner points (blue) are computed as the first intersection point between the Voronoi edge and the offset.
(Left) When the offset parameter is small, the algorithm produces more projection Steiner points,
which tends to improve the preservation of convex sharp features.
(Right) When the offset parameter is large, the algorithm produces more intersection Steiner points.
\cgalFigureCaptionEnd

By default, we recommend to set the offset parameter to a small fraction of alpha, such that alpha
becomes the main parameter that controls the final level of detail.

The image below illustrates the impact of both parameters.

\cgalFigureAnchor{aw2_param_grid_fig}

\cgalFigureCaptionBegin{aw2_param_grid_fig}
Different alpha and offset values on the bike model.
The x-axis represents the offset value equal to 1/5000, 1/500, 1/50, and 1/5 of the longest diagonal of the input bounding box, from left to right.
The y-axis represents the alpha value equal to 1/500, 1/50, and 1/5 of the longest diagonal of the input bounding box, from bottom to top.
Depending on the alpha value, an offset too small or too large will produce outputs with higher complexity.
For each alpha, the models with lower complexity can be used as a scale-space representations for collision detection, from near to far distances.
\cgalFigureCaptionEnd

\subsection aw2_two_side A Note on "Two-Sided" Wraps

The offset parameter is crucial to our approach because it guarantees that the output is a
set of 1-manifold, simple polygons.
Indeed, and even when the input is a zero-area structure such as a single segment,
the output wrap is a thin domain enclosing the said segment, see \cgalFigureRef{aw2_inputs_fig}.

Users should keep in mind that the wrapping algorithm performs using an unsigned distance field,
and has no means of determining whether it is acting on both sides of a same input segment.
It will thus produce two-sided wraps in the case of holes in the input and
values of alpha smaller than the size of the holes.

\cgalFigureAnchor{aw2_double_sided_fig}

\cgalFigureCaptionBegin{aw2_double_sided_fig}
Wrapping a Bunny in 2D, with decreasing values for alpha.
When alpha is small enough with respect the diameter of the holes, the algorithm generates a two-sided wrap.
\cgalFigureCaptionEnd

\section aw2_examples Examples

\subsection aw2_examples_polylines Wrapping a Set of Polylines

The following example illustrates how to construct the wrap of a soup of 2D segments.
Alpha is set to 1/20 of the bounding box's longest diagonal edge length,
and offset set to 1/30 of alpha (i.e., 1/600 of the bounding box diagonal edge length).

\cgalExample{Alpha_wrap_2/polyline_wrap_2.cpp}

\subsection aw2_examples_polygons Wrapping a Multipolygon

For polygons, we use multipolygons to represent input sets of polygons (possibly with holes).
The following example uses the \link IOStreamWKT WKT file format\endlink to read such input
and wrap it. Note the possible usage of the \ref PkgPolygonRepair package if a pre-emptive
repair of the polygons is desired.

\cgalExample{Alpha_wrap_2/polygon_wrap_2.cpp}

\subsection aw2_examples_points Wrapping a Point Cloud

Finally, the following example demonstrates how to wrap a 2D point set constructed from the projection
of an input 3D point cloud.

\cgalExample{Alpha_wrap_2/point_set_wrap_2.cpp}

*/

}

Alpha Wrap 2 Doc Alpha Wrap 2 Examples (`Alpha_wrap_2/doc/Alpha_wrap_2/examples.txt`) Copy Section

/*!
\example Alpha_wrap_2/polygon_wrap_2.cpp
\example Alpha_wrap_2/polyline_wrap_2.cpp
\example Alpha_wrap_2/triangle_soup_wrap_2.cpp
\example Alpha_wrap_2/point_set_wrap_2.cpp
*/

Alpha Wrap 3 Doc Alpha Wrap 3 PackageDescription (`Alpha_wrap_3/doc/Alpha_wrap_3/PackageDescription.txt`) Copy Section

/// \defgroup PkgAlphaWrap3Ref Reference Manual

/// \defgroup AW3_free_functions_grp Free Functions
/// Functions to create a wrap from point clouds, triangle soups, and triangle meshes.
/// \ingroup PkgAlphaWrap3Ref

/*!
\addtogroup PkgAlphaWrap3Ref
\cgalPkgDescriptionBegin{3D Alpha Wrapping,PkgAlphaWrap3}
\cgalPkgPicture{alpha_wrap_3.jpg}
\cgalPkgSummaryBegin
\cgalPkgAuthors{Pierre Alliez, David Cohen-Steiner, Michael Hemmer, Cédric Portaneri, and Mael Rouxel-Labbé}
\cgalPkgDesc{This component takes a 3D triangle mesh, a triangle soup, or a point set as input, and generates
a valid triangulated surface mesh that strictly contains the input (watertight, intersection-free
and 2-manifold). The algorithm proceeds by shrink-wrapping
and refining a 3D Delaunay triangulation starting from a loose bounding box of the input.
Two user-defined parameters, alpha and offset, offer control over the maximum size
of cavities where the shrink-wrapping process can enter, and the tightness
of the final surface mesh to the input, respectively. Once combined, these parameters
provide a means to trade fidelity to the input for complexity of the output.}
\cgalPkgManuals{Chapter_3D_Alpha_wrapping,PkgAlphaWrap3Ref}
\cgalPkgSummaryEnd
\cgalPkgShortInfoBegin
\cgalPkgSince{5.5}
\cgalPkgDependsOn{\ref PkgTriangulation3 and \ref PkgPolygonMeshProcessing}
\cgalPkgBib{cgal:achpr-aw3}
\cgalPkgLicense{\ref licensesGPL "GPL"}
\cgalPkgShortInfoEnd
\cgalPkgDescriptionEnd

\cgalClassifedRefPages

\cgalCRPSection{Functions}

• \link AW3_free_functions_grp CGAL::alpha_wrap_3() \endlink
  */

Alpha Wrap 3 Doc Alpha Wrap 3 Alpha Wrap 3 (`Alpha_wrap_3/doc/Alpha_wrap_3/alpha_wrap_3.txt`) Copy Section

namespace CGAL {

/*!

\mainpage User Manual
\anchor Chapter_3D_Alpha_wrapping
\cgalAutoToc

\authors Pierre Alliez, David Cohen-Steiner, Michael Hemmer, Cédric Portaneri, Mael Rouxel-Labbé

Note: a two-dimensional version of this package is also available: \ref PkgAlphaWrap2.

\section aw3_introduction Introduction

Various tasks in geometric modeling and processing require 3D objects represented as valid surface meshes,
where "valid" refers to meshes that are watertight, intersection-free, orientable, and 2-manifold.
Such representations offer well-defined notions of interior/exterior and geodesic neighborhoods.

3D data are usually acquired through measurements followed by reconstruction, designed by humans,
or generated through imperfect automated processes.
As a result, they can exhibit a wide variety of defects including gaps, missing data,
self-intersections, degeneracies such as zero-volume structures, and non-manifold features.

Given the large repertoire of possible defects, many methods and data structures have been proposed
to repair specific defects, usually with the goal of guaranteeing specific properties in the repaired 3D model.
Reliably repairing all types of defects is notoriously difficult and is often an ill-posed problem
as many valid solutions exist for a given 3D model with defects.
In addition, the input model can be overly complex with unnecessary geometric details,
spurious topological structures, nonessential inner components, or excessively fine discretizations.
For applications such as collision avoidance, path planning, or simulation,
getting an approximation of the input can be more relevant than repairing it.
Approximation herein refers to an approach capable of filtering out inner structures,
fine details and cavities, as well as wrapping the input within a user-defined offset margin.

Given an input 3D geometry, we address the problem of computing a conservative approximation,
where conservative means that the output is guaranteed to strictly enclose the input.
We seek unconditional robustness in the sense that the output mesh should be valid (oriented,
2-manifold, and without self-intersections), even for raw input with many defects
and degeneracies.
The default input is a soup of 3D triangles, but the generic interface leaves the door open
to other types of finite 3D primitives such as triangle soups and point sets.

\cgalFigureAnchor{aw3_input_1_fig}

\cgalFigureCaptionBegin{aw3_input_1_fig}
Shrink-wrapping output from a triangle soup, with many intersections and gaps.
From left to right, input model, output wrap, and superposition.
\cgalFigureCaptionEnd

\cgalFigureAnchor{aw3_input_2_fig}

\cgalFigureCaptionBegin{aw3_input_2_fig}
Dealing with non-manifold features and degeneracies.
From left to right, a non-manifold vertex, self-intersecting faces and two adjacent triangles
representing a zero-volume structure.
The algorithm handles these cases by wrapping an offset of the input.
\cgalFigureCaptionEnd

\section aw3_definition Approach

Many approaches have been devised to enclose a 3D model within a volume, featuring different balances
between the runtime and quality (i.e., tightness) of the approximation.
Within the simplest cases, an axis-aligned or oriented bounding box clearly satisfies some desired properties;
however, the approximation error is uncontrollable and often very large.
Computing the convex hull of the input also matches some of the desired properties
and improves the quality of the result, albeit at the price of increasing the runtime.
However, the approximation remains crude, especially in the case of several components.

The convex hull is, in fact, a special case of alpha shapes (\ref Chapter_3D_Alpha_Shapes).
Mathematically, the alpha shape is a subcomplex of the Delaunay triangulation, with simplicies
being part of the complex depending on the size of their minimal (empty) Delaunay ball.
Intuitively, constructing 3D alpha shapes can be thought of as carving 3D space with an empty ball
of user-defined radius alpha.
Alpha shapes yield provable, good piecewise-linear approximations of a shape \cgalCite{bb-srmua-97t},
but are defined on point sets, whereas we wish to deal with more general input data, such as triangle soups.
Even after sampling the triangle soup, alpha shapes do not guarantee to be conservative for any alpha.
Finally, inner structures are also carved within the volumes, instead of being filtered out.

Inspired by alpha shapes, we replace the above notion of carving by shrink-wrapping:
we iteratively construct a subcomplex of a 3D Delaunay triangulation by starting from
a simple 3D Delaunay triangulation enclosing the input, and then iteratively removing eligible tetrahedra
that lie on the boundary of the complex.
In addition, the underlying triangulation---and thus the complex incidentally---is refined
as shrinking proceeds.
Thus, instead of carving from the convex hull of the input data as in alpha shapes, we construct
an entirely new mesh through a Delaunay refinement-like algorithm. The refinement algorithm inserts Steiner points
on the boundary of an offset volume, defined as a level set of the unsigned distance field to the input.

This process both prevents the creation of inner structures within the output and avoids superfluous computations.
In addition, detaching our mesh construction from the geometry and discretization of the input has several advantages:
(1) the underlying data is not restricted to a specific format (triangle soups, polygon soups, point clouds, etc.)
as all that is required is answering three basic geometric queries: (a) the distance between a point
and the input, (b) the projection of a query point onto the input, (c) an intersection test
between a tetrahedron and the input, and (2) The user has more freedom to trade tightness
to the input for final mesh complexity, as constructing a conservative approximation on a large offset
of the input requires fewer mesh elements.

\subsection aw3_algorithm Algorithm

Initialization. The algorithm is initialized by inserting the eight corner vertices
of a loose bounding box into a 3D Delaunay triangulation.
In the 3D Delaunay triangulation of \cgal, all triangle facets are adjacent to two tetrahedron cells.
Each facet of the boundary of the Delaunay triangulation, which coincides with one facet
of the convex hull of the triangulation vertices, is adjacent to a so-called infinite tetrahedron cell,
an abstract cell connected to the so-called infinite vertex to ensure the aforementioned double-facet adjacency.
Initially, all infinite cells are tagged as outside, and all finite tetrahedron cells are tagged as inside.

Shrink-wrapping. The shrink-wrapping algorithm proceeds by traversing the cells
of the Delaunay triangulation from outside to inside, flood-filling from one cell to its adjacent cell,
and tagging the adjacent cell as outside whenever possible (the term possible is specified later).
Flood filling is implemented via a priority queue of Delaunay triangle facets representing
the traversal between the two adjacent cells of the facet, from outside to inside.
These triangle facets are referred to as gates in the following.

Given an outside cell and its adjacent inside cell, the common facet (i.e., a gate) is said
to be alpha-traversable if its circumradius is larger than the user-defined parameter alpha,
where circumradius refers to the radius of the relating triangle's Delaunay ball.
Intuitively, cavities smaller than alpha are not accessible as their gates are not alpha-traversable.

Initialized by the alpha-traversable gates on the convex hull, the priority queue contains only
alpha-traversable gates and is sorted by decreasing order
of the circumradius of the gate.
Traversal can be seen as a continuous process that advances along dual Voronoi edges of the gates,
with a pencil of empty balls circumscribing the gate.

\cgalFigureAnchor{aw3_pencil_fig}

\cgalFigureCaptionBegin{aw3_pencil_fig}
(Left) Pencil of empty circles (blue) circumscribing a Delaunay edge (green) in a 2D Delaunay triangulation (black).
From the top triangle circumcenter c1 to the bottom triangle circumcenter c2, the dual Voronoi edge denoted by e (doted red) is the trace of centers of the largest circles that are empty of Delaunay vertex.
(Right) The graph corresponding to the left example. The x-axis corresponds to the position of empty circle centers located on the Voronoi edge e, from c1 to c2. The y-axis is the radius value of the corresponding empty circles. In this case, the minimum radius of this pencil of empty circle is located at the midpoint of the green Delaunay edge.
In our algorithm, a gate (green Delaunay edge) is said to be not alpha-traversable when the minimum radius of the pencil of empty circle is smaller than alpha.
\cgalFigureCaptionEnd

When traversing from an outside cell \f$ c_o \f$ to an inside cell \f$ c_i \f$ through an alpha-traversable facet \f$ f \f$,
two criteria are tested to prevent the wrapping process from colliding with the input:

(1) We check for an intersection between the dual Voronoi edge of \f$ f \f$, i.e. the segment between
the circumcenters of the two incident cells, and the offset surface, defined as the level set
of unsigned isosurface to the input.
If one or several intersections exists, the first intersection point, along the dual Voronoi edge
oriented from outside to inside is inserted into the triangulation as a Steiner point.

(2) If the dual Voronoi edge does not intersect the offset surface but the neighboring cell \f$ c_i \f$
intersects the input, we compute the projection of the circumcenter of \f$ c_i \f$
onto the offset surface, and insert it into the triangulation as a Steiner point (which destroys \f$ c_i \f$).

After each of the above Steiner point insertions, all new incident cells are tagged as inside,
and the newly alpha-traversable gates are pushed into the priority queue.

If none of the above two criteria are met, the neighboring cell \f$ c_i \f$ is traversed and tagged as outside.
Alpha-Traversable facets of \f$ c_i \f$ that are separating inside from outside cells are pushed as new gates into the priority queue.

Once the queue empties---a process that is guaranteed as facets (and their circumradii) become smaller
due to the insertion of new Steiner points---the construction phase terminates.
The output triangle surface mesh is extracted from the Delaunay triangulation as the set of facets
separating inside from outside cells.

The figure below depicts the steps of the algorithm in 2D.

\cgalFigureAnchor{aw3_steps_fig}

\cgalFigureCaptionBegin{aw3_steps_fig}
Steps of the shrink-wrapping algorithm in 2D.
The algorithm is initialized by inserting the corners of the loose bounding box of the input (red)
into a Delaunay triangulation, and all finite triangles are tagged inside (grey).
The current gate (green edge) popped out from the queue is alpha-traversable. The triangle adjacent
to the gate is tagged outside when it does not intersect the input, and new alpha-traversable gates
are pushed to the queue. When the adjacent triangle intersects the input, a new Steiner point (large green disc)
is computed and inserted into the triangulation, all neighboring triangles are tagged inside,
new alpha-traversable gates are pushed to the queue, and traversal is resumed.
Grey edges depict the Delaunay triangulation. Blue edges depict the Voronoi diagram.
Pink circles depict the empty circle of radius alpha. The output edges (dark blue) separate inside from outside triangles.
\cgalFigureCaptionEnd

\subsection aw3_guarantees Guarantees

The algorithm is proven to terminate and to produce a 2-manifold triangulated surface mesh
that strictly encloses the input data.
The key element to the proof is that we wrap from outside to inside and never allow a cell
that intersects the input to be flagged outside.
Furthermore, both criteria that lead to refinement of the triangulation insert Steiner points
that are guaranteed to break the cells in need of refinement and reduce the neighbor facets circumradii.

Because the main refinement criterion is the insertion of an intersection between a dual Voronoi edge
and an offset of the input, or the projection of a Voronoi vertex onto the offset of the input,
the algorithm has similarities to popular meshing algorithms based on Delaunay filtering
and refinement (see \ref Chapter_3D_Mesh_Generation).

\section aw3_interface Interface

Our algorithm takes as input a set of triangles in 3D, provided either as a triangle soup or
as a triangle surface mesh, and two user-defined scalar parameters: the alpha and the offset values.
It proceeds by shrink-wrapping and refining a 3D Delaunay triangulation starting from a loose bounding box of the input.
The parameter alpha refers to the size of cavities or holes that cannot be traversed during wrapping,
and hence to the final level of detail, as alpha acts like a sizing field in a common Delaunay
refinement algorithm (\ref Chapter_3D_Mesh_Generation).
The parameter offset refers to the distance between the vertices of the refined triangulation
and the input, so that a large offset translates into a loose enclosing of the input.
This second parameter offers a means to control the trade-off between tightness and complexity.

The main entry point of the component is the global function CGAL::alpha_wrap_3() that generates the alpha wrap;
this function takes as input a polygon soup or a polygon mesh.
There is no prerequisite on the input connectivity so that it can take an arbitrary triangle soup,
with islands, self-intersections, or overlaps, as well as combinatorial or geometrical degeneracies.

The underlying traits class must be a model of the Kernel concept. It should use
a floating point number type as inexactness is inherent to the algorithm since there is no closed
form description of new vertices on the offset surface.

The output is a triangle surface mesh whose type is chosen by the user, under the constraint
that it must be a model of the MutableFaceGraph concept.

\section aw3_parameters Choosing Parameters

The two parameters of the algorithm impact both the level of detail and complexity of the output mesh.

\subsection aw3_alpha Alpha

The main parameter, alpha, controls whether a Delaunay facet is traversable during shrink-wrapping.
Alpha's main purpose is to control the size
of the empty balls used during wrapping, and thus to determine which features will appear in the output:
indeed, a facet is alpha-traversable if its circumradius is larger than alpha; hence, the algorithm
can only shrink-wrap through straits or holes with diameters larger than alpha.
A second, less direct consequence is that as long as a facet has a circumradius larger than alpha,
the incident inside cell will be visited and possibly refined.
Therefore, when the algorithm terminates, all facets have a circumradius smaller than alpha.
This parameter thus also behaves like a sizing criterion on the triangle facets of the output.

\cgalFigureAnchor{aw3_alpha_param_fig}

\cgalFigureCaptionBegin{aw3_alpha_param_fig}
Impact of the alpha parameter on the output.
(Left) The input triangle mesh, generated by surface reconstruction from a raw point cloud,
has many non-manifold edges and vertices, superfluous geometric details and spurious topological structures.
(Right) This component approximates the input conservatively and produces valid meshes with different
complexity and fidelity to the input, depending on the alpha parameter.
The smaller the alpha, the deeper the shrink-wrapping process will enter cavities.
The alpha parameter is decreasing from left to right, to respectively 1/50, 1/100 and 1/300 of the longest diagonal of the input bounding box.
A large alpha will produce an output less complex but less faithful to the input.
\cgalFigureCaptionEnd

\subsection aw3_offset Offset

The second parameter, the offset distance, controls the distance from the input and thus the definition
of the offset isosurface onto which the vertices of the output mesh are located.
This parameter controls the tightness of the result, which has, in turn, a few consequences.
Firstly, locating vertices away from the input enables the algorithm to generate
a less complex mesh, especially in convex areas. A trivial example of this behavior would be a very dense mesh
of a sphere, for which an as-tight-as-possible envelope would also be very dense.
Secondly, the farther the isosurface is from the input, the more new points are inserted
through the first criterion (i.e., through intersection with dual Voronoi edge, see Section \ref aw3_algorithm);
thus, the quality of the output improves in terms of angles of the triangle elements.
Finally, and depending on the value of the alpha parameter, a large offset can also offer defeaturing capabilities.
However, using a small offset parameter will tend to better preserve sharp features as projection
Steiner points tend to project onto convex sharp features.

\cgalFigureAnchor{aw3_offset_param_fig}

\cgalFigureCaptionBegin{aw3_offset_param_fig}
Impact of the offset parameter on the output.
(Left) Input mesh generated by meshing a NURBS CAD model in parameter space.
(Right) The smaller the offset, the closest sample points are to the input.
The offset parameter is decreasing from left to right, to respectively 1/50, 1/200 and 1/1000 of the longest diagonal of the input bounding box.
The alpha parameter is equal to 1/50 of the longest diagonal of the input bounding box for all level of details.
A larger offset will produce an output less complex with better triangle quality.
However, the sharp features (red edges) are well-preserved when the offset parameter is small.
\cgalFigureCaptionEnd

\cgalFigureAnchor{aw3_steiner_fig}

\cgalFigureCaptionBegin{aw3_steiner_fig}
Steiner points.
The projection Steiner points (green) are computed by projecting the triangle circumcenter onto the offset.
The intersection Steiner points (blue) are computed as the first intersection point between the Voronoi edge and the offset.
(Left) When the offset parameter is small, the algorithm produces more projection Steiner points,
which tends to improve the preservation of convex sharp features.
(Right) When the offset parameter is large, the algorithm produces more intersection Steiner points,
which tends to generate triangles with better quality in terms of angles, in 3D.
\cgalFigureCaptionEnd

By default, we recommend to set the offset parameter to a small fraction of alpha, such that alpha
becomes the main parameter that controls the final level of detail.

The image below illustrates the impact of both parameters.

\cgalFigureAnchor{aw3_param_grid_fig}

\cgalFigureCaptionBegin{aw3_param_grid_fig}
Different alpha and offset values on the bike model (533,000 triangles).
The x-axis represents the offset value equal to 1/5000, 1/2000, 1/500, 1/200, 1/50, 1/20 and 1/5 of the longest diagonal of the input bounding box, from left to right.
The y-axis represents the alpha value equal to 1/300, 1/100, 1/50, 1/20 and 1/5 of the longest diagonal of the input bounding box, from bottom to top.
The numbers below each level of detail represents their number of triangles.
Depending on the alpha value, an offset too small or too large will produce output mesh with higher complexity.
For each alpha, the models with lower complexity can be used as a scale-space representations for collision detection, from near to far distances.
\cgalFigureCaptionEnd

\subsection aw3_two_side A Note on "Two-Sided" Wraps

The offset parameter is crucial to our approach because it guarantees that the output is a closed,
2-manifold surface mesh.
Indeed, and even when the input is a zero-volume structure such as a single 3D triangle,
the output wrap is a thin volume enclosing the said triangle \cgalFigureRef{aw3_input_2_fig}.

Users should keep in mind that the wrapping algorithm has no means of determining whether it is acting on the inside or the outside
of the unsigned distance field, and will thus produce two-sided wraps in the case of holes in the input
and values of alpha smaller than the size of the holes.

\cgalFigureAnchor{aw3_double_sided_fig}

\cgalFigureCaptionBegin{aw3_double_sided_fig}
Two-sided wrap.
(Left) Wrapping a Bunny in 2D, with decreasing values for alpha.
(Right) Wrapping a defect-laden Bunny in 3D. The rightmost column depicts a clipped visualization
of the inside. When alpha is small enough with respect the diameter of the holes, the algorithm generates a two-sided wrap.
\cgalFigureCaptionEnd

\section aw3_performance Performance

The charts below plots the computation times of the wrapping algorithm on the Thingi10k dataset, as well as the complexity of the output triangle mesh.

\cgalFigureAnchor{aw3_bench_fig}

\cgalFigureCaptionBegin{aw3_bench_fig}
Execution times and output complexity for different values of alpha on the Thingi10k data set.
Alpha increases from 1/20 to 1/200 of the length of bounding box diagonal.
The x-axis represents the complexity of the output wrap mesh in number of triangle facets.
The y-axis represents the total computation time, in seconds.
The color and diameter of the dots represent the number of faces in the input triangle soup,
ranging from 10 (green) to 3154000 (blue).
\cgalFigureCaptionEnd

\section aw3_examples Examples

Here is an example with an input triangle mesh, with alpha set to 1/20 of the bounding box's longest diagonal edge length,
and offset set to 1/30 of alpha (i.e., 1/600 of the bounding box diagonal edge length).

\cgalExample{Alpha_wrap_3/triangle_mesh_wrap.cpp}

Some triangle soups might not be representable as a mesh due to non-manifoldness or incompatible orientations.
Such triangle soup is nevertheless a valid input for the wrapping algorithm, as illustrated
in the following example.

\cgalExample{Alpha_wrap_3/triangle_soup_wrap.cpp}

Here is an example with a point cloud.

\cgalExample{Alpha_wrap_3/point_set_wrap.cpp}

*/

}

Alpha Wrap 3 Doc Alpha Wrap 3 Examples (`Alpha_wrap_3/doc/Alpha_wrap_3/examples.txt`) Copy Section

/*!
\example Alpha_wrap_3/triangle_mesh_wrap.cpp
\example Alpha_wrap_3/triangle_soup_wrap.cpp
\example Alpha_wrap_3/point_set_wrap.cpp
*/

Apollonius Graph 2 Doc Apollonius Graph 2 Apollonius Graph 2 (`Apollonius_graph_2/doc/Apollonius_graph_2/Apollonius_graph_2.txt`) Copy Section

namespace CGAL {
/*!

\mainpage User Manual
\anchor Chapter_2D_Apollonius_Graphs
\anchor chapterapollonius2
\cgalAutoToc
\authors Menelaos Karavelas and Mariette Yvinec

This chapter describes the two-dimensional Apollonius graph
of \cgal. We start with a few definitions in
Section \ref secapollonius2definitions.
The software design of the 2D Apollonius graph package is described
in Section \ref secapollonius2design.
In Section \ref secapollonius2traits we discuss the geometric
traits of the 2D Apollonius graph package and in Section
\ref secapollonius2hierarchy the Apollonius graph hierarchy, a data
structure suitable for fast nearest neighbor queries, is briefly
described.

\section secapollonius2definitions Definitions

\cgalFigureBegin{figapollonius,apollonius_diagram.png,apollonius_graph.png}
The Apollonius diagram (left) and its dual the Apollonius graph (right).
\cgalFigureEnd

The 2D Apollonius graph class of \cgal is designed to compute the
dual of the Apollonius diagram or, as it is also known, the
Additively weighted Voronoi diagram. The algorithm that has been
implemented is dynamic, which means that we can perform insertions and
deletions online. The corresponding \cgal class is called
Apollonius_graph_2<ApolloniusGraphTraits_2,ApolloniusGraphDataStructure_2>
and will be discussed in more detail in the sequel. The interested
reader may want to refer to the paper by Karavelas and Yvinec
\cgalCite{cgal:ky-dawvd-02} for the general idea as well as the details of the
algorithm implemented.

Before describing the details of the implementation we make a brief
introduction to the theory of Apollonius diagrams.
The Apollonius diagram is defined over a set of sites
\f$ P_i=(c_i,w_i)\f$, \f$ i=1,\ldots,n\f$, where \f$ c_i\f$ is the point and \f$ w_i\f$
the weight of \f$ P_i\f$. It is a subdivision of the plane into connected
regions, called cells, associated with the sites (see
\cgalFigureRef{figapollonius} (left)). The cell of a
site \f$ P_i\f$ is the locus of points on the plane that are
closer to \f$ P_i\f$ than any other site \f$ P_j\f$, \f$ j\neq i\f$.
The distance \f$ \delta(x, P_i)\f$ of a point \f$ x\f$ in the plane to a
site \f$ P_i\f$ is defined as:
\f[ \delta(x,P_i)=|x-c_i|-w_i, \f]
where \f$ |\cdot|\f$ denotes the Euclidean norm.
It can easily be seen that it is a generalization of the Voronoi
diagram for points, which can actually be obtained if all the weights
\f$ w_i\f$ are equal. Unlike the case of points, however, it is
possible that a site \f$ P_i\f$ might have an empty cell. This
can also happen in the case of the power diagram, whose dual is the
regular triangulation (see Section
\ref Section_2D_Triangulations_Regular ). If this is
the case we call the site hidden (these are the black
circles in \cgalFigureRef{figapollonius} ). A site which is not
hidden will be referred to as visible.

If all weights \f$ w_i\f$ are non-negative, the Apollonius
diagram can be viewed as the Voronoi diagram of the set of circles
\f$ {P_1,\ldots, P_n}\f$, where \f$ c_i\f$ is the center of the circle \f$ P_i\f$
and \f$ w_i\f$ its radius. If the weights are allowed to be negative,
we need to go to 3D in order to explain what the Apollonius diagram
means geometrically. We identify the 2D Euclidean plane with the
\f$ xy\f$-plane in 3D. Then the Voronoi diagram of a set of points can be
seen as the vertical projection on the \f$ xy\f$-plane of the lower
envelope of a set of 3D cones defined as follows: for each point \f$ p\f$
in the set of 2D points we have a cone \f$ C_p\f$ whose apex is the point
\f$ p\f$. The axis of
\f$ C_p\f$ is a line parallel to the \f$ z\f$-axis passing through \f$ p\f$, the
angle of \f$ C_p\f$ is \f$ 45^\circ\f$ and, finally \f$ C_p\f$ is facing in the
positive \f$ z\f$-direction (that is, \f$ C_p\f$ is contained in the positive
\f$ z\f$-halfspace).
The Apollonius diagram corresponds to shifting the
apexes of these cones in the \f$ z\f$-direction by a quantity equal to the
weight. Sites with negative weight will give rise to
cones whose apex is in the negative \f$ z\f$-halfspace and sites
with positive weight will give rise to cones whose apex is in the
positive \f$ z\f$-halfspace. In a manner analogous to the case of points,
the Apollonius diagram can then be defined as the vertical projection
on the \f$ xy\f$-plane of the lower envelope of the set of shifted cones.
Notice that when all apexes are translated along the \f$ z\f$-direction by
the same amount, the projection of the lower envelope of the set of
cones does not change. In particular, we can translate all cones by a
large enough amount so that all apexes are in the positive
\f$ z\f$-halfspace. Algebraically, this means that the Apollonius diagram
does not change if we add to all weights the same quantity, which in
particular, implies that we can assume without loss of generality that
all weights are positive. Given the observations above and in order to
simplify our discussion of Apollonius diagrams, we will, from now on,
assume that all weights are positive, and we will refer to the
sites as circles.

The Apollonius diagram is a planar graph, and so is its dual, the
Apollonius graph. There are many ways to embed it on the plane and one
such way is shown in \cgalFigureRef{figapollonius} (right).
The Apollonius graph is uniquely defined once we have
the Apollonius diagram. If the circles are in general position
(see precise definition below), then the Apollonius graph is a graph
with triangular faces away from
the convex hull of the set of circles (by triangular we mean that
every face has exactly three edges). Near the convex hull we may
have some spikes (i.e., vertices of degree 1). To unify our approach
and handling of the Apollonius graph we add to the set of (finite)
circles a fictitious circle at infinity, which we call the
site at infinity. We can then connect all vertices of the outer
face of the Apollonius graph to the site at infinity which gives us
a graph with the property that all of its faces are now
triangular. However, the Apollonius graph is not a triangulation for
two main reasons: we cannot always embed it on the plane with straight
line segments that yield a triangulation and, moreover, we may have two
faces of the graph that have two edges in common, which is not allowed
in a triangulation. Both of these particularities appear when we
consider the Apollonius graph of the set of circles in
\cgalFigureRef{figapollonius}.

We would like to finish our brief introduction to the theory of
Apollonius graphs by discussing the concept of general position. We say
that a set of circles is in general position if no two triplets of
circles have the same tritangent circle. This statement is rather
technical and it is best understood in the context of points. The
equivalent statement for points is that we have no two triplets of
points that define the same circumcircle, or equivalently that no
four points are co-circular. The statement about general position made
above is a direct generalization of the (much simpler to understand)
statement about points. On the contrary, when we have circles in
degenerate position, the Apollonius graph has faces with more than
three edges on their boundary. We can get a triangulated version of
the graph by simply triangulating the corresponding faces in an
arbitrary way. In fact the algorithm that has been implemented in
\cgal has the property that it always returns a valid
triangulated version of the Apollonius graph. By valid we mean
that it contains the actual Apollonius graph (i.e., the actual dual of
the Apollonius diagram) and whenever there are faces with more than
three faces then they are triangulated. The way that they are
triangulated depends on the order of insertion and deletion of the
circles in the diagram.

One final point has to be made about hidden circles. First of all we
would like to be more precise about our definition of hidden circles:
we say that a circle is hidden if its cell has empty interior. This
definition allows us to guarantee that all visible circles have
cells that are two-dimensional regions.
Geometrically the fact that a circle is hidden means that it is
contained in the closure of the disk of another circle (see again
\cgalFigureRef{figapollonius} ). Note that a circle contained in the union
of several disks, but not in the closure of any one of them, is not
hidden.

Hidden circles pose an additional
difficulty to our algorithm and software design. Since we allow
circles to be inserted and deleted at will, it is possible that a
circle that was hidden at some point in time, may become visible at
a later point in time; for example this can happen if we delete the
circle that hides it. For this purpose we store hidden circles and
have them reappear when they become visible. We will discuss this
issue in detail below. For the time being it suffices to say that the
user has the ability to control this behavior. More specifically it is
possible to discard the circles that become hidden. This choice is
totally natural when for example we expect to do only insertions,
since in this case a circle that becomes hidden will never
reappear. On the other hand if deletions are expected as well, then we
lose the ability to have the hidden circles reappear.

Degenerate Dimensions.

The dimension of the Apollonius graph is in general 2. The exceptions
to this rule are as follows:

\section secapollonius2design Software Design

The 2D Apollonius graph class
Apollonius_graph_2<ApolloniusGraphTraits_2,ApolloniusGraphDataStructure_2>
follows the design of the triangulation packages of \cgal. It is
parametrized by two arguments:

The latter separation is exhibited by the two template parameters of
the Arrangement_2 class template; their description follows.

In this section we always use Arr_non_caching_segment_traits_2 as
our traits-class model in order to construct arrangements of line
segments. In succeeding sections we also use Arr_segment_traits_2
as our traits-class model. These two traits trade computation time
and storage space. The latter stores the underlying line of every
segment of the arrangement to expedite certain operations on the
arrangement segments. In Section \ref aos_sec-unbounded we use
Arr_linear_traits_2 to construct arrangements of linear curves
(i.e., lines, rays, and line segments). The \ref
PkgArrangementOnSurface2 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 aos_sec-geom_traits.

The function template print_arrangement_size() listed below, and
defined in the header file Arr_print.h, prints out quantitative
measures of a given arrangement. While in what follows it is used only
by examples, it demonstrates well the use of the member functions
\link Arrangement_on_surface_2::number_of_vertices()
number_of_vertices()\endlink, \link
Arrangement_on_surface_2::number_of_edges()
number_of_edges()\endlink, and \link
Arrangement_on_surface_2::number_of_faces()
number_of_faces()\endlink, which return the number of vertices,
edges, and faces of an arrangement, respectively.

\anchor lst_paz
\code{.cpp}
template
void print_arrangement_size(const Arrangement& arr) {
std::cout << "The arrangement size:\n"
<< " |V| = " << arr.number_of_vertices()
<< ", |E| = " << arr.number_of_edges()
<< ", |F| = " << arr.number_of_faces() << std::endl;
}
\endcode

You can also obtain the number of halfedges of an arrangement using
the member function \link Arrangement_on_surface_2::number_of_halfedges()
number_of_halfedges()\endlink. Recall that the number of halfedges is
always twice the number of edges.

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

The simple program listed below constructs an arrangement of three
connected line segments forming a triangle. It uses the
Cartesian kernel with an integral-number type to instantiate
the Arr_non_caching_segment_traits_2<Kernel> class template. The
resulting arrangement consists of two faces, a bounded triangular face
and the unbounded face. Constructing and maintaining arrangements
using limited-precision numbers, such as int, works properly only
under severe restrictions, which in many cases render the program not
very useful. In this example, however, the points are far apart, and
constructions of new geometric objects do not occur. Thus, it is safe
to use int after all. The program constructs an arrangement induced
by three line segments that are pairwise disjoint in their interior,
prints out the number of faces, and ends. It uses the
\link insert(Arrangement_2&, InputIterator, InputIterator) insert()\endlink
free-function, which inserts the segments into the
arrangement; see Section \ref arr_secgl_funcs. It uses the member
function \link Arrangement_on_surface_2::number_of_faces
number_of_faces()\endlink to obtain the number of faces (two in this
case). We give more elaborate examples in the rest of this
chapter. The programs in those examples rely on computing with numbers
of arbitrary precision, which guarantees robust execution and correct
results.

\code{.cpp}
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_non_caching_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

using Number_type = int;
using Kernel = CGAL::Cartesian;
using Traits = CGAL::Arr_non_caching_segment_traits_2;
using Point = Traits_2::Point_2;
using Segment = Traits_2::X_monotone_curve_2;
using Arrangement = CGAL::Arrangement_2;

int main() {
Arrangement arr;
Point p1(1, 1), p2(1, 2), p3(2, 1);
Segment cv[] = {Segment(p1, p2), Segment(p2, p3), Segment(p3, p1)};
CGAL::insert(arr, &cv[0], &cv[sizeof(cv)/sizeof(Segment)]);
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 \dcel,
which stores three containers of vertices, halfedges and faces; thus,
the Arrangement_2 class template supplies iterator types for these
containers, respectively. For example, if arr is an Arrangement_2
object, the calls \link Arrangement_on_surface_2::vertices_begin()
arr.vertices_begin()\endlink and \link
Arrangement_on_surface_2::vertices_end arr.vertices_end()\endlink
return iterators of the nested \link
Arrangement_on_surface_2::Vertex_iterator Vertex_iterator\endlink
type that define the valid range of vertices of the arrangement
arr. The value type of this iterator is \link
Arrangement_on_surface_2::Vertex Vertex\endlink. Moreover, the
vertex-iterator type is convertible to \link
Arrangement_on_surface_2::Vertex_handle Vertex_handle\endlink, 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.
See Chapter \ref Chapter_Handles_Ranges_and_Circulators
"Handles and Circulators" for more information on \cgal handles.

In addition to the iterators for arrangement vertices, halfedges, and
faces, the arrangement class also provides an iterator for edges,
namely \link Arrangement_on_surface_2::Edge_iterator
Edge_iterator\endlink. The value type of this iterator is \link
Arrangement_on_surface_2::Halfedge Halfedge\endlink, which is the
same as the value type of \link
Arrangement_on_surface_2::Halfedge_iterator
Halfedge_iterator\endlink. The calls \link
Arrangement_on_surface_2::edges_begin() arr.edges_begin()\endlink
and \link Arrangement_on_surface_2::edges_end()
arr.edges_end()\endlink return iterators that define the valid range
of arrangement edges. This range consists of half the number of
halfedges of the arrangement, as every twin halfedges has one
representative in this range.

All iterator, circulator\cgalFootnote{A circulator is used to
traverse a circular list, such as the list of halfedges incident to a
vertex.} and handle types also have non-mutable (const)
counterparts. These non-mutable iterator types are useful for
traversing an arrangement with the promise to keep it unchanged. For
example, the arrangement has a non-constant member function called
Arrangement_on_surface_2::vertices_begin() that returns a \link
Arrangement_on_surface_2::Vertex_iterator Vertex_iterator\endlink
object and another const member function that returns a \link
Arrangement_on_surface_2::Vertex_const_iterator
Vertex_const_iterator\endlink 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, \link
Arrangement_on_surface_2::Vertex_handle Vertex_handle\endlink can be
readily converted into a \link
Arrangement_on_surface_2::Vertex_const_handle
Vertex_const_handle\endlink, but not the other way around.

Conversions of non-mutable handles to the corresponding mutable
handles are nevertheless possible. They can be performed using the
overloaded member function \link
Arrangement_on_surface_2::non_const_handle()
non_const_handle()\endlink. There are three variants that accept a
non-mutable handle to a vertex, a halfedge, or a face, respectively.
The call \link Arrangement_on_surface_2::non_const_handle()
non_const_handle()\endlink can be issued only if the arrangement
object arr is mutable; see, e.g., Section \ref arr_ssecpl.

\subsubsection arr_sssectr_vertex Traversal Methods for an Arrangement Vertex

A vertex \f$v\f$ of an arrangement induced by bounded curves is always
associated with a geometric entity, namely with an \link
Arrangement_on_surface_2::Point_2 Point_2\endlink object, which can
be obtained by \link Arrangement_on_surface_2::Vertex::point()
v->point()\endlink, where v identifies a handle to \f$v\f$.

The call \link Arrangement_on_surface_2::Vertex::is_isolated()
v->is_isolated()\endlink determines whether the vertex \f$v\f$ 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 call \link
Arrangement_on_surface_2::Vertex::incident_halfedges()
v->incident_halfedges()\endlink returns a circulator of the nested
type \link Arrangement_on_surface_2::Halfedge_around_vertex_circulator
Halfedge_around_vertex_circulator\endlink that enables the traversal
of this circular list around a given vertex \f$v\f$ in a clockwise
order. The value type of this circulator is \link
Arrangement_on_surface_2::Halfedge Halfedge\endlink. By convention,
the target of the halfedge is \f$v\f$. The call \link
Arrangement_on_surface_2::Vertex::degree() v->degree()\endlink
evaluates to the number of the halfedges incident to \f$v\f$.

The function below prints all the halfedges incident to a given
arrangement vertex (assuming that objects of the \link
Arrangement_on_surface_2::Point_2 Point_2\endlink type can be
inserted into the standard output using the << operator). The
arrangement type is the same as in the simple example above.

\code
template
void print_incident_halfedges(typename Arrangement::Vertex_const_handle v) {
if (v->is_isolated()) {
std::cout << "The vertex (" << v->point() << ") is isolated\n";
return;
}
typename Arrangement::Halfedge_around_vertex_const_circulator first, curr;
first = curr = v->incident_halfedges();
std::cout << "The neighbors of the vertex (" << v->point() << ") are:";
do std::cout << " (" << curr->source()->point() << ")";
while (++curr != first);
std::cout << std::endl;
}
\endcode

If \f$v\f$ is an isolated vertex, the call \link
Arrangement_on_surface_2::Vertex::face() v->face()\endlink can be used to
obtain the face that contains \f$v\f$.

\subsubsection arr_sssectr_halfedge Traversal Methods for an Arrangement Halfedge

A halfedge \f$e\f$ of an arrangement induced by bounded curves is
associated with an \link Arrangement_on_surface_2::X_monotone_curve_2
X_monotone_curve_2\endlink object, which can be obtained by
\link Arrangement_on_surface_2::Halfedge::curve()
e->curve()\endlink, where e identifies a handle to \f$e\f$.

The calls \link Arrangement_on_surface_2::Halfedge::source()
e->source()\endlink and \link
Arrangement_on_surface_2::Halfedge::target() e->target()\endlink
return handles to the halfedge's source-vertex and target-vertex,
respectively. You can obtain a handle to the twin halfedge using \link
Arrangement_on_surface_2::Halfedge::twin() e->twin()\endlink. Note
that from the definition of halfedges in the Dcel structure, the
following invariants always hold:

Every halfedge has an incident face that lies to its left, which can
be obtained by \link Arrangement_on_surface_2::Halfedge::face()
e->face()\endlink. Recall that a halfedge is always one link in a
connected chain (CCB) of halfedges that share the same incident
face. The \link Arrangement_on_surface_2::Halfedge::prev()
e->prev()\endlink and \link
Arrangement_on_surface_2::Halfedge::next() e->next()\endlink calls
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. Indeed \link
Arrangement_on_surface_2::Halfedge::ccb() e->ccb()\endlink returns
an \link Arrangement_on_surface_2::Ccb_halfedge_circulator
Ccb_halfedge_circulator\endlink object for traversing all halfedges
along the connected component of \f$e\f$. The value type of this
circulator is \link Arrangement_on_surface_2::Halfedge
Halfedge\endlink.

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

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

\subsubsection arr_sssectr_face Traversal Methods for an Arrangement Face

An Arrangement_2 object arr that identifies an arrangement of
bounded curves always has a single unbounded face. The call \link
Arrangement_on_surface_2::unbounded_face()
arr.unbounded_face()\endlink returns a handle to this face. Note
that an empty arrangement contains nothing but the unbounded
face.

Given a handle to a face \f$f\f$, you can use the call \link
Arrangement_on_surface_2::Face::is_unbounded()
f->is_unbounded()\endlink to determine whether the face \f$f\f$ is
unbounded. Bounded faces have an outer CCB, and the \link
Arrangement_on_surface_2::Face::outer_ccb() outer_ccb()\endlink
method returns a circulator for the halfedges along this CCB. Note
that the halfedges along this CCB wind in a counterclockwise order
around the outer boundary of the face.

A face can also contain disconnected components in its interior,
namely, holes and isolated vertices. You can access these components
as follows:

The function print_face() listed below prints the outer and inner
boundaries of a given face. It uses the function template
print_ccb() listed above.

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

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

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

The function print_arrangement() listed below prints the features of
a given arrangement. The file arr_print.h, which can be found under
the examples folder, includes the definitions of this function, as
well as the definitions of all other functions listed in this
section. This concludes the preview of the various traversal methods.

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

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

// Print the arrangement faces.
std::cout << arr.number_of_faces() << " faces:\n";
for (auto 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 through the introduction of new edges or
vertices, or the modification or removal of existing edges and
vertices.

The arrangement member-functions that insert new \f$x\f$-monotone
curves into the arrangement, thus enabling the construction of a
two-dimensional surface subdivision, are rather specialized, as they
assume that the interior of the inserted curve is disjoint from all
existing arrangement vertices and edges, and in addition require
apriori knowledge of the location of the inserted curve. Indeed, for
most purposes it is more convenient to construct an arrangement using
the free (global) insertion functions, which relax these
restrictions. However, as these free functions are implemented in
terms of the specialized insertion functions, we start by describing
the fundamental functionality of the arrangement class, and describe
the operation of the free functions in Section \ref arr_secgl_funcs.

\subsection arr_sssecmf_insert_cv Inserting Pairwise Disjoint x-Monotone Curves

The most trivial functions that allow users to modify the arrangement
are the specialized functions for the insertion of an \f$x\f$-monotone
curve the interior of which is disjoint from the interior of all other
curves in the existing arrangement and does not contain any point of
the arrangement. In addition, these functions require that the
location of the curve in the arrangement be known.

The rather harsh restrictions on the inserted curves enable an
efficient implementation. While inserting an \f$x\f$-monotone curve,
the interior of which is disjoint from all curves in the existing
arrangement, is quite straightforward, as we show next, (efficiently)
inserting a curve that intersects with the curves already in the
arrangement is much more complicated and requires the application of
nontrivial geometric algorithms. The decoupling of the topological
arrangement representation from the various algorithms that operate on
it dictates that the general insertion operations be 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.

\cgalFigureBegin{aos_fig-insert,insert.png}
Illustrations of the various specialized insertion procedures. The
inserted \f$x\f$-monotone curve is drawn as a dashed line, surrounded
by two solid arrows that represent the pair of twin halfedges added to
the \dcel. Existing vertices are shown as red discs, while new
vertices are shown as blue discs. Existing halfedges 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, the
endpoints of which correspond to existing vertices \f$u_1\f$ and
\f$u_2\f$. In this case, the new pair of halfedges closes a new face
\f$f'\f$. The hole \f$h_1\f$, which belonged to \f$f\f$ before
the insertion, becomes a hole 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 the
interiors of all curves in the arrangement, only the following three
scenarios are possible, depending on the status of the endpoints of
the inserted curve:

1. Neither curve endpoints correspond to any existing arrangement vertex. In this case we have to create two new vertices that correspond to the curve endpoints, respectively, and connect them using a pair of twin halfedges. This halfedge pair forms a new hole inside the face that contains the curve in its interior.
2. 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 that corresponds to its right endpoint.) In this case 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 is isolated, we need to form a new hole inside the face that contains this vertex, essentially falling back to the handling of the previous case, naturally, skipping the creation of the existing vertex.)
3. Both endpoints correspond to existing arrangement vertices. In this case we connect these vertices using a pair of twin halfedges. (If one or both vertices are isolated, we fall back to the handling of the first or second case, respectively, naturally, skipping the creation of the existing vertices.) The two following subcases may occur:
4. Two disconnected components are merged into a single connected component (as is the case with the segment \f$s_1\f$ in the figure below).
5. A new face, which is split from an existing arrangement face, is created (as is the case with the segment \f$s_2\f$ in the figure below). 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.

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

The Arrangement_2 class offers insertion functions that perform the
special insertion procedures listed above, namely, \link
Arrangement_on_surface_2::insert_in_face_interior()
insert_in_face_interior()\endlink, \link
Arrangement_on_surface_2::insert_from_left_vertex()
insert_from_left_vertex()\endlink, \link
Arrangement_on_surface_2::insert_from_right_vertex()
insert_from_right_vertex()\endlink and \link
Arrangement_on_surface_2::insert_at_vertices()
insert_at_vertices()\endlink. 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;
more precisely:

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

The program below demonstrates the usage of the four specialized
insertion functions. It creates an arrangement of five line segments
\f$s_1, \ldots, s_5\f$, as depicted in
\cgalFigureRef{aos_fig-edge_insertion}. \cgalFootnote{Notice that in
all figures in the rest of this chapter the coordinate axes are drawn
only for illustrative purposes and are not part of the
arrangement.} The first line segment \f$s_1\f$ is inserted in the
interior of the unbounded face, while the four succeeding line
segments \f$s_2, \ldots, s_5\f$ are inserted using the vertices
created by the insertion of preceding segments. The arrows in the
figure mark the direction of the halfedges \f$e_1, \ldots, e_5\f$
returned from the insertion functions. The resulting arrangement
consists of three faces, where the two bounded faces form together a
hole in the unbounded face.

Two header files are included in the code in order to make this and
the following examples more compact. The file
arr_inexact_construction_segments.h is listed
immediately after the program. The file arr_print.h is
introduced in Section \ref arr_ssectraverse.

\cgalExample{Arrangement_on_surface_2/edge_insertion.cpp}

The statements below define the types for arrangements of line
segments common to all examples that do not construct new geometric
objects. They are kept in the header file
arr_inexact_construction_segments.h. In these examples the Traits
parameter of the Arrangement_2 class template is
substituted by an instance of the
Arr_non_caching_segment_traits_2<Kernel> class template. The
Arr_non_caching_segment_traits_2 class template is instantiated with
the predefined kernel that evaluates predicates in an exact manner,
but constructs geometric objects in an inexact manner, as none of
these examples construct new geometric objects. In the remaining
examples the traits class-template is instantiated with a kernel that
evaluates predicates and constructs geometric objects, both in an
exact manner.

\code{.cpp}
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Arr_non_caching_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

using Kernel = CGAL::Exact_predicates_inexact_constructions_kernel;
using Number_type = Kernel::FT;

using Traits = CGAL::Arr_non_caching_segment_traits_2;
using Point = Traits::Point_2;
using Segment = Traits::X_monotone_curve_2;

using Arrangement = CGAL::Arrangement_2;
using Vertex_handle = Arrangement::Vertex_handle;
using Halfedge_handle = Arrangement::Halfedge_handle;
using Face_handle = Arrangement::Face_handle;
\endcode

\subsection arr_sssecmf_iso_verts Manipulating Isolated Vertices

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

The call \link Arrangement_on_surface_2::insert_in_face_interior()
arr.insert_in_face_interior(p, f)\endlink 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 associated
with \f$p\f$ it has created. 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 calling the
member function Arrangement_on_surface_2::Vertex::face(). The member
function \link Arrangement_on_surface_2::remove_isolated_vertex()
Arrangement_on_surface_2::remove_isolated_vertex(Vertex_handle v)\endlink
accepts a handle to an isolated vertex and removes it from the
arrangement.

\cgalFigureBegin{aos_fig-isolated_vertices,isolated_vertices.png}
An arrangement of line segments containing three isolated vertices,
as constructed in \ref Arrangement_on_surface_2/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, \f$u_1\f$, \f$u_2\f$, and \f$u_3\f$, located
inside the unbounded face of the arrangement. Then, it inserts four
line segments \f$s_1, \ldots, s_4\f$, that form a square hole inside
the unbounded face (see \cgalFigureRef{aos_fig-edge_insertion} 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

While reading the previous subsection you learned how to insert new
points that induce isolated vertices into the arrangement. You may
wonder now how you can insert a new point that lies on an
\f$x\f$-monotone curve that is associated with existing arrangement
edge.

The introduction of a vertex, the geometric mapping of which is a
point \f$p\f$ that lies on an \f$x\f$-monotone curve, requires the
splitting of the curve in its interior at \f$p\f$. The two resulting
subcurves induce two new edges, respectively. In general, the
Arrangement_2 class template relies on the geometry traits to
perform such a split. As a matter of fact, it relies on the geometry
traits to perform all geometric operations. To insert a point \f$p\f$
that lies on an \f$x\f$-monotone curve associated with an existing
edge \f$e\f$ into the arrangement \f$\mathcal{A}\f$, you must first
construct the two curves \f$c_1\f$ and \f$c_2\f$, which are the two
subcurves that result from splitting the \f$x\f$-monotone curve
associated with the edge \f$e\f$ at \f$p\f$. Then, you have to issue
the call \link Arrangement_on_surface_2::split_edge()
arr.split_edge(he, c1, c2)\endlink, where arr identifies the
arrangement \f$\mathcal{A}\f$ and he is a handle to one of the two
halfedges that represent the edge \f$e\f$. The function splits the two
halfedges that represent \f$e\f$ into two pairs of halfedges,
respectively. Two new halfedges are incident to the new vertex \f$v\f$
associated with \f$p\f$. The function returns a handle to the new
halfedge, the source of which is the source vertex of the halfedge
handled by he, and the target of which is the new vertex \f$v\f$.

The reverse operation is also possible. Consider a vertex \f$v\f$ of
degree \f$2\f$ that has two incident edges \f$e_1\f$ and \f$e_2\f$
associated with two curves \f$c_1\f$ and \f$c_2\f$, respectively, such
that the union of \f$c_1\f$ and \f$c_2\f$ results in a single
continuous \f$x\f$-monotone curve \f$c\f$ of the type supported by the
traits class in use. To merge the edges \f$e_1\f$ and \f$e_2\f$ into a
single edge associated with the curve \f$c\f$, essentially removing
the vertex \f$v\f$ from the arrangement identified by arr, you need
to issue the call \link Arrangement_2.merge_edge() arr.merge_edge(he1, he2, c)\endlink, where he1 and he2 are handles to halfedges
representing \f$e_1\f$ and \f$e_2\f$, respectively.

Finally, the call \link Arrangement_2.remove_edge()
remove_edge(he)\endlink removes the edge \f$e\f$ from the
arrangement, where he is a handle to one of the two halfedges that
represents \f$e\f$. 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 \f$e\f$ causes one of its end vertices to
become isolated, this vertex is removed as well. However, you can
control this behavior and choose to keep the isolated vertices by
supplying additional Boolean flags to \link
Arrangement_on_surface_2::remove_edge remove_edge()\endlink
indicating whether the source or the target vertices are to be removed
should they become isolated.

\cgalFigureBegin{aos_fig-edge_manipulation,edge_manipulation.png}
The three steps of the example program \ref
Arrangement_on_surface_2/edge_manipulation.cpp. In Step (a) it
constructs an arrangement of four line segments. In Step (b) the edges
\f$e_1\f$ and \f$e_2\f$ are split, and the split points are connected
with a new segment \f$s\f$ that is inserted into the arrangement. This
operation is undone in Step (c), where \f$e\f$ is removed from the
arrangement, rendering its end vertices \f$u_1\f$ and \f$u_2\f$
redundant. We therefore remove these vertices by merging their
incident edges and go back to the arrangement depicted in (a).
\cgalFigureEnd

The following example program shows how the edge-manipulation
functions can be used. The program works in three steps, as
demonstrated in \cgalFigureRef{aos_fig-isolated_vertices}. Note that
the program uses the fact that \link
Arrangement_on_surface_2::split_edge() split_edge()\endlink returns
one of the new halfedges (after the split) that has the same direction
as the original halfedge (the first parameter of the function) and is
directed towards the split point. Thus, it is easy to identify the
vertices \f$u_1\f$ and \f$u_2\f$ associated with the split points.

\cgalExample{Arrangement_on_surface_2/edge_manipulation.cpp}

The member functions \link Arrangement_on_surface_2::modify_vertex()
modify_vertex()\endlink and \link
Arrangement_on_surface_2::modify_edge() modify_edge()\endlink modify
the geometric mappings of existing features of the arrangement. The
call \link Arrangement_on_surface_2::modify_vertex
arr.modify_vertex(v, p)\endlink accepts a handle to a vertex \f$v\f$
and a reference to a point \f$p\f$, and sets \f$p\f$ to be the point
associated with the vertex \f$v\f$. The call \link
Arrangement_on_surface_2::modify_edge() arr.modify_edge(he, c)\endlink accepts a handle to one of the two halfedges that
represent an edge \f$e\f$ and a reference to a curve \f$c\f$, and sets
\f$c\f$ to be the \f$x\f$-monotone curve associated with
\f$e\f$. (Note that both halfedges are modified; that is, both
expressions e->curve() and e->twin()->curve() evaluate to
\f$c\f$ after the modification.) These functions have preconditions
that \f$p\f$ is geometrically equivalent to v->point() and \f$c\f$
is equivalent to e->curve(), respectively.\cgalFootnote{Roughly
speaking, two curves are equivalent iff they have the same graph. In
Section \ref aos_sssec-geom_traits-concepts_basic we give a formal
definition of curves and curve equivalence.} If these preconditions
are not met, the corresponding operation may invalidate the structure
of the arrangement. At first glance it may seem as if these two
functions are of little use. However, you 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 you can modify this data; see more
details in Section \ref arr_sssec_tr_data_decorators. In addition, you 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, if we use some simple rational-number type to represent the
point coordinates, we can replace the point \f$(\frac{20}{40},
\frac{99}{33})\f$ associated with some vertex \f$v\f$ with an
equivalent point with normalized coordinates, namely \f$(\frac{1}{2},
3)\f$.

\subsection arr_sssecadv_insert Advanced Insertion Functions

\cgalAdvancedBegin

| \image html pred_around_vertex.png
\image latex pred_around_vertex.png | Assume that the specialized insertion function \link
Arrangement_on_surface_2::insert_from_left_vertex()
insert_from_left_vertex(c, v)\endlink is given a curve \f$c\f$, the
left endpoint of which 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, in
order to complete the insertion, it is necessary to locate the
halfedge \f$e_{\mathrm{pred}}\f$ directed toward \f$v\f$, such that
\f$c\f$ is located between the curves associated with
\f$e_{\mathrm{pred}}\f$ and the next halfedge in the clockwise order
in the circular list of halfedges around \f$v\f$; see
\cgalFigureRef{aos_fig-insert}. This search may take \cgalBigO{d} time,
where \f$d\f$ is the degree of the vertex \f$v\f$. \cgalFootnote{We
can store the handles to the halfedges incident to \f$v\f$ in an efficient
search structure to obtain \cgalBigO{\log d} access time. However, as
\f$d\f$ is usually very small, this may lead to a waste of storage
space without a meaningful improvement in running time in practice.}
However, if the halfedge \f$e_{\mathrm{pred}}\f$ is known in advance,
the insertion can be carried out in constant time, and without

performing any geometric comparisons. |
| --- | --- |

The Arrangement_2 class provides advanced versions of the
specialized insertion functions for a curve \f$c\f$, namely, \link
Arrangement_on_surface_2::insert_from_left_vertex()
insert_from_left_vertex(c, he_pred)\endlink and \link
Arrangement_on_surface_2::insert_from_right_vertex()
insert_from_right_vertex(c, he_pred)\endlink. These functions
accept a halfedge \f$e_{\mathrm{pred}}\f$ as specified above, instead
of a handle to a vertex \f$v\f$. They are more efficient, as they take
constant time and do not perform any geometric operations. Thus, you
should use them when the halfedge \f$e_{\mathrm{pred}}\f$ is known. In
cases where the vertex \f$v\f$ is isolated or the predecessor halfedge
for the newly inserted curve is not known, the simpler versions of
these insertion functions should be used. Similarly, the member
function \link Arrangement_on_surface_2::insert_at_vertices()
insert_at_vertices()\endlink is overloaded with two additional
versions as follows. One accepts two handles to the two predecessor
halfedges around the two vertices \f$v_1\f$ and \f$v_2\f$,
respectively, that correspond to the curve endpoints. The other one
accepts a handle to one vertex and a handle to the predecessor
halfedge around the other vertex.

\cgalFigureBegin{aos_fig-special_edge_insertion,special_edge_insertion.png}
An arrangement of line segments, as constructed in
\ref Arrangement_on_surface_2/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{aos_fig-special_edge_insertion} 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 object 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 useful query types defined on arrangements is the
point-location 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 lie 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

Recall that the arrangement representation is decoupled from the
geometric algorithms that operate on it. Thus, the Arrangement_2
class template does not support point-location queries directly.
Instead, the \ref PkgArrangementOnSurface2 package provides a set of
class templates that are capable of answering such queries; all are
models of the concept AosPointLocation_2. Each model employs
a different algorithm or strategy for answering queries. A
model of this concept must define the \link
AosPointLocation_2::locate() locate()\endlink member
function, which accepts an input query-point and returns a polymorphic
object representing the arrangement cell that contains this point.
The returned object is of type
Arr_point_location_result<Arrangement_2>::%Type, which is a
discriminated union container of the bounded types \link
Arrangement_on_surface_2::Vertex_const_handle
Vertex_const_handle\endlink, \link
Arrangement_on_surface_2::Halfedge_const_handle
Halfedge_const_handle\endlink, or \link
Arrangement_on_surface_2::Face_const_handle
Face_const_handle\endlink. Depending on whether the query point is
located inside a face, lies on an edge, or coincides with a vertex,
the appropriate handle can be obtained with value retrieval
by std::get as demonstrated in the example below.

Note that the handles returned by the \link
AosPointLocation_2::locate() locate()\endlink functions are
non-mutable (const). If necessary, such handles may be cast to
mutable handles using the
Arrangement_on_surface_2::non_const_handle() methods.

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 locate_point() listed below accepts a
point-location object, the type of which is a model of the
AosPointLocation_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
void locate_point(const PointLocation& pl,
const typename PointLocation::Arrangement_2::Point_2& q) {
using Point_location = PointLocation;
using Arrangement_2 = typename Point_location::Arrangement_2;
typename CGAL::Arr_point_location_result::Type obj =
pl.locate(q);

// Print the result.
print_point_location(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 std::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
void print_point_location
(const typename PointLocation::Arrangement_::Point_2& q
typename CGAL::Arr_point_location_result::Type obj) {
using Arrangement_2 = Arrangement_;

using Vertex_const_handle = typename Arrangement_2::Vertex_const_handle;
using Halfedge_const_handle = typename Arrangement_2::Halfedge_const_handle;
using Face_const_handle = typename Arrangement_2::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 = std::get_if(&obj)) // located inside a face
std::cout << "inside "
<< (((*f)->is_unbounded()) ? "the unbounded" : "a bounded")
<< " face.\n";
else if (e = std::get_if(&obj)) // located on an edge
std::cout << "on an edge: " << (*e)->curve() << std::endl;
else if (v = std::get_if(&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 aos_sssec-pl_strategy Choosing a Point-Location Strategy

Each of the various point-location class templates employs a different
algorithm or strategy\cgalFootnote{The term strategy
is borrowed from the design-pattern taxonomy \cgalCite{cgal:ghjv-dpero-95},
Chapter 5. A strategy 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:

In all cases, the function returns a handle to the vertex
associated with \f$p\f$.

The type of arr must be and instance of the Arrangement_2 class
template instantiated with a traits class that models the
AosXMonotoneTraits_2 concept, as the insertion operation may
involve the splitting of curves.

\subsubsection arr_sssecinsert_ex Inserting Intersecting Line Segments (code example)

\cgalFigureBegin{aos_fig-incremental_insertion,incremental_insertion.png}
An arrangement of five intersecting line segments, as constructed in
\ref Arrangement_on_surface_2/incremental_insertion.cpp and
\ref Arrangement_on_surface_2/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 five intersecting
line-segments \f$s_1, \ldots, s_5\f$. It is known that \f$s_1\f$ and
\f$s_2\f$ do not intersect, so
CGAL::insert_non_intersecting_curve<>() is used to insert them into
the empty arrangement. The rest of the segments are inserted using
CGAL::insert<>(). Using a kernel that constructs geometric objects
in an inexact manner (due to round-off errors) may yield a program that
computes incorrect results and crashes from time to time. This is
avoided by using a kernel that provides exact geometric-object
constructions as well as exact geometric-predicate evaluations. The
header file arr_exact_construction_segments.h, just like the header
file arr_inexact_construction_segments.h, contains the definitions
for arrangements of line segments. Unlike the latter, it uses a
kernel suitable for arrangements induced by curves that intersect each
other, namely a kernel that is exact always. Note that we alternately
use the naive point-location strategy, given explicitly to the
insertion functions, and the default walk point-location strategy.

The resulting arrangement is depicted in
\cgalFigureRef{aos_fig-incremental_insertion}, where the vertices that
correspond to segment endpoints are drawn as dark discs, and the
vertices that correspond to intersection points are drawn as
circles. It consists of 13 vertices, 16 edges, and 5 faces. We also
perform a point-location query on the resulting arrangement. The query
point \f$q\f$ is drawn as a plus sign. The face that contains it is
drawn with a shaded texture. The program calls an instance of the
function template print_arrangement_size(), which prints
quantitative measures of the arrangement; see \ref lst_paz
"code example" for its listing in Section \ref aos_ssec-basic-arr_class.

\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 into a given arrangement. Now we describe functions
that do not change the arrangement at all; nevertheless, they are
closely related to the incremental insertion functions, as they also
use the zone framework.

The free function template %CGAL::do_intersect<>(arr, c, pl) checks
whether the given query curve \f$c\f$ intersects the curves and points
of an existing arrangement arr. If \f$c\f$ is not \f$x\f$-monotone
(that is, it is of type \link AosTraits_2::Curve_2
Curve_2\endlink) the curve is subdivided into \f$x\f$-monotone
subcurves and isolated points. Each \f$x\f$-monotone curve (or point)
is checked for intersection in turn using the zone framework. For
points we simply apply point-location. Given an \f$x\f$-monotone
curve, first its 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 curve or point is
found or when the right endpoint is reached. A given point-location
object is used for locating the left endpoint of the curve in the
existing arrangement. There is a variant that instead of accepting a
user-defined point-location object, it constructs a local object of
the walk point-location type, namely, an instance of the
Arr_walk_along_line_point_location class template, and uses it to
locate the endpoint. If the given curve is \f$x\f$-monotone then the
traits type must model the AosXMonotoneTraits_2 concept. If
the curve is not \f$x\f$-monotone then the traits type must model the
AosTraits_2 concept.

The CGAL::zone<>(arr, c, oi, pl) function template computes the zone
of a given \f$x\f$-monotone curve in a given arrangement. More
precisely, it outputs all the arrangement cells (namely, vertices,
edges, and faces) that the input \f$x\f$-monotone curve \f$C\f$
intersects in the order they are discovered when traversing the curve
from left to right. The function uses a given point-location object
to locate the left endpoint of the given curve. There is a variant
that instead of accepting a user-defined point-location object, it
constructs a local object of the walk point-location type, namely, an
instance of the Arr_walk_along_line_point_location class template,
and uses it to locate the endpoint. The traits type must model the
AosXMonotoneTraits_2 concept.

\subsection arr_ssec_sweep The Surface-Sweep Algorithm

The famous plane-sweep algorithm introduced by Bentley and Ottmann was
originally formulated for sets of line segments in the plane. The \ref
PkgSurfaceSweep2 package offers a generic implementation of a
generalized version of the original plane-sweep algorithm. It (i)
operates in two-dimensional surfaces (not restricted to the plane),
(ii) accepts various families of \f$x\f$-monotone curves (not only
line segments), and (iii) handles overlaps. (Observe that the original
algorithm did not handle overlaps. Handling overlaps is difficult,
especially for polyline, as two polylines may overlap in more than one
connected component.) The generic implementation serves as the
foundation of a family of concrete operations described in the rest of
this section, such as aggregately constructing an arrangement induced
by a set of curves that lie in a two-dimensional surface and outputting
the overlay of two arrangements.

Given a set of \f$n\f$ input curves, you can insert the curves in the
set into an arrangement incrementally one by one. However, the \ref
PkgArrangementOnSurface2 package also provides a couple of free
(overloaded) functions that aggregately insert a range of curves into
an arrangement using the surface-Sweep framework.

\cgalFigureBegin{aos_fig-bounded_vd,bounded_vertical_decomposition.png}
An arrangement of four line segments and its vertical decomposition
into pseudo trapezoids, as constructed in \ref
Arrangement_on_surface_2/bounded_vertical_decomposition.cpp. The
segments of the arrangement are drawn in solid blue lines and the
segments of the vertical decomposition are drawn in dark dotted lines.
\cgalFigureEnd

In the case of an arrangement of line segments, two-dimensional cells
of the former type are trapezoids (as they have a pair of parallel
vertical edges), while two-dimensional cells of the latter type are
triangles, which can be viewed as degenerate trapezoids. The unbounded
cells can be similarly categorized into two types. Observe that the
boundary of an unbounded cell contains only one original edge or none
and it may contain only non-vertical edges. The resulting cells are
therefore referred to as pseudo trapezoids. The
\cgalFigureRef{aos_fig-bounded_vd} depicts the vertical decomposition
of an arrangement induced by four line segments, as constructed in
\ref Arrangement_on_surface_2/bounded_vertical_decomposition.cpp and
listed below. The decomposition consists of 14 pseudo trapezoids, out
of which two are bounded triangles, two are bounded trapezoids, and 10
are unbounded trapezoids.

The function template decompose() accepts an arrangement
\f$\mathcal{A}\f$ and outputs for each vertex \f$v\f$ of
\f$\mathcal{A}\f$ a pair of features---one that directly lies below
\f$v\f$ and another that directly lies above \f$v\f$. It is
implemented as a plane-sweep algorithm, which aggregately computes the
set of pairs of features. Let \f$v\f$ be a vertex of
\f$\mathcal{A}\f$. The feature above (respectively below) \f$v\f$ may
be one of the following:

\cgalExample{Arrangement_on_surface_2/bounded_vertical_decomposition.cpp}

As you might have noticed, the code above contains a call to an
instance of a the function template read_objects(). It reads the
description of geometric objects from a file and constructs them. It
accepts the name of an input file that contains the plain-text
description of the geometric objects and an output iterator for
storing the newly constructed objects. When the function is
instantiated, the first template parameter, namely Type, must be
substituted by the type of objects to read. It is assumed that an
extractor operator (>>) that extracts objects of the given type from
the input stream is available. The listing of the function template,
which is defined in the file read_objects.h, is omitted here

\cgalAdvancedBegin

In Section \ref aos_sec-unbounded you will learn that we also support
arrangements induced by unbounded curves, referred to as
unbounded arrangements. For such an arrangement we maintain an
imaginary rectangle with left, right, bottom, and top boundaries,
which bound the concrete vertices and edges of the
arrangement. Halfedges that represent the boundaries of the rectangle
are fictitious. The decompose() function
template handles unbounded arrangements. If \f$v\f$ is a vertex of an
unbounded arrangement, and \f$v\f$ is incident to an unbounded face
and there is no curve lying above (respectively below) it, the feature
above (respectively below) \f$v\f$ returned by the function template
decompose() is a fictitious edge.

\cgalAdvancedEnd

\section aos_sec-unbounded Arrangements of Unbounded Curves

All the arrangements constructed and manipulated in previous chapters
were induced only by line segments, which are, in particular, bounded
curves. Such arrangements always have one unbounded face that contains
all other arrangement features. In this section we explain how to
construct arrangements of unbounded curves. For simplicity of
exposition, we stay with linear objects and restrict our examples in
this section to lines and rays. However, the discussion in this
section, as well as the software described, apply more generally to
arbitrary curves in two-dimensional surfaces.

\subsection aos_ssec-unbounded-rep Representing Arrangements of Unbounded Curves

Given a set \f$\mathcal{C}\f$ of unbounded curves, a simple approach
for representing the arrangement induced by \f$\mathcal{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$\mathcal{C}\f$. This process would result in a set of
bounded curves (line segments if \f$\mathcal{C}\f$ consists of 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. Moreover, if
we are not given all the curves inducing the arrangement in advance,
then the choice of a good bounding rectangle may change as more curves
are introduced.

\cgalFigureBegin{aos_fig-unb_dcel,unb_dcel.png}
A \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 imaginary bounding rectangle.
\cgalFigureEnd

Instead of an explicit approach, we use an implicit bounding rectangle
embedded in the \dcel structure. \cgalFigureRef{aos_fig-unb_dcel}
shows the arrangement of four lines that subdivide the plane into
eight unbounded faces and two bounded ones. Notice that in this case
portions of the unbounded faces now have outer boundaries (those
portions inside the bounding rectangle), and the halfedges along these
outer CCBs are drawn as arrows. The bounding rectangle is drawn
dashed. The vertices \f$v_1,v_2,\ldots,v_8\f$, which lie on the
bounding rectangle, represent the unbounded ends of the four lines
that approach infinity. The halfedges connecting them, which overlap
with the bounding rectangle, are not associated with geometric curves.
Thus, we refer to them as fictitious. 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 imaginary rectangle. It forms a single hole in the face
\f$\tilde{f}\f$. We refer to \f$\tilde{f}\f$ as fictitious,
since it does not correspond to a real two-dimensional cell of the
arrangement. Finally, there are four additional vertices denoted by
\f$v_{\rm bl}, v_{\rm tl}, v_{\rm br}\f$, and \f$v_{\rm tr}\f$, which
coincide with the bottom-left, top-left, bottom-right, and top-right
corners of the bounding rectangle, respectively. They do not lie on
any curve, and are referred to as fictitious as well. These
four vertices identify each of the fictitious edges as lying on the
top, the bottom, the left, and the right edge of the imaginary
bounding rectangle. The four fictitious vertices exist even when the
arrangement is empty: In this case they are connected by four pairs of
fictitious halfedges that define a single unbounded face (which
represents the entire \f$\mathbb{R}^2\f$ plane) lying inside the
imaginary bounding rectangle and a fictitious face lying outside.

In summary, there are four types of arrangement vertices, which differ
from one another by their location with respect to the imaginary
bounding rectangle as follows:

1. \anchor type-normal A vertex, associated with a point in \f$\mathbb{R}^2\f$. Such a vertex always lies inside the bounding rectangle and has bounded coordinates..
2. \anchor type-unbounded A vertex that represents an unbounded end of an \f$x\f$-monotone curve that approaches \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{aos_fig-unb_dcel}), but in general the curve end also approaches \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{aos_fig-unb_dcel}). For convenience, we always take a "tall" enough bounding rectangle and treat such vertices as lying on either the left or the right rectangle edges (that is, if a curve approaches \f$x = -\infty\f$, its left end will be represented by a vertex on the left edge of the bounding rectangle, and if it approaches \f$x = \infty\f$, its right end will be represented by a vertex on the right edge).
3. \anchor typeunboundedvertical A vertex that represents the unbounded end of a vertical linear curve (line or ray) 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{aos_fig-unb_dcel} are of this type.
4. \anchor typefictitious The fictitious vertices that represent the four corners of the bounding rectangle.

\cgalFigureBegin{aos_fig-unb_asymptote,unb_asymptote.png}
The portions of a horizontal line, a vertical line, and two rectangular
hyperbolas with horizontal and vertical asymptotes confined to the
imaginary bounding rectangle.
\cgalFigureEnd

A vertex (at infinity) of Type 2 or Type 3 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 or
the corners of the bounding rectangle; see
\cgalFigureRef{aos_fig-unb_asymptote}. Fictitious vertices (of type 4
above) have exactly two incident fictitious edges. See Section \ref
aos_sec-geom_traits for an explanation on how the traits-class
interface helps impose the fact that a vertex at infinity is incident
to a single non-fictitious edge.

The traits class that substitutes the Traits parameter of the
Arrangement_2 class template when the latter is
instantiated specifies whether the arrangement instance supports
unbounded curves through the definitions of some tags nested in the
traits class; see Section \ref aos_sssec-geom_traits-concepts_basic
for details. Every arrangement that supports unbounded curves supports
bounded curves as well, but not vice versa. Maintaining an arrangement
that supports unbounded curves incurs an overhead due to the necessity
to manage the imaginary bounding rectangle. If you know beforehand
that all input curves that induce a particular arrangement are
bounded, define your arrangement accordingly. That is, use a traits
class that does not support unbounded curves.

\subsubsection arr_sssecunb_basic Basic Manipulation and Traversal Methods

The types \link Arrangement_on_surface_2::Vertex Vertex\endlink,
\link Arrangement_on_surface_2::Halfedge Halfedge\endlink, and \link
Arrangement_on_surface_2::Face Face\endlink nested in the
Arrangement_2 class template support the methods described below in
addition to the ones listed in Section \ref arr_ssectraverse. Let
\f$v\f$, \f$e\f$, and \f$f\f$ be handles to a vertex of type \link
Arrangement_on_surface_2::Vertex Vertex\endlink, a halfedge of type
\link Arrangement_on_surface_2::Halfedge Halfedge\endlink, and a
face of type \link Arrangement_on_surface_2::Face Face\endlink,
respectively.

The nested \link Arrangement_on_surface_2::Vertex Vertex\endlink
type also provides the Boolean predicate \link
Arrangement_on_surface_2::Vertex::is_at_open_boundary()
is_at_open_boundary()\endlink. If the call \link
Arrangement_on_surface_2::Vertex::is_at_open_boundary()
v->is_at_open_boundary()\endlink predicates evaluates to false,
you can access the point associated with \f$v\f$. Otherwise, \f$v\f$
is not associated with a \link Arrangement_on_surface_2::Point_2
Point_2\endlink object, as it represents the unbounded end of a
curve that approaches infinity.

Let \f$p_l = (x_l,y_l)\f$ and \f$p_r = (x_r,y_r)\f$ be the left and
right endpoints of a bounded \f$x\f$-monotone curve \f$c\f$,
respectively. We say that a point \f$p = (x_p,y_p)\f$ lies in the
\f$x\f$-range of \f$c\f$ if \f$x_l \leq x_p \leq x_r\f$. Let \f$p_l =
(x_l,y_l)\f$ be the left endpoint of an \f$x\f$-monotone curve \f$c\f$
unbounded from the right. A point \f$p = (x_p,y_p)\f$ lies in the
\f$x\f$-range of \f$c\f$ if \f$x_l \leq x_p\f$. Similarly, A point
\f$p = (x_p,y_p)\f$ lies in the \f$x\f$-range of an \f$x\f$-monotone
curve unbounded from the left if \f$x_p \leq x_r\f$. Naturally, every
point \f$p \in \mathbb{R}^2\f$ is in the \f$x\f$-range of an
\f$x\f$-monotone curve unbounded from the left and from the right.

\cgalAdvancedBegin

The function template is_in_x_range() listed below, and defined in
the file is_in_x_range.h, checks whether a given point \f$p\f$ is in
the \f$x\f$-range of the curve associated with a given halfedge
\f$e\f$. The function template also exemplifies how some of the above
functions can be used. The traits functor \link
AosBasicTraits_2::Compare_x_2 Compare_x_2\endlink used in
the code is described in Section \ref
aos_sssec-geom_traits-concepts_basic.

\code
// Check whether the given point is in the x-range of the curve associated
// with the given halfedge.
template
bool is_in_x_range(typename Arrangement::Halfedge_const_handle he,
const typename Arrangement::Point_2& p,
const typename Arrangement::Traits_2& traits)
{
auto cmp = traits.compare_x_2_object();

// Compare p with the source vertex (which may lie at x = +/- oo).
CGAL::Arr_parameter_space src_px = e->source()->parameter_space_in_x();
CGAL::Comparison_result res_s =
(src_px == CGAL::ARR_LEFT_BOUNDARY) ? CGAL::SMALLER :
((src_px == CGAL::ARR_RIGHT_BOUNDARY) ? CGAL::LARGER :
cmp(e->source()->point(), p));
if (res_s == CGAL::EQUAL) return true;

// Compare p with the target vertex (which may lie at x = +/- oo).
CGAL::Arr_parameter_space trg_px = e->target()->parameter_space_in_x();
CGAL::Comparison_result res_t =
(trg_px == CGAL::ARR_LEFT_BOUNDARY) ? CGAL::SMALLER :
((trg_px == CGAL::ARR_RIGHT_BOUNDARY) ? CGAL::LARGER :
cmp(e->target()->point(), p));

// p lies in the x-range of the halfedge iff its source and target lie
// at opposite x-positions.
return (res_s != res_t);
}
\endcode

\cgalAdvancedEnd

It is important to observe that the call \link
Arrangement_on_surface_2::number_of_vertices()
arr.number_of_vertices()\endlink does not count the vertices at
infinity in the arrangement arr. To find out this number you need to
issue the call \link
Arrangement_on_surface_2::number_of_vertices_at_infinity()
arr.number_of_vertices_at_infinity()\endlink. Similarly, \link
Arrangement_on_surface_2::number_of_edges()
arr.number_of_edges()\endlink does not count the fictitious edges
(whose number is always \link
Arrangement_on_surface_2::number_of_vertices_at_infinity()
arr.number_of_vertices_at_infinity()\endlink + 4) and \link
Arrangement_on_surface_2::number_of_faces()
arr.number_of_faces()\endlink does not count the fictitious
faces. The vertex, halfedge, edge, and face iterators defined by the
Arrangement_2 class template only go over true features of the
arrangement; namely, vertices at infinity and fictitious halfedges and
fictitious faces are skipped. On the other hand, the
Ccb_halfedge_circulator of the outer boundary of an unbounded face
or the Halfedge_around_vertex_circulator of a vertex at infinity do
traverse fictitious halfedges. While an arrangement induced by bounded
curves has a single unbounded face, an arrangement induced by
unbounded curves may have several unbounded faces. The call \link
Arrangement_on_surface_2::number_of_unbounded_faces()
arr.number_of_unbounded_faces()\endlink returns the number of
unbounded arrangement faces (Thus, \link
Arrangement_on_surface_2::number_of_faces()
arr.number_of_faces()\endlink - \link
Arrangement_on_surface_2::number_of_unbounded_faces()
arr.number_of_unbounded_faces()\endlink is the number of bounded
faces). The calls \link
Arrangement_on_surface_2::unbounded_faces_begin()
arr.unbounded_faces_begin()\endlink and \link
Arrangement_on_surface_2::unbounded_faces_end()
arr.unbounded_faces_end()\endlink return iterators of the type
Arrangement_on_surface_2::Unbounded_face_iterator (or its
non-mutable, const, counterpart type) that define the range of the
arrangement unbounded faces. Naturally, the value-type of this
iterator is \link Arrangement_on_surface_2::Face Face\endlink.

There is no way to directly obtain the fictitious vertices that
represent the four corners of the imaginary bounding
rectangle. However, you can obtain the fictitious face through the
call \link Arrangement_on_surface_2::fictitious_face()
arr.fictitious_face()\endlink, and then iterate over the boundary of
its single hole, which represents the imaginary bounding
rectangle. Recall that an arrangement of bounded curves does not have
a fictitious face. In this case the call above returns a null handle.

The example below exhibits the difference between an arrangement
induced by bounded curves, which has a single unbounded face, and an
arrangement induced by unbounded curves, which may have several
unbounded faces. It also demonstrates the usage of the insertion
function for pairwise interior-disjoint unbounded curves. In this case
we use an instance of the traits class-template
Arr_linear_traits_2<Kernel> to substitute the Traits parameter of
the Arrangement_2 class template when instantiated.
This traits class-template is capable of representing line segments as
well as unbounded linear curves, namely, lines and rays. Observe that
objects of the \link Arr_linear_traits_2::X_monotone_curve_2
X_monotone_curve_2\endlink type nested in this traits class-template
are constructible from objects of types \link
Arr_linear_traits_2::Line_2 Line_2\endlink, \link
Arr_linear_traits_2::Ray_2 Ray_2\endlink, and \link
Arr_linear_traits_2::Segment_2 Segment_2\endlink also nested
in the traits class-template. These three types and the \link
Arr_linear_traits_2::Point_2 Point_2\endlink type are
defined by the traits class-template Arr_linear_traits_2<Kernel> to
be the corresponding types of the kernel used to instantiate the
traits class-template; see Paragraph \ref arr_sssectr_linear.

\cgalFigureBegin{aos_fig-unbounded_non_intersecting,unbounded_non_intersecting.png}
An arrangement of unbounded linear objects, as constructed in
\ref Arrangement_on_surface_2/unbounded_non_intersecting.cpp.
\cgalFigureEnd

The first three curves, \f$c_1\f$, \f$c_2\f$, and \f$c_3\f$, are
inserted using the specialized 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 an 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.) Three additional rays are then inserted
incrementally using the insertion function for \f$x\f$-monotone curves,
the interior of which is disjoint from all arrangement features; see
the illustration in
\cgalFigureRef{aos_fig-unbounded_non_intersecting}). Finally, the
program prints the size of the arrangement using the function template
print_unbounded_arrangement_size() defined in the header file
arr_print.h. (Its listing is omitted here.) The program also
traverses the outer boundaries of its six unbounded faces and prints
the curves along these boundaries. The header file arr_linear.h,
which contains the definitions used by the example program, is listed
immediately after the listing of the main function.

\cgalExample{Arrangement_on_surface_2/unbounded_non_intersecting.cpp}

The type definitions used by the example below, as well as by other
examples that use the Arr_linear_traits_2 class template, are listed
next. These types are defined in the header file arr_linear.h.

\code
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_linear_traits_2.h>
#include <CGAL/Arrangement_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Number_type = Kernel::FT;

using Traits = CGAL::Arr_linear_traits_2;
using Point = Traits::Point_2;
using Segment = Traits::Segment_2;
using Ray = Traits::Ray_2;
using Line = Traits::Line_2;
using X_monotone_curve = Traits::X_monotone_curve_2;

using Arrangement = CGAL::Arrangement_2;
using Vertex_handle = Arrangement::Vertex_handle;
using Halfedge_handle = Arrangement::Halfedge_handle;
using Face_handle = Arrangement::Face_handle;
\endcode

\subsubsection arr_sssec-unb_global Free Functions

All the free functions that operate on arrangements of bounded curves
(see Section \ref arr_secgl_funcs) can also be applied to arrangements
of unbounded curves. For example, consider a container of linear
curves that has to be inserted into an arrangement object, the type of
which is an instance of the Arrangement_2 class
template, where the Traits parameter is substituted by the traits
class that handles linear curves; see Section \ref
arr_sssectr_linear. You can do it incrementally; namely, insert the
curves one by one as follows:
\code
for (auto it = curves.begin(); it != curves.end(); ++it) insert(arr, *it);
\endcode
Alternatively, the curves can be inserted aggregately using a single
call as follows:
\code
insert(arr, curves.begin(), curves.end());
\endcode
It is also possible to issue point-location queries 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. Note that all the point-location
strategies mentioned above, except the trapezoidal map strategy, are
capable of handling arrangements of unbounded curves.

\subsection arr_ssec-unb_duality Point-Line Duality

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 = (x_p, y_p)\f$ is given by the equation \f$y =
x_px - y_p\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 a collinear triple 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.

\section aos_sec-curved_surfaces Arrangements on Curved Surfaces

We are given a surface \f$S\f$ in \f$\mathbb{R}^3\f$ and a set
\f$\mathcal{C}\f$ of curves embedded in this surface. The curves
subdivide \f$S\f$ into cells of dimension 0 (vertices), 1
(edges), and 2 (faces). This subdivision is the
arrangement \f$\mathcal{A}(\mathcal{C})\f$ induced by
\f$\mathcal{C}\f$ on \f$S\f$. Arrangements embedded in curved surfaces
in \f$\mathbb{R}^3\f$ are generalizations of arrangements embedded in
the plane. In this section we explain how to construct, maintain, and
manipulate two-dimensional arrangements embedded in orientable
parametric surfaces in three dimensions, such as planes, cylinders,
spheres, and tori, and surfaces homeomorphic to them; see
\cgalFigureRef{aos_fig-surfaces}. Such arrangements have many
theoretical and practical applications; see, e.g.,
\cgalCite{as-aa-00}, \cgalCite{cgal:bfhks-apsca-10},
\cgalCite{cgal:bfhmw-apsgf-10}, \cgalCite{cgal:fhktww-a-07}, and
\cgalCite{cgal:h-a-04}.

\cgalFigureAnchor{aos_fig-surfaces}

\cgalFigureCaptionBegin{aos_fig-surfaces}
Various two-dimensional parametric surfaces, arrangements on which
are supported by the framework.
\cgalFigureCaptionEnd

\subsection aos_ssec-curved_surfaces-parametric Parametric Surfaces

We use \f$\overline{\mathbb{R}}\f$ to denote the compactified real line
\f$\mathbb{R} \cup {-\infty,+\infty}\f$. The mapping
\f$x \mapsto x/(1 - x^2)\f$ is a homeomorphism between
\f$(-1,+1)\f$ and \f$\mathbb{R}\f$ and between \f$[-1,+1]\f$ and
\f$\overline{\mathbb{R}}\f$. So you may also think of finite intervals
instead of the (compactified) real line in what follows.

A parametric surface \f$S\f$ is given by a continuous function
\f$\phi_S: \Phi \rightarrow \mathbb{R}^3\f$, where the domain \f$\Phi
= X \times Y\f$ is a rectangular two-dimensional parameter space and
\f$S = \phi_S(\Phi)\f$. The sets \f$X\f$ and \f$Y\f$ are open,
half-open, or closed intervals with endpoints in
\f$\overline{\mathbb{R}}\f$. We use \f$x_{\rm min}\f$, \f$x_{\rm
max}\f$, \f$y_{\rm min}\f$, and \f$y_{\rm max}\f$ to denote the
endpoints of \f$X\f$ and \f$Y\f$, respectively.

If you want to determine whether the pre-image of a point \f$p\f$
lies on identified sides, you need to employ one of the two traits
functors \link
AosIdentifiedHorizontalTraits_2::Is_on_x_identification_2
Is_on_x_identification_2\endlink or \link
AosIdentifiedVerticalTraits_2::Is_on_y_identification_2
Is_on_y_identification_2\endlink; see Section \ref
aos_ssec-traits-curved. If the pre-image of an \f$x\f$-monotone
curve \f$c\f$ does not entirely lie on identified sides, you can
determine the location of the pre-image of an endpoint of \f$c\f$
employing either the \link
AosVerticalSideTraits_2::Parameter_space_in_x_2
Parameter_space_in_x_2\endlink functor or the \link
AosHorizontalSideTraits_2::Parameter_space_in_y_2
Parameter_space_in_y_2\endlink functors; see Section \ref
aos_ssec-traits-curved. The operations in both functors accept an
enumeration that indicates the curve end, that is,
CGAL::ARR_MIN_END or CGAL::ARR_MAX_END, in addition to the curve
itself.

\cgalAdvancedBegin

The function template is_in_x_range() listed below, and defined in
the file spherical_is_in_x_range.h checks whether a given point
\f$p\f$, in the interior of the parameter space, is in the
\f$x\f$-range of an \f$x\f$-monotone curve \f$c\f$ that represents a
great-circle arc. It assumes that the left and right sides of the
parameter space are identified and the bottom and top sides are
contracted, which is the settings used by the traits class template
Arr_geodesic_arc_on_sphere_traits_2<Kernel,X,Y>; see Section \ref
arr_ssectr_spherical. The traits functors \link
AosBasicTraits_2::Construct_min_vertex_2
Construct_min_vertex_2\endlink, \link
AosBasicTraits_2::Construct_max_vertex_2
Construct_min_vertex_2\endlink, and \link
AosBasicTraits_2::Compare_x_2 Compare_x_2\endlink used in
the code are described is Section \ref
aos_sssec-geom_traits-concepts_basic. The traits functors \link
AosVerticalSideTraits_2::Parameter_space_in_x_2
Parameter_space_in_x_2\endlink, \link
AosHorizontalSideTraits_2::Parameter_space_in_y_2
Parameter_space_in_y_2\endlink, \link
AosIdentifiedVerticalTraits_2::Is_on_y_identification_2
Is_on_y_identification_2\endlink, and \link
AosHorizontalSideTraits_2::Compare_x_on_boundary_2
Compare_x_on_boundary_2\endlink, are described is Section \ref
aos_ssec-traits-curved.

\code
template
bool is_in_x_range(const typename GeometryTraits::X_monotone_curve_2& c,
const typename GeometryTraits::Point_2& p,
const GeometryTraits& traits) {
CGAL_assertion(! traits.is_on_y_identification_2_object()(p));

if (traits.is_on_y_identification_2_object()(c)) return false;

// Note that a great-circle arc that is incident to a pole is vertical.
auto cmp_x_boundary = traits.compare_x_on_boundary_2_object();
auto psy = traits.parameter_space_in_y_2_object();
auto psy_min = psy(c, CGAL::ARR_MIN_END);
if (psy_min == CGAL::ARR_BOTTOM_BOUNDARY)
return cmp_x_boundary(p, c, CGAL::ARR_MIN_END) == CGAL::EQUAL;
auto psy_max = psy(c, CGAL::ARR_MAX_END);
if (psy_max == CGAL::ARR_TOP_BOUNDARY)
return cmp_x_boundary(p, c, CGAL::ARR_MAX_END) == CGAL::EQUAL;
auto psx = traits.parameter_space_in_x_2_object();
auto psx_min = psx(c, CGAL::ARR_MIN_END);
auto psx_max = psx(c, CGAL::ARR_MAX_END);
if ((psx_min == CGAL::ARR_LEFT_BOUNDARY) &&
(psx_min == CGAL::ARR_RIGHT_BOUNDARY))
return true;
auto cmp_x = traits.compare_x_2_object();
if (psx_min == CGAL::ARR_LEFT_BOUNDARY) {
const auto& p_right = traits.construct_max_vertex_2_object()(c);
auto res = cmp_x(p, p_right);
return ((res == CGAL::SMALLER) || (res == CGAL::EQUAL));
}
if (psx_max == CGAL::ARR_RIGHT_BOUNDARY) {
const auto& p_left = traits.construct_min_vertex_2_object()(c);
auto res = cmp_x(p_left, p);
return ((res == CGAL::SMALLER) || (res == CGAL::EQUAL));
}
const auto& p_left = traits.construct_min_vertex_2_object()(c);
auto res = cmp_x(p_left, p);
if (res == CGAL::LARGER) return false;
const auto& p_right = traits.construct_max_vertex_2_object()(c);
res = cmp_x(p, p_right);
if (res == CGAL::LARGER) return false;
return true;
}
\endcode

\cgalAdvancedEnd

\section aos_sec-geom_traits The Geometry Traits

A geometry traits class encapsulates the definitions of the geometric
entities and the implementation of the geometric predicates and
constructions that handle these geometric entities, used by the
Arrangement_on_surface_2 class template and by the peripheral
modules. The identified minimal requirements imposed by the various
algorithms that apply to arrangements are organized in a hierarchy of
refined geometry-traits concepts. The requirements listed by each
concept include only the utterly essential types and operations needed
to implement specific algorithms. This modular structuring yields
controllable parts that can be produced, maintained, and utilized with
less effort. For each operation, all the preconditions that its
operands must satisfy are specified as well, as these may simplify the
implementation of models of these concepts even further. Each traits
class models one or more concepts. This section contains a detailed
description of the concepts in the refinement hierarchy and the
various traits classes that model these concepts.

All the algebra required for constructing and manipulating
arrangements is concentrated in the traits classes. The knowledge
required to devise a good traits class is very different from the
knowledge required for the development of the rest of the package or
for using the package. It has less to do with computational geometry
and it involves mainly algebra and numerical computation. This way,
traits classes for new types of curves can be developed with little
knowledge of algorithms and data structures in computational
geometry. In this section we discuss how to use existing traits
classes, but we also explain the concepts these traits classes
model---a starting point for every novice developer of such classes.

This section is divided into three parts. The first part describes the
refinement hierarchy of the arrangement geometry-traits concepts. The
second part reviews various models of these concepts. These traits
classes handle different curve families, such as line segments,
polylines, conic arcs, Bézier curves, algebraic curves, and
geodesic arcs on the sphere. The last part introduces decorators for
geometric traits classes. A decorator of a traits class attaches
auxiliary data to the geometric objects handled by the original traits
class, thereby extending it.

\subsection aos_ssec-geom_traits-concepts The Hierarchy of the Geometry Traits Concepts

A hierarchy of related concepts can be viewed as a directed acyclic
graph, where a node of the graph represents a concept and an arc
represents a refinement relation. An arc directed from concept A to concept B
indicates that concept B refines concept
A. A rather large directed acyclic graph
is required to capture the entire hierarchy of the geometry
traits-class concepts. In the following sections we review individual
clusters of the graph and describe the relations between them.
\cgalFigureRef{aos_fig-central_concept_cluster} depicts the central
cluster.

\cgalFigureBegin{aos_fig-central_concept_cluster,central_concept_cluster.png}
The hierarchy of the main geometry traits concepts.
\cgalFigureEnd

\subsubsection aos_sssec-geom_traits-concepts_basic The Basic Concept

A model of the basic concept AosBasicTraits_2 needs to
define the types \link AosBasicTraits_2::Point_2
Point_2\endlink and \link
AosBasicTraits_2::X_monotone_curve_2
X_monotone_curve_2\endlink, where objects of the former type are the
geometric mapping of arrangement vertices, and objects of the latter
type are the geometric mapping of edges. In addition, it has to
support the set of predicates listed below. This basic set of
predicates is sufficient for constructing arrangements of bounded
\f$x\f$-monotone curves that are pairwise disjoint in their interiors
and points that do not lie in the interiors of the curves. The basic
set of predicates is also sufficient for answering vertical
ray-shooting queries and point-location queries with a small
exception: Locating a point using the landmark strategy requires a
traits class that models the concept AosLandmarkTraits_2;
see Section \ref aos_sssec-tr_landmarks_concept.

\link AosBasicTraits_2::Compare_x_2 **`Compare_x_2`**\endlink:

Compares the \f$x\f$-coordinates of two points.

\link AosBasicTraits_2::Compare_xy_2 **`Compare_xy_2`**\endlink:

Compares two points lexicographically, first by their \f$x\f$-coordinates, and if they are equal, by their \f$y\f$-coordinates.

\link AosBasicTraits_2::Equal_2 **`Equal_2`**\endlink:

There are two overloaded Boolean operators that test equality. One returns `true` iff two given points represent the same geometric point in the two-dimensional surface, and the second returns `true` iff the graphs of two given \f$x\f$-monotone curves are the same.\cgalFootnote{The predicate that tests equality between graphs of two \f$x\f$-monotone curves is used only for testing as part of the test suite.}

\link AosBasicTraits_2::Construct_min_vertex_2 **`Construct_min_vertex_2`**\endlink:

Returns the lexicographically smallest (or left) endpoint of an \f$x\f$-monotone curve.

\link AosBasicTraits_2::Construct_max_vertex_2 **`Construct_max_vertex_2`**\endlink:

Returns the lexicographically largest (or right) endpoint of an \f$x\f$-monotone curve.

\link AosBasicTraits_2::Is_vertical_2 **`Is_vertical_2`**\endlink:

Determines whether an \f$x\f$-monotone curve is vertical.

\link AosBasicTraits_2::Compare_y_at_x_2 **`Compare_y_at_x_2`**\endlink:

Given an \f$x\f$-monotone curve \f$c\f$ and a point \f$p\f$ that lies in the \f$x\f$-range of \f$c\f$, determines whether \f$p\f$ is below, above or lies on \f$c\f$.

\link AosBasicTraits_2::Compare_y_at_x_right_2 **`Compare_y_at_x_right_2`**\endlink:

Given two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ that share a common minimal (left) endpoint \f$p\f$, determines whether \f$c_1\f$ is above or below \f$c_2\f$ immediately to the right of \f$p\f$, or whether the two curves overlap there.

\link AosBasicTraits_2::Do_intersect_2 **`Do_intersect_2`**\endlink:

Determines whether two given \f$x\f$-monotone curves intersect. An input flag determines whether the curve are closed or open.

Every model of the concept AosBasicTraits_2 needs to define
a nested type named \link AosBasicTraits_2::Has_left_category
Has_left_category\endlink. It determines whether the traits class
supports the following predicate:

\link AosBasicTraits_2::Compare_y_at_x_left_2 **`Compare_y_at_x_left_2`**\endlink:

Given two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ that share a common maximal (right) endpoint \f$p\f$, determines whether \f$c_1\f$ is above or under \f$c_2\f$ immediately to the left of \f$p\f$, or whether the two curves overlap there.

If the AosBasicTraits_2::Has_left_category type nested in a
model of the basic concept is defined as Tag_true\cgalFootnote{In
principle, the category type may only be convertible to the tag type,
but in practice the category is typically explicitly defined as the
tag.} the model must support the predicate. If the type is defined as
Tag_false, we resort to an internal version, which is based just on
the reduced set of provided operations. The internal version might be
less efficient, but it exempts the traits developer from the providing
an (efficient) implementation of this predicate---a task that turns
out to be nontrivial in some cases.

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,
whether they 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

1. \link AosBasicTraits_2::Left_side_category `Left_side_category`\endlink,
2. \link AosBasicTraits_2::Right_side_category `Right_side_category`\endlink,
3. \link AosBasicTraits_2::Bottom_side_category `Bottom_side_category`\endlink, and
4. \link AosBasicTraits_2::Top_side_category `Top_side_category`\endlink.

\subsubsection aos_sssec-geom_traits-concepts_intersecting Intersections

Constructing an arrangement induced by \f$x\f$-monotone curves that
may intersect in their interior requires operations that are not part
of the AosBasicTraits_2 concept. The additional operations
are listed by the concept AosXMonotoneTraits_2, which
refines the basic arrangement geometry-traits concept described above.
While models of the AosXMonotoneTraits_2 concept still
handle only \f$x\f$-monotone curves, the curves are not restricted to
be disjoint in their interiors. Such a model must be capable of
computing points of intersection between \f$x\f$-monotone curves,
splitting curves at these intersection points to obtain pairs of
interior-disjoint subcurves, and optionally merging pairs of
subcurves. A point of intersection between two curves is also
represented by the \link AosBasicTraits_2::Point_2
Point_2\endlink type. A model of the refined concept must define an
additional type called Multiplicity. An object of this type
indicates the multiplicity of the intersection point of two curves,
also referred to as the intersection
number.\cgalFootnote{See, e.g.,
https://en.wikipedia.org/wiki/Intersection_number for more information
about intersection numbers.} Loosely speaking, if two curves intersect
at a point \f$p\f$ but have different tangents (first derivatives) at
\f$p\f$, The point \f$p\f$ is of multiplicity 1. If the curve tangents
are equal but their curvatures (second derivatives) are not, \f$p\f$
is of multiplicity 2, and so on. The multiplicity of points of
intersection between line segments is always 1, and the multiplicity
of a point of intersection between two polylines is 1 if the
intersection point is interior to the corresponding two line segments
of the polylines, and undefined (coded as 0) otherwise. A model of the
refined concept thus has to support the following additional
operations:

\link AosXMonotoneTraits_2::Split_2 **`Split_2`**\endlink:

Splits an \f$x\f$-monotone curve \f$c\f$ into two subcurves at a given point \f$p\f$ that lies in the interior of \f$c\f$.

\link AosXMonotoneTraits_2::Are_mergeable_2 **`Are_mergeable_2`**\endlink:

Determines whether two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ that share a common endpoint can be merged into a single continuous \f$x\f$-monotone curve representable by the traits class.\cgalFootnote{On the face of it this seems a difficult predicate to implement. In practice we use very simple tests to decide whether two curves are mergeable: We check whether their underlying curves are identical and whether they do not bend to form a non-\f$x\f$-monotone curve.}

\link AosXMonotoneTraits_2::Merge_2 **`Merge_2`**\endlink:

Merges two mergeable \f$x\f$-monotone curves into a single curve.

\link AosXMonotoneTraits_2::Intersect_2 **`Intersect_2`**\endlink:

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. Providing the multiplicity of an intersection point is not required, but it can expedite the arrangement construction. Typically, the multiplicity is a byproduct of the intersection computation. However, if it is not available, undefined multiplicity (coded as 0) is assumed. Having the multiplicity of intersection points while constructing arrangements enables the exploitation of the geometric knowledge intersection points may have.

Using a model of the AosXMonotoneTraits_2 it is
possible to construct arrangements of sets of \f$x\f$-monotone curves
(and points) that may intersect one another. The two operations
listed above, regarding the merging of curves, are optional, and should
be provided only if the type Has_merge_category nested in a model of
the AosXMonotoneTraits_2 concept is defined as Tag_true.
Otherwise, it is not possible to merge \f$x\f$-monotone curve and
redundant vertices may be left in the arrangement due to the removal of
edges.

\subsubsection aos_sssec-geom_traits-concepts_arbitrary Supporting Arbitrary Curves

The concept AosTraits_2 refines the
AosXMonotoneTraits_2 concept. A model of the refined concept
must define an additional type that is used to represent general, not
necessarily \f$x\f$-monotone and not necessarily continuous, curves,
named \link AosTraits_2::Curve_2 Curve_2\endlink. It also
has to support the subdivision of a curve of that type into a set of
continuous \f$x\f$-monotone curves and isolated points. For example,
the curve \f$c:\ (x^2 + y^2)(x^2 + y^2 - 1) = 0\f$ comprises the unit
circle (the locus of all points for which \f$x^2 + y^2 = 1\f$) and the
origin (the singular point \f$(0,0)\f$). \f$c\f$ should therefore be
subdivided into two circular arcs, the upper part and the lower part
of the unit circle, and a single isolated point. In particular a
model of the refined concept has to support the following additional
operation:

\link AosTraits_2::Make_x_monotone_2 **`Make_x_monotone_2`**\endlink:

Divides a given general curve of type \link AosTraits_2::Curve_2 `Curve_2`\endlink into continuous weakly \f$x\f$-monotone curves and isolated points.

Note that a model of the refined concept AosTraits_2 is
required only when using the free insert() function templates (see
Section \ref arr_secgl_funcs) that accept an object of type \link
AosTraits_2::Curve_2 Curve_2\endlink or a range of objects
of that type. In all other cases it is sufficient to use a model of
the AosXMonotoneTraits_2 concept.

\subsubsection aos_sssec-tr_landmarks_concept The Landmark Concept

\cgalFigureBegin{aos_fig-landmark_concept_cluster,landmark_concept_cluster.png}
The traits-concept hierarchy for arrangements associated with the landmark
point-location strategy.
\cgalFigureEnd

The type of an arrangement associated with the landmark point-location
strategy (see Section \ref arr_ssecpl) must be an instance of the
Arrangement_on_surface_2<GeomTraits, TopolTraits> class template,
where the GeomTraits parameter is substituted by a model of the
concept AosLandmarkTraits_2. (Naturally, it can also model
either the AosXMonotoneTraits_2 concept or the
AosTraits_2 concept.) The AosLandmarkTraits_2
concept refines the two concepts AosApproximatePointTraits_2 and
AosConstructXMonotoneCurveTraits_2. Each of these two
concepts, in turn, refines the concept AosBasicTraits_2.

A model of the AosApproximatePointTraits_2 concept must define a
fixed precision number type (typically the double-precision
floating-point double) and support the operation below (in addition
to fulfilling the requirements listed by the AosBasicTraits_2
concept).

\link AosApproximatePointTraits_2::Approximate_2 **`Approximate_2`**\endlink:

Given a point `p`, approximate the \f$x\f$ and \f$y\f$-coordinates of `p` using a not necessarily multi-precision number type. We use this operation for approximate computations---there are certain operations performed during the search for the location of the point that need not be exact, and that can be performed faster when carried out, for example, using a fixed-precision number type.

A model of the AosConstructXMonotoneCurveTraits_2 concept
must support the operation below (in addition to fulfilling the
requirements listed by the AosBasicTraits_2 concept).

\link AosConstructXMonotoneCurveTraits_2::Construct_x_monotone_curve_2 **`Construct_x_monotone_curve_2`**\endlink:

Given two points \f$p_1\f$ and \f$p_2\f$, construct an \f$x\f$-monotone curve connecting \f$p_1\f$ and \f$p_2\f$.

Most traits classes model the AosTraits_2 concept, and some
also model the AosLandmarkTraits_2 concept.

The concept AosConstructCurveTraits_2 refines the concept
AosBasicTraits_2. A model of the AosConstructCurveTraits_2 concept
must support the operation below (in addition to fulfilling the
requirements listed by the AosBasicTraits_2 concept).

\subsubsection aos_sssec-tr_additional_concepts The Construct Curve Concept

\link AosConstructCurveTraits_2::Construct_curve_2 **`Construct_curve_2`**\endlink:

Given two points \f$p_1\f$ and \f$p_2\f$, construct a curve connecting \f$p_1\f$ and \f$p_2\f$.

The Arr_polyline_traits_2<SubcurveTraits_2> class template handles
polylines; see Section ~\ref arr_sssectr_polylines.
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 concept AosConstructCurveTraits_2
to enable the construction of polylines from a sequence of two or more points.

\subsubsection aos_sssec-tr_approximatetion_concept Supporting Approximations of Curves

Operations on arrangements are guaranteed to be robust only if the
operations of the geometry traits used to carry out the high-level
operations are robust. Geometry traits constructors are guaranteed to
be robust only if the kernel in use supports exact constructions, such
as the Epec kernel. Even if you only intend to perform point-location
queries on an arrangement induced by a collection of curves, you need
an exact-construction kernel, if the curves are not pairwise disjoint
in their interiors. However, when using an exact-construction kernel
you still may desire to perform (independent) operations on
approximations of the points or the interior-disjoint \f$x\f$-monotone
curves of the arrangements in order to gain speed, for example drawing
the arrangement on a raster window. Naturally, reconstructing an
arrangement from the approximations of its points and
interior-disjoint \f$x\f$-monotone curves, may result with an arrangement
of a different topology, or even worse, intersections in the interior
of the curves.

The concept AosApproximateTraits_2 refines the concept
AosApproximatePointTraits_2. In addition to the type
Approximate_number_type required by the latter, a model of the
AosApproximateTraits_2 concept must define the type
Approximate_point_2, which is typically defined as
CGAL::Cartesian<Approximate_number_type>::%Point_2. Also, it must
support the operations below (in addition to the operation required by
the concept AosApproximatePointTraits_2).