namespace CGAL {
/*!

\mainpage User Manual 
\anchor Chapter_3D_Triangulations
\anchor chapterTriangulation3
\cgalAutoToc

\authors Clément Jamin, Sylvain Pion and Monique Teillaud

\image html triangulation3.png
\image latex triangulation3.png

The basic 3D-triangulation class of \cgal is primarily designed to
represent the triangulations of a set of points \f$ A\f$ in \f$ \mathbb{R}^3\f$. It is
a partition of the convex hull of \f$ A\f$ into tetrahedra whose vertices
are the points of \f$ A\f$. Together with the unbounded cell having the
convex hull boundary as its frontier, the triangulation forms a
partition of \f$ \mathbb{R}^3\f$. Its cells (\f$ 3\f$-faces) are such that two cells
either do not intersect or share a common facet (\f$ 2\f$-face), edge
(\f$ 1\f$-face) or vertex (\f$ 0\f$-face).

\section Triangulation3secintro Representation 

In order to deal
only with tetrahedra, which is convenient for many applications, the
unbounded cell can be subdivided into tetrahedra by considering that
each convex hull facet is incident to an `infinite cell` having as
fourth vertex an auxiliary vertex called the `infinite vertex`. In
that way, each facet is incident to exactly two cells and special cases
at the boundary of the convex hull are simple to deal with.

The class `Triangulation_3<TriangulationTraits_3,TriangulationDataStructure_3>` of \cgal implements this
point of view and therefore considers the triangulation of the set
of points as a set of finite and infinite tetrahedra. Notice that the
infinite vertex has no significant coordinates and that no
geometric predicate can be applied on it.

A triangulation is a collection of vertices and cells that are linked
together through incidence and adjacency relations. Each cell gives
access to its four incident vertices and to its four adjacent
cells. Each vertex gives access to one of its incident cells.

The four vertices of a cell are indexed with 0, 1, 2 and 3 in positive
orientation, the positive orientation being defined by the orientation
of the underlying Euclidean space \f$ \mathbb{R}^3\f$ (see
\cgalFigureRef{Triangulation3figorient}). The neighbors of a cell are also
indexed with 0, 1, 2, 3 in such a way that the neighbor indexed by \f$ i\f$
is opposite to the vertex with the same index.

\cgalFigureBegin{Triangulation3figorient,orient.png}
Orientation of a cell (3-dimensional case).
\cgalFigureEnd

As in the underlying combinatorial triangulation (see
Chapter \ref chapterTDS3 "3D Triangulation Data Structure"), 
edges (\f$ 1\f$-faces) and facets (\f$ 2\f$-faces)
are not explicitly 
represented: a facet is given by a cell and an index (the facet
`i` of a cell `c` is the facet of `c` that is opposite to
the vertex with index `i`) and an edge is given by a cell and two
indices (the edge `(i,j)` of a cell `c` is the edge whose
endpoints are the vertices of `c` with indices `i` and
`j`). See \cgalFigureRef{TDS3figrepres}.

<b>Degenerate Dimensions</b>

The class `Triangulation_3` can also deal with
triangulations whose dimension \f$ d\f$ is less than 3. A triangulation of a
set of points in \f$ \mathbb{R}^d\f$ covers the whole space \f$ \mathbb{R}^d\f$ and consists of
cells having \f$ d+1\f$ vertices: some of them are infinite, they are
obtained by linking the additional infinite vertex to each facet of
the convex hull of the points.
<UL>
<LI> <I>dimension 2:</I> when a triangulation only contains
coplanar points (which is the case when there are only three points), 
it consists of triangular faces.
<LI> <I>dimension 1:</I> the triangulation contains only collinear 
points (which is the case when there are only two points), it consists
of edges.
<LI> <I>dimension 0:</I> the triangulation contains only one
finite point.
<LI> <I>dimension -1:</I> this is a convention to handle the case
when the only vertex of the triangulation is the infinite one.
</UL>

The same cell class is used in all cases: triangular faces in
2D can be considered as degenerate cells, having only three vertices
(resp. neighbors) numbered \f$ (0,1,2)\f$;
edges in 1D have only two vertices (resp. neighbors) numbered \f$ 0\f$ and \f$ 1\f$.

The implicit representation of facets (resp. edges) still holds
for degenerate dimensions (<I>i.e.</I> dimensions \f$ <3\f$): in
dimension 2, each cell has only one facet of index 3, and 3 edges
\f$ (0,1)\f$, \f$ (1,2)\f$ and \f$ (2,0)\f$; in dimension 1, each cell has one edge
\f$ (0,1)\f$.

<b>Validity</b>

A triangulation of \f$ \mathbb{R}^3\f$ is said to be *locally valid* iff

<B>(a)-(b)</B> Its underlying combinatorial graph, the triangulation
data structure, is *locally valid* 
(see Section \ref TDS3secintro "Introduction" of Chapter \ref chapterTDS3 "3D Triangulation Data Structure")

<B>(c)</B> Any cell has its vertices ordered according to positive
orientation. See \cgalFigureRef{Triangulation3figorient}.

When the triangulation is degenerated into a triangulation of
dimension 2, the geometric validity reduces to:

<B>(c-2D)</B> For any two adjacent triangles \f$ (u,v,w_1)\f$ and \f$ (u,v,w_2)\f$ with
common edge \f$ (u,v)\f$, \f$ w_1\f$ and \f$ w_2\f$ lie on opposite sides of \f$ (u,v)\f$
in the plane.

When all the points are collinear, this condition becomes:

<B>(c-1D)</B> For any two adjacent edges \f$ (u,v)\f$ and \f$ (v,w)\f$, \f$ u\f$ and
\f$ w\f$ lie on opposite sides of the common vertex \f$ v\f$ on the line.

The method  `Triangulation_3::is_valid()` checks
the local validity of a given triangulation. This does not always
ensure global validity \cgalCite{mnssssu-cgpvg-96}, \cgalCite{dlpt-ccpps-98} but it is 
sufficient for practical cases.

\section Triangulation_3Delaunay Delaunay Triangulation

The class `Delaunay_triangulation_3` represents a three-dimensional
Delaunay triangulation.

Delaunay triangulations have the specific <I>empty sphere property</I>,
that is, the circumscribing sphere of each cell of such a triangulation
does not contain any other vertex of the triangulation in its interior.
These triangulations are uniquely defined except in degenerate cases
where five points are co-spherical. Note however that the \cgal implementation
computes a unique triangulation even in these cases.

This implementation is fully dynamic: it supports insertions of points, vertex removals
and displacements of points.

\section Triangulation3secclassRegulartriangulation Regular Triangulation 

The class `Regular_triangulation_3` implements incremental regular
triangulations, also known as weighted Delaunay triangulations.

Let\f$ {p}^{(w)}=(p,w_p), p\in\mathbb{R}^3, w_p\in\mathbb{R}\f$ and 
\f$ {z}^{(w)}=(z,w_z), z\in\mathbb{R}^3, w_z\in\mathbb{R}\f$ be two weighted points. 
A weighted point
\f$ {p}^{(w)}=(p,w_p)\f$ can also be seen as a sphere of center \f$ p\f$ and
radius \f$ \sqrt{w_p}\f$. 
The <I>power product</I> between \f$ {p}^{(w)}\f$ and \f$ {z}^{(w)}\f$ is
defined as 
\f[ \Pi({p}^{(w)},{z}^{(w)}) = {\|{p-z}\|^2-w_p-w_z} \f]
where \f$ \|{p-z}\|\f$ is the Euclidean distance between \f$ p\f$ and \f$ z\f$.

The weighted points \f$ {p}^{(w)}\f$ and \f$ {z}^{(w)}\f$
are said to be <I>orthogonal</I> iff \f$ \Pi{({p}^{(w)},{z}^{(w)})}
= 0\f$ (see \cgalFigureRef{Triangulation3figortho)}.

\cgalFigureBegin{Triangulation3figortho,ortho.svg}
Orthogonal weighted points (picture in 2D).
\cgalFigureEnd

Four weighted points have a unique common orthogonal weighted point
called the <I>power sphere</I>. The weighted point orthogonal to
three weighted points in the plane defined by these three points is
called the <I>power circle</I>. The
<I>power segment</I> will denote the weighted point orthogonal to
two weighted points on the line defined by these two points.


Let \f$ {S}^{(w)}\f$ be a set of weighted points in \f$ \mathbb{R}^3\f$. 
A sphere \f$ {z}^{(w)}\f$ is said to be
<I>regular</I> if \f$ \forall {p}^{(w)}\in{S}^{(w)},
\Pi{({p}^{(w)},{z}^{(w)})}\geq 0\f$.

A triangulation of \f$ {S}^{(w)}\f$ is <I>regular</I> if the power spheres
of all simplices are regular.

The regular triangulation of
\f$ {S}^{(w)}\f$ is in fact the projection onto \f$ \mathbb{R}^3\f$ of the convex hull 
of the four-dimensional points \f$ (p,\|p-O\|^2-w_p),\f$ for
\f$ {p}^{(w)}=(p,w_p)\in{S}^{(w)}\f$. 
Note that all points of \f$ {S}^{(w)}\f$ do not
necessarily appear as vertices of the regular
triangulation. To know more about regular triangulations, see for
example \cgalCite{es-itfwr-96}.

When all weights are 0, power spheres are nothing more than
circumscribing spheres, and the regular triangulation is exactly the
Delaunay triangulation.

The implementation of 3D regular triangulation supports insertions of weighted points, and vertex removals. Displacements are not supported in the current implementation.

\section Triangulation3secdesign Software Design 

The main classes `Triangulation_3`, `Delaunay_triangulation_3` and
`Regular_triangulation_3` are connected to each other by the
derivation diagram shown in \cgalFigureRef{t3_derivation}. This diagram
also shows another class: `Triangulation_utils_3`, which provides
a set of tools operating on the indices of vertices in cells.

\cgalFigureBegin{t3_derivation,derivation.png}
Derivation diagram of the 3D triangulation classes.
\cgalFigureEnd

The three main classes (`Triangulation_3`, `Delaunay_triangulation_3`
and `Regular_triangulation_3`) provide high-level geometric functionality
such as location of a point in the triangulation \cgalCite{cgal:dpt-wt-02}, insertion
and possibly removal of a point \cgalCite{cgal:dt-pvr3d-03}, and are responsible for the
geometric validity. They are built as layers on top of a triangulation data
structure, which stores their combinatorial structure. This separation between
the geometry and the combinatorics is reflected in the software design by the
fact that these three triangulation classes take the following template parameters :

<UL>
<LI> the *geometric traits* class, which provides the type of points
to use as well as the elementary operations on them (predicates and
constructions). The concepts for these parameters are described in more
details in Section \ref Triangulation3secTraits.
<LI> the *triangulation data structure* class, which stores their
combinatorial structure, described in Section \ref TDS3secdesign "Software Design" of
Chapter \ref chapterTDS3 "3D Triangulation Data Structure".
<LI> the *location policy* tag, which is supported only by the Delaunay
triangulation class, described in Section \ref Triangulation3seclocpol.
</UL>

Optionally, the main Delaunay and regular triangulations algorithms (insert, remove) 
support multi-core shared-memory architectures to take advantage of available parallelism.
For this purpose, a model of the concept `SurjectiveLockDataStructure` can be 
given as fourth template parameter; it defaults to 
`Spatial_lock_grid_3`. This data structure
allows to lock points with coordinates (x, y, z) in a 3D domain. When a thread owns the
lock on a point, no other thread can lock this point. Locking a facet (resp. a cell)
boils down to locking all its 3 (resp. 4) incident vertices. 
See Section \ref Triangulation_3ParallelAlgorithms for more details.

\subsection Triangulation3secTraits The Geometric Traits Parameter 

The first template parameter of the triangulation class
`Triangulation_3<TriangulationTraits_3, TriangulationDataStructure_3>`
is the geometric traits class, described by the concept
`TriangulationTraits_3`. It must define the types of the geometric objects
(points, segments, triangles and tetrahedra) forming the triangulation together
with a few geometric predicates on these objects: orientation in space,
orientation in case of coplanar points, order of collinear points.

In addition to the requirements described before, the geometric traits
class of `Delaunay_triangulation_3` must define predicates to test for the
<I>empty sphere property</I>. It is described by the concept
`DelaunayTriangulationTraits_3`, which refines `TriangulationTraits_3`.

In addition to the requirements described before, the geometric traits
class of `Regular_triangulation_3` must define predicates to test for the
<I>power distances</I> and orientation tests for <I>power spheres</I>. 
It is described by the concept
`RegularTriangulationTraits_3`, which refines `TriangulationTraits_3`.



All kernels provided by \cgal can all be used as models for the geometric traits
parameter.


\subsection Triangulation3sectds The Triangulation Data Structure Parameter 

The second template parameter of the main classes (`Triangulation_3`,
`Delaunay_triangulation_3` and `Regular_triangulation_3`) is a
triangulation data structure class. This class can be seen as a container for
the cells and vertices maintaining incidence and adjacency relations (see
Chapter \ref chapterTDS3). A model of this triangulation data structure is
`Triangulation_data_structure_3`,
and it is described by the `TriangulationDataStructure_3` concept
. This model is itself
parameterized by a vertex base and a cell base classes, which gives the
possibility to customize the vertices and cells used by the triangulation data
structure, and hence by the geometric triangulation using it. Depending on the
kind of triangulation used, the requirements on the vertex and cell base
classes vary, and are expressed by various concepts, following the refinement
diagram shown in \cgalFigureRef{T3concepthierarchy}.

\cgalFigureBegin{T3concepthierarchy,concept_hierarchy.png}
Concepts refinement hierarchy for the vertex and cell base classes parameters.
\cgalFigureEnd

A default value for the triangulation data structure parameter is provided in
all the triangulation classes, so it need not be specified by the user unless
he wants to use a different triangulation data structure or a different vertex
or cell base class.

\subsection Triangulation3seclocpol The Location Policy Parameter 

The Delaunay triangulation class supports an optional feature which maintains
an additional data structure for fast point location queries. 
The fast location policy should be used when the user inserts points in a random
order or needs to do many unrelated queries.
If the user is able to give a good hint to help the point location of
its queries (and its newly inserted points), then it should prefer the default
policy. In such a case where good hints are provided,
the default policy save some memory (few percents), and is faster.
Notice that if points are not inserted one by one, but as a range, then a good hint is 
automatically computed using spatial sort.

Reading Section \ref Triangulation3seccomplexity on complexity and
performance can help making an informed choice for this parameter.

The point location strategy can be selected with the third template argument of
`Delaunay_triangulation_3`, `LocationPolicy`, which enables a fast
point location data structure when set to `Fast_location`. By default, it
uses `Compact_location`.

Note that you can specify the `LocationPolicy` parameter without specifying
the triangulation data structure, in case you are fine with the default there.
In this case, the `LocationPolicy` appears as a second parameter after the
geometric traits.\cgalFootnote{The mechanism used behind the scenes to allow this syntactical convenience is called <I>deduced parameters</I>.}

The `Fast_location` policy is implemented using a hierarchy of
triangulations; it changes the behavior of functions `locate`,
`insert`, `move`, and `remove`.
As proved in \cgalCite{cgal:d-dh-02}, this structure has an
optimal behavior when it is built for Delaunay triangulations.

In this setting, if you build a triangulation by iteratively inserting points,
you should try to shuffle the points beforehand, as the time complexity is
guaranteed only for a randomized order. For example, inserting points in
lexicographic order is typically much slower. Note that this shuffling is
performed internally by the constructor taking a range of points.

Prior to \cgal 3.6, this functionality was available through the
`Triangulation_hierarchy_3` class, which is now deprecated.

\subsection Triangulation_3FlexibilityoftheDesign Flexibility of the Design

In order to satisfy as many uses as possible, a design has been selected that
allows to exchange different parts to meet the users' needs, while still
re-using a maximum of the provided functionalities. We have already seen that
the main triangulation classes are parameterized by a geometric traits class
and a triangulation data structure (TDS), so that each of them can be
interchanged with alternate implementations.

The most useful flexibility is the ability given to the user to add his own
data in the vertices and cells by providing his own vertex and cell base
classes to `Triangulation_data_structure_3`. The
\cgalFigureRef{T3figlayers} shows in more detail the flexibility that is
provided, and the place where the user can insert his own vertex and/or cell
base classes.

\cgalFigureBegin{T3figlayers,design.png}
Triangulation software design.
\cgalFigureEnd

The design of the triangulation data structure gives the possibility to store
any kind of data, including handles (an entity akin to pointers) directly in
the vertex and cell base classes.

To do so, there are three possibilities. The simplest one is to use the
class `Triangulation_vertex_base_with_info_3`, and this approach is
illustrated in a following subsection \ref Triangulation3secexamplescolor.
The most complicated one, and probably useless for almost all cases, is to
write a vertex base class from scratch, following the documented requirements.
This is mostly useless because most of the time it is enough to derive from
the models that \cgal provides, and add the desired features.
In this case, when the user needs to access some type that depends on the
triangulation data structure (typically handles), then he should write
something like:

\code{.cpp}

...
template < class GT, class Vb = Triangulation_vertex_base<GT> >
class My_vertex
: public Vb
{
public:
typedef typename Vb::Point Point;
typedef typename Vb::Cell_handle Cell_handle;

template < class TDS2 >
struct Rebind_TDS {
typedef typename Vb::template Rebind_TDS<TDS2>::Other Vb2;
typedef My_vertex<GT, Vb2> Other;
};

My_vertex() {}
My_vertex(const Point&p) : Vb(p) {}
My_vertex(const Point&p, Cell_handle c) : Vb(p, c) {}
...
};
... // The rest has not changed

\endcode

The situation is exactly similar for cell base classes.
Section \ref TDS3secdesign "Software Design" provides more detailed information.

\subsection Triangulation_3ParallelAlgorithms Parallel Algorithms

Parallel algorithms of `Delaunay_triangulation_3` and 
`Regular_triangulation_3` are enabled 
if the `TriangulationDataStructure_3::Concurrency_tag` type is `Parallel_tag` and a
reference to a lock data structure instance is provided via the constructor or 
by using `Triangulation_3::set_lock_data_structure`. This data structure
must be a model of the concept `SurjectiveLockDataStructure` and can be 
optionally given as a template parameter of the triangulation; 
it defaults to `Spatial_lock_grid_3`.

Note that the parallel Delaunay 
triangulation must use the default compact location policy (and not the fast 
one). If those conditions are fulfilled, the insertion/removal of a 
range of points will be performed in parallel, and the individual 
insert/remove operations will be optionally thread-safe.

Parallel algorithms require the program to be linked against 
the <a href="https://www.threadingbuildingblocks.org">Intel TBB library</a>.
To control the number of threads used, the user may use the tbb::task_scheduler_init class.
See the <a href="https://www.threadingbuildingblocks.org/documentation">TBB documentation</a> 
for more details.

\section Triangulation3secexamples Examples 

\subsection Triangulation_3BasicExample Basic Example

This example shows the incremental construction of a 3D triangulation, the
location of a point and how to perform elementary operations on indices in a
cell. It uses the default parameter of the `Triangulation_3` class.

\cgalExample{Triangulation_3/simple_triangulation_3.cpp}

\subsection Triangulation_3ChangingtheVertexBase Changing the Vertex Base

The following two examples show how the user can plug his own vertex base in a
triangulation. Changing the cell base is similar.

\subsubsection Triangulation3secexamplescolor Adding a Color 

When the user doesn't need to add a type in a vertex which depends on the
`TriangulationDataStructure_3` (e.g. a `Vertex_handle` or
`Cell_handle`), then he can use the
`Triangulation_vertex_base_with_info_3` class to add his own information
easily in the vertices. The example below shows how to add a `Color`
this way.

\cgalExample{Triangulation_3/color.cpp}

\subsubsection Triangulation_3AddingHandles Adding Handles

When the user needs to add a type in a vertex which depends on the
`TriangulationDataStructure_3` (e.g. a `Vertex_handle` or
`Cell_handle`), then he has to derive his own vertex base class,
as the following example shows.

\cgalExample{Triangulation_3/adding_handles_3.cpp}

\subsection Triangulation_3SettingInformationWhileInserting Setting Information While Inserting a Range of Points

The most efficient method to insert (weighted) points in a
Delaunay (or regular) triangulation is to provide an iterator
range over (weighted) points to the insert function. However, an iterator range of
(weighted) points does not allow to set different information to each vertex.
To solve this problem, in the case the vertex type of the triangulation 
is a model of the concept `TriangulationVertexBaseWithInfo_3`
(such as `Triangulation_vertex_base_with_info_3`), we provide three examples 
doing the same operation: set an unsigned integer as the information 
of each vertex. The value of this unsigned integer is the initial order
of the corresponding point given in the range.

\subsubsection Triangulation_3UsinganIteratorOverPairs Using an Iterator Over Pairs

Each point and its information are gathered into a pair. We provide
the constructor of the triangulation (which is calling the `insert` function)
with a range of such pairs.
\cgalExample{Triangulation_3/info_insert_with_pair_iterator.cpp}

\subsubsection Triangulation_3UsingtheBoostZipIterator Using the Boost Zip Iterator

Information and points are in separate containers. We use
<A HREF="https://www.boost.org/libs/iterator/doc/index.html#specialized-adaptors">`boost::zip_iterator`</A> to provide an iterator gathering them.

\cgalExample{Triangulation_3/info_insert_with_zip_iterator.cpp}

\subsubsection Triangulation_3UsingtheBoostTransformIterator Using the Boost Transform Iterator

We define a functor `Auto_count` used together with
<A HREF="https://www.boost.org/libs/iterator/doc/index.html#specialized-adaptors">`boost::transform_iterator`</A> to set the order of each point
in the range. Note that this is correct because the iterator
is dereferenced only once per point during the insertion.
\cgalExample{Triangulation_3/info_insert_with_transform_iterator.cpp}

\subsection Triangulation3secsimplex The Simplex Class 

The triangulation defines a `Triangulation_3::Simplex` class that represents a
simplex (vertex, edge, facet or cell). This example demonstrates how
simplices can be stored in a set.

\cgalExample{Triangulation_3/simplex.cpp}

\subsection Triangulation3exfastlocation Fast Point Location for Delaunay Triangulations 

\cgalExample{Triangulation_3/fast_location_3.cpp}

\subsection Triangulation_3FindingtheCellsinConflict Finding the Cells in Conflict with a Point in a Delaunay Triangulation

\cgalExample{Triangulation_3/find_conflicts_3.cpp}

\subsection Triangulation_3RegularTriangulation Regular Triangulation

\subsubsection Triangulation_3RegularTriangulationDefaults Regular Triangulation with Defaults

This example shows the building of a regular triangulation. In this
triangulation, points have an associated weight, and some points can
be hidden and do not result in vertices in the triangulation.

\cgalExample{Triangulation_3/regular_3.cpp}


\subsubsection Triangulation_3RegularTriangulationInfo Regular Triangulation with Custom Vertex

This example shows that one must use the class `Regular_triangulation_vertex_base_3` as vertex base class,
if one has to specifiy the template parameter. 

\cgalExample{Triangulation_3/regular_with_info_3.cpp}



\subsection Triangulation_3ParallelDelaunay Parallel Insertion in Delaunay Triangulation

This example shows the parallel building of a Delaunay triangulation.

\cgalExample{Triangulation_3/parallel_insertion_in_delaunay_3.cpp}

\subsection Triangulation_3ParallelRegular Parallel Insertion and Removal in Regular Triangulation

This example shows the parallel building of a regular triangulation, followed by the parallel
removal of the first 100,000 vertices.

\cgalExample{Triangulation_3/parallel_insertion_and_removal_in_regular_3.cpp}

\subsection Triangulation3Draw Draw a 3D Triangulation
\anchor ssecDrawT3

A 3D triangulation can be visualized by calling the `CGAL::draw()` function as shown in the following example. This function opens a new window showing the given 3D triangulation. The function is blocking, that is the program continues as soon as the user closes the window.

\cgalExample{Triangulation_3/draw_triangulation_3.cpp}

This function requires CGAL_Qt5, and is only available if the flag CGAL_USE_BASIC_VIEWER is defined at compile time.

\cgalFigureBegin{fig_draw_triangulation_3,draw_triangulation_3.png}
Result of the run of the draw_triangulation_3 program. A window shows the 3D triangulation and allows to navigate through the 3D scene.
\cgalFigureEnd


\section Triangulation3seccomplexity Complexity and Performance 

In 3D, the worst case complexity of a triangulation is quadratic in the number
of points. For Delaunay triangulations, this bound is reached in cases such as
points equally distributed on two non-coplanar lines. However, the good news
is that, in many cases, the complexity of a Delaunay triangulation is linear or
close to linear in the number of points. Several
articles \cgalCite{d-hdvdl-89}, \cgalCite{e-dpssdt-02}, \cgalCite{geometrica-5986i}, \cgalCite{prisme-4453a}, \cgalCite{prisme-abl-03}
have proved such good complexity bounds for specific point distributions, such
as points distributed on surfaces under some conditions.

\subsection Triangulation_3RunningTime Running Time

There are several algorithms provided in this package. We will focus here on
the following ones and give practical numbers on their efficiency :
<UL>
<LI>construction of a triangulation from a range of points, 
<LI>location of a point (using the `locate` function),
<LI>removal of a vertex (using the `remove` function).
</UL>

We will use the following types of triangulations, using
`Exact_predicates_inexact_constructions_kernel` as geometric traits:
<UL>
<LI><B>Delaunay</B> : `Delaunay_triangulation_3`
<LI><B>Delaunay - %Fast location</B> : `Delaunay_triangulation_3` with `Fast_location`
<LI><B>Regular</B> : `Regular_triangulation_3` (default setting : memorize hidden points)
<LI><B>Regular - No hidden points</B> : `Regular_triangulation_3` with hidden points discarded.
</UL>

\cgalFigureRef{Triangulation3figbenchmarks} shows, for all these types of
triangulations, the times in seconds taken to build a triangulation from a
given number of points, then the average time to perform one point location in
triangulations of various sizes, and the average time to perform one vertex
removal (which is largely independent on the size of the triangulation).

The data sets used here are points randomly distributed in the unit cube (the
coordinates are generated using the <TT>drand48</TT> C function). In the
weighted case, the weights are all zero, which means that there are actually no
hidden points during execution.

The measurements have been performed using \cgal 3.6, using the <span class="textsc">Gnu</span> \cpp compiler
version 4.3.2, under Linux (Fedora 10 distribution), with the compilation options
<TT>-O3 -DCGAL_NDEBUG</TT>. The computer used was equipped with a 64bit Intel
Xeon 3GHz processor and 32GB of RAM (a recent desktop machine as of 2009).

\cgalFigureAnchor{Triangulation3figbenchmarks}
<CENTER>
<TABLE CELLSPACING=5 >
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>Delaunay</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Delaunay</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Regular</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Regular</B> 
<TR>
<TD ALIGN=LEFT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>%Fast location</B> 
<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>No hidden points</B> 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
Construction from \f$ 10^2\f$ points 
<TD ALIGN=RIGHT NOWRAP>
0.00054 
<TD ALIGN=RIGHT NOWRAP>
0.000576 
<TD ALIGN=RIGHT NOWRAP>
0.000948 
<TD ALIGN=RIGHT NOWRAP>
0.000955 
<TR>
<TD ALIGN=LEFT NOWRAP>
Construction from \f$ 10^3\f$ points 
<TD ALIGN=RIGHT NOWRAP>
0.00724 
<TD ALIGN=RIGHT NOWRAP>
0.00748 
<TD ALIGN=RIGHT NOWRAP>
0.0114 
<TD ALIGN=RIGHT NOWRAP>
0.0111
<TR>
<TD ALIGN=LEFT NOWRAP>
Construction from \f$ 10^4\f$ points 
<TD ALIGN=RIGHT NOWRAP>
0.0785 
<TD ALIGN=RIGHT NOWRAP>
0.0838 
<TD ALIGN=RIGHT NOWRAP>
0.122 
<TD ALIGN=RIGHT NOWRAP>
0.117 
<TR>
<TD ALIGN=LEFT NOWRAP>
Construction from \f$ 10^5\f$ points 
<TD ALIGN=RIGHT NOWRAP>
0.827 
<TD ALIGN=RIGHT NOWRAP>
0.878 
<TD ALIGN=RIGHT NOWRAP>
1.25 
<TD ALIGN=RIGHT NOWRAP>
1.19 
<TR>
<TD ALIGN=LEFT NOWRAP>
Construction from \f$ 10^6\f$ points 
<TD ALIGN=RIGHT NOWRAP>
8.5 
<TD ALIGN=RIGHT NOWRAP>
9.07 
<TD ALIGN=RIGHT NOWRAP>
12.6 
<TD ALIGN=RIGHT NOWRAP>
12.2 
<TR>
<TD ALIGN=LEFT NOWRAP>
Construction from \f$ 10^7\f$ points 
<TD ALIGN=RIGHT NOWRAP>
87.4 
<TD ALIGN=RIGHT NOWRAP>
92.5 
<TD ALIGN=RIGHT NOWRAP>
129 
<TD ALIGN=RIGHT NOWRAP>
125 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
Point location in \f$ 10^2\f$ points 
<TD ALIGN=RIGHT NOWRAP>
9.93e-07 
<TD ALIGN=RIGHT NOWRAP>
1.06e-06 
<TD ALIGN=RIGHT NOWRAP>
7.19e-06 
<TD ALIGN=RIGHT NOWRAP>
6.99e-06 
<TR>
<TD ALIGN=LEFT NOWRAP>
Point location in \f$ 10^3\f$ points 
<TD ALIGN=RIGHT NOWRAP>
2.25e-06 
<TD ALIGN=RIGHT NOWRAP>
1.93e-06 
<TD ALIGN=RIGHT NOWRAP>
1.73e-05 
<TD ALIGN=RIGHT NOWRAP>
1.76e-05 
<TR>
<TD ALIGN=LEFT NOWRAP>
Point location in \f$ 10^4\f$ points 
<TD ALIGN=RIGHT NOWRAP>
4.79e-06 
<TD ALIGN=RIGHT NOWRAP>
3.09e-06 
<TD ALIGN=RIGHT NOWRAP>
3.96e-05 
<TD ALIGN=RIGHT NOWRAP>
3.76e-05 
<TR>
<TD ALIGN=LEFT NOWRAP>
Point location in \f$ 10^5\f$ points 
<TD ALIGN=RIGHT NOWRAP>
2.98e-05 
<TD ALIGN=RIGHT NOWRAP>
6.12e-06 
<TD ALIGN=RIGHT NOWRAP>
1.06e-04 
<TD ALIGN=RIGHT NOWRAP>
1.06e-04 
<TR>
<TD ALIGN=LEFT NOWRAP>
Point location in \f$ 10^6\f$ points 
<TD ALIGN=RIGHT NOWRAP>
1e-04 
<TD ALIGN=RIGHT NOWRAP>
9.65e-06 
<TD ALIGN=RIGHT NOWRAP>
2.7e-04 
<TD ALIGN=RIGHT NOWRAP>
2.67e-04 
<TR>
<TD ALIGN=LEFT NOWRAP>
Point location in \f$ 10^7\f$ points 
<TD ALIGN=RIGHT NOWRAP>
2.59e-04 
<TD ALIGN=RIGHT NOWRAP>
1.33e-05 
<TD ALIGN=RIGHT NOWRAP>
6.25e-04 
<TD ALIGN=RIGHT NOWRAP>
6.25e-04 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
Vertex removal 
<TD ALIGN=RIGHT NOWRAP>
1e-04 
<TD ALIGN=RIGHT NOWRAP>
1.03e-04 
<TD ALIGN=RIGHT NOWRAP>
1.42e-04 
<TD ALIGN=RIGHT NOWRAP>
1.38e-04 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
</TABLE>
</CENTER>
\cgalFigureCaptionBegin{Triangulation3figbenchmarks}
Running times in seconds for algorithms on 3D triangulations.
\cgalFigureCaptionEnd

More benchmarks comparing \cgal to other software can be found
in \cgalCite{msri52:liu-snoeyink-05}.

\subsection Triangulation_3ParallelPerformance Parallel Performance

Figure \cgalFigureRef{Triangulation3figparallelspeedup} shows insertion
and removal speed-ups obtained using the parallel version of the 
triangulation algorithms of \cgal 4.5. The machine used is a PC running 
Windows 7 64-bits with two 6-core 
Intel Xeon CPU X5660 clocked at 2.80 GHz
with 32GB of RAM. The program has been compiled with 
Microsoft Visual C++ 2012 in Release mode.

\cgalFigureBegin{Triangulation3figparallelspeedup,DT3_parallel_benchmark.png}
Speed-up obtained for the insertion of 1M points randomly generated inside
a cube (red), and the removal of 100K of them (blue), compared 
to the sequential version of the algorithm.
\cgalFigureEnd

\subsection Triangulation_3MemoryUsage Memory Usage

We give here some indication about the memory usage of the triangulations.
Those structures being intensively based on pointers, the size almost doubles
on 64bit platforms compared to 32bit.

The size also depends on the size of the point type which is copied in the
vertices (hence on the kernel). Obviously, any user data added to vertices
and cells also affect the memory used.

More specifically, the memory space used to store a triangulation is first
a function of the size of its `Vertex` and `Cell` types times their
numbers (and for volumic distribution, one sees about 6.7 times more cells than
vertices). However, these are stored in memory using `Compact_container`,
which allocates them in lists of blocks of growing size, and this requires some
additional overhead for bookkeeping. Moreover, memory is only released to the
system when clearing or destroying the triangulation. This can be important
for algorithms like simplifications of data sets which will produce fragmented
memory usage (doing fresh copies of the data structures are one way out in such
cases). The asymptotic memory overhead of `Compact_container` for its
internal bookkeeping is otherwise on the order of \f$ O(\sqrt{n})\f$.

\cgalFigureRef{Triangulation3figmemory} shows the number of bytes used per
points, as measured empirically using `Memory_sizer` for large triangulations
(\f$ 10^6\f$ random points).

\cgalFigureAnchor{Triangulation3figmemory}
<CENTER>
<TABLE CELLSPACING=5 >
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>Delaunay</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Delaunay</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Regular</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Regular</B> 
<TR>
<TD ALIGN=LEFT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>%Fast location</B> 
<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>No hidden points</B> 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
32bit 
<TD ALIGN=RIGHT NOWRAP>
274 
<TD ALIGN=RIGHT NOWRAP>
291 
<TD ALIGN=RIGHT NOWRAP>
336 
<TD ALIGN=RIGHT NOWRAP>
282 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
64bit 
<TD ALIGN=RIGHT NOWRAP>
519 
<TD ALIGN=RIGHT NOWRAP>
553 
<TD ALIGN=RIGHT NOWRAP>
635 
<TD ALIGN=RIGHT NOWRAP>
527 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=5><HR>
</TABLE>
</CENTER>
\cgalFigureCaptionBegin{Triangulation3figmemory}
Memory usage in bytes per point for large data sets.
\cgalFigureCaptionEnd

\subsection Triangulation_3VariabilityDependingonthe Variability Depending on the Data Sets and the Kernel

Besides the complexity of the Delaunay triangulation that varies with the
distribution of the points, another critical aspect affects the efficiency :
the degeneracy of the data sets. These algorithms are quite sensitive to
numerical accuracy and it is important to run them using exact predicates.

Using a kernel with no exact predicates will quickly lead to crashes or
infinite loops once they are executed on non-random data sets. More precisely,
problems appear with data sets which contain (nearly) degenerate cases for the
`orientation` and `side_of_oriented_sphere` predicates, namely when
there are (nearly) coplanar or (nearly) cospherical points. This unfortunately
happens often in practice with data coming from various kinds of scanners or
other automatic acquisition devices.

Using an inexact kernel such as `Simple_cartesian<double>` would lead
to optimal performance, which is only about 30% better than
`Exact_predicates_inexact_constructions_kernel`. The latter is strongly
recommended since it takes care about potential robustness issues. The former
can be used for benchmarking purposes mostly, or when you really know that your
data sets won't exhibit any robustness issue.

Exact predicates take more time to compute when they hit (nearly) degenerate
cases. Depending on the data set, this can have a visible impact on the
overall performance of the algorithm or not.

Sometimes you need exact constructions as well, so
`Exact_predicates_exact_constructions_kernel` is a must. This is the case
for example when you need the `dual` functions to be exact, or when your
input is stored in points of such a kernel for other reasons (because it is the
output of another algorithm which has this requirement, for example). This
will slow down the computations by a factor of 4 to 5 at least, and it can be
much more.

\cgalFigureRef{Triangulation3figkernelsanddatasets} gives more detailed
timings about various kernels one the following data sets : random points in a
cube, random points on the surface of an ellipsoid, points scanned on the
surface of a Buddha statue, points on a molecular surface, and points scanned
on a dryer handle. See \cgalFigureRef{Triangulation3figdatasets} for pictures of
the last 3 objects, which respectively illustrate volumic data, surfacic data,
and data with many degenerate cases. This last data set exhibits an infinite
loop with an inexact kernel, and of course we are not sure whether what is
computed for the other data sets with this inexact kernel is a Delaunay
triangulation. General introductory information about these robustness issues
can be found in \cgalCite{cgta-kmpsy-08}. More benchmarks around this issue can
also be found in \cgalCite{cgal:dp-eegpd-03}.

\cgalFigureAnchor{Triangulation3figkernelsanddatasets}
<CENTER>
<TABLE CELLSPACING=5 >
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=6><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>Random</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Ellipsoid</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Buddha</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Molecule</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>Dryer</B> 
<TR>
<TD ALIGN=LEFT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>

<TD ALIGN=RIGHT NOWRAP>
<B>%Handle</B> 
<TR>
<TD ALIGN=LEFT NOWRAP>
Number of points 
<TD ALIGN=RIGHT NOWRAP>
<B>100000</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>100000</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>542548</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>525296</B> 
<TD ALIGN=RIGHT NOWRAP>
<B>49787</B> 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=6><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
`Simple_cartesian<double>` 
<TD ALIGN=RIGHT NOWRAP>
0.69 
<TD ALIGN=RIGHT NOWRAP>
0.627 
<TD ALIGN=RIGHT NOWRAP>
4.21 
<TD ALIGN=RIGHT NOWRAP>
3.8 
<TD ALIGN=RIGHT NOWRAP>
\f$ \infty \f$-loop 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=6><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
`Exact_predicates_inexact_constructions_kernel` 
<TD ALIGN=RIGHT NOWRAP>
0.824 
<TD ALIGN=RIGHT NOWRAP>
0.749 
<TD ALIGN=RIGHT NOWRAP>
4.99 
<TD ALIGN=RIGHT NOWRAP>
4.64 
<TD ALIGN=RIGHT NOWRAP>
1.68 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=6><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
`Exact_predicates_exact_constructions_kernel` 
<TD ALIGN=RIGHT NOWRAP>
4.59 
<TD ALIGN=RIGHT NOWRAP>
3.85 
<TD ALIGN=RIGHT NOWRAP>
30.1 
<TD ALIGN=RIGHT NOWRAP>
26.4 
<TD ALIGN=RIGHT NOWRAP>
4.57 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=6><HR>
<TR>
<TD ALIGN=LEFT NOWRAP>
`Simple_cartesian<Gmpq>` 
<TD ALIGN=RIGHT NOWRAP>
492 
<TD ALIGN=RIGHT NOWRAP>
534 
<TD ALIGN=RIGHT NOWRAP>
1120 
<TD ALIGN=RIGHT NOWRAP>
1030 
<TD ALIGN=RIGHT NOWRAP>
75.2 
<TR><TD ALIGN=LEFT NOWRAP COLSPAN=6><HR>
</TABLE>
</CENTER>
\cgalFigureCaptionBegin{Triangulation3figkernelsanddatasets}
Running times (seconds) for various kernels and data sets.
\cgalFigureCaptionEnd

 
\cgalFigureBegin{Triangulation3figdatasets,api1_01.png,b35-1.png,HD.png}
Data sets used in the benchmark of \cgalFigureRef{Triangulation3figkernelsanddatasets}.
\cgalFigureEnd

\section Triangulation_3Design Design and Implementation History

Monique Teillaud started to work on the 3D triangulation packages in
1997, following the design of the 2D triangulation packages. The
notions of degenerate dimensions and infinite vertex were formalized
\cgalCite{t-tdtc-99} and induced changes in the 2D triangulation
packages. The packages were first released in \cgal 2.1. They contained
basic functionalities on triangulations, Delaunay triangulations,
regular triangulations.

A first version of removal of a vertex from a Delaunay triangulation
was released in \cgal 2.2. However, this removal became really robust
only in \cgal 2.3, after some research that allowed to deal with
degenerate cases quite easily \cgalCite{cgal:dt-pvr3d-03}. Andreas Fabri
implemented this revised version of the removal, and a faster removal
algorithm for \cgal 3.0.

The latter algorithm was proposed by Mariette Yvinec, who contributed
in several ways to the package, first since she was maintaining the
close 2D triangulation package and participated in many discussions,
she also wrote the traits classes for regular triangulations.

In 2000, Sylvain Pion started working on these packages. He improved
the efficiency of triangulations in \cgal 2.3 and 2.4 in several ways
\cgalCite{cgal:bdpty-tc-02} he implemented the Delaunay hierarchy
\cgalCite{cgal:d-dh-02} in 2.3, he improved the memory footprint in 2.4
and 3.0, he also performed work on arithmetic filters
\cgalCite{cgal:dp-eegpd-03} (see `Filtered_kernel`) to improve
the speed of triangulations. He changed the design in \cgal 3.0,
allowing users to add handles in their own vertices and cells.

Olivier Devillers, co-author of preliminary versions of the \cgal 2d
triangulations, participated in many discussions, in particular about
the perturbations, and more concretely in the implementation of the
Delaunay hierarchy.

In 2005, Christophe Delage implemented the vertex removal function for
regular triangulations, using the symbolic perturbation proposed
in \cgalCite{cgal:dt-pvrdr-06}, which allowed to release this
functionality in \cgal 3.2.

In 2006, Nico Kruithof wrote the `Triangulation_simplex_3` class
that can store simplices of any dimension and improved the internal 
organization of the code.

As of March 2007, Christophe Delage made the iterator range insert methods and
constructors use `spatial_sort` to improve efficiency.

In 2008, Camille Wormser added a few more iterators in
the package that were integrated in release 3.4.

In 2009, Sylvain Pion simplified the design of the Delaunay hierarchy
so that it became the simple `Fast_location` policy in release 3.6.

In 2010, Pedro de Castro and Olivier Devillers added the point
displacement in release 3.7.

In 2011, Pedro de Castro and Olivier Devillers implemented in release
3.8 the
structural filtering method, improving the efficiency of point location.

A new demo of this package was introduced in \cgal 3.8, coded by Fei
(Sophie) Che, who was co-mentored by Manuel Caroli and Monique
Teillaud in the framework of the Google Summer of Code, 2010.

In 2013, Clément Jamin added parallel algorithms (insert, remove) to the
Delaunay and regular triangulations.

The authors wish to thank Lutz Kettner for inspiring discussions about
the design of \cgal. Jean-Daniel Boissonnat is also acknowledged
\cgalCite{bdty-tcgal-00}.

*/ 
} /* namespace CGAL */

