From af146a2e48c16855355ac599cbc617250727d244 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 25 Nov 2016 16:00:19 +0000 Subject: Add of tangential complex doc Separate simplex tree from alpha complex git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST_cythonize@1788 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 1cf4a35e0a099501eb1cb6b9809041dd1a1e2617 --- src/cython/doc/tangential_complex_user.rst | 144 +++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 src/cython/doc/tangential_complex_user.rst (limited to 'src/cython/doc/tangential_complex_user.rst') diff --git a/src/cython/doc/tangential_complex_user.rst b/src/cython/doc/tangential_complex_user.rst new file mode 100644 index 00000000..588de08c --- /dev/null +++ b/src/cython/doc/tangential_complex_user.rst @@ -0,0 +1,144 @@ +============================== +Tangential complex user manual +============================== +.. include:: tangential_complex_sum.rst + +Definition +---------- + +A Tangential Delaunay complex is a simplicial complex designed to reconstruct a +:math:`k`-dimensional smooth manifold embedded in :math:`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 +:math:`d` and exponentially on the intrinsic dimension :math:`k`. + +An extensive description of the Tangential complex can be found in +:cite:`tangentialcomplex2014`). + +What is a Tangential Complex? +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Let us start with the description of the Tangential complex of a simple +example, with :math:`k = 1` and :math:`d = 2`. The input data is 4 points +:math:`P` located on a curve embedded in 2D. + +.. figure:: img/tc_example_01.png + :alt: The input + :figclass: align-center + The input + +For each point :math:`p`, estimate its tangent subspace :math:`T_p` (e.g. +using PCA). + +.. figure:: img/tc_example_02.png + :alt: The estimated normals + :figclass: align-center + The estimated normals + +Let us add the Voronoi diagram of the points in orange. For each point +:math:`p`, construct its star in the Delaunay triangulation of :math:`P` +restricted to :math:`T_p`. + +.. figure:: img/tc_example_03.png + :alt: The Voronoi diagram + :figclass: align-center + 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 :math:`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 :cite:`tangentialcomplex2014`. + +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. + +.. figure:: img/tc_example_07_before.png + :alt: Before + :figclass: align-center + Before + +Let us slightly move the tangent subspace :math:`T_q` + +.. figure:: img/tc_example_07_after.png + :alt: After + :figclass: align-center + After + +Now, the star of :math:`Q` contains :math:`QP`, but the star of :math:`P` does +not contain :math:`QP`. We have an inconsistency. + +.. figure:: img/tc_example_08.png + :alt: After + :figclass: align-center + 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. + +testcode:: + + import gudhi + tc = gudhi.TangentialComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]]) + +The output is: + +testoutput:: + + Tangential complex is of dimension 2 - 25 simplices - 7 vertices. + + +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. + +testcode:: + + import gudhi + tc = gudhi.TangentialComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]]) + +The output is: + +testoutput:: -- cgit v1.2.3