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

#include <CGAL/Alpha_shape_2.h>

Inherits from

Dt.

Definition

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.

Template Parameters

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 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.

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.

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.

Examples:

Alpha_shapes_2/ex_alpha_shapes_2.cpp, and Alpha_shapes_2/ex_weighted_alpha_shapes_2.cpp.

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. More...
typedef Gt::FT	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...
typedef unspecified_type	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	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...

Creation
	Alpha_shape_2 (FT alpha=0, Mode m=GENERAL)
	Introduces an empty alpha-shape for a positive \( \alpha\)-value alpha. More...
	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. More...
template<class InputIterator >
	Alpha_shape_2 (InputIterator first, InputIterator last, const FT &alpha=0, Mode m=GENERAL)
	Initializes the family of alpha-shapes with the points in the range [first,last) and introduces an \( \alpha\)-shape for a positive \( \alpha\)-value alpha. More...

Operations
template<class InputIterator >
std::ptrdiff_t	make_alpha_shape (InputIterator first, InputIterator last)
	Initialize the family of alpha-shapes with the 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...
const FT &	get_alpha (void) const
	Returns the current \( \alpha\)-value. More...
const FT &	get_nth_alpha (size_type 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...
Mode	set_mode (Mode m=GENERAL)
	Sets the mode to its general or regularized version. More...
Mode	get_mode (void) const
	Returns the mode, that is either GENERAL or REGULARIZED. More...
Alpha_shape_vertices_iterator	alpha_shape_vertices_begin ()
	Starts at an arbitrary finite vertex which belongs to the \( \alpha\)-shape for the current \( \alpha\). More...
Alpha_shape_vertices_iterator	alpha_shape_vertices_end ()
	Past-the-end iterator. More...
Alpha_shape_edges_iterator	alpha_shape_edges_begin ()
	Starts at an arbitrary finite edge which belongs to the \( \alpha\)-shape for the current \( \alpha\). More...
Alpha_shape_edges_iterator	alpha_shape_edges_end ()
	Past-the-end iterator. More...
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 the first element with \( \alpha\)-value such that the alpha shape satisfies the following two properties: More...
ostream &	operator<< (std::ostream &os, const Alpha_shape_2< Dt > &A)
	Inserts the alpha shape for the current \( \alpha\)-value into the stream os. More...

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 k-face with respect to the alpha shape. More...
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. More...
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. More...
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. More...
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. 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...

Constructor & Destructor Documentation

template<typename Dt , typename ExactAlphaComparisonTag >

CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_shape_2	(	FT	alpha = 0,
		Mode	m = GENERAL
	)

Introduces an empty alpha-shape for a positive \( \alpha\)-value alpha.

Precondition

alpha \( \geq~0\).

template<typename Dt , typename ExactAlphaComparisonTag >

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.

Attention

This operation destroys the triangulation.

Precondition

alpha \( \geq~0\).

template<typename Dt , typename ExactAlphaComparisonTag >

template<class InputIterator >

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

Initializes the family of alpha-shapes with the points in the range [first,last) and introduces an \( \alpha\)-shape for a positive \( \alpha\)-value alpha.

Template Parameters

InputIterator

must be an input iterator with the value type Point.

Precondition

alpha \( \geq0\).

Member Function Documentation

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_2< 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_2< Dt, ExactAlphaComparisonTag >::alpha_end

(

)

const

Returns the corresponding past-the-end iterator.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_2< 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_2< 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_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.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_shape_edges_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_shape_edges_end

(

)

Past-the-end iterator.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_shape_vertices_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_shape_vertices_begin

(

)

Starts at an arbitrary finite vertex which belongs to the \( \alpha\)-shape for the current \( \alpha\).

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_shape_vertices_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_shape_vertices_end

(

)

Past-the-end iterator.

template<typename Dt , typename ExactAlphaComparisonTag >

Alpha_iterator CGAL::Alpha_shape_2< 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_2< 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 the alpha shape.

template<typename Dt , typename ExactAlphaComparisonTag >

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

Classifies the face f of the underlying triangulation with respect to the alpha shape.

template<typename Dt , typename ExactAlphaComparisonTag >

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

Classifies the edge e of the underlying triangulation with respect to the alpha shape.

template<typename Dt , typename ExactAlphaComparisonTag >

Classification_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::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.

template<typename Dt , typename ExactAlphaComparisonTag >

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

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

template<typename Dt , typename ExactAlphaComparisonTag >

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

(

)

Clears the structure.

template<typename Dt , typename ExactAlphaComparisonTag >

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 equals the number of solid components and
• all data points are either on the boundary or in the interior of the regularized version of the alpha shape.

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.

template<typename Dt , typename ExactAlphaComparisonTag >

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

(

void

)

const

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

template<typename Dt , typename ExactAlphaComparisonTag >

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

(

void

)

const

Returns the mode, that is either GENERAL or REGULARIZED.

template<typename Dt , typename ExactAlphaComparisonTag >

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.

Precondition

n \( <\) number of alphas.

template<typename Dt , typename ExactAlphaComparisonTag >

template<class InputIterator >

std::ptrdiff_t CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::make_alpha_shape	(	InputIterator	first,
		InputIterator	last
	)

Initialize the family of alpha-shapes with the points in the range [first,last).

Returns the number of inserted points.

If the function is applied to an non-empty family of alpha-shape, it is cleared before initialization.

Template Parameters

InputIterator

must be an input iterator with the value type Point.

template<typename Dt , typename ExactAlphaComparisonTag >

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

(

)

const

Returns the number of different alpha-values.

template<typename Dt , typename ExactAlphaComparisonTag >

size_type CGAL::Alpha_shape_2< 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_2< 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_2< Dt, ExactAlphaComparisonTag >::set_mode

(

Mode

m = GENERAL

)

Sets the mode to its general or regularized version.

Returns the previous mode.

Friends And Related Function Documentation

template<typename Dt , typename ExactAlphaComparisonTag >

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

related

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

Precondition

CGAL/IO/io.h must be included.

The insert operator must be defined for Point.