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>
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.
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.
Alpha_shape_2<Dt,ExactAlphaComparisonTag>::Gt | |
the alpha shape traits type.
|
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.
| |||
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 α.
| |||
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 α.
| |||
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.
|
Alpha_shape_2<Dt,ExactAlphaComparisonTag> A ( FT alpha = 0, Mode m = GENERAL); | |||
Introduces an empty α-shape A for a positive α-value
alpha.
| |||
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.
| |||
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.
|
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.
| ||||
void | A.clear () | Clears the structure. | ||
FT | A.set_alpha ( FT alpha) |
Sets the α-value to alpha.
Returns the previous α-value.
| ||
FT | A.get_alpha ( void) const | Returns the current α-value. | ||
FT | A.get_nth_alpha ( size_type n) const | |||
Returns the n-th alpha-value, sorted in an increasing order.
| ||||
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. |
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. |
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.
|
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.