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

5 files changed, 194 insertions, 20 deletions

diff --git a/src/cython/doc/alpha_complex_user.rst b/src/cython/doc/alpha_complex_user.rst
index b6b6e550..5ad3a9e7 100644
--- a/src/cython/doc/alpha_complex_user.rst
+++ b/src/cython/doc/alpha_complex_user.rst
@@ -22,15 +22,17 @@ This example builds the Delaunay triangulation from the given points, and initia
 
 .. testcode::
 
-   import gudhi
-   alpha_complex = gudhi.AlphaComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]],
-                                      max_alpha_square=60.0)
-   result_str = 'Alpha complex is of dimension ' + repr(alpha_complex.dimension()) + ' - ' + \
-       repr(alpha_complex.num_simplices()) + ' simplices - ' + \
-       repr(alpha_complex.num_vertices()) + ' vertices.'
-   print(result_str)
-   for fitered_value in alpha_complex.get_filtered_tree():
-       print(fitered_value)
+    import gudhi
+    alpha_complex = gudhi.AlphaComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]])
+
+    simplex_tree = gudhi.SimplexTree()
+    alpha_complex.create_simplex_tree(simplex_tree, max_alpha_square=60.0)
+    result_str = 'Alpha complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \
+        repr(simplex_tree.num_simplices()) + ' simplices - ' + \
+        repr(simplex_tree.num_vertices()) + ' vertices.'
+    print(result_str)
+    for fitered_value in simplex_tree.get_filtered_tree():
+        print(fitered_value)
 
 The output is:
 
@@ -152,15 +154,16 @@ Then, it is asked to display information about the alpha complex:
 
 .. testcode::
 
-   import gudhi
-   alpha_complex = gudhi.AlphaComplex(off_file='alphacomplexdoc.off',
-                                      max_alpha_square=59.0)
-   result_str = 'Alpha complex is of dimension ' + repr(alpha_complex.dimension()) + ' - ' + \
-       repr(alpha_complex.num_simplices()) + ' simplices - ' + \
-       repr(alpha_complex.num_vertices()) + ' vertices.'
-   print(result_str)
-   for fitered_value in alpha_complex.get_filtered_tree():
-       print(fitered_value)
+    import gudhi
+    alpha_complex = gudhi.AlphaComplex(off_file='alphacomplexdoc.off')
+    simplex_tree = gudhi.SimplexTree()
+    alpha_complex.create_simplex_tree(simplex_tree, max_alpha_square=59.0)
+    result_str = 'Alpha complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \
+        repr(simplex_tree.num_simplices()) + ' simplices - ' + \
+        repr(simplex_tree.num_vertices()) + ' vertices.'
+    print(result_str)
+    for fitered_value in simplex_tree.get_filtered_tree():
+        print(fitered_value)
 
 the program output is:
 
diff --git a/src/cython/doc/persistence_graphical_tools_user.rst b/src/cython/doc/persistence_graphical_tools_user.rst
index 0cb61cf1..b23ad5e6 100644
--- a/src/cython/doc/persistence_graphical_tools_user.rst
+++ b/src/cython/doc/persistence_graphical_tools_user.rst
@@ -41,6 +41,7 @@ This function can display the persistence result as a diagram:
     import gudhi
     
     alpha_complex = gudhi.AlphaComplex(off_file='tore3D_300.off')
-    alpha_complex.initialize_filtration()
-    diag = alpha_complex.persistence()
+    simplex_tree = gudhi.SimplexTree()
+    alpha_complex.create_simplex_tree(simplex_tree)
+    diag = simplex_tree.persistence()
     gudhi.diagram_persistence(diag)
diff --git a/src/cython/doc/tangential_complex_ref.rst b/src/cython/doc/tangential_complex_ref.rst
new file mode 100644
index 00000000..35589475
--- /dev/null
+++ b/src/cython/doc/tangential_complex_ref.rst
@@ -0,0 +1,10 @@
+===================================
+Tangential complex reference manual
+===================================
+
+.. autoclass:: gudhi.TangentialComplex
+   :members:
+   :undoc-members:
+   :show-inheritance:
+
+   .. automethod:: gudhi.TangentialComplex.__init__
diff --git a/src/cython/doc/tangential_complex_sum.rst b/src/cython/doc/tangential_complex_sum.rst
new file mode 100644
index 00000000..a2c0be0e
--- /dev/null
+++ b/src/cython/doc/tangential_complex_sum.rst
@@ -0,0 +1,16 @@
+=====================================  =====================================  =====================================
+:Author: Clément Jamin                 :Introduced in: GUDHI 1.4.0            :Copyright: GPL v3
+=====================================  =====================================  =====================================
+:Requires: CGAL ≥ 4.8.0             Eigen3
+=====================================  =====================================  =====================================
+
++-------------------------------------------+----------------------------------------------------------------------+
+| .. image::                                | A Tangential Delaunay complex is a simplicial complex designed to    |
+|      img/tc_examples.png                  | reconstruct a :math:`k`-dimensional manifold embedded in :math:`d`-  |
+|                                           | dimensional Euclidean space. The input is a point sample coming from |
+|                                           | an unknown manifold. The running time depends only linearly on the   |
+|                                           | extrinsic dimension :math:`d` and exponentially on the intrinsic     |
+|                                           | dimension :math:`k`.                                                 |
++-------------------------------------------+----------------------------------------------------------------------+
+| :doc:`tangential_complex_user`            | :doc:`tangential_complex_ref`                                             |
++-------------------------------------------+----------------------------------------------------------------------+
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::