Geogram
Version 1.9.1
A programming library of geometric algorithms
|
Computes semi-discrete optimal transport maps. More...
#include <exploragram/optimal_transport/optimal_transport.h>
Classes | |
class | Callback |
Base class for the callbacks executed for each intersection between a Laguerre cell and a simplex of the background mesh. More... | |
Public Member Functions | |
OptimalTransportMap (index_t dimension, Mesh *mesh, const std::string &delaunay="default", bool BRIO=false) | |
OptimalTransportMap constructor. More... | |
virtual | ~OptimalTransportMap () |
OptimalTransportMap destructor. | |
index_t | dimension () const |
Gets the dimension. More... | |
Mesh & | mesh () |
Gets the mesh. More... | |
void | set_Newton (bool x) |
Sets whether Newton algorithm should be used. More... | |
void | set_points (index_t nb_points, const double *points, index_t stride=0) |
Sets the points that define the target distribution. More... | |
void | set_air_particles (index_t nb_air_particles, const double *air_particles, index_t stride, double air_fraction) |
Sets the air particles that define the volume occupied by the free space. More... | |
double | air_fraction () const |
Gets the air fraction. More... | |
index_t | nb_air_particles () const |
Gets the number of air particles. More... | |
void | set_nu (index_t i, double nu) |
Sets the desired mass at one of the Diracs. More... | |
void | set_Laguerre_centroids (double *x) |
Specifies a user vector where the centroids of the Laguerre cells will be stored after computing transport. More... | |
void | set_epsilon (double eps) |
Sets the maximum error. More... | |
void | set_linsolve_epsilon (double eps) |
Sets the tolerance for linear solve. More... | |
void | set_linsolve_maxiter (index_t maxiter) |
Sets the maximum number of iterations for linear solve. More... | |
void | set_linesearch_maxiter (index_t maxiter) |
Sets the maximum number of line search iterations. More... | |
void | set_linesearch_init_iter (index_t init_iter) |
Sets the number of steplength reductions to be done at the first iteration. More... | |
void | set_regularization (double eps_reg) |
Sets the weight of the regularization term. More... | |
void | set_linear_solver (OTLinearSolver solver) |
Specifies whether a direct solver should be used. More... | |
void | optimize (index_t max_iterations) |
Computes the weights that realize the optimal transport map between the source mesh and the target pointset. More... | |
void | set_verbose (bool x) |
Enable/disable messages during optimization. More... | |
void | optimize_full_Newton (index_t max_iterations, index_t n=0) |
Computes the weights that realize the optimal transport map between the source mesh and the target pointset. More... | |
void | optimize_level (index_t b, index_t e, index_t max_iterations) |
Optimizes one level of the multilevel algorithm. More... | |
void | optimize_levels (const vector< index_t > &levels, index_t max_iterations) |
Multi-level optimization. More... | |
index_t | nb_points () const |
Gets the number of points. More... | |
const double * | point_ptr (index_t i) const |
Gets a point. More... | |
double | weight (index_t i) const |
Gets weight of a point. More... | |
void | set_weight (index_t i, double val) |
Sets a weight of a point. More... | |
double | potential (index_t i) const |
Gets the d+1-th coordinate of the embedding for a point. More... | |
RestrictedVoronoiDiagram * | RVD () |
Gets the restricted Voronoi diagram. More... | |
void | set_save_RVD_iter (bool x, bool show_RVD_seed=false, bool last_iter_only=false) |
Sets whether the restricted Voronoi diagram at each iteration should be saved. More... | |
virtual void | get_RVD (Mesh &M)=0 |
Computes a mesh with the restricted Voronoi diagram. More... | |
virtual void | compute_Laguerre_centroids (double *centroids)=0 |
Computes the centroids of the Laguerre cells. More... | |
void | update_sparsity_pattern () |
Updates the sparsity pattern of the Hessian right after a new Laguerre diagram was computed. | |
void | new_linear_system (index_t n, double *x) |
Starts a new linear system. More... | |
void | add_ij_coefficient (index_t i, index_t j, double a) |
Adds a coefficient to the matrix of the system. More... | |
void | add_i_right_hand_side (index_t i, double a) |
Adds a coefficient to the right hand side. More... | |
void | solve_linear_system () |
Solves a linear system. More... | |
void | set_initial_weight (index_t i, double w) |
Sets the initial value of the weight associated with one of the points. More... | |
double | total_mass () const |
Gets the total mass of the domain. More... | |
void | compute_P1_Laplacian (const double *weights, NLMatrix Laplacian, double *measures) |
Computes the P1 Laplacian of the Laguerre cells. More... | |
Static Public Member Functions | |
static void | funcgrad_CB (index_t n, double *x, double &f, double *g) |
Callback for the numerical solver. More... | |
static void | newiteration_CB (index_t n, const double *x, double f, const double *g, double gnorm) |
Callback for the numerical solver. More... | |
Protected Member Functions | |
double | nu (index_t p) const |
Gets the mass of the Dirac associated with point p. More... | |
virtual void | newiteration () |
Callback for the numerical solver. | |
void | save_RVD (index_t id) |
Saves the RVD at each iteration if specified on command line (just for debugging/ explaining the algorithm). More... | |
void | funcgrad (index_t n, double *w, double &f, double *g) |
Computes the objective function and its gradient. More... | |
virtual void | call_callback_on_RVD ()=0 |
Calls the callback for each intersection between a Laguerre cell and a simplex of the background mesh. | |
void | eval_func_grad_Hessian (index_t n, const double *w, double &f, double *g) |
Computes the objective function, its gradient and its Hessian. More... | |
double | gradient_threshold (index_t n) const |
Computes the stopping criterion of the solver. More... | |
Protected Attributes | |
index_t | dimension_ |
index_t | dimp1_ |
dimension_ + 1 | |
Mesh * | mesh_ |
Delaunay_var | delaunay_ |
RestrictedVoronoiDiagram_var | RVD_ |
vector< double > | points_dimp1_ |
vector< double > | weights_ |
double | total_mass_ |
double | constant_nu_ |
Value of one of the Diracs if cte. | |
vector< double > | nu_ |
Value of all the Diracs. | |
double | epsilon_ |
Acceptable relative deviation for the measure of a cell. | |
index_t | current_call_iter_ |
Callback * | callback_ |
std::string | last_stats_ |
bool | pretty_log_ |
index_t | level_ |
bool | save_RVD_iter_ |
bool | save_RVD_last_iter_ |
bool | show_RVD_seed_ |
index_t | current_iter_ |
bool | newton_ |
bool | verbose_ |
double | epsilon_regularization_ |
Add a regularization term to remove translational degree of freedom for the weights. | |
index_t | nbZ_ |
Number of empty cells in last iteration. | |
double | g_norm_ |
Norm of the gradient in last iteration. | |
double | measure_of_smallest_cell_ |
Measure of the smallest Laguerre cell. | |
bool | w_did_not_change_ |
True if w did not change, thus there is no need to recompute the power diagram. | |
double * | Laguerre_centroids_ |
If user-specified, then Laguerre centroids are output here. | |
double | linsolve_epsilon_ |
maximum value of \( \| Ax - b \| / \| b \| \) | |
index_t | linsolve_maxiter_ |
maximum number of iterations for linear solve | |
index_t | linesearch_maxiter_ |
maximum number of steplength divisions | |
index_t | linesearch_init_iter_ |
starting number of steplength divisions | |
OTLinearSolver | linear_solver_ |
one of OT_PRECG, OT_SUPERLU, OT_CHOLMOD. | |
const double * | air_particles_ |
if set, pointer to the air particles. | |
index_t | nb_air_particles_ |
if non-zero, number of air particles. | |
index_t | air_particles_stride_ |
Number of doubles between two consecutive air particles in air_particles_. | |
double | air_fraction_ |
The fraction of the total mass occupied by air. | |
bool | clip_by_balls_ |
Enabled if air fraction is specified without any air particles. | |
bool | user_H_g_ |
True if class is just used by user to compute Hessian and gradient instead of doing full computation. | |
NLMatrix | user_H_ |
User-defined Hessian matrix. | |
Static Protected Attributes | |
static OptimalTransportMap * | instance_ |
Computes semi-discrete optimal transport maps.
Computes an optimal transport map between two distributions. The first distribution is represented by a simplicial mesh. The second distribution is a sum of Diracs. The algorithm is described in the following references:
Definition at line 91 of file optimal_transport.h.
GEO::OptimalTransportMap::OptimalTransportMap | ( | index_t | dimension, |
Mesh * | mesh, | ||
const std::string & | delaunay = "default" , |
||
bool | BRIO = false |
||
) |
OptimalTransportMap constructor.
[in] | mesh | the source distribution, represented as a nd mesh. |
[in] | delaunay | factory name of the Delaunay triangulation. |
[in] | BRIO | true if vertices are already ordered using BRIO |
|
inline |
Adds a coefficient to the right hand side.
[in] | i | the index of the coefficient |
[in] | a | the value to be added to the coefficient |
Definition at line 493 of file optimal_transport.h.
Adds a coefficient to the matrix of the system.
[in] | i,j | the indices of the coefficient |
[in] | a | the value to be added to the coefficient |
Definition at line 477 of file optimal_transport.h.
|
inline |
Gets the air fraction.
Definition at line 181 of file optimal_transport.h.
|
pure virtual |
Computes the centroids of the Laguerre cells.
[out] | centroids | a pointer to the dimension()*nb_points coordinates of the centroids. |
Implemented in GEO::OptimalTransportMapOnSurface, GEO::OptimalTransportMap3d, and GEO::OptimalTransportMap2d.
void GEO::OptimalTransportMap::compute_P1_Laplacian | ( | const double * | weights, |
NLMatrix | Laplacian, | ||
double * | measures | ||
) |
Computes the P1 Laplacian of the Laguerre cells.
[in] | Omega | the domain, either a surfacic or a volumetric mesh. |
[in] | weights | the weights of the Laguerre diagram. |
[out] | Laplacian | P1 Laplacian of the Laguerre diagram or nullptr if not needed. |
[out] | measures | optional measures the measures of all Laguerre cells, or nullptr if not needed. |
|
inline |
|
protected |
Computes the objective function, its gradient and its Hessian.
Gradient and Hessian are used to solve a Newton step H p = -g
[in] | n | number of variables |
[in] | w | current value of the variables |
[out] | f | current value of the objective function |
[out] | g | gradient of the objective function |
|
protected |
Computes the objective function and its gradient.
[in] | n | number of variables |
[in] | w | current value of the variables |
[out] | f | current value of the objective function |
[out] | g | gradient of the objective function |
|
static |
Callback for the numerical solver.
Evaluates the objective function and its gradient.
[in] | n | number of variables |
[in] | x | current value of the variables |
[out] | f | current value of the objective function |
[out] | g | gradient of the objective function |
|
pure virtual |
Computes a mesh with the restricted Voronoi diagram.
[out] | M | a reference to the computed restricted Voronoi diagram. |
Implemented in GEO::OptimalTransportMapOnSurface, GEO::OptimalTransportMap3d, and GEO::OptimalTransportMap2d.
|
inlineprotected |
Computes the stopping criterion of the solver.
The stopping criterion is determined from the user-specified epsilon, number of samples and target measure of a cell (constant_nu_).
n | number of samples |
Definition at line 602 of file optimal_transport.h.
|
inline |
|
inline |
Gets the number of air particles.
Definition at line 189 of file optimal_transport.h.
|
inline |
Gets the number of points.
Definition at line 345 of file optimal_transport.h.
void GEO::OptimalTransportMap::new_linear_system | ( | index_t | n, |
double * | x | ||
) |
Starts a new linear system.
[in] | n | the dimension of the system |
[in] | x | pointer to a contiguous array of n doubles, where the solution will be stored. |
|
static |
Callback for the numerical solver.
[in] | n | number of variables |
[in] | x | current value of the variables |
[in] | f | current value of the objective function |
[in] | g | gradient of the objective function |
[in] | gnorm | norm of the gradient of the objective function |
|
inlineprotected |
Gets the mass of the Dirac associated with point p.
Definition at line 545 of file optimal_transport.h.
void GEO::OptimalTransportMap::optimize | ( | index_t | max_iterations | ) |
Computes the weights that realize the optimal transport map between the source mesh and the target pointset.
[in] | max_iterations | maximum number of solver iterations. |
Computes the weights that realize the optimal transport map between the source mesh and the target pointset.
The algorithm is described in http://arxiv.org/abs/1603.05579 Kitawaga, Merigot, Thibert, A Newton Algorithm for semi-discrete OT.
[in] | max_iterations | maximum number of solver iterations. |
[in] | n | number of weights to optimize, used in hierarchical mode. If zero, optimizes all the weights. |
Optimizes one level of the multilevel algorithm.
The function supposes that the sequence [0,b) has been previously optimized. It is used to initialize the sequence [b,e). The whole sequence [0,e) is then optimized.
[in] | b | index fo the first point in the level |
[in] | e | one position past the last index of the level |
[in] | max_iterations | maximum number of iterations |
void GEO::OptimalTransportMap::optimize_levels | ( | const vector< index_t > & | levels, |
index_t | max_iterations | ||
) |
Multi-level optimization.
The points specified by set_points() need to have a hierarchical structure. They can be constructed by compute_hierarchical_sampling().
[in] | levels | sample indices that correspond to level l are in the range levels[l] (included) ... levels[l+1] (excluded) |
[in] | max_iterations | maximum number of iterations |
|
inline |
Gets a point.
[in] | i | index of the point |
i
Definition at line 355 of file optimal_transport.h.
|
inline |
Gets the d+1-th coordinate of the embedding for a point.
[in] | i | index of the point |
i
Definition at line 383 of file optimal_transport.h.
|
inline |
Gets the restricted Voronoi diagram.
Definition at line 415 of file optimal_transport.h.
|
protected |
Saves the RVD at each iteration if specified on command line (just for debugging/ explaining the algorithm).
[in] | id | index to be used for the file, that will be named RVD_id.meshb |
|
inline |
Sets the air particles that define the volume occupied by the free space.
If air particles are used, then set_air_particles() needs to be called before set_points().
[in] | nb_air_particles | number of air particles. |
[in] | air_particles | a pointer to the array of doubles with the coordinates of the air particles. |
[in] | stride | number of doubles between two consecutive air particles in the array, or 0 if tightly packed. |
[in] | air_fraction | the fraction of the total mass occupied by air. |
Definition at line 164 of file optimal_transport.h.
|
inline |
Sets the maximum error.
eps | acceptable relative deviation for the measure of a Voronoi cell. |
Definition at line 218 of file optimal_transport.h.
|
inline |
Sets the initial value of the weight associated with one of the points.
[in] | i | index of the point, in 0..nb_points-1, where np_points corresponds to the parameter of set_points. |
[in] | w | the value of the weight. |
Definition at line 513 of file optimal_transport.h.
|
inline |
Specifies a user vector where the centroids of the Laguerre cells will be stored after computing transport.
[out] | x | a vector of nb points * dimension() doubles. |
Definition at line 209 of file optimal_transport.h.
|
inline |
Specifies whether a direct solver should be used.
[in] | solver | one of OT_PRECG (default), OT_SUPERLU, OT_CHOLMOD. |
The direct solvers (OT_SUPERLU, OT_CHOLMOD) are recommended only for surfacic data, since the sparse factors become not so sparse when volumetric meshes are considered.
Definition at line 281 of file optimal_transport.h.
|
inline |
Sets the number of steplength reductions to be done at the first iteration.
[in] | init_iter | the number of steplength reductions to be apllied at the first iteration. If left 0, start with Newton step at each iteration, else do tentative steplength prediction. |
Definition at line 258 of file optimal_transport.h.
|
inline |
Sets the maximum number of line search iterations.
[in] | maxiter | the maximum number of step length reduction for line search. |
Definition at line 246 of file optimal_transport.h.
|
inline |
Sets the tolerance for linear solve.
[in] | eps | the maximum value of \( \| Ax - b \| / \| b \| \)b |
Definition at line 228 of file optimal_transport.h.
|
inline |
Sets the maximum number of iterations for linear solve.
[in] | maxiter | the maximum number of iterations. |
Definition at line 237 of file optimal_transport.h.
|
inline |
Sets whether Newton algorithm should be used.
It is (for now) incompatible with multilevel.
[in] | x | if set, Newton algorithm is used instead of BFGS. |
Definition at line 133 of file optimal_transport.h.
void GEO::OptimalTransportMap::set_nu | ( | index_t | i, |
double | nu | ||
) |
Sets the desired mass at one of the Diracs.
If unspecified, then default value is total mass divided by number of point. Note that the sum of all specified masses should match the total mass.
[in] | i | the index of the dirac, in 0 .. nb_points-1 |
[in] | nu | the desired mass at point i |
void GEO::OptimalTransportMap::set_points | ( | index_t | nb_points, |
const double * | points, | ||
index_t | stride = 0 |
||
) |
Sets the points that define the target distribution.
If air particles are used, then set_air_particles() needs to be called before set_points().
[in] | nb_points | number of points in the target distribution |
[in] | points | an array of size nb_points * dimension() with the coordinates of the Diracs centers in the target distribution. |
[in] | stride | number of doubles between two consecutive points. If 0 (default), then point coordinates are considered to be packed. |
|
inline |
Sets the weight of the regularization term.
The regularization term (norm of the weight vector) cancels the translational degree of freedom of the weights.
[in] | eps_reg | the weight of the regularization term. Use 0.0 for no regularization. |
Definition at line 269 of file optimal_transport.h.
|
inline |
Sets whether the restricted Voronoi diagram at each iteration should be saved.
If flag is set, then each iteration is saved in file "RVD_nnn.geogram".
[in] | x | true if each iteration should be saved, false otherwise. |
[in] | show_RVD_seed | if true, the seed associated with each restricted Voronoi cell is connected to it |
[in] | last_iter_only | if true, only the last iteration is saved |
Definition at line 431 of file optimal_transport.h.
|
inline |
Enable/disable messages during optimization.
[in] | x | true if messages should be displayed, false otherwise. |
Definition at line 298 of file optimal_transport.h.
|
inline |
Sets a weight of a point.
[in] | i | index of the point |
[in] | val | new value of the weight |
Definition at line 374 of file optimal_transport.h.
void GEO::OptimalTransportMap::solve_linear_system | ( | ) |
Solves a linear system.
The solution is stored in the vector that was previously specified to new_linear_system().
|
inline |
Gets the total mass of the domain.
Definition at line 521 of file optimal_transport.h.
|
inline |
Gets weight of a point.
[in] | i | index of the point |
i
Definition at line 365 of file optimal_transport.h.