|
CGAL 4.11 - Optimal Transportation Curve Reconstruction
|
|
CGAL 4.11 - Optimal Transportation Curve Reconstruction
|
#include <CGAL/Optimal_transportation_reconstruction_2.h>
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().
| 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). |
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 | |
| 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 | 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... | |
| 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.
| InputRange | is a model of Range with forward iterators, providing input points and point masses through the PointPMap and MassPMap property maps. |
| 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. |
| 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.
| 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>. |
| 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. |
| 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.
| 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.
| 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.
| steps | The number of edge collapse operators to be performed. |
true if the required number of steps was performed, false if the algorithm was prematurely ended because no more edge collapse was possible. | 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.
| np | The number of points which will be present in the output. |
true if the number of points np was reached, false if the algorithm was prematurely ended because no more edge collapse was possible. | 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.
| sample_size | If sample_size != 0, the size of the random sample replaces the priority queue. |
| void CGAL::Optimal_transportation_reconstruction_2< Traits, PointPMap, MassPMap >::set_relevance | ( | const FT | relevance) |
| 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.
| 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.
| verbose | The verbosity level. |
1.8.4