CGAL 6.1.1 - Optimal Transportation Curve Reconstruction

Loading...
Searching...
No Matches
List of all members | Protected Attributes
CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap > Class Template Reference
Reference Manual » Classes

`#include <CGAL/Optimal_transportation_reconstruction_2.h>`

## Definition

template<class Traits, class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>
class CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >

This class provides a means to reconstruct a 1-dimensional shape from a set of 2D points with masses.

The algorithm computes an initial 2D Delaunay triangulation from the input points, and performs a simplification of the triangulation by performing half edge collapses, edge flips and vertex relocations.

The edges are either processed in the order imposed by an priority queue, or in an order based on random selection of edge collapse operators. As the exhaustive priority queue guarantees a higher quality it is the default. The user can switch to the other method, for example for an initial simplification round, by calling `set_random_sample_size()`.

By default edge flip operators are applied to ensure that every edge of the triangulation are candidate to be collapsed, while preserving a valid embedding of the triangulation. This option can be disabled by calling `set_use_flip(false)` to reduce the running times.

By default the vertices are not relocated after each half edge collapse. This option can be changed by setting the number of vertex relocation steps performed between two edge collapse operators.

The simplification is performed by calling either `run_until(n)` or `run(steps)`. The former simplifies the triangulation until n points remain, while the latter stops after `steps` edge collapse operators have been performed. Furthermore, we can relocate the vertices by calling `relocate_all_points()`.

Template Parameters

  Traits | a model of the concept `OptimalTransportationReconstructionTraits_2`.
  PointPMap | a model of `ReadablePropertyMap` with value type `Traits::Point_2`. Defaults to `boost::typed_identity_property_map<Traits::Point_2>` (for the case the input is points without mass).
  MassPMap | a model of `ReadablePropertyMap` with value type `Traits::FT` Defaults to `boost::static_property_map<Traits::FT>` (for the case the input is points without mass).

Examples
  Optimal_transportation_reconstruction_2/otr2_indexed_output_example.cpp, Optimal_transportation_reconstruction_2/otr2_list_output_example.cpp, Optimal_transportation_reconstruction_2/otr2_mass_example.cpp, Optimal_transportation_reconstruction_2/otr2_simplest_example.cpp, and Optimal_transportation_reconstruction_2/otr2_simplest_example_with_tolerance.cpp.

## Protected Attributes
std::vector< Sample_ > | m_samples
Triangulation | m_dt
Traits const & | m_traits
MultiIndex | m_mindex
int | m_ignore
int | m_verbose
std::size_t | m_mchoice
bool | m_use_flip
FT | m_alpha
FT | m_ghost
unsigned int | m_relocation
FT | m_tolerance
PointPMap | point_pmap
MassPMap | mass_pmap

## Types
typedef Traits::FT | FT
| Number type.
typedef Traits::Point_2 | Point
| Point type.
typedef Traits::Segment_2 | Segment
| Segment type.

## Initialization
template<class InputRange >
| Optimal_transportation_reconstruction_2 (const InputRange &input_range, PointPMap point_map=PointPMap(), MassPMap mass_map=MassPMap(1), std::size_t sample_size=0, bool use_flip=true, unsigned int relocation=2, int verbose=0, Traits traits=Traits())
| Constructor of the optimal transportation reconstruction class.

## Setting Parameters
void | set_random_sample_size (std::size_t sample_size)
| If `sample_size == 0`, the simplification is performed using an exhaustive priority queue.
void | set_verbose (int verbose)
| Determines how much console output the algorithm generates.
void | set_use_flip (const bool use_flip)
| The use_flip parameter determines whether the edge flipping procedure is used for the half-edge collapse.
void | set_relocation (unsigned int relocation)
| Sets the number of vertex relocations that are performed between two edge collapses.
void | set_relevance (const FT relevance)

## Simplification
You can freely mix calls of the following functions.
bool | run_until (std::size_t np)
| Computes a shape consisting of `np` points, reconstructing the input points.
bool | run (const unsigned int steps)
| Computes a shape, reconstructing the input, by performing `steps` edge collapse operators on the output simplex.
void | run_under_wasserstein_tolerance (const FT tolerance)
| Computes a shape, reconstructing the input, by performing edge collapse operators on the output simplex until the user-defined tolerance is reached.
void | relocate_all_points ()
| Since noise and missing data may prevent the reconstructed shape to have sharp corners well located, the algorithm offers the possibility to automatically relocate points after each edge collapse.

## Output
template<typename PointOutputIterator , typename IndexOutputIterator , typename IndexPairOutputIterator >
std::tuple< PointOutputIterator, IndexOutputIterator, IndexPairOutputIterator > | indexed_output (PointOutputIterator points, IndexOutputIterator isolated_points, IndexPairOutputIterator segments) const
| Writes the points and segments of the output simplex in an indexed format into output iterators.
template<class PointOutputIterator , class SegmentOutputIterator >
void | list_output (PointOutputIterator v_it, SegmentOutputIterator e_it) const
| Returns the solid edges and vertices present after the reconstruction process finished.

## Constructor & Destructor Documentation

## ◆ Optimal_transportation_reconstruction_2()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>
template<class InputRange >

CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::Optimal_transportation_reconstruction_2 | ( | const InputRange & | input_range,
|  | PointPMap | point_map = `PointPMap()`,
|  | MassPMap | mass_map = `MassPMap(1)`,
|  | std::size_t | sample_size = `0`,
|  | bool | use_flip = `true`,
|  | unsigned int | relocation = `2`,
|  | int | verbose = `0`,
|  | Traits | traits = `Traits()`
| ) |  |

Constructor of the optimal transportation reconstruction class.

It builds an initial simplicial complex for a given range of point-mass pairs.

Template Parameters

  InputRange | is a model of `Range` with forward iterators, providing input points and point masses through the `PointPMap` and `MassPMap` property maps.

Parameters

  input_range | Range of input data.
  point_map | A `ReadablePropertyMap` used to access the input points.
  mass_map | A `ReadablePropertyMap` used to access the input points' masses.
  sample_size | If `sample_size != 0`, the size of the random sample which replaces the exhaustive priority queue.
  use_flip | If `true` the edge flipping procedure is used to ensure that every edge can be made collapsible.
  relocation | The number of point relocations that are performed between two edge collapses.
  verbose | Controls how much console output is produced by the algorithm. The values are 0, 1, or > 1.
  traits | The traits class.

## Member Function Documentation

## ◆ indexed_output()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>
template<typename PointOutputIterator , typename IndexOutputIterator , typename IndexPairOutputIterator >

std::tuple< PointOutputIterator, IndexOutputIterator, IndexPairOutputIterator > CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::indexed_output | ( | PointOutputIterator | points,
|  | IndexOutputIterator | isolated_points,
|  | IndexPairOutputIterator | segments
| ) |  | const

Writes the points and segments of the output simplex in an indexed format into output iterators.

Template Parameters

  PointOutputIterator | An output iterator with value type Point .
  IndexOutputIterator | An output iterator with value type `std::size_t`.
  IndexPairOutputIterator | An output iterator with value type `std::pair<std::size_t, std::size_t>`.

Parameters

  points | The output iterator for all points.
  isolated_points | The output iterator for the indices of isolated points.
  segments | The output iterator for the pairs of segment indices.

## ◆ list_output()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>
template<class PointOutputIterator , class SegmentOutputIterator >

void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::list_output | ( | PointOutputIterator | v_it,
|  | SegmentOutputIterator | e_it
| ) |  | const

Returns the solid edges and vertices present after the reconstruction process finished.

It takes two output iterators, one for storing the isolated points and one for storing the edges of the reconstructed shape.

Template Parameters

  PointOutputIterator | An output iterator with value type Point .
  SegmentOutputIterator | An output iterator with value type Segment .

## ◆ relocate_all_points()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::relocate_all_points | ( |  | ) |

Since noise and missing data may prevent the reconstructed shape to have sharp corners well located, the algorithm offers the possibility to automatically relocate points after each edge collapse.

The new location of the points is chosen such that the fitting of the output segments to the input points is improved.

## ◆ run()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

bool CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::run | ( | const unsigned int | steps | ) |

Computes a shape, reconstructing the input, by performing `steps` edge collapse operators on the output simplex.

Parameters

  steps | The number of edge collapse operators to be performed.

Returns
  `true` if the required number of steps was performed, `false` if the algorithm was prematurely ended because no more edge collapse was possible.

## ◆ run_under_wasserstein_tolerance()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::run_under_wasserstein_tolerance | ( | const FT | tolerance | ) |

Computes a shape, reconstructing the input, by performing edge collapse operators on the output simplex until the user-defined tolerance is reached.

Note
  The tolerance is given in the sense of the Wasserstein distance. It is not a Hausdorff tolerance: it does not mean that the distance between the input samples and the output polyline is guaranteed to be less than `tolerance`. It means that the square root of transport cost per mass (homogeneous to a distance) is at most `tolerance`.

Parameters

  tolerance | Tolerance on the Wasserstein distance.

## ◆ run_until()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

bool CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::run_until | ( | std::size_t | np | ) |

Computes a shape consisting of `np` points, reconstructing the input points.

Parameters

  np | The number of points which will be present in the output.

Returns
  `true` if the number of points `np` was reached, `false` if the algorithm was prematurely ended because no more edge collapse was possible.

## ◆ set_random_sample_size()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::set_random_sample_size | ( | std::size_t | sample_size | ) |

If `sample_size == 0`, the simplification is performed using an exhaustive priority queue.

If `sample_size` is strictly positive the simplification is performed using a multiple choice approach, i.e., a best-choice selection in a random sample of edge collapse operators, of size `sample_size`. A typical value for the sample size is 15, but this value must be enlarged when targeting a very coarse simplification.

Parameters

  sample_size | If `sample_size != 0`, the size of the random sample replaces the priority queue.

## ◆ set_relevance()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::set_relevance | ( | const FT | relevance | ) |

Parameters

  relevance | The relevance threshold used for filtering the edges. An edge is relevant from the approximation point of view if it is long, covers a large mass (or equivalently the number of points when all masses are equal), and has a small transport cost. This notion is defined as \( m(e) * |e|^2 / cost(e) \), where \( m(e) \) denotes the mass of the points approximated by the edge, \( |e| \) denotes the edge length and \( cost(e) \) its approximation error. As the cost is defined by mass time squared distance the relevance is unitless.

The default value is 1, so that all edges receiving some mass are considered relevant. Setting a large relevance value is used to get robustness to a large amount of outliers.

## ◆ set_verbose()

template<class Traits , class PointPMap = boost::typed_identity_property_map <typename Traits::Point_2>, class MassPMap = boost::static_property_map <typename Traits::FT>>

void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::set_verbose | ( | int | verbose | ) |

Determines how much console output the algorithm generates.

If set to a value larger than 0 details about the reconstruction process are written to `std::cerr`.

Parameters

  verbose | The verbosity level.