CGAL 6.0  2D Alpha Shapes

#include <CGAL/Alpha_shape_2.h>
Dt.
The class Alpha_shape_2
represents the family of \( \alpha\)shapes of points in a plane for all positive \( \alpha\).
It maintains the underlying triangulation Dt
which represents connectivity and order among its faces. Each \( k\)dimensional face of the Dt
is associated with an interval that specifies for which values of \( \alpha\) the face belongs to the \( \alpha\)shape. There are links between the intervals and the \( k\)dimensional faces of the triangulation.
Note that this class is at the same time used for basic and for weighted Alpha Shapes.
The modifying functions Alpha_shape_2::insert()
and Alpha_shape_2::remove()
will overwrite the one inherited from the underlying triangulation class Dt
. At the moment, only the static version is implemented.
Dt  must be either Delaunay_triangulation_2 or Regular_triangulation_2 . Note that Dt::Geom_traits , Dt::Vertex , and Dt::Face must be model the concepts AlphaShapeTraits_2 , AlphaShapeVertex_2 and AlphaShapeFace_2 , respectively. 
ExactAlphaComparisonTag  is a tag that, when set to Tag_true , triggers exact comparisons between alpha values. This is useful when the underlying triangulation is instantiated with an exact predicates inexact constructions kernel. By default the ExactAlphaComparisonTag is set to Tag_false as it induces a small overhead. Note that the tag ExactAlphaComparisonTag is currently ignored (meaning that the code will behave as if ExactAlphaComparisonTag were set to Tag_false ) if Dt::Geom_traits::FT is not a floating point number type as this strategy does not make sense if the traits class already provides exact constructions. 
ExactAlphaComparisonTag
is set to Tag_true
, the class Cartesian_converter
is used internally to switch between the traits class and the CGAL kernel CGAL::Simple_cartesian<NT>
, where NT
can be either CGAL::Interval_nt
or CGAL::Exact_rational
. Cartesian_converter
must thus offer the necessary functors to convert a twodimensional point of the traits class to a twodimensional point of CGAL::Simple_cartesian<NT>
. However, these functors are not necessarily provided by the basic Cartesian_converter
. For example when using the traits class CGAL::Projection_traits_xy_3
, a CGAL::Point_3
is camouflaged as a Point_2
and the basic Cartesian_converter
does not know how to convert from the camouflaged CGAL::Point_3
to the twodimensional point of CGAL::Simple_cartesian<NT>
. In this case, a partial specialization of Cartesian_converter
must be provided by the user. An example of such specialization is given in the example ex_alpha_projection_traits.cpp. ExactAlphaComparisonTag
cannot be used in conjunction with periodic triangulations. When the tag ExactAlphaComparisonTag
is set to Tag_true
, the evaluations of predicates such as Side_of_oriented_circle_2
are done lazily. Consequently, the predicates store pointers to the geometrical positions of the points passed as arguments of the predicates. It is thus important that these points are not temporary objects. Points of the triangulation are accessed using the function point(Face_handle, int)
of the underlying triangulation. In the case of periodic triangulations, the point(Face_handle, int)
function is actually a construction that returns a temporary, which thus cannot be used along with a lazy predicate evaluation. I/O
The I/O operators are defined for std::iostream
. The format for the iostream is an internal format.
Implementation
The set of intervals associated with the \( k\)dimensional faces of the underlying triangulation are stored in multimaps
.
The cross links between the intervals and the \( k\)dimensional faces of the triangulation are realized using methods in the \( k\)dimensional faces themselves.
Alpha_shape_2::alpha_find()
uses linear search, while Alpha_shape_2::alpha_lower_bound()
and Alpha_shape_2::alpha_upper_bound()
use binary search. Alpha_shape_2::number_of_solid_components()
performs a graph traversal and takes time linear in the number of faces of the underlying triangulation. Alpha_shape_2::find_optimal_alpha()
uses binary search and takes time \(O(n \log n)\), where \( n\) is the number of points.
Types  
enum  Classification_type { EXTERIOR , SINGULAR , REGULAR , INTERIOR } 
Distinguishes the different cases for classifying a \( k\)dimensional face of the underlying triangulation of the \( \alpha\)shape. More...  
enum  Mode { GENERAL , REGULARIZED } 
In general, an alpha shape can be disconnected and contain many singular edges or vertices. More...  
typedef unspecified_type  Gt 
the alpha shape traits type.  
typedef Gt::FT  FT 
the number type of alpha values.  
typedef Dt::Point  Point 
The point type.  
typedef unspecified_type  size_type 
The size type.  
typedef unspecified_type  Alpha_iterator 
A bidirectional and nonmutable iterator that allow to traverse the increasing sequence of different \( \alpha\)values.  
typedef unspecified_type  Alpha_shape_vertices_iterator 
A bidirectional and nonmutable iterator that allow to traverse the vertices which belongs to the \( \alpha\)shape for the current \( \alpha\).  
typedef unspecified_type  Alpha_shape_edges_iterator 
A bidirectional and nonmutable iterator that allow to traverse the edges which belongs to the \( \alpha\)shape for the current \( \alpha\).  
Creation  
Alpha_shape_2 (FT alpha=0, Mode m=GENERAL)  
Introduces an empty alphashape for a positive \( \alpha\)value alpha .  
Alpha_shape_2 (Dt &dt, FT alpha=0, Mode m=GENERAL)  
Builds an alpha shape of mode m from the triangulation dt for a positive \( \alpha\)value alpha .  
template<class InputIterator >  
Alpha_shape_2 (InputIterator first, InputIterator last, const FT &alpha=0, Mode m=GENERAL)  
Initializes the family of alphashapes with the points in the range [first,last) and introduces an \( \alpha\)shape for a positive \( \alpha\)value alpha .  
Operations  
template<class InputIterator >  
std::ptrdiff_t  make_alpha_shape (InputIterator first, InputIterator last) 
Initialize the family of alphashapes with the points in the range [first,last) .  
void  clear () 
Clears the structure.  
FT  set_alpha (const FT &alpha) 
Sets the \( \alpha\)value to alpha .  
const FT &  get_alpha (void) const 
Returns the current \( \alpha\)value.  
const FT &  get_nth_alpha (size_type n) const 
Returns the n th \(\alpha\)value, sorted in an increasing order.  
size_type  number_of_alphas () const 
Returns the number of different alphavalues.  
Mode  set_mode (Mode m=GENERAL) 
Sets the mode to its general or regularized version.  
Mode  get_mode (void) const 
Returns the mode, that is either GENERAL or REGULARIZED .  
Alpha_shape_vertices_iterator  alpha_shape_vertices_begin () 
Starts at an arbitrary finite vertex which belongs to the \( \alpha\)shape for the current \( \alpha\).  
Alpha_shape_vertices_iterator  alpha_shape_vertices_end () 
Pasttheend iterator.  
Alpha_shape_edges_iterator  alpha_shape_edges_begin () 
Starts at an arbitrary finite edge which belongs to the \( \alpha\)shape for the current \( \alpha\).  
Alpha_shape_edges_iterator  alpha_shape_edges_end () 
Pasttheend iterator.  
size_type  number_of_solid_components (const FT &alpha=get_alpha()) const 
Returns the number of solid components of the alpha shape, that is, the number of components of its regularized version.  
Alpha_iterator  find_optimal_alpha (size_type nb_components) const 
Returns an iterator pointing to the first element with \( \alpha\)value such that the alpha shape satisfies the following two properties:  
ostream &  operator<< (std::ostream &os, const Alpha_shape_2< Dt > &A) 
Inserts the alpha shape for the current \( \alpha\)value into the stream os .  
Predicates  
Classification_type  classify (const Point &p, const FT &alpha=get_alpha()) const 
Locates a point p in the underlying triangulation and Classifies the associated kface with respect to the alpha shape.  
Classification_type  classify (Face_handle f, const FT &alpha=get_alpha()) const 
Classifies the face f of the underlying triangulation with respect to the alpha shape.  
Classification_type  classify (Edge e, const FT &alpha=get_alpha()) const 
Classifies the edge e of the underlying triangulation with respect to the alpha shape.  
Classification_type  classify (Face_handle f, int i, const FT &alpha=get_alpha()) const 
Classifies the edge of the face f opposite to the vertex with index i of the underlying triangulation with respect to the alpha shape.  
Classification_type  classify (Vertex_handle v, const FT &alpha=get_alpha()) const 
Classifies the vertex v of the underlying triangulation with respect to the alpha shape.  
Traversal of the alphaValues  
Alpha_iterator  alpha_begin () const 
Returns an iterator that allows to traverse the sorted sequence of \( \alpha\)values of the family of alpha shapes.  
Alpha_iterator  alpha_end () const 
Returns the corresponding pasttheend iterator.  
Alpha_iterator  alpha_find (const FT &alpha) const 
Returns an iterator pointing to an element with \( \alpha\)value alpha , or the corresponding pasttheend iterator if such an element is not found.  
Alpha_iterator  alpha_lower_bound (const FT &alpha) const 
Returns an iterator pointing to the first element with \( \alpha\)value not less than alpha .  
Alpha_iterator  alpha_upper_bound (const FT &alpha) const 
Returns an iterator pointing to the first element with \( \alpha\)value greater than alpha .  
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_iterator 
A bidirectional and nonmutable iterator that allow to traverse the increasing sequence of different \( \alpha\)values.
value_type
is FT
. typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_edges_iterator 
A bidirectional and nonmutable iterator that allow to traverse the edges which belongs to the \( \alpha\)shape for the current \( \alpha\).
value_type
is Dt::Edge
. typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_vertices_iterator 
A bidirectional and nonmutable iterator that allow to traverse the vertices which belongs to the \( \alpha\)shape for the current \( \alpha\).
value_type
is Dt::Vertex_handle
. typedef Gt::FT CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::FT 
the number type of alpha values.
In case ExactAlphaComparisonTag
is CGAL::Tag_false
, it is Gt::FT.
In case ExactAlphaComparisonTag
is CGAL::Tag_true
, it is a number type allowing filtered exact comparisons (that is, interval arithmetic is first used before resorting to exact arithmetic). Access to the interval containing the exact value is provided through the function FT::Approximate_nt approx() const
where FT::Approximate_nt
is CGAL::Interval_nt<Protected>
with Protected=true
. Access to the exact value is provided through the function FT::Exact_nt exact() const
where FT::Exact_nt
depends on the configuration of CGAL (it is Gmpq
if gmp
is available and Quotient<CGAL::MP_Float>
otherwise). An overload for the function double to_double(FT)
is also available. Its precision is controlled through FT::set_relative_precision_of_to_double()
in exactly the same way as with Lazy_exact_nt<NT>
, so a call to to_double
may trigger an exact evaluation. It must be noted that an object of type FT
is valid as long as the alpha shapes class that creates it is valid and has not been modified. For convenience, classical comparison operators are provided for the type FT
.
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Gt 
the alpha shape traits type.
it has to derive from a triangulation traits class. For example Dt::Point
is a point class.
typedef Dt::Point CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Point 
The point type.
For basic alpha shapes, Point
will be equal to Gt::Point_2
. For weighted alpha shapes, Point
will be equal to Gt::Weighted_point_2
.
enum CGAL::Alpha_shape_2::Classification_type 
Distinguishes the different cases for classifying a \( k\)dimensional face of the underlying triangulation of the \( \alpha\)shape.
enum CGAL::Alpha_shape_2::Mode 
CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_2  (  FT  alpha = 0 , 
Mode  m = GENERAL 

) 
Introduces an empty alphashape for a positive \( \alpha\)value alpha
.
alpha
\( \geq~0\). CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_2  (  Dt &  dt, 
FT  alpha = 0 , 

Mode  m = GENERAL 

) 
Builds an alpha shape of mode m
from the triangulation dt
for a positive \( \alpha\)value alpha
.
alpha
\( \geq~0\). CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_2  (  InputIterator  first, 
InputIterator  last,  
const FT &  alpha = 0 , 

Mode  m = GENERAL 

) 
Initializes the family of alphashapes with the points in the range [first,last)
and introduces an \( \alpha\)shape for a positive \( \alpha\)value alpha
.
InputIterator  must be an input iterator with the value type Point . 
alpha
\( \geq0\). Alpha_shape_edges_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_shape_edges_begin  (  ) 
Starts at an arbitrary finite edge which belongs to the \( \alpha\)shape for the current \( \alpha\).
In regularized mode, edges are represented as a pair (f,i), where f is an interior face of the \( \alpha\)shape.
Alpha_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::find_optimal_alpha  (  size_type  nb_components  )  const 
Returns an iterator pointing to the first element with \( \alpha\)value such that the alpha shape satisfies the following two properties:
nb_components
.If no such value is found, the iterator points to the first element with \( \alpha\)value such that the alpha shape satisfies the second property.
const FT & CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::get_nth_alpha  (  size_type  n  )  const 
Returns the n
th \(\alpha\)value, sorted in an increasing order.
n
\( <\) number of alphas. std::ptrdiff_t CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::make_alpha_shape  (  InputIterator  first, 
InputIterator  last  
) 
Initialize the family of alphashapes with the points in the range [first,last)
.
Returns the number of inserted points.
If the function is applied to an nonempty family of alphashape, it is cleared before initialization.
InputIterator  must be an input iterator with the value type Point . 
FT CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::set_alpha  (  const FT &  alpha  ) 
Sets the \( \alpha\)value to alpha
.
Returns the previous \( \alpha\)value.
alpha
\( \geq0\). Mode CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::set_mode  (  Mode  m = GENERAL  ) 
Sets the mode to its general or regularized version.
Returns the previous mode.

related 
Inserts the alpha shape for the current \( \alpha\)value into the stream os
.
Point
.