diff options
Diffstat (limited to 'src')
36 files changed, 3002 insertions, 997 deletions
diff --git a/src/Alpha_complex/doc/Intro_alpha_complex.h b/src/Alpha_complex/doc/Intro_alpha_complex.h new file mode 100644 index 00000000..34af2b98 --- /dev/null +++ b/src/Alpha_complex/doc/Intro_alpha_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): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * 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 <http://www.gnu.org/licenses/>. + */ + +// needs namespace for Doxygen to link on classes +namespace Gudhi { +// needs namespace for Doxygen to link on classes +namespace alphacomplex { + +/** \defgroup alpha_complex Alpha complex + * + * \author Vincent Rouvreau + * + * @{ + * + * \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 a more complete alpha complex definition. + * + * 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. + * + * Then, it is asked to display information about the alpha complex. + * + * \include Alpha_complex_from_off.cpp + * + * When launching: + * + * \code $> ./alphaoffreader ../../data/points/alphacomplexdoc.off + * \endcode + * + * the program output is: + * + * \include alphaoffreader_for_doc.txt + * + * \section algorithm Algorithm + * + * <b>Data structure</b> + * + * 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" + * + * <b>Filtration value computation algorithm</b> + * + * \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 + +} // namespace alphacomplex + +} // namespace Gudhi 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 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70005" creator="Ipe 7.1.4"> +<info created="D:20150603143945" modified="D:20150622134959"/> +<ipestyle name="basic"> +<symbol name="arrow/arc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/farc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="mark/circle(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</symbol> +<symbol name="mark/disk(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +</path> +</symbol> +<symbol name="mark/fdisk(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +0.5 0 0 0.5 0 0 e +</path> +<path fill="sym-stroke" fillrule="eofill"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</group> +</symbol> +<symbol name="mark/box(sx)" transformations="translations"> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</symbol> +<symbol name="mark/square(sx)" transformations="translations"> +<path fill="sym-stroke"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +</path> +</symbol> +<symbol name="mark/fsquare(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h +</path> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</group> +</symbol> +<symbol name="mark/cross(sx)" transformations="translations"> +<group> +<path fill="sym-stroke"> +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h +</path> +<path fill="sym-stroke"> +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h +</path> +</group> +</symbol> +<symbol name="arrow/fnormal(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/pointed(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fpointed(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/linear(spx)"> +<path stroke="sym-stroke" pen="sym-pen"> +-1 0.333 m +0 0 l +-1 -0.333 l +</path> +</symbol> +<symbol name="arrow/fdouble(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/double(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<pen name="heavier" value="0.8"/> +<pen name="fat" value="1.2"/> +<pen name="ultrafat" value="2"/> +<symbolsize name="large" value="5"/> +<symbolsize name="small" value="2"/> +<symbolsize name="tiny" value="1.1"/> +<arrowsize name="large" value="10"/> +<arrowsize name="small" value="5"/> +<arrowsize name="tiny" value="3"/> +<color name="red" value="1 0 0"/> +<color name="green" value="0 1 0"/> +<color name="blue" value="0 0 1"/> +<color name="yellow" value="1 1 0"/> +<color name="orange" value="1 0.647 0"/> +<color name="gold" value="1 0.843 0"/> +<color name="purple" value="0.627 0.125 0.941"/> +<color name="gray" value="0.745"/> +<color name="brown" value="0.647 0.165 0.165"/> +<color name="navy" value="0 0 0.502"/> +<color name="pink" value="1 0.753 0.796"/> +<color name="seagreen" value="0.18 0.545 0.341"/> +<color name="turquoise" value="0.251 0.878 0.816"/> +<color name="violet" value="0.933 0.51 0.933"/> +<color name="darkblue" value="0 0 0.545"/> +<color name="darkcyan" value="0 0.545 0.545"/> +<color name="darkgray" value="0.663"/> +<color name="darkgreen" value="0 0.392 0"/> +<color name="darkmagenta" value="0.545 0 0.545"/> +<color name="darkorange" value="1 0.549 0"/> +<color name="darkred" value="0.545 0 0"/> +<color name="lightblue" value="0.678 0.847 0.902"/> +<color name="lightcyan" value="0.878 1 1"/> +<color name="lightgray" value="0.827"/> +<color name="lightgreen" value="0.565 0.933 0.565"/> +<color name="lightyellow" value="1 1 0.878"/> +<dashstyle name="dashed" value="[4] 0"/> +<dashstyle name="dotted" value="[1 3] 0"/> +<dashstyle name="dash dotted" value="[4 2 1 2] 0"/> +<dashstyle name="dash dot dotted" value="[4 2 1 2 1 2] 0"/> +<textsize name="large" value="\large"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="small" value="\small"/> +<textsize name="footnote" value="\footnotesize"/> +<textsize name="tiny" value="\tiny"/> +<textstyle name="center" begin="\begin{center}" end="\end{center}"/> +<textstyle name="itemize" begin="\begin{itemize}" end="\end{itemize}"/> +<textstyle name="item" begin="\begin{itemize}\item{}" end="\end{itemize}"/> +<gridsize name="4 pts" value="4"/> +<gridsize name="8 pts (~3 mm)" value="8"/> +<gridsize name="16 pts (~6 mm)" value="16"/> +<gridsize name="32 pts (~12 mm)" value="32"/> +<gridsize name="10 pts (~3.5 mm)" value="10"/> +<gridsize name="20 pts (~7 mm)" value="20"/> +<gridsize name="14 pts (~5 mm)" value="14"/> +<gridsize name="28 pts (~10 mm)" value="28"/> +<gridsize name="56 pts (~20 mm)" value="56"/> +<anglesize name="90 deg" value="90"/> +<anglesize name="60 deg" value="60"/> +<anglesize name="45 deg" value="45"/> +<anglesize name="30 deg" value="30"/> +<anglesize name="22.5 deg" value="22.5"/> +<tiling name="falling" angle="-60" step="4" width="1"/> +<tiling name="rising" angle="30" step="4" width="1"/> +</ipestyle> +<page> +<layer name="alpha"/> +<view layers="alpha" active="alpha"/> +<use layer="alpha" matrix="1 0 0 1 -240 0" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -239.3 -10.1537" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -240 0" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -240 0" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -240 0" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -240 0" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -240 0" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<path matrix="1 0 0 1 -240 0" stroke="darkcyan"> +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -240 0" stroke="darkcyan"> +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -240 0" stroke="darkcyan"> +320 580 m +370 580 l +350 520 l +320 580 l +</path> +<text matrix="1 0 0 1 -260 0" transformations="translations" pos="380 530" stroke="darkcyan" type="label" width="118.196" height="8.307" depth="2.32" valign="baseline" size="large">Delaunay triangulation</text> +<text matrix="1 0 0 1 -242.155 -3.50128" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 -240 0" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -240 0" transformations="translations" pos="310.693 578.759" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -240 0" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -240 0" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -239.3 -10.1537" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 -240 0" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<path matrix="1 0 0 1 -240 0" stroke="darkcyan"> +280 660 m +300 710 l +370 690 l +280 660 l +</path> +<path matrix="1 0 0 1 -240 0" stroke="darkcyan"> +320 580 m +370 690 l +370 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -240 0" stroke="darkcyan"> +280 660 m +370 690 l +320 580 l +280 660 l +</path> +<text matrix="1 0 0 1 -40 -40" transformations="translations" pos="360 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="360 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="360 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="370 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -30 -40" transformations="translations" pos="380 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -30 -40" transformations="translations" pos="380 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -10 -40" transformations="translations" pos="400 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -40 -40" transformations="translations" pos="390 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -40 -40" transformations="translations" pos="400 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -30 -40" transformations="translations" pos="410 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -10 -40" transformations="translations" pos="430 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="370 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="380 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -40 -40" transformations="translations" pos="430 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -20 -40" transformations="translations" pos="460 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="430 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 -50 -40" transformations="translations" pos="450 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 -40 -40" transformations="translations" pos="460 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 -30 -40" transformations="translations" pos="520 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 90 -40" transformations="translations" pos="300 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 100 -40" transformations="translations" pos="350 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 90 -40" transformations="translations" pos="350 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 90 -40" transformations="translations" pos="350 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 90 -40" transformations="translations" pos="380 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 90 -40" stroke="black"> +4 0 0 4 320 704 e +</path> +<path matrix="1 0 0 1 90 -40" stroke="black"> +322.919 706.788 m +317.189 701.058 l +317.189 701.203 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black"> +317.551 706.934 m +322.629 701.058 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 120 -40" stroke="black" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 160 -40" stroke="black" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 210 -40" stroke="black" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +230 680 m +220 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +230 680 m +230 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +220 660 m +220 650 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +230 660 m +230 650 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +260 680 m +260 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +260 660 m +260 650 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +300 680 m +300 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +300 680 m +290 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +290 660 m +290 650 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +300 660 m +300 650 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +330 680 m +330 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +350 680 m +350 670 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +350 660 m +350 650 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +240 690 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +270 690 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +310 690 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +330 690 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +350 690 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +380 690 l +</path> +<path matrix="1 0 0 1 90 -40" stroke="black" arrow="normal/tiny"> +320 700 m +400 690 l +</path> +<path matrix="1 0 0 1 50 0" stroke="black"> +240 620 m +220 600 l +</path> +<path matrix="1 0 0 1 50 0" stroke="black"> +240 620 m +220 640 l +</path> +<text transformations="translations" pos="180 620" stroke="black" type="label" width="97.274" height="6.926" depth="1.93" valign="baseline">Simplex tree structure</text> +<path stroke="black"> +280 630 m +170 630 l +</path> +<path stroke="black"> +280 610 m +170 610 l +</path> +</page> +</ipe> diff --git a/src/Alpha_complex/doc/alpha_complex_doc.png b/src/Alpha_complex/doc/alpha_complex_doc.png Binary files differnew file mode 100644 index 00000000..ff51ea9a --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc.png 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 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70005" creator="Ipe 7.1.4"> +<info created="D:20150603143945" modified="D:20150623140121"/> +<ipestyle name="basic"> +<symbol name="arrow/arc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/farc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="mark/circle(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</symbol> +<symbol name="mark/disk(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +</path> +</symbol> +<symbol name="mark/fdisk(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +0.5 0 0 0.5 0 0 e +</path> +<path fill="sym-stroke" fillrule="eofill"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</group> +</symbol> +<symbol name="mark/box(sx)" transformations="translations"> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</symbol> +<symbol name="mark/square(sx)" transformations="translations"> +<path fill="sym-stroke"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +</path> +</symbol> +<symbol name="mark/fsquare(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h +</path> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</group> +</symbol> +<symbol name="mark/cross(sx)" transformations="translations"> +<group> +<path fill="sym-stroke"> +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h +</path> +<path fill="sym-stroke"> +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h +</path> +</group> +</symbol> +<symbol name="arrow/fnormal(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/pointed(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fpointed(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/linear(spx)"> +<path stroke="sym-stroke" pen="sym-pen"> +-1 0.333 m +0 0 l +-1 -0.333 l +</path> +</symbol> +<symbol name="arrow/fdouble(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/double(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<pen name="heavier" value="0.8"/> +<pen name="fat" value="1.2"/> +<pen name="ultrafat" value="2"/> +<symbolsize name="large" value="5"/> +<symbolsize name="small" value="2"/> +<symbolsize name="tiny" value="1.1"/> +<arrowsize name="large" value="10"/> +<arrowsize name="small" value="5"/> +<arrowsize name="tiny" value="3"/> +<color name="red" value="1 0 0"/> +<color name="green" value="0 1 0"/> +<color name="blue" value="0 0 1"/> +<color name="yellow" value="1 1 0"/> +<color name="orange" value="1 0.647 0"/> +<color name="gold" value="1 0.843 0"/> +<color name="purple" value="0.627 0.125 0.941"/> +<color name="gray" value="0.745"/> +<color name="brown" value="0.647 0.165 0.165"/> +<color name="navy" value="0 0 0.502"/> +<color name="pink" value="1 0.753 0.796"/> +<color name="seagreen" value="0.18 0.545 0.341"/> +<color name="turquoise" value="0.251 0.878 0.816"/> +<color name="violet" value="0.933 0.51 0.933"/> +<color name="darkblue" value="0 0 0.545"/> +<color name="darkcyan" value="0 0.545 0.545"/> +<color name="darkgray" value="0.663"/> +<color name="darkgreen" value="0 0.392 0"/> +<color name="darkmagenta" value="0.545 0 0.545"/> +<color name="darkorange" value="1 0.549 0"/> +<color name="darkred" value="0.545 0 0"/> +<color name="lightblue" value="0.678 0.847 0.902"/> +<color name="lightcyan" value="0.878 1 1"/> +<color name="lightgray" value="0.827"/> +<color name="lightgreen" value="0.565 0.933 0.565"/> +<color name="lightyellow" value="1 1 0.878"/> +<dashstyle name="dashed" value="[4] 0"/> +<dashstyle name="dotted" value="[1 3] 0"/> +<dashstyle name="dash dotted" value="[4 2 1 2] 0"/> +<dashstyle name="dash dot dotted" value="[4 2 1 2 1 2] 0"/> +<textsize name="large" value="\large"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="small" value="\small"/> +<textsize name="footnote" value="\footnotesize"/> +<textsize name="tiny" value="\tiny"/> +<textstyle name="center" begin="\begin{center}" end="\end{center}"/> +<textstyle name="itemize" begin="\begin{itemize}" end="\end{itemize}"/> +<textstyle name="item" begin="\begin{itemize}\item{}" end="\end{itemize}"/> +<gridsize name="4 pts" value="4"/> +<gridsize name="8 pts (~3 mm)" value="8"/> +<gridsize name="16 pts (~6 mm)" value="16"/> +<gridsize name="32 pts (~12 mm)" value="32"/> +<gridsize name="10 pts (~3.5 mm)" value="10"/> +<gridsize name="20 pts (~7 mm)" value="20"/> +<gridsize name="14 pts (~5 mm)" value="14"/> +<gridsize name="28 pts (~10 mm)" value="28"/> +<gridsize name="56 pts (~20 mm)" value="56"/> +<anglesize name="90 deg" value="90"/> +<anglesize name="60 deg" value="60"/> +<anglesize name="45 deg" value="45"/> +<anglesize name="30 deg" value="30"/> +<anglesize name="22.5 deg" value="22.5"/> +<tiling name="falling" angle="-60" step="4" width="1"/> +<tiling name="rising" angle="30" step="4" width="1"/> +</ipestyle> +<page> +<layer name="alpha"/> +<view layers="alpha" active="alpha"/> +<use layer="alpha" matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0.700256 69.8463" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<path matrix="1 0 0 1 0 80" stroke="lightgray"> +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 0 80" stroke="darkcyan" pen="heavier"> +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 0 80" stroke="lightgray"> +320 580 m +370 580 l +350 520 l +320 580 l +</path> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="380 530" stroke="darkcyan" type="label" width="54.628" height="8.965" depth="2.99" valign="baseline" size="large">Cell [5,3,1]</text> +<text matrix="1 0 0 1 -2.15463 76.4987" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="310.693 578.759" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 0.700256 69.8463" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<path matrix="1 0 0 1 0 80" stroke="lightgray"> +280 660 m +300 710 l +370 690 l +280 660 l +</path> +<path matrix="1 0 0 1 0 80" stroke="lightgray"> +320 580 m +370 690 l +370 580 l +320 580 l +</path> +<path matrix="1 0 0 1 0 80" stroke="lightgray"> +280 660 m +370 690 l +320 580 l +280 660 l +</path> +<path matrix="1 0 0 1 0 80" stroke="darkcyan"> +77.2727 0 0 77.2727 243.636 591.818 e +</path> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="243.636 591.818" size="normal" stroke="darkcyan" fill="white"/> +<path matrix="1 0 0 1 0 80" stroke="darkcyan"> +243.428 591.569 m +186.061 643.28 l +</path> +<text matrix="1 0 0 1 0 80" transformations="translations" pos="212.724 627.389" stroke="darkcyan" type="label" width="18.785" height="4.294" depth="1.49" valign="baseline">$\alpha_{531}$</text> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -263.3 -172.154" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<path matrix="1 0 0 1 -264 -162" stroke="lightgray"> +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -264 -162" stroke="lightgray"> +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -264 -162" stroke="lightgray"> +320 580 m +370 580 l +350 520 l +320 580 l +</path> +<text matrix="0.582962 0 0 1 -211.265 -209.555" transformations="translations" pos="380 530" stroke="darkcyan" type="label" width="231.798" height="8.965" depth="2.99" valign="baseline" size="large">[3,1] is Gabriel $\rightarrow$ $\alpha_{31}$ is not$\\$ +modified (NaN) +</text> +<text matrix="1 0 0 1 -266.155 -165.501" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 -264 -162" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -264 -162" transformations="translations" pos="310.693 578.759" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -264 -162" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -264 -172" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -263.3 -172.154" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 -264 -162" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<path matrix="1 0 0 1 -264 -162" stroke="lightgray"> +280 660 m +300 710 l +370 690 l +280 660 l +</path> +<path matrix="1 0 0 1 -264 -162" stroke="lightgray"> +320 580 m +370 690 l +370 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -264 -162" stroke="lightgray"> +280 660 m +370 690 l +320 580 l +280 660 l +</path> +<text matrix="1 0 0 1 -166.834 -240.52" transformations="translations" pos="212.724 627.389" stroke="darkcyan" type="label" width="14.814" height="4.294" depth="1.49" valign="baseline">$\alpha_{31}$</text> +<path matrix="1 0 0 1 -264 -162" stroke="darkcyan" pen="heavier"> +290 530 m +320 580 l +</path> +<path matrix="1 0 0 1 -264 -162" stroke="darkcyan"> +29.1548 0 0 29.1548 305 555 e +</path> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="305 555" size="normal" stroke="darkcyan" fill="white"/> +<path matrix="1 0 0 1 -264 -162" stroke="darkcyan"> +304.883 555.015 m +334.509 555.015 l +</path> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -37.2997 -174.154" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="darkred" fill="white"/> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<path matrix="1 0 0 1 -37.2997 -163.65" stroke="lightgray"> +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -38 -164" stroke="lightgray"> +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -38 -164" stroke="lightgray"> +320 580 m +370 580 l +350 520 l +320 580 l +</path> +<text matrix="1 0 0 1 -199.21 -189.117" transformations="translations" pos="380 530" stroke="darkred" type="label" width="168.308" height="8.965" depth="2.99" valign="baseline" size="large">[1,5] is not Gabriel $\rightarrow$ $\alpha_{15} = \alpha_{135}$</text> +<text matrix="1 0 0 1 -40.1546 -167.501" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 -38 -164" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -38 -164" transformations="translations" pos="310.693 578.759" stroke="darkred" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -38 -164" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -38 -164" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -37.2997 -174.154" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 -38 -164" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<path matrix="1 0 0 1 -38 -164" stroke="lightgray"> +280 660 m +300 710 l +370 690 l +280 660 l +</path> +<path matrix="1 0 0 1 -38 -164" stroke="lightgray"> +320 580 m +370 690 l +370 580 l +320 580 l +</path> +<path matrix="1 0 0 1 -38 -164" stroke="lightgray"> +280 660 m +370 690 l +320 580 l +280 660 l +</path> +<text matrix="1 0 0 1 52.4654 -193.97" transformations="translations" pos="212.724 627.389" stroke="darkcyan" type="label" width="14.814" height="4.294" depth="1.49" valign="baseline">$\alpha_{15}$</text> +<path matrix="1 0 0 1 -38 -164" stroke="darkcyan" pen="heavier"> +290 530 m +280 660 l +</path> +<path matrix="1 0 0 1 -38 -164" stroke="darkred" pen="heavier"> +65.192 0 0 65.192 285 595 e +</path> +<use matrix="1 0 0 1 126 -162" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 126.7 -172.154" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 126 -162" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 126 -162" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 126 -162" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 126 -162" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 126 -162" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<path matrix="1 0 0 1 126 -162" stroke="lightgray"> +320 580 m +350 520 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 126 -162" stroke="lightgray"> +320 580 m +280 660 l +290 530 l +320 580 l +320 580 l +</path> +<path matrix="1 0 0 1 126 -162" stroke="lightgray"> +320 580 m +370 580 l +350 520 l +320 580 l +</path> +<text matrix="1 0 0 1 123.845 -165.501" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 126 -162" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 126 -162" transformations="translations" pos="310.693 578.759" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 126 -162" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 126.7 -172.154" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 126 -162" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<path matrix="1 0 0 1 126 -162" stroke="lightgray"> +280 660 m +300 710 l +370 690 l +280 660 l +</path> +<path matrix="1 0 0 1 126 -162" stroke="lightgray"> +320 580 m +370 690 l +370 580 l +320 580 l +</path> +<path matrix="1 0 0 1 126 -162" stroke="lightgray"> +280 660 m +370 690 l +320 580 l +280 660 l +</path> +<text matrix="1 0 0 1 225.859 -165.729" transformations="translations" pos="212.724 627.389" stroke="darkcyan" type="label" width="14.814" height="4.294" depth="1.49" valign="baseline">$\alpha_{35}$</text> +<text matrix="1 0 0 1 122 -164" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<path stroke="darkcyan" pen="heavier"> +406.093 497.775 m +446.094 418.092 l +</path> +<path stroke="darkcyan"> +44.5799 0 0 44.5799 425.934 457.774 e +</path> +<use name="mark/fdisk(sfx)" pos="425.934 457.774" size="normal" stroke="darkcyan" fill="white"/> +<path stroke="darkcyan"> +425.854 457.774 m +470.795 457.774 l +</path> +<text matrix="1 0 0 1 -48.9756 -209.799" transformations="translations" pos="380 530" stroke="darkcyan" type="label" width="231.798" height="8.965" depth="2.99" valign="baseline" size="large">[3,5] is Gabriel $\rightarrow$ $\alpha_{35}$ is not modified (NaN) +</text> +<path stroke="darkblue" arrow="normal/normal"> +205.028 596.091 m +110.946 544.02 l +</path> +<path stroke="darkblue" arrow="normal/normal"> +280.768 588.99 m +280.768 547.57 l +</path> +<path stroke="darkblue" arrow="normal/normal"> +341.123 594.316 m +413.904 554.079 l +</path> +<text matrix="1 0 0 1 39.645 -2.36686" transformations="translations" pos="199.703 569.464" stroke="darkblue" type="label" width="93.206" height="7.473" depth="2.49" valign="baseline">For all faces of [5,3,1]</text> +<text matrix="1 0 0 1 -93.391 2.68003" transformations="translations" pos="104.437 300.174" stroke="black" type="label" width="208.621" height="6.926" depth="1.93" valign="baseline">N.B. : is Gabriel on a single point has no sense.</text> +<text matrix="1 0 0 1 -36.9231 10" transformations="translations" pos="48 784" stroke="black" type="label" width="118.324" height="7.473" depth="2.49" valign="baseline">Dimension =2 - $\sigma$ = [5,3,1]</text> +<use name="mark/fdisk(sfx)" pos="247 431" size="normal" stroke="darkcyan" fill="white"/> +<path stroke="darkcyan"> +247.333 430.892 m +311.764 430.892 l +</path> +</page> +</ipe> diff --git a/src/Alpha_complex/doc/alpha_complex_doc_135.png b/src/Alpha_complex/doc/alpha_complex_doc_135.png Binary files differnew file mode 100644 index 00000000..edf61368 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc_135.png 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 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70005" creator="Ipe 7.1.4"> +<info created="D:20150603143945" modified="D:20150623144233"/> +<ipestyle name="basic"> +<symbol name="arrow/arc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/farc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="mark/circle(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</symbol> +<symbol name="mark/disk(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +</path> +</symbol> +<symbol name="mark/fdisk(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +0.5 0 0 0.5 0 0 e +</path> +<path fill="sym-stroke" fillrule="eofill"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</group> +</symbol> +<symbol name="mark/box(sx)" transformations="translations"> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</symbol> +<symbol name="mark/square(sx)" transformations="translations"> +<path fill="sym-stroke"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +</path> +</symbol> +<symbol name="mark/fsquare(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h +</path> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</group> +</symbol> +<symbol name="mark/cross(sx)" transformations="translations"> +<group> +<path fill="sym-stroke"> +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h +</path> +<path fill="sym-stroke"> +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h +</path> +</group> +</symbol> +<symbol name="arrow/fnormal(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/pointed(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fpointed(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/linear(spx)"> +<path stroke="sym-stroke" pen="sym-pen"> +-1 0.333 m +0 0 l +-1 -0.333 l +</path> +</symbol> +<symbol name="arrow/fdouble(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/double(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<pen name="heavier" value="0.8"/> +<pen name="fat" value="1.2"/> +<pen name="ultrafat" value="2"/> +<symbolsize name="large" value="5"/> +<symbolsize name="small" value="2"/> +<symbolsize name="tiny" value="1.1"/> +<arrowsize name="large" value="10"/> +<arrowsize name="small" value="5"/> +<arrowsize name="tiny" value="3"/> +<color name="red" value="1 0 0"/> +<color name="green" value="0 1 0"/> +<color name="blue" value="0 0 1"/> +<color name="yellow" value="1 1 0"/> +<color name="orange" value="1 0.647 0"/> +<color name="gold" value="1 0.843 0"/> +<color name="purple" value="0.627 0.125 0.941"/> +<color name="gray" value="0.745"/> +<color name="brown" value="0.647 0.165 0.165"/> +<color name="navy" value="0 0 0.502"/> +<color name="pink" value="1 0.753 0.796"/> +<color name="seagreen" value="0.18 0.545 0.341"/> +<color name="turquoise" value="0.251 0.878 0.816"/> +<color name="violet" value="0.933 0.51 0.933"/> +<color name="darkblue" value="0 0 0.545"/> +<color name="darkcyan" value="0 0.545 0.545"/> +<color name="darkgray" value="0.663"/> +<color name="darkgreen" value="0 0.392 0"/> +<color name="darkmagenta" value="0.545 0 0.545"/> +<color name="darkorange" value="1 0.549 0"/> +<color name="darkred" value="0.545 0 0"/> +<color name="lightblue" value="0.678 0.847 0.902"/> +<color name="lightcyan" value="0.878 1 1"/> +<color name="lightgray" value="0.827"/> +<color name="lightgreen" value="0.565 0.933 0.565"/> +<color name="lightyellow" value="1 1 0.878"/> +<dashstyle name="dashed" value="[4] 0"/> +<dashstyle name="dotted" value="[1 3] 0"/> +<dashstyle name="dash dotted" value="[4 2 1 2] 0"/> +<dashstyle name="dash dot dotted" value="[4 2 1 2 1 2] 0"/> +<textsize name="large" value="\large"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="small" value="\small"/> +<textsize name="footnote" value="\footnotesize"/> +<textsize name="tiny" value="\tiny"/> +<textstyle name="center" begin="\begin{center}" end="\end{center}"/> +<textstyle name="itemize" begin="\begin{itemize}" end="\end{itemize}"/> +<textstyle name="item" begin="\begin{itemize}\item{}" end="\end{itemize}"/> +<gridsize name="4 pts" value="4"/> +<gridsize name="8 pts (~3 mm)" value="8"/> +<gridsize name="16 pts (~6 mm)" value="16"/> +<gridsize name="32 pts (~12 mm)" value="32"/> +<gridsize name="10 pts (~3.5 mm)" value="10"/> +<gridsize name="20 pts (~7 mm)" value="20"/> +<gridsize name="14 pts (~5 mm)" value="14"/> +<gridsize name="28 pts (~10 mm)" value="28"/> +<gridsize name="56 pts (~20 mm)" value="56"/> +<anglesize name="90 deg" value="90"/> +<anglesize name="60 deg" value="60"/> +<anglesize name="45 deg" value="45"/> +<anglesize name="30 deg" value="30"/> +<anglesize name="22.5 deg" value="22.5"/> +<tiling name="falling" angle="-60" step="4" width="1"/> +<tiling name="rising" angle="30" step="4" width="1"/> +</ipestyle> +<page> +<layer name="alpha"/> +<view layers="alpha" active="alpha"/> +<use layer="alpha" matrix="1 0 0 1 -170.178 30.1775" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -169.478 20.0238" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -170.178 30.1775" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -170.178 30.1775" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -170.178 30.1775" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -170.178 30.1775" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -170.178 30.1775" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<text matrix="1 0 0 1 -190.178 30.1775" transformations="translations" pos="380 530" stroke="darkred" type="label" width="63.793" height="8.307" depth="2.32" valign="baseline" size="large">Alpha shape</text> +<text matrix="1 0 0 1 -172.333 26.6762" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 -170.178 30.1775" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -170.178 30.1775" transformations="translations" pos="310.693 578.759" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -170.178 30.1775" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -170.178 30.1775" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -169.478 20.0238" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 -170.178 30.1775" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 29.8225 -9.82249" transformations="translations" pos="360 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="360 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="360 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="370 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 39.8225 -9.82249" transformations="translations" pos="380 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 39.8225 -9.82249" transformations="translations" pos="380 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 59.8225 -9.82249" transformations="translations" pos="400 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 29.8225 -9.82249" transformations="translations" pos="390 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 29.8225 -9.82249" transformations="translations" pos="400 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 39.8225 -9.82249" transformations="translations" pos="410 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 59.8225 -9.82249" transformations="translations" pos="430 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="370 640" stroke="darkgray" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="380 660" stroke="darkgray" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 29.8225 -9.82249" transformations="translations" pos="430 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 49.8225 -9.82249" transformations="translations" pos="460 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="430 640" stroke="darkgray" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 19.8225 -9.82249" transformations="translations" pos="450 660" stroke="darkgray" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 29.8225 -9.82249" transformations="translations" pos="460 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 39.8225 -9.82249" transformations="translations" pos="520 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 159.822 -9.82249" transformations="translations" pos="300 640" stroke="darkgray" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 169.822 -9.82249" transformations="translations" pos="350 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 159.822 -9.82249" transformations="translations" pos="350 660" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 159.822 -9.82249" transformations="translations" pos="350 640" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">7</text> +<text matrix="1 0 0 1 159.822 -9.82249" transformations="translations" pos="380 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black"> +4 0 0 4 320 704 e +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black"> +322.919 706.788 m +317.189 701.058 l +317.189 701.203 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black"> +317.551 706.934 m +322.629 701.058 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="darkgray" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 189.822 -9.82249" stroke="black" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 229.822 -9.82249" stroke="darkgray" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 279.822 -9.82249" stroke="black" arrow="normal/tiny"> +230 680 m +240 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +230 680 m +220 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +230 680 m +230 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +220 660 m +220 650 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="darkgray" arrow="normal/tiny"> +230 660 m +230 650 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +260 680 m +260 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +260 660 m +260 650 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +300 680 m +300 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +300 680 m +290 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="darkgray" arrow="normal/tiny"> +290 660 m +290 650 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="darkgray" arrow="normal/tiny"> +300 660 m +300 650 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +330 680 m +330 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +350 680 m +350 670 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +350 660 m +350 650 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +240 690 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +270 690 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +310 690 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +330 690 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +350 690 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +380 690 l +</path> +<path matrix="1 0 0 1 159.822 -9.82249" stroke="black" arrow="normal/tiny"> +320 700 m +400 690 l +</path> +<text matrix="1 0 0 1 181.065 -17.7515" transformations="translations" pos="180 620" stroke="black" type="label" width="108.04" height="6.926" depth="1.93" valign="baseline">Alpha complex structure</text> +<path matrix="1 0 0 1 0.147054 -27.9437" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 17.3033 -128.43" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -40.8179 81.2962" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -77.2312 -186.201" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -126.949 -81.8634" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -122.048 -59.1051" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -11.057 -91.3168" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -44.3191 -30.7447" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -96.4882 -133.682" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -146.206 42.0819" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 -53.4225 -19.5406" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +60 710 m +40 660 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +40 660 m +130 690 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +130 690 m +60 710 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +40 660 m +80 580 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +80 580 m +130 580 l +130 580 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +130 580 m +110 520 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +110 520 m +50 530 l +50 530 l +50 530 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +50 530 m +80 580 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +80 580 m +110 520 l +110 520 l +</path> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkred"> +130 580 m +130 690 l +</path> +<use matrix="1 0 0 1 69.8225 30.1775" name="mark/fdisk(sfx)" pos="108.285 743.72" size="normal" stroke="darkgray" fill="white"/> +<path matrix="1 0 0 1 69.8225 30.1775" stroke="darkgray"> +108.275 743.531 m +166.45 743.531 l +</path> +<text matrix="1 0 0 1 69.8225 30.1775" transformations="translations" pos="127.397 746.763" stroke="darkgray" type="label" width="6.41" height="4.289" depth="0" valign="baseline">$\alpha$</text> +<text matrix="1 0 0 1 180.473 -27.8112" transformations="translations" pos="180 620" stroke="darkgray" type="label" width="132.41" height="6.926" depth="1.93" valign="baseline">filtration value $> \alpha$ are greyed</text> +<path stroke="black"> +280 660 m +300 680 l +</path> +<path stroke="black"> +280 660 m +300 640 l +</path> +<path stroke="black"> +370 660 m +350 680 l +</path> +<path stroke="black"> +370 660 m +350 640 l +</path> +<path stroke="black"> +290 670 m +360 670 l +</path> +<path stroke="black"> +290 650 m +360 650 l +</path> +<text matrix="1 0 0 1 2.36686 -1.77515" transformations="translations" pos="300 660" stroke="black" type="label" width="44.002" height="6.926" depth="1.93" valign="baseline">equivalent</text> +</page> +</ipe> diff --git a/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png b/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png Binary files differnew file mode 100644 index 00000000..516de126 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc_alpha_shape.png diff --git a/src/Alpha_complex/example/Alpha_complex_from_off.cpp b/src/Alpha_complex/example/Alpha_complex_from_off.cpp new file mode 100644 index 00000000..ce278419 --- /dev/null +++ b/src/Alpha_complex/example/Alpha_complex_from_off.cpp @@ -0,0 +1,44 @@ +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" +#include "gudhi/Alpha_complex.h" + +#include <stdio.h> +#include <stdlib.h> +#include <string> + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << " filename.off" << std::endl; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if (argc != 2) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; + usage(argv[0]); + } + + std::string off_file_name(argv[1]); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from an OFF file + // ---------------------------------------------------------------------------- + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << + " - " << alpha_complex_from_file.num_simplices() << " simplices - " << + alpha_complex_from_file.num_vertices() << " vertices." << std::endl; + + std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : alpha_complex_from_file.filtration_simplex_range()) { + std::cout << " ( "; + for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << ") -> " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] "; + std::cout << std::endl; + } + return 0; +}
\ No newline at end of file diff --git a/src/Alpha_complex/example/Alpha_complex_from_points.cpp b/src/Alpha_complex/example/Alpha_complex_from_points.cpp new file mode 100644 index 00000000..fc0e2460 --- /dev/null +++ b/src/Alpha_complex/example/Alpha_complex_from_points.cpp @@ -0,0 +1,71 @@ +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" +#include "gudhi/Alpha_complex.h" + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string> + +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; +typedef Kernel::Point_d Point; +typedef std::vector<Point> Vector_of_points; + +int main(int argc, char **argv) { + + // ---------------------------------------------------------------------------- + // Init of a list of points + // ---------------------------------------------------------------------------- + Vector_of_points points; + std::vector<double> coords; + + coords.clear(); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(1.0); + points.push_back(Point(coords.begin(), coords.end())); + coords.clear(); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(1.0); + coords.push_back(0.0); + points.push_back(Point(coords.begin(), coords.end())); + coords.clear(); + coords.push_back(0.0); + coords.push_back(1.0); + coords.push_back(0.0); + coords.push_back(0.0); + points.push_back(Point(coords.begin(), coords.end())); + coords.clear(); + coords.push_back(1.0); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(0.0); + points.push_back(Point(coords.begin(), coords.end())); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from the list of points + // ---------------------------------------------------------------------------- + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_points(3, points.size(), points.begin(), points.end()); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Alpha complex is of dimension " << alpha_complex_from_points.dimension() << + " - " << alpha_complex_from_points.num_simplices() << " simplices - " << + alpha_complex_from_points.num_vertices() << " vertices." << std::endl; + + std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + std::cout << " ( "; + for (auto vertex : alpha_complex_from_points.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << ") -> " << "[" << alpha_complex_from_points.filtration(f_simplex) << "] "; + std::cout << std::endl; + } + return 0; +}
\ No newline at end of file diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt new file mode 100644 index 00000000..2e64e4db --- /dev/null +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -0,0 +1,29 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIAlphaShapesExample) + +# need CGAL 4.7 +# cmake -DCGAL_DIR=~/workspace/CGAL-4.7-Ic-41 ../../.. +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + + #add_definitions(-DDEBUG_TRACES) + add_executable ( alphaoffreader Alpha_complex_from_off.cpp ) + target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + + add_executable ( alphapoints Alpha_complex_from_points.cpp ) + target_link_libraries(alphapoints ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") + endif () +endif() diff --git a/src/Alpha_complex/example/alphaoffreader_for_doc.txt b/src/Alpha_complex/example/alphaoffreader_for_doc.txt new file mode 100644 index 00000000..1153f097 --- /dev/null +++ b/src/Alpha_complex/example/alphaoffreader_for_doc.txt @@ -0,0 +1,27 @@ +Alpha complex is of dimension 2 - 25 simplices - 7 vertices. +Iterator on alpha complex simplices in the filtration order, with [filtration value]: + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 7 ) -> [0] + ( 4 3 ) -> [6.25] + ( 6 5 ) -> [7.25] + ( 3 1 ) -> [8.5] + ( 2 1 ) -> [9.25] + ( 4 2 ) -> [10] + ( 3 2 ) -> [11.25] + ( 4 3 2 ) -> [12.5] + ( 3 2 1 ) -> [12.9959] + ( 7 6 ) -> [13.25] + ( 5 3 ) -> [20] + ( 7 5 ) -> [22.7367] + ( 7 6 5 ) -> [22.7367] + ( 7 4 ) -> [30.25] + ( 7 3 ) -> [36.5] + ( 7 4 3 ) -> [36.5] + ( 7 5 3 ) -> [37.2449] + ( 5 1 ) -> [59.7107] + ( 5 3 1 ) -> [59.7107] diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h new file mode 100644 index 00000000..138270ff --- /dev/null +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -0,0 +1,346 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ +#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ + +// to construct a simplex_tree from Delaunay_triangulation +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/Simplex_tree.h> + +#include <stdio.h> +#include <stdlib.h> +#include <math.h> // isnan, fmax + +#include <boost/bimap.hpp> + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> +#include <CGAL/algorithm.h> +#include <CGAL/assertions.h> +#include <CGAL/enum.h> + +#include <iostream> +#include <iterator> +#include <vector> +#include <string> +#include <limits> // NaN +#include <iterator> // std::iterator + +namespace Gudhi { + +namespace alphacomplex { + +#define Kinit(f) =k.f() + +/** + * \brief Alpha complex data structure. + * + * \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. + * + */ +class Alpha_complex : public Simplex_tree<> { + private: + // From Simplex_tree + // Type required to insert into a simplex_tree (with or without subfaces). + typedef std::vector<Vertex_handle> Vector_vertex; + + // Simplex_result is the type returned from simplex_tree insert function. + typedef typename std::pair<Simplex_handle, bool> Simplex_result; + + // From CGAL + // Kernel for the Delaunay_triangulation. Dimension can be set dynamically. + typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; + + // Delaunay_triangulation type required to create an alpha-complex. + typedef CGAL::Delaunay_triangulation<Kernel> Delaunay_triangulation; + + typedef typename Kernel::Compute_squared_radius_d Squared_Radius; + typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; + + // Type required to compute squared radius, or side of bounded sphere on a vector of points. + typedef std::vector<Kernel::Point_d> Vector_of_CGAL_points; + + // Vertex_iterator type from CGAL. + typedef Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; + + // Boost bimap type to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa. + typedef boost::bimap< CGAL_vertex_iterator, Vertex_handle > Bimap_vertex; + + // size_type type from CGAL. + typedef Delaunay_triangulation::size_type size_type; + + private: + /** \brief Boost bimap to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa.*/ + Bimap_vertex cgal_simplextree; + /** \brief Pointer on the CGAL Delaunay triangulation.*/ + Delaunay_triangulation* triangulation; + + public: + /** \brief Alpha_complex constructor from an OFF file name. + * Uses the Delaunay_triangulation_off_reader to construct the Delaunay triangulation required to initialize + * the Alpha_complex. + * + * @param[in] off_file_name OFF file [path and] name. + */ + Alpha_complex(const std::string& off_file_name) + : triangulation(nullptr) { + Gudhi::Delaunay_triangulation_off_reader<Delaunay_triangulation> off_reader(off_file_name); + if (!off_reader.is_valid()) { + std::cerr << "Alpha_complex - Unable to read file " << off_file_name << std::endl; + exit(-1); // ----- >> + } + triangulation = off_reader.get_complex(); + init(); + } + + /** \brief Alpha_complex constructor from a Delaunay triangulation. + * + * @param[in] triangulation_ptr Pointer on a Delaunay triangulation. + */ + Alpha_complex(Delaunay_triangulation* triangulation_ptr) + : triangulation(triangulation_ptr) { + init(); + } + + /** \brief Alpha_complex constructor from a list of points. + * Uses the Delaunay_triangulation_off_reader to construct the Delaunay triangulation required to initialize + * the Alpha_complex. + * + * @param[in] dimension Dimension of points to be inserted. + * @param[in] size Number of points to be inserted. + * @param[in] firstPoint Iterator on the first point to be inserted. + * @param[in] last Point Iterator on the last point to be inserted. + */ + template<typename ForwardIterator > + Alpha_complex(int dimension, size_type size, ForwardIterator firstPoint, ForwardIterator lastPoint) + : triangulation(nullptr) { + triangulation = new Delaunay_triangulation(dimension); + Delaunay_triangulation::size_type inserted = triangulation->insert<ForwardIterator>(firstPoint, lastPoint); + if (inserted != size) { + std::cerr << "Alpha_complex - insertion failed " << inserted << " != " << size<< std::endl; + exit(-1); // ----- >> + } + init(); + } + + /** \brief Alpha_complex destructor from a Delaunay triangulation. + * + * @warning Deletes the Delaunay triangulation. + */ + ~Alpha_complex() { + delete triangulation; + } + + private: + /** \brief Initialize the Alpha_complex from the Delaunay triangulation. + * + * @warning Delaunay triangulation must be already constructed with at least one vertex and dimension must be more + * than 0. + * + * Initialization can be launched once. + */ + void init() { + if (triangulation == nullptr) { + std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation" << std::endl; + return; // ----- >> + } + if (triangulation->number_of_vertices() < 1) { + std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices" << std::endl; + return; // ----- >> + } + if (triangulation->maximal_dimension() < 1) { + std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation" << std::endl; + return; // ----- >> + } + if (num_vertices() > 0) { + std::cerr << "Alpha_complex init - Cannot init twice" << std::endl; + return; // ----- >> + } + + set_dimension(triangulation->maximal_dimension()); + + // -------------------------------------------------------------------------------------------- + // bimap to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa + // Start to insert at handle = 0 - default integer value + Vertex_handle vertex_handle = Vertex_handle(); + // Loop on triangulation vertices list + for (CGAL_vertex_iterator vit = triangulation->vertices_begin(); vit != triangulation->vertices_end(); ++vit) { + cgal_simplextree.insert(Bimap_vertex::value_type(vit, vertex_handle)); + vertex_handle++; + } + // -------------------------------------------------------------------------------------------- + + // -------------------------------------------------------------------------------------------- + // Simplex_tree construction from loop on triangulation finite full cells list + for (auto cit = triangulation->finite_full_cells_begin(); cit != triangulation->finite_full_cells_end(); ++cit) { + Vector_vertex vertexVector; +#ifdef DEBUG_TRACES + std::cout << "Simplex_tree insertion "; +#endif // DEBUG_TRACES + for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { +#ifdef DEBUG_TRACES + std::cout << " " << cgal_simplextree.left.at(*vit); +#endif // DEBUG_TRACES + // Vector of vertex construction for simplex_tree structure + vertexVector.push_back(cgal_simplextree.left.at(*vit)); + } +#ifdef DEBUG_TRACES + std::cout << std::endl; +#endif // DEBUG_TRACES + // Insert each simplex and its subfaces in the simplex tree - filtration is NaN + Simplex_result insert_result = insert_simplex_and_subfaces(vertexVector, + std::numeric_limits<double>::quiet_NaN()); + if (!insert_result.second) { + std::cerr << "Alpha_complex::init insert_simplex_and_subfaces failed" << std::endl; + } + } + // -------------------------------------------------------------------------------------------- + + Filtration_value filtration_max = 0.0; + // -------------------------------------------------------------------------------------------- + // ### For i : d -> 0 + for (int decr_dim = dimension(); decr_dim >= 0; decr_dim--) { + // ### Foreach Sigma of dim i + for (auto f_simplex : skeleton_simplex_range(decr_dim)) { + int f_simplex_dim = dimension(f_simplex); + if (decr_dim == f_simplex_dim) { + Vector_of_CGAL_points pointVector; +#ifdef DEBUG_TRACES + std::cout << "Sigma of dim " << decr_dim << " is"; +#endif // DEBUG_TRACES + for (auto vertex : simplex_vertex_range(f_simplex)) { + pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); +#ifdef DEBUG_TRACES + std::cout << " " << vertex; +#endif // DEBUG_TRACES + } +#ifdef DEBUG_TRACES + std::cout << std::endl; +#endif // DEBUG_TRACES + // ### If filt(Sigma) is NaN : filt(Sigma) = alpha(Sigma) + if (isnan(filtration(f_simplex))) { + Filtration_value alpha_complex_filtration = 0.0; + // No need to compute squared_radius on a single point - alpha is 0.0 + if (f_simplex_dim > 0) { + // squared_radius function initialization + Kernel k; + Squared_Radius squared_radius Kinit(compute_squared_radius_d_object); + + alpha_complex_filtration = squared_radius(pointVector.begin(), pointVector.end()); + } + assign_filtration(f_simplex, alpha_complex_filtration); + filtration_max = fmax(filtration_max, alpha_complex_filtration); +#ifdef DEBUG_TRACES + std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << filtration(f_simplex) << std::endl; +#endif // DEBUG_TRACES + } + propagate_alpha_filtration(f_simplex, decr_dim); + } + } + } + // -------------------------------------------------------------------------------------------- + +#ifdef DEBUG_TRACES + std::cout << "filtration_max=" << filtration_max << std::endl; +#endif // DEBUG_TRACES + set_filtration(filtration_max); + } + + template<typename Simplex_handle> + void propagate_alpha_filtration(Simplex_handle f_simplex, int decr_dim) { + // ### Foreach Tau face of Sigma + for (auto f_boundary : boundary_simplex_range(f_simplex)) { +#ifdef DEBUG_TRACES + std::cout << " | --------------------------------------------------" << std::endl; + std::cout << " | Tau "; + for (auto vertex : simplex_vertex_range(f_boundary)) { + std::cout << vertex << " "; + } + std::cout << "is a face of Sigma" << std::endl; + std::cout << " | isnan(filtration(Tau)=" << isnan(filtration(f_boundary)) << std::endl; +#endif // DEBUG_TRACES + // ### If filt(Tau) is not NaN + if (!isnan(filtration(f_boundary))) { + // ### filt(Tau) = fmin(filt(Tau), filt(Sigma)) + Filtration_value alpha_complex_filtration = fmin(filtration(f_boundary), filtration(f_simplex)); + assign_filtration(f_boundary, alpha_complex_filtration); + // No need to check for filtration_max, alpha_complex_filtration is a min of an existing filtration value +#ifdef DEBUG_TRACES + std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << filtration(f_boundary) << std::endl; +#endif // DEBUG_TRACES + // ### Else + } else { + // No need to compute is_gabriel for dimension <= 2 + // i.e. : Sigma = (3,1) => Tau = 1 + if (decr_dim > 1) { + // insert the Tau points in a vector for is_gabriel function + Vector_of_CGAL_points pointVector; + Vertex_handle vertexForGabriel = Vertex_handle(); + for (auto vertex : simplex_vertex_range(f_boundary)) { + pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); + } + // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function + for (auto vertex : simplex_vertex_range(f_simplex)) { + if (std::find(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertex))->point()) + == pointVector.end()) { + // vertex is not found in Tau + vertexForGabriel = vertex; + // No need to continue loop + break; + } + } + // is_gabriel function initialization + Kernel k; + Is_Gabriel is_gabriel Kinit(side_of_bounded_sphere_d_object); +#ifdef DEBUG_TRACES + bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) + != CGAL::ON_BOUNDED_SIDE; + std::cout << " | Tau is_gabriel(Sigma)=" << is_gab << " - vertexForGabriel=" << vertexForGabriel << std::endl; +#endif // DEBUG_TRACES + // ### If Tau is not Gabriel of Sigma + if ((is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) + == CGAL::ON_BOUNDED_SIDE)) { + // ### filt(Tau) = filt(Sigma) + Filtration_value alpha_complex_filtration = filtration(f_simplex); + assign_filtration(f_boundary, alpha_complex_filtration); + // No need to check for filtration_max, alpha_complex_filtration is an existing filtration value +#ifdef DEBUG_TRACES + std::cout << " | filt(Tau) = filt(Sigma) = " << filtration(f_boundary) << std::endl; +#endif // DEBUG_TRACES + } + } + } + } + } +}; + +} // namespace alphacomplex + +} // namespace Gudhi + +#endif // SRC_ALPHA_COMPLEX_INCLUDE_GUDHI_ALPHA_COMPLEX_H_ diff --git a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp new file mode 100644 index 00000000..9530314c --- /dev/null +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -0,0 +1,163 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#define BOOST_TEST_MODULE alpha_complex +#include <boost/test/included/unit_test.hpp> +#include <boost/system/error_code.hpp> +#include <boost/chrono/thread_clock.hpp> +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" +#include "gudhi/Alpha_complex.h" + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> + +#include <cmath> // float comparison +#include <limits> + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; +typedef Kernel::Point_d Point; +typedef std::vector<Point> Vector_of_points; +// The triangulation uses the default instantiation of the TriangulationDataStructure template parameter + +BOOST_AUTO_TEST_CASE(S4_100_OFF_file) { + // ---------------------------------------------------------------------------- + // + // Init of an alpha-complex from a OFF file + // + // ---------------------------------------------------------------------------- + std::string off_file_name("S4_100.off"); + std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; + + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + + const int DIMENSION = 4; + std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); + + const int NUMBER_OF_VERTICES = 100; + std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); + + const int NUMBER_OF_SIMPLICES = 6879; + std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_simplices() == NUMBER_OF_SIMPLICES); + +} + +BOOST_AUTO_TEST_CASE(S8_10_OFF_file) { + // ---------------------------------------------------------------------------- + // + // Init of an alpha-complex from a OFF file + // + // ---------------------------------------------------------------------------- + std::string off_file_name("S8_10.off"); + std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; + + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + + const int DIMENSION = 8; + std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); + + const int NUMBER_OF_VERTICES = 10; + std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); + + const int NUMBER_OF_SIMPLICES = 1007; + std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_simplices() == NUMBER_OF_SIMPLICES); +} + +bool are_almost_the_same(float a, float b) { + return std::fabs(a - b) < std::numeric_limits<float>::epsilon(); +} + +BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { + + // ---------------------------------------------------------------------------- + // Init of a list of points + // ---------------------------------------------------------------------------- + Vector_of_points points; + std::vector<double> coords; + + coords.clear(); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(1.0); + points.push_back(Point(coords.begin(), coords.end())); + coords.clear(); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(1.0); + coords.push_back(0.0); + points.push_back(Point(coords.begin(), coords.end())); + coords.clear(); + coords.push_back(0.0); + coords.push_back(1.0); + coords.push_back(0.0); + coords.push_back(0.0); + points.push_back(Point(coords.begin(), coords.end())); + coords.clear(); + coords.push_back(1.0); + coords.push_back(0.0); + coords.push_back(0.0); + coords.push_back(0.0); + points.push_back(Point(coords.begin(), coords.end())); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from the list of points + // ---------------------------------------------------------------------------- + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_points(3, points.size(), points.begin(), points.end()); + + std::cout << "========== Alpha_complex_from_points ==========" << std::endl; + + std::cout << "alpha_complex_from_points.dimension()=" << alpha_complex_from_points.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_points.dimension() == 3); + std::cout << "alpha_complex_from_points.num_simplices()=" << alpha_complex_from_points.num_simplices() << std::endl; + BOOST_CHECK(alpha_complex_from_points.num_simplices() == 15); + std::cout << "alpha_complex_from_points.num_vertices()=" << alpha_complex_from_points.num_vertices() << std::endl; + BOOST_CHECK(alpha_complex_from_points.num_vertices() == 4); + + for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + switch (alpha_complex_from_points.dimension(f_simplex)) { + case 0: + BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 0.0)); + break; + case 1: + BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 1.0/2.0)); + break; + case 2: + BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 2.0/3.0)); + break; + case 3: + BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 3.0/4.0)); + break; + default: + BOOST_CHECK(false); // Shall not happen + break; + } + } + +} diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt new file mode 100644 index 00000000..79300790 --- /dev/null +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -0,0 +1,32 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIAlphaComplexTest) + +# need CGAL 4.7 +# cmake -DCGAL_DIR=~/workspace/CGAL-4.7-Ic-41 ../../.. +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + include_directories (BEFORE "../../include") + + #add_definitions(-DDEBUG_TRACES) + add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) + target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + add_test(AlphaComplexUT ${CMAKE_CURRENT_BINARY_DIR}/AlphaComplexUT + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/AlphaComplexUT.xml --log_level=test_suite --report_level=no) + + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha complex feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha complex feature. Version 4.6.0 is required.") + endif () +endif() + diff --git a/src/Alpha_shapes/test/README b/src/Alpha_complex/test/README index cddd46ca..45b87d91 100644 --- a/src/Alpha_shapes/test/README +++ b/src/Alpha_complex/test/README @@ -1,14 +1,12 @@ To compile: *********** -cd /path-to-gudhi/ cmake . -cd /path-to-test/ make To launch with details: *********************** -./AlphaShapesUT --report_level=detailed --log_level=all +./AlphaComplexUnitTest --report_level=detailed --log_level=all ==> echo $? returns 0 in case of success (non-zero otherwise) diff --git a/src/Alpha_shapes/test/S4_100.off b/src/Alpha_complex/test/S4_100.off index 0a5dc58c..cd017e12 100644 --- a/src/Alpha_shapes/test/S4_100.off +++ b/src/Alpha_complex/test/S4_100.off @@ -1,5 +1,5 @@ -OFF -100 0 0 +nOFF +4 100 0 0 0.562921 -0.735261 -0.256472 0.277007 -0.803733 -0.0527915 -0.315125 0.501918 -0.24946 -0.354982 -0.410773 -0.801887 diff --git a/src/Alpha_shapes/test/S8_10.off b/src/Alpha_complex/test/S8_10.off index 1d67e10f..4e147c44 100644 --- a/src/Alpha_shapes/test/S8_10.off +++ b/src/Alpha_complex/test/S8_10.off @@ -1,5 +1,5 @@ -OFF -10 0 0 +nOFF +8 10 0 0 0.440036 -0.574754 -0.200485 0.216537 -0.501251 -0.0329236 -0.196529 0.313023 -0.129367 -0.184089 -0.213021 -0.415848 0.783529 -0.0438025 0.317256 0.120749 0.132429 0.683748 -0.124536 -0.166133 -0.540695 -0.0887576 0.390234 -0.139031 diff --git a/src/Alpha_shapes/example/Delaunay_triangulation_off_rw.cpp b/src/Alpha_shapes/example/Delaunay_triangulation_off_rw.cpp deleted file mode 100644 index 03f6440d..00000000 --- a/src/Alpha_shapes/example/Delaunay_triangulation_off_rw.cpp +++ /dev/null @@ -1,105 +0,0 @@ -/* 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): Vincent Rouvreau - * - * Copyright (C) 2014 INRIA Saclay (France) - * - * 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 <http://www.gnu.org/licenses/>. - */ - -// to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" - -#include <CGAL/Delaunay_triangulation.h> -#include <CGAL/Epick_d.h> -#include <CGAL/point_generators_d.h> -#include <CGAL/algorithm.h> -#include <CGAL/assertions.h> - -#include <iostream> -#include <iterator> -#include <vector> - -#include <stdio.h> -#include <stdlib.h> -#include <string> - -// Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; -typedef CGAL::Delaunay_triangulation<K> T; -// The triangulation uses the default instanciation of the -// TriangulationDataStructure template parameter - -void usage(char * const progName) { - std::cerr << "Usage: " << progName << " filename.off dimension" << std::endl; - exit(-1); // ----- >> -} - -int main(int argc, char **argv) { - if (argc != 3) { - std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; - usage(argv[0]); - } - - int dimension = 0; - int returnedScanValue = sscanf(argv[2], "%d", &dimension); - if ((returnedScanValue == EOF) || (dimension <= 0)) { - std::cerr << "Error: " << argv[2] << " is not correct" << std::endl; - usage(argv[0]); - } - - T dt(dimension); - std::string offFileName(argv[1]); - Gudhi::alphashapes::Delaunay_triangulation_off_reader<T> off_reader(offFileName, dt, true, true); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << offFileName << std::endl; - exit(-1); // ----- >> - } - - std::cout << "number of vertices=" << dt.number_of_vertices() << std::endl; - std::cout << "number of full cells=" << dt.number_of_full_cells() << std::endl; - std::cout << "number of finite full cells=" << dt.number_of_finite_full_cells() << std::endl; - - // Points list - /*for (T::Vertex_iterator vit = dt.vertices_begin(); vit != dt.vertices_end(); ++vit) { - for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { - std::cout << *Coord << " "; - } - std::cout << std::endl; - } - std::cout << std::endl;*/ - - int i = 0, j = 0; - typedef T::Full_cell_iterator Full_cell_iterator; - typedef T::Facet Facet; - - for (Full_cell_iterator cit = dt.full_cells_begin(); cit != dt.full_cells_end(); ++cit) { - if (!dt.is_infinite(cit)) { - j++; - continue; - } - Facet fct(cit, cit->index(dt.infinite_vertex())); - i++; - } - std::cout << "There are " << i << " facets on the convex hull." << std::endl; - std::cout << "There are " << j << " facets not on the convex hull." << std::endl; - - - std::string offOutputFile("out.off"); - Gudhi::alphashapes::Delaunay_triangulation_off_writer<T> off_writer(offOutputFile, dt); - - return 0; -}
\ No newline at end of file diff --git a/src/Alpha_shapes/example/Simplex_tree_from_delaunay_triangulation.cpp b/src/Alpha_shapes/example/Simplex_tree_from_delaunay_triangulation.cpp deleted file mode 100644 index 3a17b519..00000000 --- a/src/Alpha_shapes/example/Simplex_tree_from_delaunay_triangulation.cpp +++ /dev/null @@ -1,103 +0,0 @@ -/* 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): Vincent Rouvreau - * - * Copyright (C) 2014 INRIA Saclay (France) - * - * 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 <http://www.gnu.org/licenses/>. - */ - -// to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" -#include "gudhi/Alpha_shapes.h" - -// to construct a simplex_tree from Delaunay_triangulation -#include "gudhi/graph_simplicial_complex.h" -#include "gudhi/Simplex_tree.h" - -#include <CGAL/Delaunay_triangulation.h> -#include <CGAL/Epick_d.h> -#include <CGAL/point_generators_d.h> -#include <CGAL/algorithm.h> -#include <CGAL/assertions.h> - -#include <iostream> -#include <iterator> - -#include <stdio.h> -#include <stdlib.h> -#include <string> - -// Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; -typedef CGAL::Delaunay_triangulation<K> T; -// The triangulation uses the default instanciation of the -// TriangulationDataStructure template parameter - -void usage(char * const progName) { - std::cerr << "Usage: " << progName << " filename.off dimension" << std::endl; - exit(-1); // ----- >> -} - -int main(int argc, char **argv) { - if (argc != 3) { - std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; - usage(argv[0]); - } - - int dimension = 0; - int returnedScanValue = sscanf(argv[2], "%d", &dimension); - if ((returnedScanValue == EOF) || (dimension <= 0)) { - std::cerr << "Error: " << argv[2] << " is not correct" << std::endl; - usage(argv[0]); - } - - // ---------------------------------------------------------------------------- - // - // Init of an alpha-shape from a Delaunay triangulation - // - // ---------------------------------------------------------------------------- - T dt(dimension); - std::string off_file_name(argv[1]); - - Gudhi::alphashapes::Delaunay_triangulation_off_reader<T> off_reader(off_file_name, dt, false, false); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_name << std::endl; - exit(-1); // ----- >> - } - - std::cout << "number of vertices=" << dt.number_of_vertices() << std::endl; - std::cout << "number of full cells=" << dt.number_of_full_cells() << std::endl; - std::cout << "number of finite full cells=" << dt.number_of_finite_full_cells() << std::endl; - - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_dt(dt); - //std::cout << alpha_shapes_from_dt << std::endl; - - // ---------------------------------------------------------------------------- - // - // Init of an alpha-shape from a OFF file - // - // ---------------------------------------------------------------------------- - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_file(off_file_name, dimension); - //std::cout << alpha_shapes_from_file << std::endl; - - std::cout << "alpha_shapes_from_file.dimension()=" << alpha_shapes_from_file.dimension() << std::endl; - std::cout << "alpha_shapes_from_file.filtration()=" << alpha_shapes_from_file.filtration() << std::endl; - std::cout << "alpha_shapes_from_file.num_simplices()=" << alpha_shapes_from_file.num_simplices() << std::endl; - std::cout << "alpha_shapes_from_file.num_vertices()=" << alpha_shapes_from_file.num_vertices() << std::endl; - - return 0; -}
\ No newline at end of file diff --git a/src/Alpha_shapes/include/gudhi/Alpha_shapes.h b/src/Alpha_shapes/include/gudhi/Alpha_shapes.h deleted file mode 100644 index b8efdb4d..00000000 --- a/src/Alpha_shapes/include/gudhi/Alpha_shapes.h +++ /dev/null @@ -1,200 +0,0 @@ -/* 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): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * 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 <http://www.gnu.org/licenses/>. - */ - -#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ -#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ - -// to construct a Delaunay_triangulation from a OFF file -#include <gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h> - -// to construct a simplex_tree from Delaunay_triangulation -#include <gudhi/graph_simplicial_complex.h> -#include <gudhi/Simplex_tree.h> - -#include <stdio.h> -#include <stdlib.h> - -#include <CGAL/Delaunay_triangulation.h> -#include <CGAL/Epick_d.h> -#include <CGAL/algorithm.h> -#include <CGAL/assertions.h> - -#include <iostream> -#include <iterator> -#include <vector> -#include <string> - -namespace Gudhi { - -namespace alphashapes { - -/** \defgroup alpha_shapes Alpha shapes in dimension N - * - <DT>Implementations:</DT> - Alpha shapes in dimension N are a subset of Delaunay Triangulation in dimension N. - - - * \author Vincent Rouvreau - * \version 1.0 - * \date 2015 - * \copyright GNU General Public License v3. - * @{ - */ - -/** - * \brief Alpha shapes 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. - * - * \implements FilteredComplex - * - */ -class Alpha_shapes { - private: - // From Simplex_tree - /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ - typedef std::vector<Vertex_handle> typeVectorVertex; - - // From CGAL - /** \brief Kernel for the Delaunay_triangulation. - * Dimension can be set dynamically. - */ - typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - /** \brief Delaunay_triangulation type required to create an alpha-shape. - */ - typedef CGAL::Delaunay_triangulation<Kernel> Delaunay_triangulation; - - private: - /** \brief Upper bound on the simplex tree of the simplicial complex.*/ - Gudhi::Simplex_tree<> _st; - - public: - - Alpha_shapes(std::string off_file_name, int dimension) { - Delaunay_triangulation dt(dimension); - Gudhi::alphashapes::Delaunay_triangulation_off_reader<Delaunay_triangulation> - off_reader(off_file_name, dt, true, true); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_name << std::endl; - exit(-1); // ----- >> - } -#ifdef DEBUG_TRACES - std::cout << "number of vertices=" << dt.number_of_vertices() << std::endl; - std::cout << "number of full cells=" << dt.number_of_full_cells() << std::endl; - std::cout << "number of finite full cells=" << dt.number_of_finite_full_cells() << std::endl; -#endif // DEBUG_TRACES - init<Delaunay_triangulation>(dt); - } - - template<typename T> - Alpha_shapes(T triangulation) { - init<T>(triangulation); - } - - ~Alpha_shapes() { } - - private: - - template<typename T> - void init(T triangulation) { - _st.set_dimension(triangulation.maximal_dimension()); - _st.set_filtration(0.0); - // triangulation points list - for (auto vit = triangulation.finite_vertices_begin(); - vit != triangulation.finite_vertices_end(); ++vit) { - typeVectorVertex vertexVector; - Vertex_handle vertexHdl = std::distance(triangulation.finite_vertices_begin(), vit); - vertexVector.push_back(vertexHdl); - - // Insert each point in the simplex tree - _st.insert_simplex(vertexVector, 0.0); - -#ifdef DEBUG_TRACES - std::cout << "P" << vertexHdl << ":"; - for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { - std::cout << *Coord << " "; - } - std::cout << std::endl; -#endif // DEBUG_TRACES - } - // triangulation finite full cells list - for (auto cit = triangulation.finite_full_cells_begin(); - cit != triangulation.finite_full_cells_end(); ++cit) { - typeVectorVertex vertexVector; - for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { - // Vertex handle is distance - 1 - Vertex_handle vertexHdl = std::distance(triangulation.vertices_begin(), *vit) - 1; - vertexVector.push_back(vertexHdl); - } - // Insert each point in the simplex tree - _st.insert_simplex_and_subfaces(vertexVector, 0.0); - -#ifdef DEBUG_TRACES - std::cout << "C" << std::distance(triangulation.finite_full_cells_begin(), cit) << ":"; - for (auto value : vertexVector) { - std::cout << value << ' '; - } - std::cout << std::endl; -#endif // DEBUG_TRACES - } - } - - public: - - /** \brief Returns the number of vertices in the complex. */ - size_t num_vertices() { - return _st.num_vertices(); - } - - /** \brief Returns the number of simplices in the complex. - * - * Does not count the empty simplex. */ - const unsigned int& num_simplices() const { - return _st.num_simplices(); - } - - /** \brief Returns an upper bound on the dimension of the simplicial complex. */ - int dimension() { - return _st.dimension(); - } - - /** \brief Returns an upper bound of the filtration values of the simplices. */ - Filtration_value filtration() { - return _st.filtration(); - } - - friend std::ostream& operator<<(std::ostream& os, const Alpha_shapes& alpha_shape) { - // TODO: Program terminated with signal SIGABRT, Aborted - Maybe because of copy constructor - Gudhi::Simplex_tree<> st = alpha_shape._st; - os << st << std::endl; - return os; - } -}; - -} // namespace alphashapes - -} // namespace Gudhi - -#endif // SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ diff --git a/src/Alpha_shapes/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h b/src/Alpha_shapes/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h deleted file mode 100644 index 693b393e..00000000 --- a/src/Alpha_shapes/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h +++ /dev/null @@ -1,213 +0,0 @@ -/* 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): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * 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 <http://www.gnu.org/licenses/>. - */ -#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ -#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ - -#include <string> -#include <vector> -#include <fstream> - -#include "gudhi/Off_reader.h" - -namespace Gudhi { - -namespace alphashapes { - -/** - *@brief Off reader visitor with flag that can be passed to Off_reader to read a Delaunay_triangulation_complex. - */ -template<typename Complex> -class Delaunay_triangulation_off_flag_visitor_reader { - Complex& complex_; - typedef typename Complex::Point Point; - - const bool load_only_points_; - - public: - explicit Delaunay_triangulation_off_flag_visitor_reader(Complex& complex, bool load_only_points = false) : - complex_(complex), - load_only_points_(load_only_points) { } - - void init(int dim, int num_vertices, int num_faces, int num_edges) { -#ifdef DEBUG_TRACES - std::cout << "init" << std::endl; -#endif // DEBUG_TRACES - } - - void point(const std::vector<double>& point) { -#ifdef DEBUG_TRACES - std::cout << "p "; - for (auto coordinate: point) { - std::cout << coordinate << " | "; - } - std::cout << std::endl; -#endif // DEBUG_TRACES - complex_.insert(Point(point.size(), point.begin(), point.end())); - } - - void maximal_face(const std::vector<int>& face) { - // For alpha shapes, only points are read - } - - void done() { -#ifdef DEBUG_TRACES - std::cout << "done" << std::endl; -#endif // DEBUG_TRACES - } -}; - -/** - *@brief Off reader visitor that can be passed to Off_reader to read a Delaunay_triangulation_complex. - */ -template<typename Complex> -class Delaunay_triangulation_off_visitor_reader { - Complex& complex_; - // typedef typename Complex::Vertex_handle Vertex_handle; - // typedef typename Complex::Simplex_handle Simplex_handle; - typedef typename Complex::Point Point; - - const bool load_only_points_; - std::vector<Point> points_; - // std::vector<Simplex_handle> maximal_faces_; - - public: - explicit Delaunay_triangulation_off_visitor_reader(Complex& complex, bool load_only_points = false) : - complex_(complex), - load_only_points_(load_only_points) { } - - void init(int dim, int num_vertices, int num_faces, int num_edges) { -#ifdef DEBUG_TRACES - std::cout << "init - " << num_vertices << std::endl; -#endif // DEBUG_TRACES - // maximal_faces_.reserve(num_faces); - points_.reserve(num_vertices); - } - - void point(const std::vector<double>& point) { -#ifdef DEBUG_TRACES - std::cout << "p "; - for (auto coordinate: point) { - std::cout << coordinate << " | "; - } - std::cout << std::endl; -#endif // DEBUG_TRACES - points_.emplace_back(Point(point.size(), point.begin(), point.end())); - } - - void maximal_face(const std::vector<int>& face) { - // For alpha shapes, only points are read - } - - void done() { - complex_.insert(points_.begin(), points_.end()); -#ifdef DEBUG_TRACES - std::cout << "done" << std::endl; -#endif // DEBUG_TRACES - } -}; - -/** - *@brief Class that allows to load a Delaunay_triangulation_complex from an off file. - */ -template<typename Complex> -class Delaunay_triangulation_off_reader { - public: - /** - * name_file : file to read - * read_complex : complex that will receive the file content - * read_only_points : specify true if only the points must be read - */ - Delaunay_triangulation_off_reader(const std::string & name_file, Complex& read_complex, bool read_only_points = false, - bool is_flag = false) : valid_(false) { - std::ifstream stream(name_file); - if (stream.is_open()) { - if (is_flag) { - // For alpha shapes, only points are read - Delaunay_triangulation_off_flag_visitor_reader<Complex> off_visitor(read_complex, true); - Off_reader off_reader(stream); - valid_ = off_reader.read(off_visitor); - } else { - // For alpha shapes, only points are read - Delaunay_triangulation_off_visitor_reader<Complex> off_visitor(read_complex, true); - Off_reader off_reader(stream); - valid_ = off_reader.read(off_visitor); - } - } - } - - /** - * return true if reading did not meet problems. - */ - bool is_valid() const { - return valid_; - } - - private: - bool valid_; -}; - -template<typename Complex> -class Delaunay_triangulation_off_writer { - public: - /** - * name_file : file where the off will be written - * save_complex : complex that be outputted in the file - * for now only save triangles. - */ - Delaunay_triangulation_off_writer(const std::string & name_file, const Complex& save_complex) { - std::ofstream stream(name_file); - if (stream.is_open()) { - // OFF header - stream << "OFF" << std::endl; - // no endl on next line - don't know why... - stream << save_complex.number_of_vertices() << " " << save_complex.number_of_finite_full_cells() << " 0"; - - // Points list - for (auto vit = save_complex.vertices_begin(); vit != save_complex.vertices_end(); ++vit) { - for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { - stream << *Coord << " "; - } - stream << std::endl; - } - - // Finite cells list - for (auto cit = save_complex.finite_full_cells_begin(); cit != save_complex.finite_full_cells_end(); ++cit) { - stream << std::distance(cit->vertices_begin(), cit->vertices_end()) << " "; // Dimension - for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { - auto vertexHdl = *vit; - // auto vertexHdl = std::distance(save_complex.vertices_begin(), *vit) - 1; - // stream << std::distance(save_complex.vertices_begin(), *(vit)) - 1 << " "; - } - stream << std::endl; - } - stream.close(); - } else { - std::cerr << "could not open file " << name_file << std::endl; - } - } -}; - -} // namespace alphashapes - -} // namespace Gudhi - -#endif // SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ diff --git a/src/Alpha_shapes/test/Alpha_shapes_unit_test.cpp b/src/Alpha_shapes/test/Alpha_shapes_unit_test.cpp deleted file mode 100644 index b4c32321..00000000 --- a/src/Alpha_shapes/test/Alpha_shapes_unit_test.cpp +++ /dev/null @@ -1,126 +0,0 @@ -/* 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): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * 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 <http://www.gnu.org/licenses/>. - */ - -#define BOOST_TEST_MODULE alpha_shapes test -#include <boost/test/included/unit_test.hpp> -#include <boost/system/error_code.hpp> -#include <boost/chrono/thread_clock.hpp> -// to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" -#include "gudhi/Alpha_shapes.h" - -// to construct a simplex_tree from Delaunay_triangulation -#include "gudhi/graph_simplicial_complex.h" -#include "gudhi/Simplex_tree.h" - -#include <CGAL/Delaunay_triangulation.h> -#include <CGAL/Epick_d.h> -#include <CGAL/point_generators_d.h> -#include <CGAL/algorithm.h> -#include <CGAL/assertions.h> - -#include <iostream> -#include <iterator> - -#include <stdio.h> -#include <stdlib.h> -#include <string> - -// Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; -typedef CGAL::Delaunay_triangulation<K> T; -// The triangulation uses the default instanciation of the -// TriangulationDataStructure template parameter - -BOOST_AUTO_TEST_CASE( OFF_file ) { - // ---------------------------------------------------------------------------- - // - // Init of an alpha-shape from a OFF file - // - // ---------------------------------------------------------------------------- - std::string off_file_name("S4_100.off"); - std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_file(off_file_name, 4); - - const int DIMENSION = 4; - std::cout << "alpha_shapes_from_file.dimension()=" << alpha_shapes_from_file.dimension() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.dimension() == DIMENSION); - - const double FILTRATION = 0.0; - std::cout << "alpha_shapes_from_file.filtration()=" << alpha_shapes_from_file.filtration() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.filtration() == FILTRATION); - - const int NUMBER_OF_VERTICES = 100; - std::cout << "alpha_shapes_from_file.num_vertices()=" << alpha_shapes_from_file.num_vertices() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.num_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_SIMPLICES = 6779; - std::cout << "alpha_shapes_from_file.num_simplices()=" << alpha_shapes_from_file.num_simplices() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.num_simplices() == NUMBER_OF_SIMPLICES); - -} - -BOOST_AUTO_TEST_CASE( Delaunay_triangulation ) { - // ---------------------------------------------------------------------------- - // - // Init of an alpha-shape from a Delauny triangulation - // - // ---------------------------------------------------------------------------- - T dt(8); - std::string off_file_name("S8_10.off"); - std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - - Gudhi::alphashapes::Delaunay_triangulation_off_reader<T> off_reader(off_file_name, dt, true, true); - std::cout << "off_reader.is_valid()=" << off_reader.is_valid() << std::endl; - BOOST_CHECK(off_reader.is_valid()); - - const int NUMBER_OF_VERTICES = 10; - std::cout << "dt.number_of_vertices()=" << dt.number_of_vertices() << std::endl; - BOOST_CHECK(dt.number_of_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_FULL_CELLS = 30; - std::cout << "dt.number_of_full_cells()=" << dt.number_of_full_cells() << std::endl; - BOOST_CHECK(dt.number_of_full_cells() == NUMBER_OF_FULL_CELLS); - - const int NUMBER_OF_FINITE_FULL_CELLS = 6; - std::cout << "dt.number_of_finite_full_cells()=" << dt.number_of_finite_full_cells() << std::endl; - BOOST_CHECK(dt.number_of_finite_full_cells() == NUMBER_OF_FINITE_FULL_CELLS); - - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_dt(dt); - - const int DIMENSION = 8; - std::cout << "alpha_shapes_from_dt.dimension()=" << alpha_shapes_from_dt.dimension() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.dimension() == DIMENSION); - - const double FILTRATION = 0.0; - std::cout << "alpha_shapes_from_dt.filtration()=" << alpha_shapes_from_dt.filtration() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.filtration() == FILTRATION); - - std::cout << "alpha_shapes_from_dt.num_vertices()=" << alpha_shapes_from_dt.num_vertices() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.num_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_SIMPLICES = 997; - std::cout << "alpha_shapes_from_dt.num_simplices()=" << alpha_shapes_from_dt.num_simplices() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.num_simplices() == NUMBER_OF_SIMPLICES); -} - diff --git a/src/Alpha_shapes/test/CMakeLists.txt b/src/Alpha_shapes/test/CMakeLists.txt deleted file mode 100644 index e0d33827..00000000 --- a/src/Alpha_shapes/test/CMakeLists.txt +++ /dev/null @@ -1,48 +0,0 @@ -cmake_minimum_required(VERSION 2.6) -project(GUDHIAlphaShapesUT) - -# need CGAL 4.6 -# cmake -DCGAL_DIR=~/workspace/CGAL-4.6-beta1 ../../.. -if(CGAL_FOUND) - if (NOT CGAL_VERSION VERSION_LESS 4.6.0) - message(STATUS "CGAL version: ${CGAL_VERSION}.") - - include( ${CGAL_USE_FILE} ) - - find_package(Eigen3 3.1.0) - if (EIGEN3_FOUND) - message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") - include( ${EIGEN3_USE_FILE} ) - include_directories (BEFORE "../../include") - - if (GCOVR_PATH) - # for gcovr to make coverage reports - Corbera Jenkins plugin - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage") - set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -fprofile-arcs -ftest-coverage") - set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -fprofile-arcs -ftest-coverage") - endif() - if (GPROF_PATH) - # for gprof to make coverage reports - Jenkins - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") - set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -pg") - set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pg") - endif() - - # uncomment to display debug traces - # add_definitions(-DDEBUG_TRACES) - add_executable ( AlphaShapesUT Alpha_shapes_unit_test.cpp ) - target_link_libraries(AlphaShapesUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) - add_test(NAME AlphaShapesUT - COMMAND ${CMAKE_CURRENT_BINARY_DIR}/AlphaShapesUT - # XML format for Jenkins xUnit plugin - --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/AlphaShapesUT.xml --log_level=test_suite --report_level=no) - - - else() - message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") - endif() - else() - message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") - endif () -endif() - diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 3be05c4f..7b30f77a 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -39,12 +39,13 @@ else() LINK_DIRECTORIES(${Boost_LIBRARY_DIRS}) include_directories(include/) + add_subdirectory(example/common) add_subdirectory(example/Simplex_tree) add_subdirectory(example/Persistent_cohomology) add_subdirectory(example/Skeleton_blocker) add_subdirectory(example/Contraction) add_subdirectory(example/Hasse_complex) - add_subdirectory(example/Alpha_shapes) + add_subdirectory(example/Alpha_complex) add_subdirectory(example/Bottleneck) # GudhUI diff --git a/src/Doxyfile b/src/Doxyfile index 62412627..0724de1c 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -672,7 +672,7 @@ LAYOUT_FILE = # search path. Do not use file names with spaces, bibtex cannot handle them. See # also \cite for info how to create references. -CITE_BIB_FILES = ../biblio/bibliography.bib +CITE_BIB_FILES = biblio/bibliography.bib #--------------------------------------------------------------------------- # Configuration options related to warning and progress messages @@ -811,7 +811,8 @@ EXCLUDE_SYMBOLS = # that contain example code fragments that are included (see the \include # command). -EXAMPLE_PATH = +EXAMPLE_PATH = example/common/ \ + example/Alpha_complex/ # If the value of the EXAMPLE_PATH tag contains directories, you can use the # EXAMPLE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp and @@ -831,9 +832,10 @@ EXAMPLE_RECURSIVE = NO # that contain images that are to be included in the documentation (see the # \image command). -IMAGE_PATH = Skeleton_blocker/doc/ \ - common/doc/ \ - Contraction/doc/ +IMAGE_PATH = doc/Skeleton_blocker/ \ + doc/Alpha_complex/ \ + doc/common/ \ + doc/Contraction/ # The INPUT_FILTER tag can be used to specify a program that doxygen should @@ -1595,7 +1597,7 @@ PAPER_TYPE = a4 # If left blank no extra packages will be included. # This tag requires that the tag GENERATE_LATEX is set to YES. -EXTRA_PACKAGES = amsfonts amsmath amssymb +EXTRA_PACKAGES = amsfonts amsmath amssymb algorithm algpseudocode # The LATEX_HEADER tag can be used to specify a personal LaTeX header for the # generated LaTeX document. The header should contain everything until the first diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 9d0cf755..5239c859 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -37,7 +37,6 @@ #include <vector> namespace Gudhi { - /** \defgroup simplex_tree Filtered Complexes * * A simplicial complex \f$\mathbf{K}\f$ @@ -84,8 +83,8 @@ namespace Gudhi { * */ template<typename IndexingTag = linear_indexing_tag, - typename FiltrationValue = double, typename SimplexKey = int // must be a signed integer type - , typename VertexHandle = int // must be a signed integer type, int convertible to it +typename FiltrationValue = double, typename SimplexKey = int // must be a signed integer type +, typename VertexHandle = int // must be a signed integer type, int convertible to it // , bool ContiguousVertexHandles = true //true is Vertex_handles are exactly the set [0;n) > class Simplex_tree { @@ -245,6 +244,7 @@ class Simplex_tree { Filtration_simplex_range filtration_simplex_range() { return filtration_simplex_range(Indexing_tag()); } + /** \brief Returns a range over the vertices of a simplex. * * The order in which the vertices are visited is the decreasing order for < on Vertex_handles, @@ -316,12 +316,14 @@ class Simplex_tree { Simplex_key key(Simplex_handle sh) { return sh->second.key(); } + /** \brief Returns the simplex associated to a key. * * The filtration must be initialized. */ Simplex_handle simplex(Simplex_key key) { return filtration_vect_[key]; } + /** \brief Returns the filtration value of a simplex. * * Called on the null_simplex, returns INFINITY. */ @@ -330,12 +332,23 @@ class Simplex_tree { return sh->second.filtration(); } else { return INFINITY; - } // filtration(); } + } + } + + /** \brief Sets the filtration value of a simplex. + * + * No action if called on the null_simplex*/ + void assign_filtration(Simplex_handle sh, Filtration_value fv) { + if (sh != null_simplex()) { + sh->second.assign_filtration(fv); + } } + /** \brief Returns an upper bound of the filtration values of the simplices. */ Filtration_value filtration() const { return threshold_; } + /** \brief Returns a Simplex_handle different from all Simplex_handles * associated to the simplices in the simplicial complex. * @@ -343,20 +356,24 @@ class Simplex_tree { Simplex_handle null_simplex() const { return Dictionary_it(NULL); } + /** \brief Returns a key different for all keys associated to the * simplices of the simplicial complex. */ Simplex_key null_key() const { return -1; } + /** \brief Returns a Vertex_handle different from all Vertex_handles associated * to the vertices of the simplicial complex. */ Vertex_handle null_vertex() const { return null_vertex_; } + /** \brief Returns the number of vertices in the complex. */ size_t num_vertices() const { return root_.members_.size(); } + /** \brief Returns the number of simplices in the complex. * * Does not count the empty simplex. */ @@ -376,6 +393,7 @@ class Simplex_tree { } return dim - 1; } + /** \brief Returns an upper bound on the dimension of the simplicial complex. */ int dimension() const { return dimension_; @@ -423,7 +441,6 @@ class Simplex_tree { Simplex_handle find_vertex(Vertex_handle v) { return root_.members_.begin() + v; } -//{ return root_.members_.find(v); } /** \brief Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex. * @@ -479,7 +496,6 @@ class Simplex_tree { return res_insert; } - /** \brief Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of * Vertex_handles, in the simplicial complex. * @@ -487,33 +503,35 @@ class Simplex_tree { * @param[in] filtration the filtration value assigned to the new N-simplex. */ template<class RandomAccessVertexRange> - void insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, - Filtration_value filtration = 0.0) { + std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, + Filtration_value filtration = 0.0) { + std::pair<Simplex_handle, bool> returned; if (Nsimplex.size() > 1) { for (unsigned int NIndex = 0; NIndex < Nsimplex.size(); NIndex++) { // insert N (N-1)-Simplex RandomAccessVertexRange NsimplexMinusOne; for (unsigned int NListIter = 0; NListIter < Nsimplex.size() - 1; NListIter++) { // (N-1)-Simplex creation - NsimplexMinusOne.push_back( Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); + NsimplexMinusOne.push_back(Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); } // (N-1)-Simplex recursive call - insert_simplex_and_subfaces(NsimplexMinusOne, filtration); + returned = insert_simplex_and_subfaces(NsimplexMinusOne, filtration); } // N-Simplex insert - std::pair<Simplex_handle, bool> returned = insert_simplex(Nsimplex, filtration); + returned = insert_simplex(Nsimplex, filtration); if (returned.second == true) { num_simplices_++; } } else if (Nsimplex.size() == 1) { // 1-Simplex insert - End of recursivity - std::pair<Simplex_handle, bool> returned = insert_simplex(Nsimplex, filtration); + returned = insert_simplex(Nsimplex, filtration); if (returned.second == true) { num_simplices_++; } } else { // Nothing to insert - empty vector } + return returned; } /** \brief Assign a value 'key' to the key of the simplex @@ -540,17 +558,6 @@ class Simplex_tree { return sh->second.children(); } -// void display_simplex(Simplex_handle sh) -// { -// std::cout << " " << "[" << filtration(sh) << "] "; -// for( auto vertex : simplex_vertex_range(sh) ) -// { std::cout << vertex << " "; } -// } - - // void print(Simplex_handle sh, std::ostream& os = std::cout) - // { for(auto v : simplex_vertex_range(sh)) {os << v << " ";} - // os << std::endl; } - public: /** Returns a pointer to the root nodes of the simplex tree. */ Siblings * root() { @@ -562,10 +569,12 @@ class Simplex_tree { void set_filtration(Filtration_value fil) { threshold_ = fil; } + /** Set a number of simplices for the simplicial complex. */ void set_num_simplices(unsigned int num_simplices) { num_simplices_ = num_simplices; } + /** Set a dimension for the simplicial complex. */ void set_dimension(int dimension) { dimension_ = dimension; @@ -623,6 +632,7 @@ class Simplex_tree { } return ((it1 == rg1.end()) && (it2 != rg2.end())); } + /** \brief StrictWeakOrdering, for the simplices, defined by the filtration. * * It corresponds to the partial order @@ -631,8 +641,7 @@ class Simplex_tree { * to be smaller. The filtration function must be monotonic. */ struct is_before_in_filtration { explicit is_before_in_filtration(Simplex_tree * st) - : st_(st) { - } + : st_(st) { } bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const { if (st_->filtration(sh1) != st_->filtration(sh2)) { @@ -708,6 +717,7 @@ class Simplex_tree { } } } + /** \brief Expands the Simplex_tree containing only its one skeleton * until dimension max_dim. * @@ -731,6 +741,7 @@ class Simplex_tree { } private: + /** \brief Recursive expansion of the simplex tree.*/ void siblings_expansion(Siblings * siblings, // must contain elements int k) { @@ -769,6 +780,7 @@ class Simplex_tree { } } } + /** \brief Intersects Dictionary 1 [begin1;end1) with Dictionary 2 [begin2,end2) * and assigns the maximal possible Filtration_value to the Nodes. */ static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection, @@ -800,6 +812,7 @@ class Simplex_tree { } } } + /** Maximum over 3 values.*/ static Filtration_value maximum(Filtration_value a, Filtration_value b, Filtration_value c) { diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 315aa0ac..770d2216 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -48,8 +48,10 @@ CGAL is a C++ library which provides easy access to efficient and reliable geome The following example requires the <a href="http://www.cgal.org/">Computational Geometry Algorithms Library</a> (CGAL) and will not be built if CGAL is not installed: - Simplex_tree/simplex_tree_from_alpha_shapes_3 + - Alpha_complex/Alpha_complex_from_off + - Alpha_complex/Alpha_complex_from_points -Having CGAL version 4.4 or higher installed is recommended. The procedure to install this library according to +Having CGAL version 4.7 or higher installed is recommended. The procedure to install this library according to your operating system is detailed here http://doc.cgal.org/latest/Manual/installation.html \subsection demos Demos and examples diff --git a/src/Alpha_shapes/example/CMakeLists.txt b/src/common/example/CMakeLists.txt index 753238a5..4cb03dbe 100644 --- a/src/Alpha_shapes/example/CMakeLists.txt +++ b/src/common/example/CMakeLists.txt @@ -1,8 +1,7 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHIAlphaShapesExample) +project(GUDHIDelaunayTriangulationOffFileReadWrite) # need CGAL 4.6 -# cmake -DCGAL_DIR=~/workspace/CGAL-4.6-beta1 ../../.. if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.6.0) message(STATUS "CGAL version: ${CGAL_VERSION}.") @@ -13,16 +12,11 @@ if(CGAL_FOUND) if (EIGEN3_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) - include_directories (BEFORE "../../include") - + add_executable ( dtoffrw Delaunay_triangulation_off_rw.cpp ) target_link_libraries(dtoffrw ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test(dtoffrw_tore3D ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off 3) + add_test(dtoffrw ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw ${CMAKE_SOURCE_DIR}/data/points/alphacomplexdoc.off ${CMAKE_CURRENT_BINARY_DIR}/result.off) - # uncomment to display debug traces - # add_definitions(-DDEBUG_TRACES) - add_executable ( stfromdt Simplex_tree_from_delaunay_triangulation.cpp ) - target_link_libraries(stfromdt ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) else() message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") endif() diff --git a/src/common/example/Delaunay_triangulation_off_rw.cpp b/src/common/example/Delaunay_triangulation_off_rw.cpp new file mode 100644 index 00000000..d1aa7988 --- /dev/null +++ b/src/common/example/Delaunay_triangulation_off_rw.cpp @@ -0,0 +1,55 @@ +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string> + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; +typedef CGAL::Delaunay_triangulation<K> T; +// The triangulation uses the default instantiation of the +// TriangulationDataStructure template parameter + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << " inputFile.off outputFile.off" << std::endl; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if (argc != 3) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; + usage(argv[0]); + } + + std::string offInputFile(argv[1]); + // Read the OFF file (input file name given as parameter) and triangulates points + Gudhi::Delaunay_triangulation_off_reader<T> off_reader(offInputFile); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << offInputFile << std::endl; + exit(-1); // ----- >> + } + + // Retrieve the triangulation + T* triangulation = off_reader.get_complex(); + // Operations on triangulation + std::cout << "Number of vertices= " << triangulation->number_of_vertices() << std::endl; + std::cout << "Number of finite full cells= " << triangulation->number_of_finite_full_cells() << std::endl; + + std::string outFileName(argv[2]); + std::string offOutputFile(outFileName); + // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces + Gudhi::Delaunay_triangulation_off_writer<T> off_writer(offOutputFile, triangulation); + + // Check the write operation was correct + if (!off_writer.is_valid()) { + std::cerr << "Unable to write file " << offOutputFile << std::endl; + exit(-1); // ----- >> + } + + return 0; +}
\ No newline at end of file diff --git a/src/common/example/dtoffrw_alphashapedoc_result.txt b/src/common/example/dtoffrw_alphashapedoc_result.txt new file mode 100644 index 00000000..57761d14 --- /dev/null +++ b/src/common/example/dtoffrw_alphashapedoc_result.txt @@ -0,0 +1,3 @@ +Number of vertices= 7 +Number of finite full cells= 6 + diff --git a/src/common/include/gudhi/Delaunay_triangulation_off_io.h b/src/common/include/gudhi/Delaunay_triangulation_off_io.h new file mode 100644 index 00000000..de5fa2af --- /dev/null +++ b/src/common/include/gudhi/Delaunay_triangulation_off_io.h @@ -0,0 +1,308 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * 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 <http://www.gnu.org/licenses/>. + */ +#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ +#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ + +#include <string> +#include <vector> +#include <fstream> +#include <map> + +#include "gudhi/Off_reader.h" + +namespace Gudhi { + +/** \brief OFF file visitor implementation according to Off_reader in order to construct 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/ + */ +template<typename Complex> +class Delaunay_triangulation_off_visitor_reader { + private: + Complex* _complex; + typedef typename Complex::Point Point; + + public: + + // TODO(VR) : Pass a Complex as a parameter is required, even if not used. Otherwise, compilation is KO. + + /** \brief Delaunay_triangulation_off_visitor_reader constructor + * + * @param[in] _complex_ptr pointer on a Delaunay triangulation. + */ + Delaunay_triangulation_off_visitor_reader(Complex* _complex_ptr) + : _complex(nullptr) { } + + /** \brief Off_reader visitor init implementation. + * + * The init parameters are set from OFF file header. + * Dimension value is required in order to construct Delaunay triangulation. + * + * @param[in] dim space dimension of vertices. + * @param[in] num_vertices number of vertices in the OFF file (not used). + * @param[in] num_faces number of faces in the OFF file (not used). + * @param[in] num_edges number of edges in the OFF file (not used). + */ + void init(int dim, int num_vertices, int num_faces, int num_edges) { +#ifdef DEBUG_TRACES + std::cout << "Delaunay_triangulation_off_visitor_reader::init - dim=" << dim << " - num_vertices=" << + num_vertices << " - num_faces=" << num_faces << " - num_edges=" << num_edges << std::endl; +#endif // DEBUG_TRACES + if (num_faces > 0) { + std::cerr << "Delaunay_triangulation_off_visitor_reader::init faces are not taken into account from OFF " << + "file for Delaunay triangulation - faces are computed." << std::endl; + } + if (num_edges > 0) { + std::cerr << "Delaunay_triangulation_off_visitor_reader::init edges are not taken into account from OFF " << + "file for Delaunay triangulation - edges are computed." << std::endl; + } + // Complex construction with dimension from file + _complex = new Complex(dim); + } + + /** \brief Off_reader visitor point implementation. + * + * The point function is called on each vertex line from OFF file. + * This function inserts the vertex in the Delaunay triangulation. + * + * @param[in] point vector of vertex coordinates. + */ + void point(const std::vector<double>& point) { +#ifdef DEBUG_TRACES + std::cout << "Delaunay_triangulation_off_visitor_reader::point "; + for (auto coordinate : point) { + std::cout << coordinate << " | "; + } + std::cout << std::endl; +#endif // DEBUG_TRACES + _complex->insert(Point(point.size(), point.begin(), point.end())); + } + + // Off_reader visitor maximal_face implementation - not used + void maximal_face(const std::vector<int>& face) { + // For Delaunay Triangulation, only points are read + } + + // Off_reader visitor done implementation - not used + void done() { + // Nothing to be done on end of OFF file read + } + + /** \brief Returns the constructed Delaunay triangulation. + * + * @return A pointer on the Delaunay triangulation. + * + * @warning The returned pointer can be nullptr. + */ + Complex* get_complex() const { + return _complex; + } +}; + +/** \brief OFF file reader implementation in order to construct a Delaunay triangulation. + * + * This class is using the Delaunay_triangulation_off_visitor_reader to visit the OFF file according to Off_reader. + * + * For more informations on CGAL Delaunay triangulation, please refer to the corresponding chapter in page + * http://doc.cgal.org/latest/Triangulation/ + * + * \section Example + * + * This example loads points from an OFF file and builds the Delaunay triangulation. + * Then, it is asked to display the number of vertices and finites full cells from the Delaunay triangulation. + * + * \include Delaunay_triangulation_off_rw.cpp + * + * When launching: + * + * \code $> ./dtoffrw ../../data/points/alphashapedoc.off triangulated.off + * \endcode + * + * the program output is: + * + * \include dtoffrw_alphashapedoc_result.txt + */ +template<typename Complex> +class Delaunay_triangulation_off_reader { + public: + + /** \brief Reads the OFF file and constructs the Delaunay triangulation from the points + * that are in the OFF file. + * + * @param[in] name_file OFF file to read. + * + * @warning Check with is_valid() function to see if read operation was successful. + */ + Delaunay_triangulation_off_reader(const std::string & name_file) + : valid_(false) { + std::ifstream stream(name_file); + if (stream.is_open()) { + Delaunay_triangulation_off_visitor_reader<Complex> off_visitor(_complex); + Off_reader off_reader(stream); + valid_ = off_reader.read(off_visitor); + if (valid_) { + _complex = off_visitor.get_complex(); + if (_complex == nullptr) { + std::cerr << "Delaunay_triangulation_off_reader::Delaunay_triangulation_off_reader off_visitor returns an empty pointer" << std::endl; + valid_ = false; + } + } + } else { + std::cerr << "Delaunay_triangulation_off_reader::Delaunay_triangulation_off_reader could not open file " << + name_file << std::endl; + } + + } + + /** \brief Returns if the OFF file read operation was successful or not. + * + * @return OFF file read status. + */ + bool is_valid() const { + return valid_; + } + + /** \brief Returns the constructed Delaunay triangulation. + * + * @return A pointer on the Delaunay triangulation. + * + * @warning The returned pointer can be nullptr. + */ + Complex* get_complex() const { + if (valid_) + return _complex; + return nullptr; + + } + + private: + /** \brief OFF file read status.*/ + bool valid_; + /** \brief A pointer on the Delaunay triangulation.*/ + Complex* _complex; +}; + +/** \brief OFF file writer from a Delaunay triangulation. + * + * This class constructs the OFF file header according to http://www.geomview.org/docs/html/OFF.html + * + * The header is followed by the list of points coordinates (Delaunay triangulation vertices) + * + * And finally is followed by the list of faces (Delaunay triangulation finite full cells) + * + * For more informations on CGAL Delaunay triangulation, please refer to the corresponding chapter in page + * http://doc.cgal.org/latest/Triangulation/ + * + * \section Example + * + * This example loads points from an OFF file and builds the Delaunay triangulation. + * Then, the Delaunay triangulation is saved in a new file including the triangulation as a list of faces. + * + * \include Delaunay_triangulation_off_rw.cpp + * + * When launching: + * + * \code $> ./dtoffrw ../../data/points/alphashapedoc.off triangulated.off + * \endcode + * + * The result will be an OFF file of dimension 2 with the 7 points from alphashapedoc.off followed by the 6 + * triangulations of dimension 3 (the first value on each faces): + * \include dtoffrw_alphashapedoc_result.off + */ +template<typename Complex> +class Delaunay_triangulation_off_writer { + public: + typedef typename Complex::Point Point; + + /** \brief Writes the OFF file from the Delaunay triangulation + * + * @param[in] name_file OFF file to write. + * @param[in] complex_ptr pointer on a Delaunay triangulation. + * + * @warning Check with is_valid() function to see if write operation was successful. + */ + Delaunay_triangulation_off_writer(const std::string & name_file, Complex* complex_ptr) + : valid_(false) { + std::ofstream stream(name_file); + if (stream.is_open()) { + if (complex_ptr->current_dimension() == 3) { + // OFF header + stream << "OFF" << std::endl; + // no endl on next line - don't know why... + stream << complex_ptr->number_of_vertices() << " " << complex_ptr->number_of_finite_full_cells() << " 0"; + } else { + // nOFF header + stream << "nOFF" << std::endl; + // no endl on next line - don't know why... + stream << complex_ptr->current_dimension() << " " << complex_ptr->number_of_vertices() << " " << + complex_ptr->number_of_finite_full_cells() << " 0"; + + } + + // bimap to retrieve vertex handles from points and vice versa + std::map< Point, int > points_to_vh; + // Start to insert at default handle value + int vertex_handle = int(); + + // Points list + for (auto vit = complex_ptr->vertices_begin(); vit != complex_ptr->vertices_end(); ++vit) { + for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { + stream << *Coord << " "; + } + stream << std::endl; + points_to_vh[vit->point()] = vertex_handle; + vertex_handle++; + } + + for (auto cit = complex_ptr->finite_full_cells_begin(); cit != complex_ptr->finite_full_cells_end(); ++cit) { + std::vector<int> vertexVector; + stream << std::distance(cit->vertices_begin(), cit->vertices_end()) << " "; + for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { + stream << points_to_vh[(*vit)->point()] << " "; + } + stream << std::endl; + } + stream.close(); + valid_ = true; + } else { + std::cerr << "Delaunay_triangulation_off_writer::Delaunay_triangulation_off_writer could not open file " << + name_file << std::endl; + } + } + + /** \brief Returns if the OFF write operation was successful or not. + * + * @return OFF file write status. + */ + bool is_valid() const { + return valid_; + } + + private: + /* \brief OFF file write status. */ + bool valid_; +}; + +} // namespace Gudhi + +#endif // SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ diff --git a/src/common/include/gudhi/Off_reader.h b/src/common/include/gudhi/Off_reader.h index e29218d8..a8abb507 100644 --- a/src/common/include/gudhi/Off_reader.h +++ b/src/common/include/gudhi/Off_reader.h @@ -7,7 +7,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) * * 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 @@ -36,163 +36,150 @@ namespace Gudhi { -/** - * Read an off file and calls a visitor methods while reading it. - * An off file must have its first/snd line in this format : - * OFF - * num_vert num_faces num_edges - * - * A noff file must have its first/snd line in this format : - * nOFF - * dim num_vert num_faces num_edges - * - * The number of edges num_edges is optional and can be left to zero. +/** \brief OFF file reader top class visitor. + * + * OFF file must be conform to format described here : + * http://www.geomview.org/docs/html/OFF.html */ -class Off_reader{ -public: - Off_reader(std::ifstream& stream):stream_(stream){ - } -// Off_reader(const std::string& name):stream_(name){ -// if(!stream_.is_open()) -// std::cerr <<"could not open file \n"; -// } - - ~Off_reader(){ - stream_.close(); - } - - /** - * read an off file and calls the following methods : - * void init(int dim,int num_vertices,int num_faces,int num_edges); //num_edges may not be set - * void point(const std::vector<double>& point); - * void maximal_face(const std::list<int>& face); - * void done(); - * of the visitor when reading a point or a maximal face. - */ - template<typename OffVisitor> - bool read(OffVisitor& off_visitor){ - bool success_read_off_preambule = read_off_preambule(off_visitor); - if(!success_read_off_preambule) { - std::cerr <<"could not read off preambule\n"; - return false; - } - - bool success_read_off_points = read_off_points(off_visitor); - if(!success_read_off_points) { - std::cerr <<"could not read off points\n"; - return false; - } - - bool success_read_off_faces = read_off_faces(off_visitor); - if(!success_read_off_faces) { - std::cerr <<"could not read off faces\n"; - return false; - } - - off_visitor.done(); - return success_read_off_preambule && success_read_off_points && success_read_off_faces; - } - -private: - std::ifstream& stream_; - - struct Off_info{ - int dim; - int num_vertices; - int num_edges; - int num_faces; - }; - - Off_info off_info_; - - template<typename OffVisitor> - bool read_off_preambule(OffVisitor& off_visitor){ - std::string line; - if(!goto_next_uncomment_line(line)) return false; - - bool is_off_file = (line.find("OFF") != std::string::npos); - bool is_noff_file = (line.find("nOFF") != std::string::npos); - - if(!is_off_file && !is_noff_file) { - std::cerr << line<<std::endl; - std::cerr << "missing off header\n"; - return false; - } - - if(!goto_next_uncomment_line(line)) return false; - std::istringstream iss(line); - if(is_off_file){ - off_info_.dim = 3; - if(!(iss >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)){ - std::cerr << "incorrect number of vertices/faces/edges\n"; - return false; - } - } - else - if(!(iss >> off_info_.dim >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)){ - std::cerr << "incorrect number of vertices/faces/edges\n"; - return false; - } - off_visitor.init(off_info_.dim,off_info_.num_vertices,off_info_.num_faces,off_info_.num_edges); - - return true; - } - - bool goto_next_uncomment_line(std::string& uncomment_line){ - uncomment_line.clear(); - do - std::getline(stream_, uncomment_line); - while(uncomment_line[0] == '%');// || uncomment_line.empty()); - return (uncomment_line.size()>0 && uncomment_line[0] != '%'); - } - - - template<typename OffVisitor> - bool read_off_points(OffVisitor& visitor){ - int num_vertices_to_read = off_info_.num_vertices; - while(num_vertices_to_read--){ - std::string line; - if(!goto_next_uncomment_line(line)) return false; - std::vector<double> point; - std::istringstream iss(line); - point.assign(std::istream_iterator<double>(iss),std::istream_iterator<double>()); -// if(point.size() != off_info_.dim) return false; - visitor.point(point); - } - return true; - } - - template<typename OffVisitor> - bool read_off_faces(OffVisitor& visitor){ - std::string line; - while(goto_next_uncomment_line(line)){ - std::istringstream iss(line); - int num_face_vertices; - iss >> num_face_vertices; - std::vector<int> face; - face.assign(std::istream_iterator<int>(iss),std::istream_iterator<int>()); - if(!face.size() == off_info_.num_vertices) return false; - visitor.maximal_face(face); - } - return true; - } +class Off_reader { + public: + + Off_reader(std::ifstream& stream) : stream_(stream) { } + + ~Off_reader() { + stream_.close(); + } + + /** \brief + * Read an OFF file and calls the following methods : + * + * <CODE>void init(int dim,int num_vertices,int num_faces,int num_edges); // from file header - num_edges may not be set + * + * void point(const std::vector<double>& point); // for each point read + * + * void maximal_face(const std::list<int>& face); // for each face read + * + * void done(); // upon file read is finished</CODE> + * + * of the visitor when reading a point or a maximal face. Edges are not taken into account. + */ + template<typename OffVisitor> + bool read(OffVisitor& off_visitor) { + bool success_read_off_preambule = read_off_preambule(off_visitor); + if (!success_read_off_preambule) { + std::cerr << "could not read off preambule\n"; + return false; + } + + bool success_read_off_points = read_off_points(off_visitor); + if (!success_read_off_points) { + std::cerr << "could not read off points\n"; + return false; + } + + bool success_read_off_faces = read_off_faces(off_visitor); + if (!success_read_off_faces) { + std::cerr << "could not read off faces\n"; + return false; + } + + off_visitor.done(); + return success_read_off_preambule && success_read_off_points && success_read_off_faces; + } + + private: + std::ifstream& stream_; + + struct Off_info { + int dim; + int num_vertices; + int num_edges; + int num_faces; + }; + + Off_info off_info_; + + template<typename OffVisitor> + bool read_off_preambule(OffVisitor& off_visitor) { + std::string line; + if (!goto_next_uncomment_line(line)) return false; + + bool is_off_file = (line.find("OFF") != std::string::npos); + bool is_noff_file = (line.find("nOFF") != std::string::npos); + + if (!is_off_file && !is_noff_file) { + std::cerr << line << std::endl; + std::cerr << "missing off header\n"; + return false; + } + + if (!goto_next_uncomment_line(line)) return false; + std::istringstream iss(line); + if ((is_off_file) && (!is_noff_file)) { + off_info_.dim = 3; + if (!(iss >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)) { + std::cerr << "incorrect number of vertices/faces/edges\n"; + return false; + } + } else + if (!(iss >> off_info_.dim >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)) { + std::cerr << "incorrect number of vertices/faces/edges\n"; + return false; + } + off_visitor.init(off_info_.dim, off_info_.num_vertices, off_info_.num_faces, off_info_.num_edges); + + return true; + } + + bool goto_next_uncomment_line(std::string& uncomment_line) { + uncomment_line.clear(); + do + std::getline(stream_, uncomment_line); while (uncomment_line[0] == '%'); + return (uncomment_line.size() > 0 && uncomment_line[0] != '%'); + } + + template<typename OffVisitor> + bool read_off_points(OffVisitor& visitor) { + int num_vertices_to_read = off_info_.num_vertices; + while (num_vertices_to_read--) { + std::string line; + if (!goto_next_uncomment_line(line)) return false; + std::vector<double> point; + std::istringstream iss(line); + point.assign(std::istream_iterator<double>(iss), std::istream_iterator<double>()); + // if(point.size() != off_info_.dim) return false; + visitor.point(point); + } + return true; + } + + template<typename OffVisitor> + bool read_off_faces(OffVisitor& visitor) { + std::string line; + while (goto_next_uncomment_line(line)) { + std::istringstream iss(line); + int num_face_vertices; + iss >> num_face_vertices; + std::vector<int> face; + face.assign(std::istream_iterator<int>(iss), std::istream_iterator<int>()); + if (!face.size() == off_info_.num_vertices) return false; + visitor.maximal_face(face); + } + return true; + } }; - template<typename OFFVisitor> -void read_off(const std::string& name_file_off,OFFVisitor& vis){ - std::ifstream stream(name_file_off); - if(!stream.is_open()) - std::cerr <<"could not open file \n"; - else{ - Off_reader off_reader(stream); - off_reader.read(vis); - } +void read_off(const std::string& name_file_off, OFFVisitor& vis) { + std::ifstream stream(name_file_off); + if (!stream.is_open()) + std::cerr << "could not open file \n"; + else { + Off_reader off_reader(stream); + off_reader.read(vis); + } } - - } // namespace Gudhi - -#endif /* GUDHI_OFF_READER_H_ */ +#endif // GUDHI_OFF_READER_H_ diff --git a/src/common/test/CMakeLists.txt b/src/common/test/CMakeLists.txt new file mode 100644 index 00000000..1b4dd6e0 --- /dev/null +++ b/src/common/test/CMakeLists.txt @@ -0,0 +1,41 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIDelaunayTriangulationOffFileReadWriteUT) + +if(NOT MSVC) + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} --coverage") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} --coverage") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} --coverage") +endif() + +# need CGAL 4.6 +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.6.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + + add_executable ( dtoffrw_UT dtoffrw_unit_test.cpp ) + target_link_libraries(dtoffrw_UT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + + # Unitary tests + add_test(dtoffrw_UT ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_UT + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/dtoffrw_UT.xml --log_level=test_suite --report_level=no) + + if (DIFF_PATH) + add_test(dtoffrw_diff_files_UT ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/UT.off ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_alphashapedoc_result.off) + endif() + + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") + endif () +endif() + diff --git a/src/common/test/README b/src/common/test/README new file mode 100644 index 00000000..f2a7eb5a --- /dev/null +++ b/src/common/test/README @@ -0,0 +1,14 @@ +To compile: +*********** + +cmake . +make + +To launch with details: +*********************** + +./dtoffrw_UT --report_level=detailed --log_level=all + + ==> echo $? returns 0 in case of success (non-zero otherwise) + + diff --git a/src/common/test/dtoffrw_alphashapedoc_result.off b/src/common/test/dtoffrw_alphashapedoc_result.off new file mode 100644 index 00000000..13c255c6 --- /dev/null +++ b/src/common/test/dtoffrw_alphashapedoc_result.off @@ -0,0 +1,15 @@ +nOFF +2 7 6 0 +1 1 +7 0 +4 6 +9 6 +0 14 +2 19 +9 17 +3 1 2 3 +3 4 3 2 +3 5 1 3 +3 5 3 7 +3 7 3 4 +3 6 5 7 diff --git a/src/common/test/dtoffrw_unit_test.cpp b/src/common/test/dtoffrw_unit_test.cpp new file mode 100644 index 00000000..d2705955 --- /dev/null +++ b/src/common/test/dtoffrw_unit_test.cpp @@ -0,0 +1,91 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#define BOOST_TEST_MODULE DelaunayTriangulationOffFileReadWrite test + +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string> + +#include <boost/test/included/unit_test.hpp> +#include <boost/system/error_code.hpp> +//#include <boost/chrono/thread_clock.hpp> + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; +typedef CGAL::Delaunay_triangulation<K> T; + +BOOST_AUTO_TEST_CASE( Delaunay_triangulation_doc_test ) +{ + // Read the OFF file (input file name given as parameter) and triangulates points + Gudhi::Delaunay_triangulation_off_reader<T> off_reader("../../../data/points/alphacomplexdoc.off"); + // Check the read operation was correct + BOOST_CHECK(off_reader.is_valid()); + + // Retrieve the triangulation + T* triangulation = off_reader.get_complex(); + BOOST_CHECK(triangulation != nullptr); + // Operations on triangulation + BOOST_CHECK(triangulation->number_of_vertices() == 7); + BOOST_CHECK(triangulation->number_of_finite_full_cells() == 6); + + // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces + Gudhi::Delaunay_triangulation_off_writer<T> off_writer("UT.off", triangulation); + + // Check the write operation was correct + BOOST_CHECK(off_writer.is_valid()); + + delete triangulation; +} + +BOOST_AUTO_TEST_CASE( Delaunay_triangulation_unexisting_file_read_test ) +{ + Gudhi::Delaunay_triangulation_off_reader<T> off_reader("pouetpouet_tralala.off"); + // Check the read operation was correct + BOOST_CHECK(!off_reader.is_valid()); + T* triangulation = off_reader.get_complex(); + BOOST_CHECK(triangulation == nullptr); +} + +BOOST_AUTO_TEST_CASE( Delaunay_triangulation_unexisting_file_write_test ) +{ + // Read the OFF file (input file name given as parameter) and triangulates points + Gudhi::Delaunay_triangulation_off_reader<T> off_reader("../../../data/points/alphacomplexdoc.off"); + + // Retrieve the triangulation + T* triangulation = off_reader.get_complex(); + + // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces + Gudhi::Delaunay_triangulation_off_writer<T> off_writer("/pouetpouet_tralala/pouetpouet_tralala/pouetpouet_tralala.off", triangulation); + + // Check the write operation was correct + BOOST_CHECK(!off_writer.is_valid()); + + delete triangulation; +} + |