\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.12 - Optimal Transportation Curve Reconstruction
CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap > Class Template Reference

#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
Traitsa model of the concept OptimalTransportationReconstructionTraits_2.
PointPMapa 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).
MassPMapa 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.

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

Settting Parameters

void set_random_sample_size (std::size_t sample_size)
 If sample_size == 0, the simplification is performed using an exhaustive priority queue. More...
 
void set_verbose (int verbose)
 Determines how much console output the algorithm generates. More...
 
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. More...
 
bool run (const unsigned steps)
 Computes a shape, reconstructing the input, by performing steps edge collapse operators on the output simplex. More...
 
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. More...
 
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. More...
 

Output

template<typename PointOutputIterator , typename IndexOutputIterator , typename IndexPairOutputIterator >
CGAL::cpp11::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. More...
 
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. More...
 

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
InputRangeis a model of Range with forward iterators, providing input points and point masses through the PointPMap and MassPMap property maps.
Parameters
input_rangeRange of input data.
point_mapA ReadablePropertyMap used to access the input points.
mass_mapA ReadablePropertyMap used to access the input points' masses.
sample_sizeIf sample_size != 0, the size of the random sample which replaces the exhaustive priority queue.
use_flipIf true the edge flipping procedure is used to ensure that every edge can be made collapsible.
relocationThe number of point relocations that are performed between two edge collapses.
verboseControls how much console output is produced by the algorithm. The values are 0, 1, or > 1.
traitsThe 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 >
CGAL::cpp11::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
PointOutputIteratorAn output iterator with value type Point .
IndexOutputIteratorAn output iterator with value type std::size_t.
IndexPairOutputIteratorAn output iterator with value type std::pair<std::size_t, std::size_t>.
Parameters
pointsThe output iterator for all points.
isolated_pointsThe output iterator for the indices of isolated points.
segmentsThe 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
PointOutputIteratorAn output iterator with value type Point .
SegmentOutputIteratorAn 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  steps)

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

Parameters
stepsThe 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
toleranceTolerance 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
npThe 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 stricly positive the simplification is performed using a multiple choice approach, ie, 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_sizeIf 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
relevanceThe 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
verboseThe verbosity level.