Alpha_shape

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

CGAL::Alpha_shape_3<Dt>

Definition

The class Alpha_shape_3<Dt> represents the family of alpha shapes of points in the 3D space for all positive . It maintains an underlying triangulation of the class 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 the face belongs to the alpha shape.

Note that this class is at the same time used for basic and for weighted Alpha Shapes .

Inherits From

This class is the underlying triangulation class.

The modifying functions insert and remove will overwrite the inherited functions. At the moment, only the static version is implemented.

Types

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 Gt::FT NT; the number type of alpha values.

Alpha_shape_3<Dt>::Alpha_iterator
A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different alpha values.
Precondition: Its value_type is NT

enum Mode { GENERAL , REGULARIZED };
In GENERAL mode, the alpha complex can have singular faces, i. e. faces of dimension k, for k=(0,1,2) that are not subfaces of a k+1 face of the complex. In REGULARIZED mode, the complex is regularized, that is singular faces are dropped and the alpha complex includes only a subset of the tetrahedral cells of the triangulation and the subfaces of those cells.

enum Classification_type { EXTERIOR , SINGULAR , REGULAR , INTERIOR };
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.

Creation

Alpha_shape_3<Dt> A ( FT alpha = 0, Mode m = REGULARIZED);
Introduces an empty alpha shape data structure A for and set the current alpha value to alpha and the mode to m.

Alpha_shape_3<Dt> A ( Dt& dt, NT alpha = 0, Mode m = REGULARIZED);
Build an alpha shape of mode m from the triangulation dt. Be carefull that this operation destroy the triangulation.

template < class InputIterator >

Alpha_shape_3<Dt> A ( InputIterator first,
InputIterator last,
FT alpha = 0,
Mode m = REGULARIZED);

Buil an alpha shape data structure in mode m for the points in the range [.first, last.) and set the current alpha value to alpha.
Precondition: The value_type of first and last is Point (the type point of the underlying triangulation.)

Modifiers

template < class InputIterator >

int
A.make_alpha_shape ( InputIterator first,
InputIterator last)

Initialize the alpha shape data structure for points in the range [.first, last.). Returns the number of data points inserted in the underlying triangulation.
If the function is applied to an non-empty alpha shape data structure, it is cleared before initialization.
Precondition: The value_type of first and last is Point.

void A.clear () Clears the structure.

FT A.set_alpha ( Coord_type alpha)
Sets the -value to alpha. Returns the previous -value.
Precondition: alpha 0.

Mode A.set_mode ( Mode m = REGULARIZED)
Sets A in GENERAL or REGULARIZED. Returns the previous mode. Changing the mode of an alpha shape data structure entails a partial recomputation of the data structure.

Query Functions

Mode A.get_mode ( void) Returns whether A is general or regularized.

FT A.get_alpha ( void)
Returns the current -value.

FT A.get_nth_alpha ( int n)
Returns the n-th alpha-value, sorted in an increasing order.
Precondition: n < number of alphas.

int A.number_of_alphas ()
Returns the number of different alpha-values.

Classification_type
A.classify ( Point p, FT alpha = get_alpha())
Locates a point p in the underlying triangulation and Classifies the associated k-face with respect to alpha.

Classification_type
A.classify ( Cell_handle f, FT alpha = get_alpha())
Classifies the cell f of the underlying triangulation with respect to alpha.

Classification_type
A.classify ( Facet f, FT alpha = get_alpha())
Classifies the facet e of the underlying triangulation with respect to alpha.

Classification_type

A.classify ( Cell_handle f,
int i,
FT alpha = get_alpha())

Classifies the facet of the cell f opposite to the vertex with index i of the underlying triangulation with respect to alpha.

Classification_type
A.classify ( Edge e, FT alpha = get_alpha())
Classifies the edge e with respect to alpha .

Classification_type
A.classify ( Vertex_handle v, FT alpha = get_alpha())
Classifies the vertex v of the underlying triangulation with respect to alpha.

template<class OutputIterator>

OutputIterator
A.get_alpha_shape_cells ( OutputIterator it,
Classification_type type,
NT alpha = get_alpha())

Write the cells which are of type type for the alpha value alpha to the sequence pointed to by the output iterator it. Return past the end of the output sequence.

template<class OutputIterator>

OutputIterator
A.get_alpha_shape_facets ( OutputIterator it,
Classification_type type,
NT alpha= get_alpha())

Write the facets which are of type type for the alpha value alpha to the sequence pointed to by the output iterator it. Return past the end of the output sequence.

template<class OutputIterator>

OutputIterator
A.get_alpha_shape_edges ( OutputIterator it,
Classification_type type,
NT alpha = get_alpha())

Write the edges which are of type type for the alpha value alpha to the sequence pointed to by the output iterator it. Return past the end of the output sequence.

template<class OutputIterator>

OutputIterator
A.get_alpha_shape_vertices ( OutputIterator it,
Classification_type type,
NT alphaget_alpha())

)

Write the vertices which are of type type for the alpha value alpha to the sequence pointed to by the output iterator it. Return past the end of the output sequence.

Traversal of the -Values

Alpha_iterator A.alpha_begin () Returns an iterator that allows to traverse the sorted sequence of -values of the family of alpha shapes.

Alpha_iterator A.alpha_end () Returns the corresponding past-the-end iterator.

Alpha_iterator A.alpha_find ( FT alpha)
Returns an iterator pointing to an element with -value alpha, or the corresponding past-the-end iterator if such an element is not found.

Alpha_iterator A.alpha_lower_bound ( FT alpha)
Returns an iterator pointing to the first element with -value not less than alpha.

Alpha_iterator A.alpha_upper_bound ( FT alpha)
Returns an iterator pointing to the first element with -value greater than alpha.

Operations

int A.number_of_solid_components ( FT alpha = get_alpha())
Returns the number of solid components of A, that is, the number of components of its regularized version.

Alpha_iterator A.find_optimal_alpha ( int nb_components)
Returns an iterator pointing to smallest value such that A satisfies the following two properties:
all data points are either on the boundary or in the interior of the regularized version of A.
The number of solid component of A is equal to or smaller than nb_components.

I/O

The I/O operators are defined for iostream, and for the window stream provided by CGAL. The format for the iostream is an internal format.

#include <CGAL/IO/io.h>

ostream& ostream& os << A Inserts the alpha shape A for the current alpha value into the stream os.
Precondition: The insert operator must be defined for Point.

#include <CGAL/IO/Geomview_stream.h>

#include <CGAL/IO/alpha_shape_geomview_ostream_3.h>

Geomview_stream& Geomview_stream& W << A
Inserts the alpha shape A for the current alpha value into the Geomview stream W.
Precondition: The insert operator must be defined for Point and Triangle.

Implementation

In GENERAL mode, the alpha intervals of each triangulation face is computed and stored at initialization time. In REGULARIZED mode, the alpha shape intervals of edges are not stored nor computed at initialization. Edges are simply classified on the fly upon request. This allows to have much faster building of alpha shapes in REGULARIZED mode.

A.alpha find uses linear search, while A.alpha lower bound and A.alpha upper bound use binary search. A.number of solid components performs a graph traversal and takes time linear in the number of cells of the underlying triangulation. A.find of optimal alpha uses binary search and takes time O( n log n ), where n is the number of points.

Next: Alpha_shape_cell_base_3<Traits,Fb>

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .

Alpha_shape_3<Dt>::Alpha_iterator
	A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different alpha values. Precondition: Its value_type is NT

enum Mode { GENERAL , REGULARIZED };
	In GENERAL mode, the alpha complex can have singular faces, i. e. faces of dimension k, for k=(0,1,2) that are not subfaces of a k+1 face of the complex. In REGULARIZED mode, the complex is regularized, that is singular faces are dropped and the alpha complex includes only a subset of the tetrahedral cells of the triangulation and the subfaces of those cells.

enum Classification_type { EXTERIOR , SINGULAR , REGULAR , INTERIOR };
	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.

Alpha_iterator	A.alpha_begin ()	Returns an iterator that allows to traverse the sorted sequence of -values of the family of alpha shapes.

Alpha_iterator	A.alpha_end ()	Returns the corresponding past-the-end iterator.

Alpha_iterator	A.alpha_find ( FT alpha)
		Returns an iterator pointing to an element with -value alpha, or the corresponding past-the-end iterator if such an element is not found.

Alpha_iterator	A.alpha_lower_bound ( FT alpha)
		Returns an iterator pointing to the first element with -value not less than alpha.

Alpha_iterator	A.alpha_upper_bound ( FT alpha)
		Returns an iterator pointing to the first element with -value greater than alpha.

int	A.number_of_solid_components ( FT alpha = get_alpha())
		Returns the number of solid components of A, that is, the number of components of its regularized version.

Alpha_iterator	A.find_optimal_alpha ( int nb_components)
		Returns an iterator pointing to smallest value such that A satisfies the following two properties: all data points are either on the boundary or in the interior of the regularized version of A. The number of solid component of A is equal to or smaller than nb_components.

Geomview_stream&	Geomview_stream& W << A
		Inserts the alpha shape A for the current alpha value into the Geomview stream W. Precondition: The insert operator must be defined for Point and Triangle.