Alpha_shape_2<Dt,ExactAlphaComparisonTag>

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL::Alpha_shape_2<Dt,ExactAlphaComparisonTag>

Definition

The class Alpha_shape_2<Dt,ExactAlphaComparisonTag> 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.

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

#include <CGAL/Alpha_shape_2.h>

Parameters

The template parameter Dt has to be either Delaunay_triangulation_2 or Regular_triangulation_2. Note that DT::Geom_traits, DT::Vertex and DT::Face must model the concepts AlphaShapeTraits_2, AlphaShapeVertex_2 and AlphaShapeFace_2 respectively.

The template parameter ExactAlphaComparisonTag is a tag that, when set to CGAL::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 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.

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_2<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 Gt::FT

FT;

the number type for computation.

Alpha_shape_2<Dt,ExactAlphaComparisonTag>::size_type

The size type.

Alpha_shape_2<Dt,ExactAlphaComparisonTag>::Alpha_iterator

A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different α-values.

Precondition:

Its value_type is FT

Alpha_shape_2<Dt,ExactAlphaComparisonTag>::Alpha_shape_vertices_iterator

A bidirectional and non-mutable iterator that allow to traverse the vertices which belongs to the α-shape for the current α.

Precondition:

Its value_type is Dt::Vertex_handle

Alpha_shape_2<Dt,ExactAlphaComparisonTag>::Alpha_shape_edges_iterator

A bidirectional and non-mutable iterator that allow to traverse the edges which belongs to the α-shape for the current α.

Precondition:

Its value_type is Dt::Edge.

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,ExactAlphaComparisonTag> A ( FT alpha = 0, Mode m = GENERAL);

Introduces an empty α-shape A for a positive α-value alpha.

Precondition:

alpha ≥ 0.

Alpha_shape_2<Dt,ExactAlphaComparisonTag> A ( Dt& dt, FT alpha = 0, Mode m = GENERAL);

Builds an alpha shape of mode m from the triangulation dt for a positive α-value alpha. Be careful that this operation destroys the triangulation.

Precondition:

alpha ≥ 0.

template < class InputIterator >

Alpha_shape_2<Dt,ExactAlphaComparisonTag> A ( InputIterator first, InputIterator last, FT 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 >

std::ptrdiff_t

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

Precondition:

The value_type of first and last is Point.

void

A.clear ()

Clears the structure.

A.set_alpha ( FT alpha)

Sets the α-value to alpha. Returns the previous α-value.

Precondition:

alpha ≥ 0.

A.get_alpha ( void) const

Returns the current α-value.

A.get_nth_alpha ( size_type n) const

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

Precondition:

n < number of alphas.

size_type

A.number_of_alphas () const

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) const

Returns whether A is general or regularized.

Alpha_shape_vertices_iterator

A.alpha_shape_vertices_begin ()

Starts at an arbitrary finite vertex which belongs to the α-shape for the current α.

Alpha_shape_vertices_iterator

A.alpha_shape_vertices_end ()

Past-the-end iterator.

Alpha_shape_edges_iterator

A.alpha_shape_edges_begin ()

Starts at an arbitrary finite edge which belongs to the α-shape for the current α. In regularized mode, edges are represented as a pair (f,i), where f is an interior face of the α-shape.

Alpha_shape_edges_iterator

A.alpha_shape_edges_end ()

Past-the-end iterator.

Predicates

Classification_type	A.classify ( Point p, FT alpha = get_alpha()) const
		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, FT alpha = get_alpha()) const
		Classifies the face f of the underlying triangulation with respect to A.

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

Classification_type	A.classify ( Face_handle f, int i, 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 A.

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

Traversal of the α-Values

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

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

Alpha_iterator	A.alpha_find ( FT alpha) const	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) const
		Returns an iterator pointing to the first element with α-value not less than alpha.

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

Operations

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

Alpha_iterator	A.find_optimal_alpha ( size_type nb_components) const
		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. The format for the iostream is an internal format.

#include <CGAL/IO/io.h>

ostream&

ostream& os << Alpha_shape_2<Dt> A

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

Precondition:

The insert operator must be defined for Point.

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.

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 faces of the underlying triangulation. A.find_optimal_alpha uses binary search and takes time O( n log n ), where n is the number of points.

Next: AlphaShapeFace_2

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL Open Source Project. Release 4.0.2. 4 July 2012.