From 16aaf4cda5fd97da12a7f1da8b0a5168fac2e289 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 11 Oct 2016 13:57:03 +0000 Subject: Problem of merge with tangentialcomplex branch. Redo in an integration branch git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/tangential_integration@1701 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: fa029e8e90b3e203ea675f02098ec6fe95596f9f --- .../doc/Intro_tangential_complex.h | 119 +++++++++++++++++++++ src/Tangential_complex/doc/tc_example_01.png | Bin 0 -> 20323 bytes src/Tangential_complex/doc/tc_example_02.png | Bin 0 -> 36017 bytes src/Tangential_complex/doc/tc_example_03.png | Bin 0 -> 62990 bytes src/Tangential_complex/doc/tc_example_05.png | Bin 0 -> 36032 bytes src/Tangential_complex/doc/tc_example_06.png | Bin 0 -> 37195 bytes src/Tangential_complex/doc/tc_example_07.png | Bin 0 -> 49399 bytes src/Tangential_complex/doc/tc_example_07_after.png | Bin 0 -> 50132 bytes .../doc/tc_example_07_before.png | Bin 0 -> 48898 bytes src/Tangential_complex/doc/tc_example_08.png | Bin 0 -> 63636 bytes src/Tangential_complex/doc/tc_example_09.png | Bin 0 -> 35453 bytes src/Tangential_complex/doc/tc_examples.png | Bin 0 -> 150776 bytes 12 files changed, 119 insertions(+) create mode 100644 src/Tangential_complex/doc/Intro_tangential_complex.h create mode 100644 src/Tangential_complex/doc/tc_example_01.png create mode 100644 src/Tangential_complex/doc/tc_example_02.png create mode 100644 src/Tangential_complex/doc/tc_example_03.png create mode 100644 src/Tangential_complex/doc/tc_example_05.png create mode 100644 src/Tangential_complex/doc/tc_example_06.png create mode 100644 src/Tangential_complex/doc/tc_example_07.png create mode 100644 src/Tangential_complex/doc/tc_example_07_after.png create mode 100644 src/Tangential_complex/doc/tc_example_07_before.png create mode 100644 src/Tangential_complex/doc/tc_example_08.png create mode 100644 src/Tangential_complex/doc/tc_example_09.png create mode 100644 src/Tangential_complex/doc/tc_examples.png (limited to 'src/Tangential_complex/doc') diff --git a/src/Tangential_complex/doc/Intro_tangential_complex.h b/src/Tangential_complex/doc/Intro_tangential_complex.h new file mode 100644 index 00000000..3d687c1d --- /dev/null +++ b/src/Tangential_complex/doc/Intro_tangential_complex.h @@ -0,0 +1,119 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Clement Jamin + * + * Copyright (C) 2016 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef DOC_TANGENTIAL_COMPLEX_INTRO_TANGENTIAL_COMPLEX_H_ +#define DOC_TANGENTIAL_COMPLEX_INTRO_TANGENTIAL_COMPLEX_H_ + +// needs namespaces for Doxygen to link on classes +namespace Gudhi { +namespace tangential_complex { + +/** \defgroup tangential_complex Tangential complex + +\author Clément Jamin + +@{ + +\section tangentialdefinition Definition + +A Tangential Delaunay complex is a simplicial complex +designed to reconstruct a \f$k\f$-dimensional smooth manifold embedded in \f$d\f$-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 \f$ d \f$ +and exponentially on the intrinsic dimension \f$ k \f$. + +An extensive description of the Tangential complex can be found in \cite tangentialcomplex2014. + +\subsection whatisthetc What is a Tangential Complex? + +Let us start with the description of the Tangential complex of a simple example, with \f$ k=1 \f$ and \f$ d=2 \f$. +The input data is 4 points \f$ P \f$ located on a curve embedded in 2D. +\image html "tc_example_01.png" "The input" +For each point \f$ p \f$, estimate its tangent subspace \f$ T_p \f$ (e.g. using PCA). +\image html "tc_example_02.png" "The estimated normals" +Let us add the Voronoi diagram of the points in orange. For each point \f$ p \f$, construct its star in the Delaunay triangulation of \f$ P \f$ restricted to \f$ T_p \f$. +\image html "tc_example_03.png" "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 \f$ k \f$-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. + +\subsection inconsistencies 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. +\image html "tc_example_07_before.png" "Before" +Let us slightly move the tangent subspace \f$ T_q \f$ +\image html "tc_example_07_after.png" "After" +Now, the star of \f$ Q \f$ contains \f$ QP \f$, but the star of \f$ P \f$ does not contain \f$ QP \f$. We have an inconsistency. +\image html "tc_example_08.png" "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 \ref example_with_perturb 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. + +\subsection output 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. + +\section simple_example 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 Tangential_complex/example_basic.cpp + +\section example_with_perturb 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 Tangential_complex/example_with_perturb.cpp + +\copyright GNU General Public License v3. +\verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim + */ +/** @} */ // end defgroup tangential_complex + +} // namespace tangential_complex + +} // namespace Gudhi + +#endif // DOC_TANGENTIAL_COMPLEX_INTRO_TANGENTIAL_COMPLEX_H_ diff --git a/src/Tangential_complex/doc/tc_example_01.png b/src/Tangential_complex/doc/tc_example_01.png new file mode 100644 index 00000000..8afe6198 Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_01.png differ diff --git a/src/Tangential_complex/doc/tc_example_02.png b/src/Tangential_complex/doc/tc_example_02.png new file mode 100644 index 00000000..01591c1d Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_02.png differ diff --git a/src/Tangential_complex/doc/tc_example_03.png b/src/Tangential_complex/doc/tc_example_03.png new file mode 100644 index 00000000..5de04e01 Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_03.png differ diff --git a/src/Tangential_complex/doc/tc_example_05.png b/src/Tangential_complex/doc/tc_example_05.png new file mode 100644 index 00000000..fdd5e5fa Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_05.png differ diff --git a/src/Tangential_complex/doc/tc_example_06.png b/src/Tangential_complex/doc/tc_example_06.png new file mode 100644 index 00000000..31ad3c43 Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_06.png differ diff --git a/src/Tangential_complex/doc/tc_example_07.png b/src/Tangential_complex/doc/tc_example_07.png new file mode 100644 index 00000000..47e34de7 Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_07.png differ diff --git a/src/Tangential_complex/doc/tc_example_07_after.png b/src/Tangential_complex/doc/tc_example_07_after.png new file mode 100644 index 00000000..981350d2 Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_07_after.png differ diff --git a/src/Tangential_complex/doc/tc_example_07_before.png b/src/Tangential_complex/doc/tc_example_07_before.png new file mode 100644 index 00000000..ddc6bc7b Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_07_before.png differ diff --git a/src/Tangential_complex/doc/tc_example_08.png b/src/Tangential_complex/doc/tc_example_08.png new file mode 100644 index 00000000..119a87de Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_08.png differ diff --git a/src/Tangential_complex/doc/tc_example_09.png b/src/Tangential_complex/doc/tc_example_09.png new file mode 100644 index 00000000..31bac1e0 Binary files /dev/null and b/src/Tangential_complex/doc/tc_example_09.png differ diff --git a/src/Tangential_complex/doc/tc_examples.png b/src/Tangential_complex/doc/tc_examples.png new file mode 100644 index 00000000..b6544afe Binary files /dev/null and b/src/Tangential_complex/doc/tc_examples.png differ -- cgit v1.2.3