|
CGAL 4.7 - 3D Alpha Shapes
|
|
CGAL 4.7 - 3D Alpha Shapes
|
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 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 \( S\). The alpha complex is a subcomplex of the Delaunay triangulation. For a given value of \( \alpha\), the alpha complex includes all the simplices in the Delaunay triangulation which have an empty circumscribing sphere with squared radius equal or smaller than \( \alpha\). Here "empty" means that the open sphere do not include any points of \( S\). The alpha shape is then simply the domain covered by the simplices of the alpha complex (see [1]).
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 \( 0 \leq k \leq d-1\), a \( k\)-simplex of the alpha complex is said to be singular if it is not a facet of a \( (k+1)\)-simplex of the complex
The alpha shapes of a set of points \( S\) form a discrete family, even though they are defined for all real numbers \( \alpha\). The entire family of alpha shapes can be represented through 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 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 \( \alpha\) 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 \( C_1, C_2\) and radii \( r_1, r_2 \) are said to be orthogonal iff \( C_1C_2 ^2 = r_1^2 + r_2^2\) and suborthogonal iff \( C_1C_2 ^2 < r_1^2 + r_2^2\). For a given value of \( \alpha\) 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.
AlphaShapeTraits_3WeightedAlphaShapeTraits_3AlphaShapeCell_3AlphaShapeVertex_3FixedAlphaShapeTraits_3FixedWeightedAlphaShapeTraits_3FixedAlphaShapeCell_3FixedAlphaShapeVertex_3CGAL::Alpha_status<NT>CGAL::Alpha_shape_3<Dt,ExactAlphaComparisonTag>CGAL::Alpha_shape_vertex_base_3<Traits,Vb>CGAL::Alpha_shape_cell_base_3<Traits,Fb>CGAL::Fixed_alpha_shape_3<Dt>CGAL::Fixed_alpha_shape_vertex_base_3<Traits,Vb>CGAL::Fixed_alpha_shape_cell_base_3<Traits,Fb> Modules | |
| Concepts | |
Types | |
| enum | CGAL::Fixed_alpha_shape_3< Dt >::Classification_type { CGAL::Fixed_alpha_shape_3< Dt >::EXTERIOR, CGAL::Fixed_alpha_shape_3< Dt >::SINGULAR, CGAL::Fixed_alpha_shape_3< Dt >::REGULAR, CGAL::Fixed_alpha_shape_3< Dt >::INTERIOR } |
| Enum to classify the simplices of the underlying triangulation with respect to a given alpha value. More... | |
| typedef unspecified_type | CGAL::Fixed_alpha_shape_3< Dt >::Gt |
| the alpha shape traits type. More... | |
| typedef Gt::FT | CGAL::Fixed_alpha_shape_3< Dt >::FT |
| the number type of alpha. More... | |
| typedef unspecified_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::Alpha_iterator |
A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different alpha values.
value_type is FT. | typedef Gt::FT CGAL::Fixed_alpha_shape_3< Dt >::FT |
the number type of alpha.
| typedef unspecified_type CGAL::Alpha_shape_3< 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 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.
| typedef unspecified_type CGAL::Fixed_alpha_shape_3< Dt >::Gt |
the alpha shape traits type.
It has to derive from a triangulation traits class. For example Dt::Point is a Point class.
| typedef unspecified_type CGAL::Alpha_shape_3< 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 unspecified_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::size_type |
The size type.
| enum CGAL::Fixed_alpha_shape_3::Classification_type |
Enum to classify the simplices of the underlying triangulation with respect to a given alpha value.
Each k-dimensional simplex of the triangulation can be classified as EXTERIOR, SINGULAR, REGULAR or INTERIOR. A \( k\) simplex is REGULAR if it is on the boundary of the alpha complex and belongs to a \( k+1\) simplex in this complex and it is SINGULAR if it is a boundary simplex that is not included in a \( k+1\) simplex of the complex.
| Enumerator | |
|---|---|
| EXTERIOR | |
| SINGULAR | |
| REGULAR | |
| INTERIOR | |
| enum CGAL::Alpha_shape_3::Classification_type |
Enum to classify the faces of the underlying triangulation with respect to the alpha shape.
In GENERAL mode, for \( k=(0,1,2)\), each k-dimensional simplex of the triangulation can be classified as EXTERIOR, SINGULAR, REGULAR or INTERIOR. In GENERAL mode a \( k\) simplex is REGULAR if it is on the boundary f the alpha complex and belongs to a \( k+1\) simplex in this complex and it is SINGULAR if it is a boundary simplex that is not included in a \( k+1\) simplex of the complex.
In REGULARIZED mode, for \( k=(0,1,2)\) each k-dimensional simplex of the triangulation can be classified as EXTERIOR, REGULAR or INTERIOR, i.e. there is no singular faces. A \( k\) simplex is REGULAR if it is on the boundary of alpha complex and belongs to a tetrahedral cell of the complex.
| Enumerator | |
|---|---|
| EXTERIOR | |
| SINGULAR | |
| REGULAR | |
| INTERIOR | |
| enum CGAL::Alpha_shape_3::Mode |
In GENERAL mode, In REGULARIZED mode,.
1.8.8