CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag > Class Template Reference

#include <CGAL/Alpha_shape_3.h>

Inherits from

Dt.

Definition

The class Alpha_shape_3 represents the family of alpha shapes of points in the 3D space for all real \( \alpha\).

It maintains an underlying triangulation of the class Dt. Each k-dimensional face of Dt is associated with an interval that specifies for which values of alpha the face belongs to the alpha shape. The second template parameter ExactAlphaComparisonTag is a tag that, when set to CGAL::Tag_true, triggers exact comparisons between alpha values. This is useful when the Delaunay triangulation is instantiated with an exact predicates inexact constructions kernel. By default the ExactAlphaComparisonTag is set to CGAL::Tag_false as it induces a small overhead. Note that since such a strategy does not make sense if used together with a traits class with exact constructions, the tag ExactAlphaComparisonTag is not taken into account if Dt::Geom_traits::FT is not a floating point number type.

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

The modifying functions insert and remove will overwrite the one inherited from the underlying triangulation class Dt. At the moment, only the static version is implemented.

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.

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.

Function Alpha_shape_3::alpha_find() uses linear search, while Alpha_shape_3::alpha_lower_bound() and Alpha_shape_3::alpha_upper_bound() use binary search. Alpha_shape_3::number_of_solid_components() performs a graph traversal and takes time linear in the number of cells of the underlying triangulation. Alpha_shape_3::find_optimal_alpha() uses binary search and takes time \( O(n \log n)\), where \( n\) is the number of points.

Examples:

Alpha_shapes_3/ex_alpha_shapes_3.cpp, Alpha_shapes_3/ex_alpha_shapes_exact_alpha.cpp, Alpha_shapes_3/ex_alpha_shapes_with_fast_location_3.cpp, Alpha_shapes_3/ex_periodic_alpha_shapes_3.cpp, and Alpha_shapes_3/ex_weighted_alpha_shapes_3.cpp.

Related Functions
(Note that these are not member functions.)
ostream &	operator<< (std::ostream &os, const Alpha_shape_3< Dt, ExactAlphaComparisonTag > &A)
	Inserts the alpha shape A for the current alpha value into the stream os. More...
Geomview_stream &	operator<< (Geomview_stream &W, const Alpha_shape_3< Dt, ExactAlphaComparisonTag > &A)
	Inserts the alpha shape A for the current alpha value into the Geomview stream W. More...

Types
enum	Mode { GENERAL, REGULARIZED }
	In GENERAL mode, In REGULARIZED mode,. More...
enum	Classification_type { EXTERIOR, SINGULAR, REGULAR, INTERIOR }
	Enum to classify the faces of the underlying triangulation with respect to the alpha shape. More...
typedef unspecified_type	Gt
	the alpha shape traits type. More...
typedef unspecified_type	FT
	the number type of alpha values. More...
typedef unspecified_type	size_type
	The size type. More...
typedef unspecified_type	Alpha_iterator
	A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different alpha values. More...

Creation
	Alpha_shape_3 (FT alpha=0, Mode m=REGULARIZED)
	Introduces an empty alpha shape, sets the current alpha value to alpha and the mode to m. More...
	Alpha_shape_3 (Dt &dt, FT alpha=0, Mode m=REGULARIZED)
	Builds an alpha shape of mode m from the triangulation dt. More...
template<class InputIterator >
	Alpha_shape_3 (InputIterator first, InputIterator last, const FT &alpha=0, Mode m=REGULARIZED)
	Builds an alpha shape of mode m for the points in the range [first,last) and set the current alpha value to alpha. More...

Modifiers
template<class InputIterator >
std::ptrdiff_t	make_alpha_shape (InputIterator first, InputIterator last)
	Initialize the alpha shape data structure for points in the range [first,last). More...
void	clear ()
	Clears the structure. More...
FT	set_alpha (const FT &alpha)
	Sets the \( \alpha\)-value to alpha. More...
Mode	set_mode (Mode m=REGULARIZED)
	Sets the mode of the alpha shape to GENERAL or REGULARIZED. More...

Query Functions
Mode	get_mode (void) const
	Returns whether the alpha shape is general or regularized. More...
const FT &	get_alpha (void) const
	Returns the current \( \alpha\)-value. More...
const FT &	get_nth_alpha (int n) const
	Returns the n-th alpha-value, sorted in an increasing order. More...
size_type	number_of_alphas () const
	Returns the number of different alpha-values. More...
Classification_type	classify (const Point &p, const FT &alpha=get_alpha()) const
	Locates a point p in the underlying triangulation and Classifies the associated k-face with respect to alpha. More...
Classification_type	classify (Cell_handle f, const FT &alpha=get_alpha()) const
	Classifies the cell f of the underlying triangulation with respect to alpha. More...
Classification_type	classify (Facet f, const FT &alpha=get_alpha()) const
	Classifies the facet f of the underlying triangulation with respect to alpha. More...
Classification_type	classify (Cell_handle f, int i, const FT &alpha=get_alpha()) const
	Classifies the facet of the cell f opposite to the vertex with index i of the underlying triangulation with respect to alpha. More...
Classification_type	classify (const Edge &e, const FT &alpha=get_alpha()) const
	Classifies the edge e with respect to alpha . More...
Classification_type	classify (Vertex_handle v, const FT &alpha=get_alpha()) const
	Classifies the vertex v of the underlying triangulation with respect to alpha. More...
Alpha_status< FT >	get_alpha_status (const Edge &e) const
	Returns the alpha-status of the edge e. More...
Alpha_status< FT >	get_alpha_status (const Facet &f) const
	Returns the alpha-status of the facet f. More...
template<class OutputIterator >
OutputIterator	get_alpha_shape_cells (OutputIterator it, Classification_type type, const FT &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. More...
template<class OutputIterator >
OutputIterator	get_alpha_shape_facets (OutputIterator it, Classification_type type, const FT &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. More...
template<class OutputIterator >
OutputIterator	get_alpha_shape_edges (OutputIterator it, Classification_type type, const FT &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. More...
template<class OutputIterator >
OutputIterator	get_alpha_shape_vertices (OutputIterator it, Classification_type type, const FT &alpha)
	Write the vertices which are of type type for the alpha value alpha to the sequence pointed to by the output iterator it. More...
template<class OutputIterator >
OutputIterator	filtration (OutputIterator it) const
	Output all the faces of the triangulation in increasing order of the alpha value for which they appear in the alpha complex. More...
template<class OutputIterator >
OutputIterator	filtration_with_alpha_values (OutputIterator it) const
	Output all the faces of the triangulation in increasing order of the alpha value for which they appear in the alpha complex. More...

Traversal of the alpha-Values
Alpha_iterator	alpha_begin () const
	Returns an iterator that allows to traverse the sorted sequence of \( \alpha\)-values of the family of alpha shapes. More...
Alpha_iterator	alpha_end () const
	Returns the corresponding past-the-end iterator. More...
Alpha_iterator	alpha_find (const FT &alpha) const
	Returns an iterator pointing to an element with \( \alpha\)-value alpha, or the corresponding past-the-end iterator if such an element is not found. More...
Alpha_iterator	alpha_lower_bound (const FT &alpha) const
	Returns an iterator pointing to the first element with \( \alpha\)-value not less than alpha. More...
Alpha_iterator	alpha_upper_bound (const FT &alpha) const
	Returns an iterator pointing to the first element with \( \alpha\)-value greater than alpha. More...

Operations
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. More...
Alpha_iterator	find_optimal_alpha (size_type nb_components) const
	Returns an iterator pointing to smallest \( \alpha\) value such that the alpha shape satisfies the following two properties: More...

Constructor & Destructor Documentation

template<typename Dt , typename ExactAlphaComparisonTag >

CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::Alpha_shape_3	(	FT	alpha = 0,
		Mode	m = REGULARIZED
	)

Introduces an empty alpha shape, sets the current alpha value to alpha and the mode to m.

template<typename Dt , typename ExactAlphaComparisonTag >

CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::Alpha_shape_3	(	Dt &	dt,
		FT	alpha = 0,
		Mode	m = REGULARIZED
	)

Builds an alpha shape of mode m from the triangulation dt.

Attention

This operation destroys the triangulation dt.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class InputIterator >

CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::Alpha_shape_3	(	InputIterator	first,
		InputIterator	last,
		const FT &	alpha = 0,
		Mode	m = REGULARIZED
	)

Builds an alpha shape of mode m for the points in the range [first,last) and set the current alpha value to alpha.

Template Parameters

InputIterator

must be an input iterator with value type Point (the point type of the underlying triangulation.)

Member Function Documentation

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::alpha_begin

(

)

const

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

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::alpha_end

(

)

const

Returns the corresponding past-the-end iterator.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::alpha_find

(

const FT &

alpha

)

const

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

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::alpha_lower_bound

(

const FT &

alpha

)

const

Returns an iterator pointing to the first element with \( \alpha\)-value not less than alpha.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::alpha_upper_bound

(

const FT &

alpha

)

const

Returns an iterator pointing to the first element with \( \alpha\)-value greater than alpha.

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::classify	(	const Point &	p,
		const FT &	alpha = get_alpha()
	)		const

Locates a point p in the underlying triangulation and Classifies the associated k-face with respect to alpha.

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::classify	(	Cell_handle	f,
		const FT &	alpha = get_alpha()
	)		const

Classifies the cell f of the underlying triangulation with respect to alpha.

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::classify	(	Facet	f,
		const FT &	alpha = get_alpha()
	)		const

Classifies the facet f of the underlying triangulation with respect to alpha.

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::classify	(	Cell_handle	f,
		int	i,
		const FT &	alpha = get_alpha()
	)		const

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

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::classify	(	const Edge &	e,
		const FT &	alpha = get_alpha()
	)		const

Classifies the edge e with respect to alpha .

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::classify	(	Vertex_handle	v,
		const FT &	alpha = get_alpha()
	)		const

Classifies the vertex v of the underlying triangulation with respect to alpha.

template<typename Dt , typename ExactAlphaComparisonTag >

void CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::clear

(

)

Clears the structure.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class OutputIterator >

OutputIterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::filtration

(

OutputIterator

it

)

const

Output all the faces of the triangulation in increasing order of the alpha value for which they appear in the alpha complex.

In case of equal alpha value lower dimensional faces are output first.

Template Parameters

OutputIterator

must be an output iterator accepting variables of type Object.

Warning

The result of this function depends on the mode of the Alpha-shape. In most case, Alpha_shape_3::GENERAL is the most interesting one.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class OutputIterator >

OutputIterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::filtration_with_alpha_values

(

OutputIterator

it

)

const

Output all the faces of the triangulation in increasing order of the alpha value for which they appear in the alpha complex.

In case of equal alpha value lower dimensional faces are output first. In addition the value of alpha at which each face appears are also reported. Each face and its alpha value are reported successively.

Template Parameters

OutputIterator

must be an output iterator accepting variables of type Object and FT. The class Dispatch_output_iterator can be used for this purpose.

Warning

The result of this function dependents on the mode of the Alpha-shape. In most case, Alpha_shape_3::GENERAL is the most interesting one.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::find_optimal_alpha

(

size_type

nb_components

)

const

Returns an iterator pointing to smallest \( \alpha\) value such that the alpha shape satisfies the following two properties:

all data points are either on the boundary or in the interior of the regularized version of the alpha shape.

The number of solid component of the alpha shape is equal to or smaller than nb_components.

template<typename Dt , typename ExactAlphaComparisonTag >

const FT& CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha

(

void

)

const

Returns the current \( \alpha\)-value.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class OutputIterator >

OutputIterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha_shape_cells	(	OutputIterator	it,
		Classification_type	type,
		const FT &	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.

Returns past the end of the output sequence.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class OutputIterator >

OutputIterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha_shape_edges	(	OutputIterator	it,
		Classification_type	type,
		const FT &	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.

Returns past the end of the output sequence.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class OutputIterator >

OutputIterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha_shape_facets	(	OutputIterator	it,
		Classification_type	type,
		const FT &	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.

Returns past the end of the output sequence.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class OutputIterator >

OutputIterator CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha_shape_vertices	(	OutputIterator	it,
		Classification_type	type,
		const FT &	alpha
	)

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

Returns past the end of the output sequence.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_status<FT> CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha_status

(

const Edge &

e

)

const

Returns the alpha-status of the edge e.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_status<FT> CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_alpha_status

(

const Facet &

f

)

const

Returns the alpha-status of the facet f.

template<typename Dt , typename ExactAlphaComparisonTag >

Mode CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_mode

(

void

)

const

Returns whether the alpha shape is general or regularized.

template<typename Dt , typename ExactAlphaComparisonTag >

const FT& CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::get_nth_alpha

(

int

n

)

const

Returns the n-th alpha-value, sorted in an increasing order.

Precondition

n < number of alphas.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class InputIterator >

std::ptrdiff_t CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::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.

Template Parameters

InputIterator

must be an input iterator with value type Point.

template<typename Dt , typename ExactAlphaComparisonTag >

size_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::number_of_alphas

(

)

const

Returns the number of different alpha-values.

template<typename Dt , typename ExactAlphaComparisonTag >

size_type CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::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.

template<typename Dt , typename ExactAlphaComparisonTag >

FT CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::set_alpha

(

const FT &

alpha

)

Sets the \( \alpha\)-value to alpha.

Returns the previous \( \alpha\)-value.

Precondition

alpha \( \geq0\).

template<typename Dt , typename ExactAlphaComparisonTag >

Mode CGAL::Alpha_shape_3< Dt, ExactAlphaComparisonTag >::set_mode

(

Mode

m = REGULARIZED

)

Sets the mode of the alpha shape to GENERAL or REGULARIZED.

Returns the previous mode. Changing the mode of an alpha shape entails a partial re-computation of the data structure.

Friends And Related Function Documentation

template<typename Dt , typename ExactAlphaComparisonTag >

ostream & operator<< ( std::ostream &  os, const Alpha_shape_3< Dt, ExactAlphaComparisonTag > &  A  )

related

Inserts the alpha shape A for the current alpha value into the stream os.

Defined in CGAL/IO/io.h

Precondition

The insert operator must be defined for Point.

template<typename Dt , typename ExactAlphaComparisonTag >

Geomview_stream & operator<< ( Geomview_stream &  W, const Alpha_shape_3< Dt, ExactAlphaComparisonTag > &  A  )

related

Inserts the alpha shape A for the current alpha value into the Geomview stream W.

Precondition

The insert operator must be defined for GT::Point and GT::Triangle.

Defined in CGAL/IO/Geomview_stream.h and CGAL/IO/alpha_shape_geomview_ostream_3.h