Definition

The class Alpha_shape_2<Dt> represents the family of $$-shapes of points in a plane for all positive $$. 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 $$ the face belongs to the $$-shape. There are links between the intervals and the $$k-dimensional faces of the triangulation.

#include <CGAL/Alpha_shape_2.h>

Inherits From

Dt

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_2<Dt>::Gt
	the alpha shape traits type.

it contains a Delaunay triangulation traits class. For example Dt::Point is a Point class.

typedef Gt::Coord_type
	Coord_type;	the number type for computation.

Alpha_shape_2<Dt>::Alpha_iterator
	An iterator that allow to traverse the increasing sequence of different $$-values. The iterator is bidirectional and non-mutable. Its value_type is Coord_type
enum Classification_type { EXTERIOR, SINGULAR, REGULAR, INTERIOR};
	Distinguishes the different cases for classifying a $$k-dimensional face of the underlying triangulation of the $$-shape. EXTERIOR if the face does not belong to the $$-complex. SINGULAR if the face belongs to the boundary of the $$-shape, but is not incident to any 2-dimensional face of the $$-complex REGULAR if the face belongs to the boundary of the $$-shape and is incident to a 2-dimensional face of the $$-complex INTERIOR if the face belongs to the $$-complex, but does not belong to the boundary of the $$-shape
enum Mode { GENERAL, REGULARIZED};
	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

Creation

Alpha_shape_2<Dt> A ( Coord_type alpha = 0, Mode m = GENERAL);
	Introduces an empty $$-shape A for a positive $$-value alpha. Precondition: alpha $$  0.
template < class InputIterator >
Alpha_shape_2<Dt> A ( InputIterator first, InputIterator last, Coord_type alpha = 0, Mode m = GENERAL);
	Initializes the family of alpha-shapes with the points in the range $$[.first, last$$.) and introduces an $$-shape A for a positive $$-value alpha. Precondition: The value_type of first and last is Point. alpha $$ 0.

Operations

template < class InputIterator >
int	A.make_alpha_shape ( InputIterator first, InputIterator last, Coord_type alpha = 0, Mode m = GENERAL)
		Initialize the family of alpha-shapes with the points in the range $$[.first, last$$.) and introduces an $$-shape A for a positive $$-value alpha. Returns the number of inserted points. If the function is applied to an non-empty family of alpha-shape, it is cleared before initialization. Precondition: The value_type of first and last is Point. alpha $$ 0.
void	A.clear ()	Clears the structure.
Coord_type	A.set_alpha ( Coord_type alpha)
		Sets the $$-value to alpha. Returns the previous $$-value. Precondition: alpha $$ 0.
Coord_type	A.get_alpha ( void)
		Returns the current $$-value.
Coord_type	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.
Mode	A.set_mode ( Mode m = GENERAL)
		Sets A to its general or regularized version. Returns the previous mode.
Mode	A.get_mode ( void)	Returns whether A is general or regularized.
template < class OutputIterator >
OutputIterator	A.get_alpha_shape_vertices ( OutputIterator result)
		Writes the vertices of the alpha shape A for the current $$-value to the container where result refers to. The value_type of result is Vertex_handle. Returns an output iterator which is the end of the constructed range.
template < class OutputIterator >
OutputIterator	A.get_alpha_shape_edges ( OutputIterator result)
		Writes the edges of the alpha shape A for the current $$-value to the container where result refers to. The value_type of result is pair<Face_handle, int>. Returns an output iterator which is the end of the constructed range.

Predicates

Classification_type
	A.classify ( Point p, Coord_type alpha = get_alpha())
		Locates a point p in the underlying triangulation and Classifies the associated k-face with respect to A.
Classification_type
	A.classify ( Face_handle f, Coord_type alpha = get_alpha())
		Classifies the face f of the underlying triangulation with respect to A.
Classification_type
	A.classify ( pair<Face_handle, int> e, Coord_type alpha = get_alpha())
		Classifies the edge e of the underlying triangulation with respect to A.
Classification_type
	A.classify ( Face_handle f, int i, Coord_type alpha = get_alpha())
		Classifies the edge of the face f opposite to the vertex with index i of the underlying triangulation with respect to A.
Classification_type
	A.classify ( Vertex_handle v, Coord_type alpha = get_alpha())
		Classifies the vertex v of the underlying triangulation with respect to A.

Traversal of the $$-Values

The alpha shape class defines an iterator that allows to visit the sorted sequence of $$-values. This iterator is non-mutable and bidirectional. Its value type is Coord_type.

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 ( Coord_type 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 ( Coord_type alpha)
		Returns an iterator pointing to the first element with $$-value not less than alpha.
Alpha_iterator	A.alpha_upper_bound ( Coord_type alpha)
		Returns an iterator pointing to the first element with $$-value greater than alpha.

Operations

int	A.number_solid_components ( Coord_type 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 the first element with $$-value such that A 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 A. If no such value is found, the iterator points to the first element with $$-value such that A satisfies the second property.

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 $$-value into the stream os. Precondition: The insert operator must be defined for Point.

#include <CGAL/IO/Window_stream.h>

#include <CGAL/IO/alpha_shapes_2_window_stream.h>

Window_stream&	Window_stream& W << A
		Inserts the alpha shape A for the current $$-value into the window stream W. Precondition: The insert operator must be defined for Point and Segment.