From 01b0bf84f780b9998a48f0dbe338319da1c6d6f2 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 23 Jun 2015 13:50:46 +0000 Subject: Alpha complex documentation - 2nd part git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@633 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 023b5aaa57593a4e8e77cf12f388559b638f0eb1 --- src/Alpha_complex/doc/alpha_complex_doc.ipe | 438 ++++++++++++++++++ src/Alpha_complex/doc/alpha_complex_doc.png | Bin 0 -> 46226 bytes src/Alpha_complex/doc/alpha_complex_doc_135.ipe | 514 +++++++++++++++++++++ src/Alpha_complex/doc/alpha_complex_doc_135.png | Bin 0 -> 94098 bytes .../doc/alpha_complex_doc_alpha_shape.ipe | 493 ++++++++++++++++++++ .../doc/alpha_complex_doc_alpha_shape.png | Bin 0 -> 70425 bytes src/Alpha_complex/include/gudhi/Alpha_complex.h | 90 +++- src/Doxyfile | 3 +- 8 files changed, 1521 insertions(+), 17 deletions(-) create mode 100644 src/Alpha_complex/doc/alpha_complex_doc.ipe create mode 100644 src/Alpha_complex/doc/alpha_complex_doc.png create mode 100644 src/Alpha_complex/doc/alpha_complex_doc_135.ipe create mode 100644 src/Alpha_complex/doc/alpha_complex_doc_135.png create mode 100644 src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.ipe create mode 100644 src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png (limited to 'src') diff --git a/src/Alpha_complex/doc/alpha_complex_doc.ipe b/src/Alpha_complex/doc/alpha_complex_doc.ipe new file mode 100644 index 00000000..6257b2f4 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc.ipe @@ -0,0 +1,438 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l + + +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l + + +320 580 m +370 580 l +350 520 l +320 580 l + +Delaunay triangulation +1 +2 +3 +4 +5 +6 +7 + +280 660 m +300 710 l +370 690 l +280 660 l + + +320 580 m +370 690 l +370 580 l +320 580 l + + +280 660 m +370 690 l +320 580 l +280 660 l + +1 +2 +3 +3 +2 +3 +3 +4 +4 +4 +4 +5 +5 +5 +5 +7 +7 +7 +7 +7 +7 +6 +7 +6 + +4 0 0 4 320 704 e + + +322.919 706.788 m +317.189 701.058 l +317.189 701.203 l + + +317.551 706.934 m +322.629 701.058 l + + +230 680 m +240 670 l + + +230 680 m +240 670 l + + +230 680 m +240 670 l + + +230 680 m +240 670 l + + +230 680 m +220 670 l + + +230 680 m +230 670 l + + +220 660 m +220 650 l + + +230 660 m +230 650 l + + +260 680 m +260 670 l + + +260 660 m +260 650 l + + +300 680 m +300 670 l + + +300 680 m +290 670 l + + +290 660 m +290 650 l + + +300 660 m +300 650 l + + +330 680 m +330 670 l + + +350 680 m +350 670 l + + +350 660 m +350 650 l + + +320 700 m +240 690 l + + +320 700 m +270 690 l + + +320 700 m +310 690 l + + +320 700 m +330 690 l + + +320 700 m +350 690 l + + +320 700 m +380 690 l + + +320 700 m +400 690 l + + +240 620 m +220 600 l + + +240 620 m +220 640 l + +Simplex tree structure + +280 630 m +170 630 l + + +280 610 m +170 610 l + + + diff --git a/src/Alpha_complex/doc/alpha_complex_doc.png b/src/Alpha_complex/doc/alpha_complex_doc.png new file mode 100644 index 00000000..ff51ea9a Binary files /dev/null and b/src/Alpha_complex/doc/alpha_complex_doc.png differ diff --git a/src/Alpha_complex/doc/alpha_complex_doc_135.ipe b/src/Alpha_complex/doc/alpha_complex_doc_135.ipe new file mode 100644 index 00000000..df55639a --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc_135.ipe @@ -0,0 +1,514 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l + + +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l + + +320 580 m +370 580 l +350 520 l +320 580 l + +Cell [5,3,1] +1 +2 +3 +4 +5 +6 +7 + +280 660 m +300 710 l +370 690 l +280 660 l + + +320 580 m +370 690 l +370 580 l +320 580 l + + +280 660 m +370 690 l +320 580 l +280 660 l + + +77.2727 0 0 77.2727 243.636 591.818 e + + + +243.428 591.569 m +186.061 643.28 l + +$\alpha_{531}$ + + + + + + + + +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l + + +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l + + +320 580 m +370 580 l +350 520 l +320 580 l + +[3,1] is Gabriel $\rightarrow$ $\alpha_{31}$ is not$\\$ +modified (NaN) + +1 +2 +3 +4 +5 +6 +7 + +280 660 m +300 710 l +370 690 l +280 660 l + + +320 580 m +370 690 l +370 580 l +320 580 l + + +280 660 m +370 690 l +320 580 l +280 660 l + +$\alpha_{31}$ + +290 530 m +320 580 l + + +29.1548 0 0 29.1548 305 555 e + + + +304.883 555.015 m +334.509 555.015 l + + + + + + + + + +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l + + +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l + + +320 580 m +370 580 l +350 520 l +320 580 l + +[1,5] is not Gabriel $\rightarrow$ $\alpha_{15} = \alpha_{135}$ +1 +2 +3 +4 +5 +6 +7 + +280 660 m +300 710 l +370 690 l +280 660 l + + +320 580 m +370 690 l +370 580 l +320 580 l + + +280 660 m +370 690 l +320 580 l +280 660 l + +$\alpha_{15}$ + +290 530 m +280 660 l + + +65.192 0 0 65.192 285 595 e + + + + + + + + + +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l + + +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l + + +320 580 m +370 580 l +350 520 l +320 580 l + +1 +2 +3 +4 +6 +7 + +280 660 m +300 710 l +370 690 l +280 660 l + + +320 580 m +370 690 l +370 580 l +320 580 l + + +280 660 m +370 690 l +320 580 l +280 660 l + +$\alpha_{35}$ +5 + +406.093 497.775 m +446.094 418.092 l + + +44.5799 0 0 44.5799 425.934 457.774 e + + + +425.854 457.774 m +470.795 457.774 l + +[3,5] is Gabriel $\rightarrow$ $\alpha_{35}$ is not modified (NaN) + + +205.028 596.091 m +110.946 544.02 l + + +280.768 588.99 m +280.768 547.57 l + + +341.123 594.316 m +413.904 554.079 l + +For all faces of [5,3,1] +N.B. : is Gabriel on a single point has no sense. +Dimension =2 - $\sigma$ = [5,3,1] + + +247.333 430.892 m +311.764 430.892 l + + + diff --git a/src/Alpha_complex/doc/alpha_complex_doc_135.png b/src/Alpha_complex/doc/alpha_complex_doc_135.png new file mode 100644 index 00000000..edf61368 Binary files /dev/null and b/src/Alpha_complex/doc/alpha_complex_doc_135.png differ diff --git a/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.ipe b/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.ipe new file mode 100644 index 00000000..192ea772 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.ipe @@ -0,0 +1,493 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Alpha shape +1 +2 +3 +4 +5 +6 +7 +1 +2 +3 +3 +2 +3 +3 +4 +4 +4 +4 +5 +5 +5 +5 +7 +7 +7 +7 +7 +7 +6 +7 +6 + +4 0 0 4 320 704 e + + +322.919 706.788 m +317.189 701.058 l +317.189 701.203 l + + +317.551 706.934 m +322.629 701.058 l + + +230 680 m +240 670 l + + +230 680 m +240 670 l + + +230 680 m +240 670 l + + +230 680 m +240 670 l + + +230 680 m +220 670 l + + +230 680 m +230 670 l + + +220 660 m +220 650 l + + +230 660 m +230 650 l + + +260 680 m +260 670 l + + +260 660 m +260 650 l + + +300 680 m +300 670 l + + +300 680 m +290 670 l + + +290 660 m +290 650 l + + +300 660 m +300 650 l + + +330 680 m +330 670 l + + +350 680 m +350 670 l + + +350 660 m +350 650 l + + +320 700 m +240 690 l + + +320 700 m +270 690 l + + +320 700 m +310 690 l + + +320 700 m +330 690 l + + +320 700 m +350 690 l + + +320 700 m +380 690 l + + +320 700 m +400 690 l + +Alpha complex structure + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +58.1341 0 0 58.1341 218.925 692.601 e + + +60 710 m +40 660 l + + +40 660 m +130 690 l + + +130 690 m +60 710 l + + +40 660 m +80 580 l + + +80 580 m +130 580 l +130 580 l + + +130 580 m +110 520 l + + +110 520 m +50 530 l +50 530 l +50 530 l + + +50 530 m +80 580 l + + +80 580 m +110 520 l +110 520 l + + +130 580 m +130 690 l + + + +108.275 743.531 m +166.45 743.531 l + +$\alpha$ +filtration value $> \alpha$ are greyed + +280 660 m +300 680 l + + +280 660 m +300 640 l + + +370 660 m +350 680 l + + +370 660 m +350 640 l + + +290 670 m +360 670 l + + +290 650 m +360 650 l + +equivalent + + diff --git a/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png b/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png new file mode 100644 index 00000000..516de126 Binary files /dev/null and b/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png differ diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 44741e3b..191ff853 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -51,47 +51,105 @@ namespace alphacomplex { #define Kinit(f) =k.f() -/** \defgroup alpha_complex Alpha complex in dimension N - * @{ +/** \tableofcontents + * \defgroup alpha_complex Alpha complex + * * \author Vincent Rouvreau - * - * \section Definition * - * Alpha_complex is a Simplex_tree constructed from each finite cell of a Delaunay Triangulation in dimension N. + * @{ + * + * \section definition Definition + * + * Alpha_complex is a Simplex_tree constructed from each finite cell of a Delaunay Triangulation. * * The filtration value of each simplex is computed from the alpha value of the simplex if it is Gabriel or * from the alpha value of the simplex coface that makes the simplex not Gabriel. * - * Please refer to \cite AlphaShapesDefinition for the alpha complex definition or to - * \cite AlphaShapesIntroduction for alpha complex concept vulgarization. + * Please refer to \cite AlphaShapesDefinition for a more complete alpha complex definition. * - * \section Example + * Alpha complex are interesting because it looks like an \ref alpha-shape "Alpha shape" as described in + * \cite AlphaShapesIntroduction (an alpha complex concept vulgarization). + * + * \section example Example + * + * This example loads points from an OFF file, builds the Delaunay triangulation from the points, and finally + * initialize the alpha complex with it. * - * This example loads points from an OFF file, builds the Delaunay triangulation, and finally initialize the - * alpha complex with it. * Then, it is asked to display information about the alpha complex. * * \include Alpha_complex_from_off.cpp * * When launching: * - * \code $> ./alphaoffreader ../../data/points/alphashapedoc.off + * \code $> ./alphaoffreader ../../data/points/alphacomplexdoc.off * \endcode * * the program output is: * * \include alphaoffreader_for_doc.txt + * + * \section algorithm Algorithm + * + * Data structure + * + * In order to build the alpha complex, first, a Simplex tree is build from the cells of a Delaunay Triangulation. + * (The filtration value is set to NaN, which stands for unknown value): + * \image html "alpha_complex_doc.png" "Simplex tree structure construction example" + * + * Filtration value computation algorithm + * + * \f{algorithm}{ + * \caption{Filtration value computation algorithm}\label{alpha} + * \begin{algorithmic} + * \For{i : dimension $\rightarrow$ 1} + * \ForAll{$\sigma$ of dimension i} + * \If {filtration($\sigma$) is NaN} + * \State filtration($\sigma$) = $\alpha(\sigma)$ + * \EndIf + * \ForAll{$\tau$ face of $\sigma$} \Comment{propagate alpha filtration value} + * \If {filtration($\tau$) is not NaN} + * \State filtration($\tau$) = min (filtration($\tau$), filtration($\sigma$)) + * \Else + * \If {$\tau$ is not Gabriel for $\sigma$} + * \State filtration($\tau$) = filtration($\sigma$) + * \EndIf + * \EndIf + * \EndFor + * \EndFor + * \EndFor + * \end{algorithmic} + * \f} + * + * From the example above, it means the algorithm will look into each triangulation ([1,2,3], [2,3,4], [1,3,5], ...), + * will compute the filtration value of the triangulation, and then will propagate the filtration value as described + * here : + * \image html "alpha_complex_doc_135.png" "Filtration value propagation example" + * Then, the algorithm will look into each edge ([1,2], [2,3], [1,3], ...), + * will compute the filtration value of the edge (in this case, propagation will have no effect). + * + * Finally, the algorithm will look into each vertex ([1], [2], [3], [4], [5], [6] and [7]), + * will set the filtration value (0 in case of a vertex - propagation will have no effect). + * + * \section alpha-shape Alpha shape + * + * In the example above, the alpha shape of \f$\alpha_{74} < \alpha < \alpha_{73}\f$ is the alpha complex where the + * \f$\alpha_{74} <\f$ filtration value \f$< \alpha_{73}\f$ as described in \cite AlphaShapesIntroduction + * + * \image html "alpha_complex_doc_alpha_shape.png" "Alpha shape example" + * \copyright GNU General Public License v3. + * \verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim */ /** @} */ // end defgroup alpha_complex /** * \brief Alpha complex data structure. * - * \details Every simplex \f$[v_0, \cdots ,v_d]\f$ admits a canonical orientation - * induced by the order relation on vertices \f$ v_0 < \cdots < v_d \f$. - * - * Details may be found in \cite boissonnatmariasimplextreealgorithmica. - * + * \details + * The data structure can be constructed from a CGAL Delaunay triangulation (for more informations on CGAL Delaunay + * triangulation, please refer to the corresponding chapter in page http://doc.cgal.org/latest/Triangulation/) or from + * an OFF file (cf. Delaunay_triangulation_off_reader). + * + * Please refer to \ref alpha_complex for examples. * */ template