CGAL 6.1 - 2D Alpha Shapes

Loading...
Searching...
No Matches
List of all members
CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag > Class Template Reference
Reference Manual

`#include <CGAL/Alpha_shape_2.h>`

## Inherits from

Dt.

## Definition

template<typename Dt, typename ExactAlphaComparisonTag>
class CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >

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.

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.

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 the tag `ExactAlphaComparisonTag` is currently ignored (meaning that the code will behave as if `ExactAlphaComparisonTag` were set to `Tag_false`) if `Dt::Geom_traits::FT` is not a floating point number type as this strategy does not make sense if the traits class already provides exact constructions.

Warning
  - When the tag `ExactAlphaComparisonTag` is set to `Tag_true`, the class `Cartesian_converter` is used internally to switch between the traits class and the CGAL kernel `CGAL::Simple_cartesian<NT>`, where `NT` can be either `CGAL::Interval_nt` or `CGAL::Exact_rational`. `Cartesian_converter` must thus offer the necessary functors to convert a two-dimensional point of the traits class to a two-dimensional point of `CGAL::Simple_cartesian<NT>`. However, these functors are not necessarily provided by the basic `Cartesian_converter`. For example when using the traits class `CGAL::Projection_traits_xy_3`, a `CGAL::Point_3` is camouflaged as a `Point_2` and the basic `Cartesian_converter` does not know how to convert from the camouflaged `CGAL::Point_3` to the two-dimensional point of `CGAL::Simple_cartesian<NT>`. In this case, a partial specialization of `Cartesian_converter` must be provided by the user. An example of such specialization is given in the example ex_alpha_projection_traits.cpp.
  - The tag `ExactAlphaComparisonTag` cannot be used in conjunction with periodic triangulations. When the tag `ExactAlphaComparisonTag` is set to `Tag_true`, the evaluations of predicates such as `Side_of_oriented_circle_2` are done lazily. Consequently, the predicates store pointers to the geometrical positions of the points passed as arguments of the predicates. It is thus important that these points are not temporary objects. Points of the triangulation are accessed using the function `point(Face_handle, int)` of the underlying triangulation. In the case of periodic triangulations, the `point(Face_handle, int)` function is actually a construction that returns a temporary, which thus cannot be used along with a lazy predicate evaluation.

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_projection_traits.cpp, Alpha_shapes_2/ex_alpha_shapes_2.cpp, Alpha_shapes_2/ex_periodic_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.
typedef Gt::FT | FT
| the number type of alpha values.
typedef Dt::Point | Point
| The point type.
typedef unspecified_type | size_type
| The size type.
typedef unspecified_type | Alpha_iterator
| A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different \( \alpha\)-values.
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\).
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\).

## Creation
| Alpha_shape_2 (FT alpha=0, Mode m=GENERAL)
| Introduces an empty alpha-shape for a positive \( \alpha\)-value `alpha`.
| 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`.
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`.

## 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)`.
void | clear ()
| Clears the structure.
FT | set_alpha (const FT &alpha)
| Sets the \( \alpha\)-value to `alpha`.
const FT & | get_alpha (void) const
| Returns the current \( \alpha\)-value.
const FT & | get_nth_alpha (size_type n) const
| Returns the `n`-th \(\alpha\)-value, sorted in an increasing order.
size_type | number_of_alphas () const
| Returns the number of different alpha-values.
Mode | set_mode (Mode m=GENERAL)
| Sets the mode to its general or regularized version.
Mode | get_mode (void) const
| Returns the mode, that is either `GENERAL` or `REGULARIZED`.
Alpha_shape_vertices_iterator | alpha_shape_vertices_begin ()
| Starts at an arbitrary finite vertex which belongs to the \( \alpha\)-shape for the current \( \alpha\).
Alpha_shape_vertices_iterator | alpha_shape_vertices_end ()
| Past-the-end iterator.
Alpha_shape_edges_iterator | alpha_shape_edges_begin ()
| Starts at an arbitrary finite edge which belongs to the \( \alpha\)-shape for the current \( \alpha\).
Alpha_shape_edges_iterator | alpha_shape_edges_end ()
| Past-the-end iterator.
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.
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:
ostream & | operator<< (std::ostream &os, const Alpha_shape_2< Dt > &A)
| Inserts the alpha shape for the current \( \alpha\)-value into the stream `os`.

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

## 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.
Alpha_iterator | alpha_end () const
| Returns the corresponding past-the-end iterator.
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.
Alpha_iterator | alpha_lower_bound (const FT &alpha) const
| Returns an iterator pointing to the first element with \( \alpha\)-value not less than `alpha`.
Alpha_iterator | alpha_upper_bound (const FT &alpha) const
| Returns an iterator pointing to the first element with \( \alpha\)-value greater than `alpha`.

## Member Typedef Documentation

## ◆ Alpha_iterator

template<typename Dt , typename ExactAlphaComparisonTag >

typedef unspecified_type CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Alpha_iterator

A bidirectional and non-mutable iterator that allow to traverse the increasing sequence of different \( \alpha\)-values.

Precondition
  Its `value_type` is `FT`.

## ◆ Alpha_shape_edges_iterator

template<typename Dt , typename ExactAlphaComparisonTag >

typedef unspecified_type CGAL::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 \( \alpha\)-shape for the current \( \alpha\).

Precondition
  Its `value_type` is `Dt::Edge`.

## ◆ Alpha_shape_vertices_iterator

template<typename Dt , typename ExactAlphaComparisonTag >

typedef unspecified_type CGAL::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 \( \alpha\)-shape for the current \( \alpha\).

Precondition
  Its `value_type` is `Dt::Vertex_handle`.

## ◆ FT

template<typename Dt , typename ExactAlphaComparisonTag >

typedef Gt::FT CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::FT

the number type of alpha values.

In case `ExactAlphaComparisonTag` is `CGAL::Tag_false`, it is Gt::FT.

In case `ExactAlphaComparisonTag` is `CGAL::Tag_true`, it is a number type allowing filtered exact comparisons (that is, interval arithmetic is first used before resorting to exact arithmetic). Access to the interval containing the exact value is provided through the function `FT::Approximate_nt approx() const` where `FT::Approximate_nt` is `CGAL::Interval_nt<Protected>` with `Protected=true`. Access to the exact value is provided through the function `FT::Exact_nt exact() const` where `FT::Exact_nt` depends on the configuration of CGAL (it is `Gmpq` if `gmp` is available and `Quotient<CGAL::MP_Float>` otherwise). An overload for the function `double to_double(FT)` is also available. Its precision is controlled through `FT::set_relative_precision_of_to_double()` in exactly the same way as with `Lazy_exact_nt<NT>`, so a call to `to_double` may trigger an exact evaluation. It must be noted that an object of type `FT` is valid as long as the alpha shapes class that creates it is valid and has not been modified. For convenience, classical comparison operators are provided for the type `FT`.

## ◆ Gt

template<typename Dt , typename ExactAlphaComparisonTag >

typedef unspecified_type CGAL::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.

## ◆ Point

template<typename Dt , typename ExactAlphaComparisonTag >

typedef Dt::Point CGAL::Alpha_shape_2< Dt, ExactAlphaComparisonTag >::Point

The point type.

For basic alpha shapes, `Point` will be equal to `Gt::Point_2`. For weighted alpha shapes, `Point` will be equal to `Gt::Weighted_point_2`.

## Member Enumeration Documentation

## ◆ Classification_type

template<typename Dt , typename ExactAlphaComparisonTag >

enum CGAL::Alpha_shape_2::Classification_type

Distinguishes the different cases for classifying a \( k\)-dimensional face of the underlying triangulation of the \( \alpha\)-shape.

Enumerator
EXTERIOR | if the face does not belong to the alpha-complex.
SINGULAR | if the face belongs to the boundary of the alpha-shape, but is not incident to any 2-dimensional face of the alpha-complex
REGULAR | if the face belongs to the boundary of the alpha-shape and is incident to a 2-dimensional face of the alpha-complex
INTERIOR | if the face belongs to the alpha-complex, but does not belong to the boundary of the alpha-shape.

## ◆ Mode

template<typename Dt , typename ExactAlphaComparisonTag >

enum CGAL::Alpha_shape_2::Mode

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.

Enumerator
GENERAL |
REGULARIZED |

## Constructor & Destructor Documentation

## ◆ Alpha_shape_2() [1/3]

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

## ◆ Alpha_shape_2() [2/3]

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

## ◆ Alpha_shape_2() [3/3]

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

## ◆ alpha_shape_edges_begin()

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.

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

## ◆ find_optimal_alpha()

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:

- All data points are either on the boundary or in the interior of the regularized version of the alpha shape.
- The number of solid component of the alpha shape is equal to or smaller than `nb_components`.

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.

## ◆ get_nth_alpha()

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.

## ◆ make_alpha_shape()

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

## ◆ set_alpha()

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

## ◆ set_mode()

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

## ◆ operator<<()

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