Tangential complex

Classes

class  Gudhi::tangential_complex::Tangential_complex< Kernel_, DimensionTag, Concurrency_tag, Triangulation_ >
 Tangential complex data structure. More...
 

Detailed Description

Author
Clément Jamin

Definition

A Tangential Delaunay complex is a simplicial complex designed to reconstruct a \(k\)-dimensional smooth manifold embedded in \(d\)-dimensional Euclidean space. The input is a point sample coming from an unknown manifold, which means that the points lie close to a structure of "small" intrinsic dimension. The running time depends only linearly on the extrinsic dimension \( d \) and exponentially on the intrinsic dimension \( k \).

An extensive description of the Tangential complex can be found in [4].

What is a Tangential Complex?

Let us start with the description of the Tangential complex of a simple example, with \( k=1 \) and \( d=2 \). The point set \( \mathscr P \) is located on a closed curve embedded in 2D. Only 4 points will be displayed (more are required for PCA) to simplify the figures.

The input

For each point \( P \), estimate its tangent subspace \( T_P \) using PCA.

The estimated normals

Let us add the Voronoi diagram of the points in orange. For each point \( P \), construct its star in the Delaunay triangulation of \( \mathscr P \) restricted to \( T_P \).

The Voronoi diagram

The Tangential Delaunay complex is the union of those stars.

In practice, neither the ambient Voronoi diagram nor the ambient Delaunay triangulation is computed. Instead, local \( k \)-dimensional regular triangulations are computed with a limited number of points as we only need the star of each point. More details can be found in [4].

Inconsistencies

Inconsistencies between the stars can occur. An inconsistency occurs when a simplex is not in the star of all its vertices.

Let us take the same example.

Before

Let us slightly move the tangent subspace \( T_Q \)

After

Now, the star of \( Q \) contains \( QP \), but the star of \( P \) does not contain \( QP \). We have an inconsistency.

After

One way to solve inconsistencies is to randomly perturb the positions of the points involved in an inconsistency. In the current implementation, this perturbation is done in the tangent subspace of each point. The maximum perturbation radius is given as a parameter to the constructor.

In most cases, we recommend to provide a point set where the minimum distance between any two points is not too small. This can be achieved using the functions provided by the Subsampling module. Then, a good value to start with for the maximum perturbation radius would be around half the minimum distance between any two points. The Example with perturbation below shows an example of such a process.

In most cases, this process is able to dramatically reduce the number of inconsistencies, but is not guaranteed to succeed.

Output

The result of the computation is exported as a Simplex_tree. It is the union of the stars of all the input points. A vertex in the Simplex Tree is the index of the point in the range provided by the user. The point corresponding to a vertex can also be obtained through the Tangential_complex::get_point function. Note that even if the positions of the points are perturbed, their original positions are kept (e.g. Tangential_complex::get_point returns the original position of the point).

The result can be obtained after the computation of the Tangential complex itself and/or after the perturbation process.

Simple example

This example builds the Tangential complex of point set. Note that the dimension of the kernel here is dynamic, which is slower, but more flexible: the intrinsic and ambient dimensions does not have to be known at compile-time.

#include <gudhi/Tangential_complex.h>
#include <gudhi/sparsify_point_set.h>
#include <gudhi/Simplex_tree.h>
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
#include <array>
#include <vector>
namespace tc = Gudhi::tangential_complex;
typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_d Point;
typedef Kernel::Vector_d Vector;
Kernel, CGAL::Dynamic_dimension_tag,
CGAL::Parallel_tag> TC;
int main(void) {
const int INTRINSIC_DIM = 2;
const int AMBIENT_DIM = 3;
const int NUM_POINTS = 100;
Kernel k;
// Generate points on a 2-sphere
CGAL::Random_points_on_sphere_d<Point> generator(AMBIENT_DIM, 3.);
std::vector<Point> points;
points.reserve(NUM_POINTS);
for (int i = 0; i < NUM_POINTS; ++i)
points.push_back(*generator++);
// Compute the TC
TC tc(points, INTRINSIC_DIM, k);
tc.compute_tangential_complex();
// Export the TC into a Simplex_tree
tc.create_complex(stree);
// Display stats about inconsistencies
tc.number_of_inconsistent_simplices(true); // verbose
return 0;
}
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:95
Tangential complex data structure.
Definition: Tangential_complex.h:126

Example with perturbation

This example builds the Tangential complex of a point set, then tries to solve inconsistencies by perturbing the positions of points involved in inconsistent simplices. Note that the dimension of the kernel here is static, which is the best choice when the dimensions are known at compile-time.

#include <gudhi/Tangential_complex.h>
#include <gudhi/sparsify_point_set.h>
#include <gudhi/Simplex_tree.h>
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
#include <array>
#include <vector>
namespace subsampl = Gudhi::subsampling;
namespace tc = Gudhi::tangential_complex;
typedef CGAL::Epick_d<CGAL::Dimension_tag < 3 >> Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_d Point;
typedef Kernel::Vector_d Vector;
Kernel, CGAL::Dimension_tag<2>,
CGAL::Parallel_tag> TC;
int main(void) {
const int INTRINSIC_DIM = 2;
const int AMBIENT_DIM = 3;
const int NUM_POINTS = 50;
Kernel k;
// Generate points on a 2-sphere
CGAL::Random_points_on_sphere_d<Point> generator(AMBIENT_DIM, 3.);
std::vector<Point> points;
points.reserve(NUM_POINTS);
for (int i = 0; i < NUM_POINTS; ++i)
points.push_back(*generator++);
// Sparsify the point set
std::vector<Point> sparsified_points;
subsampl::sparsify_point_set(k, points, 0.1 * 0.1,
std::back_inserter(sparsified_points));
sparsified_points.swap(points);
// Compute the TC
TC tc(points, INTRINSIC_DIM, k);
tc.compute_tangential_complex();
// Try to fix inconsistencies. Give it 10 seconds to succeed
tc.fix_inconsistencies_using_perturbation(0.05, 10);
// Export the TC into a Simplex_tree
tc.create_complex(stree);
return 0;
}
void sparsify_point_set(const Kernel &k, Point_range const &input_pts, typename Kernel::FT min_squared_dist, OutputIterator output_it)
Outputs a subset of the input points so that the squared distance between any two points is greater t...
Definition: sparsify_point_set.h:50