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

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

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