CGAL 4.7 - 2D Alpha Shapes
|
#include <CGAL/Alpha_shape_2.h>
Dt.
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.
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.
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... | |
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
.
alpha
\( \geq~0\). 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
.
alpha
\( \geq~0\). 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
.
InputIterator | must be an input iterator with the value type Point . |
alpha
\( \geq0\). 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.
Alpha_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_end | ( | ) | const |
Returns the corresponding past-the-end iterator.
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.
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
.
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.
Alpha_shape_edges_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_shape_edges_end | ( | ) |
Past-the-end iterator.
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\).
Alpha_shape_vertices_iterator CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::alpha_shape_vertices_end | ( | ) |
Past-the-end iterator.
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
.
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.
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.
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.
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.
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.
void CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::clear | ( | ) |
Clears the structure.
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 andIf no such value is found, the iterator points to the first element with \( \alpha\)-value such that the alpha shape satisfies the second property.
const FT& CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::get_alpha | ( | void | ) | const |
Returns the current \( \alpha\)-value.
Mode CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::get_mode | ( | void | ) | const |
Returns the mode, that is either GENERAL
or REGULARIZED
.
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.
n
\( <\) number of alphas. 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.
InputIterator | must be an input iterator with the value type Point . |
size_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::number_of_alphas | ( | ) | const |
Returns the number of different alpha-values.
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.
FT CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::set_alpha | ( | const FT & | alpha | ) |
Sets the \( \alpha\)-value to alpha
.
Returns the previous \( \alpha\)-value.
alpha
\( \geq0\). 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.
|
related |
Inserts the alpha shape for the current \( \alpha\)-value into the stream os
.
Point
.