\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.7 - 2D Alpha Shapes
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
2D Alpha Shapes Reference

alpha-detail.png
Tran Kai Frank Da
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).


Introduced in: CGAL 2.1
Depends on: 2D Triangulation
BibTeX: cgal:d-as2-15a
License: GPL
Windows Demo: 2D Alpha Shapes
Common Demo Dlls: dlls

This chapter presents a framework for alpha shapes. The description is based on the articles [1], [e-was-92.] Alpha shapes are the generalization of the convex hull of a point set. Let \( S\) be a finite set of points in \( \mathbb{R}^d\), \( d = 2,3\) and \( \alpha\) a parameter with \( 0 \leq \alpha \leq \infty\). For \( \alpha = \infty\), the \( \alpha\)-shape is the convex hull of \( S\). As \( \alpha\) decreases, the \( \alpha\)-shape shrinks and develops cavities, as soon as a sphere of radius \( \sqrt{\alpha}\) can be put inside. Finally, for \( \alpha = 0\), the \( \alpha\)-shape is the set \( S\) 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. Example for Basic Alpha-Shapes) is associated with the Delaunay triangulation (cf. Section Delaunay Triangulations). The weighted alpha shape (cf. Example for Weighted Alpha-Shapes ) is associated with the regular triangulation (cf. Section Regular Triangulations).

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

In general, an \( \alpha\)-complex is a non-connected and non-pure polytope, it means, that one \( k\)-simplex, \( 0 \leq k \leq d-1\) is not necessary adjacent to a \( (k+1)\)-simplex.

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

Classified Reference Pages

Concepts

Classes

Modules

 Concepts
 

Classes

class  CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >
 The class Alpha_shape_2 represents the family of \( \alpha\)-shapes of points in a plane for all positive \( \alpha\). More...
 
class  CGAL::Alpha_shape_face_base_2< Traits, Fb, ExactAlphaComparisonTag >
 The class Alpha_shape_face_base_2 is the default model for the concept AlphaShapeFace_2. More...
 
class  CGAL::Alpha_shape_vertex_base_2< Traits, Vb, ExactAlphaComparisonTag >
 The class Alpha_shape_vertex_base_2 is the default model for the concept AlphaShapeVertex_2. More...
 
class  CGAL::Weighted_alpha_shape_euclidean_traits_2< K >
 The class Weighted_alpha_shape_euclidean_traits_2 is the default model for the concept AlphaShapeTraits_2 for the regular version of Alpha Shapes. More...
 

Types

enum  CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Classification_type { CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::EXTERIOR, CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::SINGULAR, CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::REGULAR, CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::INTERIOR }
 Distinguishes the different cases for classifying a \( k\)-dimensional face of the underlying triangulation of the \( \alpha\)-shape. More...
 
enum  CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Mode { CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::GENERAL, CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::REGULARIZED }
 In general, an alpha shape can be disconnected and contain many singular edges or vertices. More...
 
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Gt
 the alpha shape traits type. More...
 
typedef Gt::FT CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::FT
 the number type of alpha values. More...
 
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::size_type
 The size type. More...
 
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_iterator
 A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different \( \alpha\)-values. More...
 
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_vertices_iterator
 A bidirectional and non-mutable iterator that allow to traverse the vertices which belongs to the \( \alpha\)-shape for the current \( \alpha\). More...
 
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_edges_iterator
 A bidirectional and non-mutable iterator that allow to traverse the edges which belongs to the \( \alpha\)-shape for the current \( \alpha\). More...
 

Typedef Documentation

template<typename Dt , typename ExactAlphaComparisonTag >
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_iterator

A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different \( \alpha\)-values.

Precondition
Its value_type is FT.
template<typename Dt , typename ExactAlphaComparisonTag >
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_edges_iterator

A bidirectional and non-mutable iterator that allow to traverse the edges which belongs to the \( \alpha\)-shape for the current \( \alpha\).

Precondition
Its value_type is Dt::Edge.
template<typename Dt , typename ExactAlphaComparisonTag >
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_vertices_iterator

A bidirectional and non-mutable iterator that allow to traverse the vertices which belongs to the \( \alpha\)-shape for the current \( \alpha\).

Precondition
Its value_type is Dt::Vertex_handle.
template<typename Dt , typename ExactAlphaComparisonTag >
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). 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.

template<typename Dt , typename ExactAlphaComparisonTag >
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.

template<typename Dt , typename ExactAlphaComparisonTag >
typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::size_type

The size type.

Enumeration Type Documentation

template<typename Dt , typename ExactAlphaComparisonTag >
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.

Enumerator
EXTERIOR 

if the face does not belong to the alpha-complex.

SINGULAR 

if the face belongs to the boundary of the alpha-shape, but is not incident to any 2-dimensional face of the alpha-complex

REGULAR 

if the face belongs to the boundary of the alpha-shape and is incident to a 2-dimensional face of the alpha-complex

INTERIOR 

if the face belongs to the alpha-complex, but does not belong to the boundary of the alpha-shape.

template<typename Dt , typename ExactAlphaComparisonTag >
enum CGAL::Alpha_shape_2::Mode

In general, an alpha shape can be disconnected and contain many singular edges or vertices.

Its regularized version is formed by the set of regular edges and their vertices.

Enumerator
GENERAL 
REGULARIZED