diff options
Diffstat (limited to 'src/Alpha_complex')
16 files changed, 2523 insertions, 0 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..226bb257 --- /dev/null +++ b/src/Alpha_complex/doc/Intro_alpha_complex.h @@ -0,0 +1,168 @@ +/* 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 DOC_ALPHA_COMPLEX_INTRO_ALPHA_COMPLEX_H_ +#define DOC_ALPHA_COMPLEX_INTRO_ALPHA_COMPLEX_H_ + +// 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 <a target="_blank" href="https://en.wikipedia.org/wiki/Simplicial_complex">simplicial complex</a> + * constructed from the finite cells of a Delaunay Triangulation. + * + * The filtration value of each simplex is computed as the square of the circumradius of the simplex if the circumsphere is empty (the simplex is then said to be Gabriel), and as the minimum of the filtration + * values of the codimension 1 cofaces that make it not Gabriel otherwise. + * + * All simplices that have a filtration value strictly greater than a given alpha squared value are not inserted into + * the complex. + * + * \image html "alpha_complex_representation.png" "Alpha-complex representation" + * + * Alpha_complex is constructing a `Simplex_tree` using <a target="_blank" + * href="http://doc.cgal.org/latest/Triangulation/index.html#Chapter_Triangulations">Delaunay Triangulation</a> + * \cite cgal:hdj-t-15b from <a target="_blank" href="http://www.cgal.org/">CGAL</a> (the Computational Geometry + * Algorithms Library \cite cgal:eb-15b). + * + * The complex is a template class requiring an Epick_d <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/index.html#Chapter_dD_Geometry_Kernel">dD Geometry Kernel</a> + * \cite cgal:s-gkd-15b from CGAL as template parameter. + * + * \remark When Alpha_complex is constructed with an infinite value of alpha, the complex is a Delaunay complex. + * + * \section pointsexample Example from points + * + * This example builds the Delaunay triangulation from the given points in a 2D static kernel, and initializes the + * alpha complex with it. + * + * Then, it is asked to display information about the alpha complex. + * + * \include Alpha_complex/Alpha_complex_from_points.cpp + * + * When launching: + * + * \code $> ./alphapoints + * \endcode + * + * the program output is: + * + * \include Alpha_complex/alphaoffreader_for_doc_60.txt + * + * \section algorithm Algorithm + * + * \subsection datastructure Data structure + * + * In order to build the alpha complex, first, a Simplex tree is built 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" + * + * \subsection filtrationcomputation Filtration value computation algorithm + * + * \f{algorithm}{ + * \caption{Filtration value computation algorithm}\label{alpha} + * \begin{algorithmic} + * \For{i : dimension $\rightarrow$ 0} + * \ForAll{$\sigma$ of dimension i} + * \If {filtration($\sigma$) is NaN} + * \State filtration($\sigma$) = $\alpha^2(\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 + * \State make\_filtration\_non\_decreasing() + * \State prune\_above\_filtration() + * \end{algorithmic} + * \f} + * + * \subsubsection dimension2 Dimension 2 + * + * From the example above, it means the algorithm looks into each triangle ([0,1,2], [0,2,4], [1,2,3], ...), + * computes the filtration value of the triangle, and then propagates the filtration value as described + * here : + * \image html "alpha_complex_doc_420.png" "Filtration value propagation example" + * + * \subsubsection dimension1 Dimension 1 + * + * Then, the algorithm looks into each edge ([0,1], [0,2], [1,2], ...), + * computes the filtration value of the edge (in this case, propagation will have no effect). + * + * \subsubsection dimension0 Dimension 0 + * + * Finally, the algorithm looks into each vertex ([0], [1], [2], [3], [4], [5] and [6]) and + * sets the filtration value (0 in case of a vertex - propagation will have no effect). + * + * \subsubsection nondecreasing Non decreasing filtration values + * + * As the squared radii computed by CGAL are an approximation, it might happen that these alpha squared values do not quite define a proper filtration (i.e. non-decreasing with respect to inclusion). + * We fix that up by calling `Simplex_tree::make_filtration_non_decreasing()`. + * + * \subsubsection pruneabove Prune above given filtration value + * + * The simplex tree is pruned from the given maximum alpha squared value (cf. `Simplex_tree::prune_above_filtration()`). + * In the following example, the value is given by the user as argument of the program. + * + * + * \section offexample Example from OFF file + * + * This example builds the Delaunay triangulation in a dynamic kernel, and initializes the alpha complex with it. + * + * + * Then, it is asked to display information about the alpha complex. + * + * \include Alpha_complex/Alpha_complex_from_off.cpp + * + * When launching: + * + * \code $> ./alphaoffreader ../../data/points/alphacomplexdoc.off 32.0 + * \endcode + * + * the program output is: + * + * \include Alpha_complex/alphaoffreader_for_doc_32.txt + * + * \copyright GNU General Public License v3. + * \verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim + */ +/** @} */ // end defgroup alpha_complex + +} // namespace alphacomplex + +} // namespace Gudhi + +#endif // DOC_ALPHA_COMPLEX_INTRO_ALPHA_COMPLEX_H_ 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..baf0d26a --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc.ipe @@ -0,0 +1,595 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70107" creator="Ipe 7.1.10"> +<info created="D:20150603143945" modified="D:20160406112209"/> +<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="small" value="\small"/> +<textsize name="tiny" value="\tiny"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="footnote" value="\footnotesize"/> +<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"/> +<path layer="alpha" 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">0</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">1</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">2</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">3</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">4</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">5</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">6</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> +<path matrix="1 0 0 1 104.05 -60.1773" stroke="black"> +4 0 0 4 320 704 e +</path> +<path matrix="1 0 0 1 104.05 -60.1773" stroke="black"> +322.919 706.788 m +317.189 701.058 l +317.189 701.203 l +</path> +<path matrix="1 0 0 1 104.05 -60.1773" stroke="black"> +317.551 706.934 m +322.629 701.058 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> +<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="280 660" 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"/> +<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="290 530" size="normal" stroke="black" fill="white"/> +<text matrix="1 0 0 1 4 -96" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<path matrix="1 0 0 1 4 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 24 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<path matrix="1 0 0 1 36 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<path matrix="1 0 0 1 24 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 24 -76" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 12 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<path matrix="1 0 0 1 12 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<path matrix="1 0 0 1 24 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 12 -96" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 64 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<path matrix="1 0 0 1 64 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 52 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<path matrix="1 0 0 1 52 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 36 -96" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 104 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 104 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 92 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<path matrix="1 0 0 1 92 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<path matrix="1 0 0 1 96 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 84 -96" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<text matrix="1 0 0 1 148 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 148 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 136 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<path matrix="1 0 0 1 136 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<path matrix="1 0 0 1 120 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 108 -76" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 120 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 108 -76" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 48 -96" stroke="black"> +292 716 m +292 728 l +316 728 l +316 716 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +316 716 m +316 728 l +340 728 l +340 716 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +340 716 m +340 728 l +364 728 l +364 716 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +364 716 m +364 728 l +388 728 l +388 716 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +388 716 m +388 728 l +412 728 l +412 716 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +412 716 m +412 728 l +436 728 l +436 716 l +h +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +436 716 m +436 728 l +460 728 l +460 716 l +h +</path> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="304 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">0</text> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="328 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="352 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="376 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="400 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="424 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 48 -96" transformations="translations" pos="448 720" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 -12 -96" stroke="black"> +436 708 m +436 716 l +</path> +<path matrix="1 0 0 1 28 -96" stroke="black"> +364 708 m +364 716 l +</path> +<path matrix="1 0 0 1 36 -96" stroke="black"> +364 688 m +364 696 l +</path> +<path matrix="1 0 0 1 36 -96" stroke="black"> +320 688 m +320 696 l +</path> +<path matrix="1 0 0 1 36 -96" stroke="black"> +296 708 m +308 716 l +308 716 l +</path> +<path matrix="1 0 0 1 48 -96" stroke="black"> +264 688 m +268 696 l +</path> +<path matrix="1 0 0 1 40 -96" stroke="black"> +292 688 m +292 696 l +</path> +<path matrix="1 0 0 1 36 -96" stroke="black"> +388 736 m +388 728 l +</path> +<path stroke="black"> +372 612 m +376 620 l +</path> +<path stroke="black"> +448 612 m +448 620 l +</path> +<text matrix="1 0 0 1 80 -76" transformations="translations" pos="304 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<path matrix="1 0 0 1 80 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<path matrix="1 0 0 1 80 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 68 -96" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 24 -96" stroke="black"> +364 688 m +364 696 l +</path> +<path matrix="1 0 0 1 136 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 124 -96" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 136 -96" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 124 -96" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 4 -116" stroke="black"> +436 708 m +436 716 l +</path> +<path matrix="1 0 0 1 168 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 156 -76" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 168 -76" stroke="black"> +300 688 m +300 676 l +312 676 l +312 688 l +h +</path> +<text matrix="1 0 0 1 156 -76" transformations="translations" pos="316 680" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 36 -96" stroke="black"> +436 708 m +436 716 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..0b6201da --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc.png diff --git a/src/Alpha_complex/doc/alpha_complex_doc_420.ipe b/src/Alpha_complex/doc/alpha_complex_doc_420.ipe new file mode 100644 index 00000000..5d1d29d4 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc_420.ipe @@ -0,0 +1,514 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70107" creator="Ipe 7.1.10"> +<info created="D:20150603143945" modified="D:20151130095019"/> +<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="small" value="\small"/> +<textsize name="tiny" value="\tiny"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="footnote" value="\footnotesize"/> +<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"/> +<path layer="alpha" 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 [4,2,0]</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">0</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">1</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">2</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">3</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">4</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">5</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">6</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> +<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_{420}$</text> +<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">[2,0] is Gabriel $\rightarrow$ $\alpha_{20}$ 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">0</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">2</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">3</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">4</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">5</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">6</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_{20}$</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> +<path matrix="1 0 0 1 -264 -162" stroke="darkcyan"> +304.883 555.015 m +334.509 555.015 l +</path> +<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">[0,4] is not Gabriel $\rightarrow$ $\alpha_{40} = \alpha_{420}$</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">0</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">3</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">5</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">6</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_{40}$</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 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">0</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">1</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">2</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">3</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">5</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">6</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_{42}$</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">4</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> +<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">[2,4] is Gabriel $\rightarrow$ $\alpha_{42}$ 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 [4,2,0]</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$ = [4,2,0]</text> +<path stroke="darkcyan"> +247.333 430.892 m +311.764 430.892 l +</path> +<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="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="243.636 591.818" size="normal" stroke="darkcyan" fill="white"/> +<use matrix="1 0 0 1 0 80" name="mark/fdisk(sfx)" pos="370 580" 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="290 530" 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="280 660" 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="370 580" 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"/> +<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">1</text> +<use matrix="1 0 0 1 -264 -162" name="mark/fdisk(sfx)" pos="305 555" size="normal" stroke="darkcyan" 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="320 580" 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"/> +<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">4</text> +<use name="mark/fdisk(sfx)" pos="247 431" size="normal" stroke="darkcyan" fill="white"/> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +<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">1</text> +<use matrix="1 0 0 1 -38 -164" name="mark/fdisk(sfx)" pos="370 580" 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"/> +<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">2</text> +<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 -38 -164" 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="290 530" 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="280 660" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="425.934 457.774" size="normal" stroke="darkcyan" 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"/> +<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 -38 -164" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +</page> +</ipe> diff --git a/src/Alpha_complex/doc/alpha_complex_doc_420.png b/src/Alpha_complex/doc/alpha_complex_doc_420.png Binary files differnew file mode 100644 index 00000000..ef7187f7 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_doc_420.png diff --git a/src/Alpha_complex/doc/alpha_complex_representation.ipe b/src/Alpha_complex/doc/alpha_complex_representation.ipe new file mode 100644 index 00000000..e8096b93 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_representation.ipe @@ -0,0 +1,321 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70107" creator="Ipe 7.1.10"> +<info created="D:20150603143945" modified="D:20160404172133"/> +<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="small" value="\small"/> +<textsize name="tiny" value="\tiny"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="footnote" value="\footnotesize"/> +<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"/> +<path layer="alpha" fill="lightblue"> +109.771 601.912 m +159.595 601.797 l +140.058 541.915 l +h +</path> +<path fill="lightblue"> +79.8776 552.169 m +109.756 601.699 l +139.812 542.209 l +h +</path> +<path fill="lightblue"> +69.8453 682.419 m +159.925 712.208 l +90.12 732.039 l +h +</path> +<text matrix="1 0 0 1 -230.178 22.1775" transformations="translations" pos="380 530" stroke="seagreen" type="label" width="76.735" height="8.307" depth="2.32" valign="baseline" size="large">Alpha complex</text> +<text matrix="1 0 0 1 -212.333 18.6762" transformations="translations" pos="282.952 524.893" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">0</text> +<text matrix="1 0 0 1 -210.178 22.1775" transformations="translations" pos="352.708 510.349" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">1</text> +<text matrix="1 0 0 1 -210.178 22.1775" transformations="translations" pos="310.693 578.759" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">2</text> +<text matrix="1 0 0 1 -210.178 22.1775" transformations="translations" pos="375.332 578.49" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">3</text> +<text matrix="1 0 0 1 -210.178 22.1775" transformations="translations" pos="272.179 660.635" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">4</text> +<text matrix="1 0 0 1 -209.478 12.0238" transformations="translations" pos="296.419 724.197" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">5</text> +<text matrix="1 0 0 1 -210.178 22.1775" transformations="translations" pos="375.332 689.453" stroke="black" type="label" width="4.981" height="6.42" depth="0" valign="baseline">6</text> +<path matrix="1 0 0 1 31.9779 -58.7483" stroke="darkgray"> +58.1341 0 0 58.1341 218.925 692.601 e +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +60 710 m +40 660 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +40 660 m +130 690 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +130 690 m +60 710 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +40 660 m +80 580 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +80 580 m +130 580 l +130 580 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +130 580 m +110 520 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +110 520 m +50 530 l +50 530 l +50 530 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +50 530 m +80 580 l +</path> +<path matrix="1 0 0 1 29.8225 22.1775" stroke="black" pen="heavier"> +130 580 m +130 690 l +</path> +<use matrix="1 0 0 1 142.618 -109.867" name="mark/fdisk(sfx)" pos="108.285 743.72" size="normal" stroke="darkgray" fill="white"/> +<path matrix="1 0 0 1 142.618 -109.867" stroke="darkgray"> +108.275 743.531 m +166.45 743.531 l +</path> +<text matrix="1 0 0 1 142.618 -109.867" transformations="translations" pos="127.397 746.763" stroke="darkgray" type="label" width="6.41" height="4.289" depth="0" valign="baseline">$\alpha$</text> +<use matrix="1 0 0 1 -209.478 12.0238" name="mark/fdisk(sfx)" pos="300 720" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -210.178 22.1775" name="mark/fdisk(sfx)" pos="280 660" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -210.178 22.1775" name="mark/fdisk(sfx)" pos="370 690" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -210.178 22.1775" name="mark/fdisk(sfx)" pos="370 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -210.178 22.1775" name="mark/fdisk(sfx)" pos="290 530" size="normal" stroke="black" fill="white"/> +<path matrix="1 0 0 1 -40 -8" stroke="black" pen="heavier"> +150.038 609.9 m +179.929 549.727 l +</path> +<use matrix="1 0 0 1 -210.178 22.1775" name="mark/fdisk(sfx)" pos="320 580" size="normal" stroke="black" fill="white"/> +<use matrix="1 0 0 1 -210.178 22.1775" name="mark/fdisk(sfx)" pos="350 520" size="normal" stroke="black" fill="white"/> +</page> +</ipe> diff --git a/src/Alpha_complex/doc/alpha_complex_representation.png b/src/Alpha_complex/doc/alpha_complex_representation.png Binary files differnew file mode 100644 index 00000000..7b81cd69 --- /dev/null +++ b/src/Alpha_complex/doc/alpha_complex_representation.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..963ef5ca --- /dev/null +++ b/src/Alpha_complex/example/Alpha_complex_from_off.cpp @@ -0,0 +1,56 @@ +#include <gudhi/Alpha_complex.h> +#include <CGAL/Epick_d.h> + +#include <iostream> +#include <string> + +void usage(int nbArgs, char * const progName) { + std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; + std::cerr << "Usage: " << progName << " filename.off alpha_square_max_value [ouput_file.txt]\n"; + std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0\n"; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if ((argc != 3) && (argc != 4)) usage(argc, (argv[0] - 1)); + + std::string off_file_name(argv[1]); + double alpha_square_max_value = atof(argv[2]); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from an OFF file + // ---------------------------------------------------------------------------- + typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; + Gudhi::alphacomplex::Alpha_complex<Kernel> alpha_complex_from_file(off_file_name, alpha_square_max_value); + + std::streambuf* streambufffer; + std::ofstream ouput_file_stream; + + if (argc == 4) { + ouput_file_stream.open(std::string(argv[3])); + streambufffer = ouput_file_stream.rdbuf(); + } else { + streambufffer = std::cout.rdbuf(); + } + + std::ostream output_stream(streambufffer); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + output_stream << "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; + + output_stream << "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()) { + output_stream << " ( "; + for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) { + output_stream << vertex << " "; + } + output_stream << ") -> " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] "; + output_stream << std::endl; + } + ouput_file_stream.close(); + return 0; +} 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..cd17af1e --- /dev/null +++ b/src/Alpha_complex/example/Alpha_complex_from_points.cpp @@ -0,0 +1,62 @@ +#include <CGAL/Epick_d.h> +#include <gudhi/Alpha_complex.h> + +#include <iostream> +#include <string> +#include <vector> +#include <limits> // for numeric limits + +typedef CGAL::Epick_d< CGAL::Dimension_tag<2> > Kernel; +typedef Kernel::Point_d Point; +typedef std::vector<Point> Vector_of_points; + +void usage(int nbArgs, char * const progName) { + std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; + std::cerr << "Usage: " << progName << " [alpha_square_max_value]\n"; + std::cerr << " i.e.: " << progName << " 60.0\n"; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if ((argc != 1) && (argc != 2)) usage(argc, (argv[0] - 1)); + + // Delaunay complex if alpha_square_max_value is not given by the user. + double alpha_square_max_value = std::numeric_limits<double>::infinity(); + if (argc == 2) + alpha_square_max_value = atof(argv[1]); + + // ---------------------------------------------------------------------------- + // Init of a list of points + // ---------------------------------------------------------------------------- + Vector_of_points points; + points.push_back(Point(1.0, 1.0)); + points.push_back(Point(7.0, 0.0)); + points.push_back(Point(4.0, 6.0)); + points.push_back(Point(9.0, 6.0)); + points.push_back(Point(0.0, 14.0)); + points.push_back(Point(2.0, 19.0)); + points.push_back(Point(9.0, 17.0)); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from the list of points + // ---------------------------------------------------------------------------- + Gudhi::alphacomplex::Alpha_complex<Kernel> alpha_complex_from_points(points, alpha_square_max_value); + + // ---------------------------------------------------------------------------- + // 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; +} diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt new file mode 100644 index 00000000..f1346867 --- /dev/null +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -0,0 +1,43 @@ +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}.") + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + + add_executable ( alphapoints Alpha_complex_from_points.cpp ) + target_link_libraries(alphapoints ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + add_executable ( alphaoffreader Alpha_complex_from_off.cpp ) + target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(alphapoints ${TBB_RELEASE_LIBRARY}) + target_link_libraries(alphaoffreader ${TBB_RELEASE_LIBRARY}) + endif() + + add_test(alphapoints ${CMAKE_CURRENT_BINARY_DIR}/alphapoints) + # Do not forget to copy test files in current binary dir + file(COPY "${CMAKE_SOURCE_DIR}/data/points/alphacomplexdoc.off" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + add_test(alphaoffreader_doc_60 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader alphacomplexdoc.off 60.0 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_60.txt) + add_test(alphaoffreader_doc_32 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader alphacomplexdoc.off 32.0 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_32.txt) + if (DIFF_PATH) + # Do not forget to copy test results files in current binary dir + file(COPY "alphaoffreader_for_doc_32.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + file(COPY "alphaoffreader_for_doc_60.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + + add_test(alphaoffreader_doc_60_diff_files ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_60.txt ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_for_doc_60.txt) + add_test(alphaoffreader_doc_32_diff_files ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_32.txt ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_for_doc_32.txt) + 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/Alpha_complex/example/alphaoffreader_for_doc_32.txt b/src/Alpha_complex/example/alphaoffreader_for_doc_32.txt new file mode 100644 index 00000000..13183e86 --- /dev/null +++ b/src/Alpha_complex/example/alphaoffreader_for_doc_32.txt @@ -0,0 +1,22 @@ +Alpha complex is of dimension 2 - 20 simplices - 7 vertices. +Iterator on alpha complex simplices in the filtration order, with [filtration value]: + ( 0 ) -> [0] + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 3 2 ) -> [6.25] + ( 5 4 ) -> [7.25] + ( 2 0 ) -> [8.5] + ( 1 0 ) -> [9.25] + ( 3 1 ) -> [10] + ( 2 1 ) -> [11.25] + ( 3 2 1 ) -> [12.5] + ( 2 1 0 ) -> [12.9959] + ( 6 5 ) -> [13.25] + ( 4 2 ) -> [20] + ( 6 4 ) -> [22.7367] + ( 6 5 4 ) -> [22.7367] + ( 6 3 ) -> [30.25] diff --git a/src/Alpha_complex/example/alphaoffreader_for_doc_60.txt b/src/Alpha_complex/example/alphaoffreader_for_doc_60.txt new file mode 100644 index 00000000..71f29a00 --- /dev/null +++ b/src/Alpha_complex/example/alphaoffreader_for_doc_60.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]: + ( 0 ) -> [0] + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 3 2 ) -> [6.25] + ( 5 4 ) -> [7.25] + ( 2 0 ) -> [8.5] + ( 1 0 ) -> [9.25] + ( 3 1 ) -> [10] + ( 2 1 ) -> [11.25] + ( 3 2 1 ) -> [12.5] + ( 2 1 0 ) -> [12.9959] + ( 6 5 ) -> [13.25] + ( 4 2 ) -> [20] + ( 6 4 ) -> [22.7367] + ( 6 5 4 ) -> [22.7367] + ( 6 3 ) -> [30.25] + ( 6 2 ) -> [36.5] + ( 6 3 2 ) -> [36.5] + ( 6 4 2 ) -> [37.2449] + ( 4 0 ) -> [59.7107] + ( 4 2 0 ) -> [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..ca2b68ca --- /dev/null +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -0,0 +1,415 @@ +/* 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 ALPHA_COMPLEX_H_ +#define ALPHA_COMPLEX_H_ + +// to construct a simplex_tree from Delaunay_triangulation +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Debug_utils.h> +// to construct Alpha_complex from a OFF file of points +#include <gudhi/Points_off_io.h> + +#include <stdlib.h> +#include <math.h> // isnan, fmax + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> +#include <CGAL/Spatial_sort_traits_adapter_d.h> + +#include <iostream> +#include <vector> +#include <string> +#include <limits> // NaN +#include <map> +#include <utility> // std::pair +#include <stdexcept> +#include <numeric> // for std::iota + +namespace Gudhi { + +namespace alphacomplex { + +/** + * \class Alpha_complex Alpha_complex.h gudhi/Alpha_complex.h + * \brief Alpha complex data structure. + * + * \ingroup alpha_complex + * + * \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. Points_off_reader). + * + * Please refer to \ref alpha_complex for examples. + * + * The complex is a template class requiring an Epick_d <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/index.html#Chapter_dD_Geometry_Kernel">dD Geometry Kernel</a> + * \cite cgal:s-gkd-15b from CGAL as template, default value is <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> + * < <a target="_blank" href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dynamic__dimension__tag.html"> + * CGAL::Dynamic_dimension_tag </a> > + * + * \remark When Alpha_complex is constructed with an infinite value of alpha, the complex is a Delaunay complex. + * + */ +template<class Kernel = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>> +class Alpha_complex : public Simplex_tree<> { + public: + // Add an int in TDS to save point index in the structure + typedef CGAL::Triangulation_data_structure<CGAL::Dynamic_dimension_tag, + CGAL::Triangulation_vertex<Kernel, std::ptrdiff_t>, + CGAL::Triangulation_full_cell<Kernel> > TDS; + /** \brief A Delaunay triangulation of a set of points in \f$ \mathbb{R}^D\f$.*/ + typedef CGAL::Delaunay_triangulation<Kernel, TDS> Delaunay_triangulation; + + /** \brief A point in Euclidean space.*/ + typedef typename Kernel::Point_d Point_d; + /** \brief Geometric traits class that provides the geometric types and predicates needed by Delaunay + * triangulations.*/ + typedef Kernel Geom_traits; + + 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; + + typedef typename Kernel::Compute_squared_radius_d Squared_Radius; + typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; + typedef typename Kernel::Point_dimension_d Point_Dimension; + + // Type required to compute squared radius, or side of bounded sphere on a vector of points. + typedef typename std::vector<Point_d> Vector_of_CGAL_points; + + // Vertex_iterator type from CGAL. + typedef typename Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; + + // size_type type from CGAL. + typedef typename Delaunay_triangulation::size_type size_type; + + // Map type to switch from simplex tree vertex handle to CGAL vertex iterator. + typedef typename std::map< Vertex_handle, CGAL_vertex_iterator > Vector_vertex_iterator; + + private: + /** \brief Vertex iterator vector to switch from simplex tree vertex handle to CGAL vertex iterator. + * Vertex handles are inserted sequentially, starting at 0.*/ + Vector_vertex_iterator vertex_handle_to_iterator_; + /** \brief Pointer on the CGAL Delaunay triangulation.*/ + Delaunay_triangulation* triangulation_; + /** \brief Kernel for triangulation_ functions access.*/ + Kernel kernel_; + + 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. + * + * Duplicate points are inserted once in the Alpha_complex. This is the reason why the vertices may be not contiguous. + * + * @param[in] off_file_name OFF file [path and] name. + * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. + */ + Alpha_complex(const std::string& off_file_name, + Filtration_value max_alpha_square = std::numeric_limits<Filtration_value>::infinity()) + : triangulation_(nullptr) { + Gudhi::Points_off_reader<Point_d> off_reader(off_file_name); + if (!off_reader.is_valid()) { + std::cerr << "Alpha_complex - Unable to read file " << off_file_name << "\n"; + exit(-1); // ----- >> + } + + init_from_range(off_reader.get_point_cloud(), max_alpha_square); + } + + /** \brief Alpha_complex constructor from a list of points. + * + * Duplicate points are inserted once in the Alpha_complex. This is the reason why the vertices may be not contiguous. + * + * @param[in] points Range of points to triangulate. Points must be in Kernel::Point_d + * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. + * + * The type InputPointRange must be a range for which std::begin and + * std::end return input iterators on a Kernel::Point_d. + * + * @post Compare num_simplices with InputPointRange points number (not the same in case of duplicate points). + */ + template<typename InputPointRange > + Alpha_complex(const InputPointRange& points, + Filtration_value max_alpha_square = std::numeric_limits<Filtration_value>::infinity()) + : triangulation_(nullptr) { + init_from_range(points, max_alpha_square); + } + + /** \brief Alpha_complex destructor. + * + * @warning Deletes the Delaunay triangulation. + */ + ~Alpha_complex() { + delete triangulation_; + } + + // Forbid copy/move constructor/assignment operator + Alpha_complex(const Alpha_complex& other) = delete; + Alpha_complex& operator= (const Alpha_complex& other) = delete; + Alpha_complex (Alpha_complex&& other) = delete; + Alpha_complex& operator= (Alpha_complex&& other) = delete; + + /** \brief get_point returns the point corresponding to the vertex given as parameter. + * + * @param[in] vertex Vertex handle of the point to retrieve. + * @return The point found. + * @exception std::out_of_range In case vertex is not found (cf. std::vector::at). + */ + Point_d get_point(Vertex_handle vertex) const { + return vertex_handle_to_iterator_.at(vertex)->point(); + } + + private: + template<typename InputPointRange > + void init_from_range(const InputPointRange& points, Filtration_value max_alpha_square) { + auto first = std::begin(points); + auto last = std::end(points); + if (first != last) { + // point_dimension function initialization + Point_Dimension point_dimension = kernel_.point_dimension_d_object(); + + // Delaunay triangulation is point dimension. + triangulation_ = new Delaunay_triangulation(point_dimension(*first)); + + std::vector<Point_d> points(first, last); + + // Creates a vector {0, 1, ..., N-1} + std::vector<std::ptrdiff_t> indices(boost::counting_iterator<std::ptrdiff_t>(0), + boost::counting_iterator<std::ptrdiff_t>(points.size())); + + // Sort indices considering CGAL spatial sort + typedef CGAL::Spatial_sort_traits_adapter_d<Kernel, Point_d*> Search_traits_d; + spatial_sort(indices.begin(), indices.end(), Search_traits_d(&(points[0]))); + + typename Delaunay_triangulation::Full_cell_handle hint; + for (auto index : indices) { + typename Delaunay_triangulation::Vertex_handle pos = triangulation_->insert(points[index], hint); + // Save index value as data to retrieve it after insertion + pos->data() = index; + hint = pos->full_cell(); + } + init(max_alpha_square); + } + } + + /** \brief Initialize the Alpha_complex from the Delaunay triangulation. + * + * @param[in] max_alpha_square maximum for alpha square value. + * + * @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(Filtration_value max_alpha_square) { + if (triangulation_ == nullptr) { + std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation\n"; + return; // ----- >> + } + if (triangulation_->number_of_vertices() < 1) { + std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices\n"; + return; // ----- >> + } + if (triangulation_->maximal_dimension() < 1) { + std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation\n"; + return; // ----- >> + } + if (num_vertices() > 0) { + std::cerr << "Alpha_complex init - Cannot init twice\n"; + return; // ----- >> + } + + set_dimension(triangulation_->maximal_dimension()); + + // -------------------------------------------------------------------------------------------- + // double map to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa + // Loop on triangulation vertices list + for (CGAL_vertex_iterator vit = triangulation_->vertices_begin(); vit != triangulation_->vertices_end(); ++vit) { + if (!triangulation_->is_infinite(*vit)) { +#ifdef DEBUG_TRACES + std::cout << "Vertex insertion - " << vit->data() << " -> " << vit->point() << std::endl; +#endif // DEBUG_TRACES + vertex_handle_to_iterator_.emplace(vit->data(), vit); + } + } + // -------------------------------------------------------------------------------------------- + + // -------------------------------------------------------------------------------------------- + // 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) { + if (*vit != nullptr) { +#ifdef DEBUG_TRACES + std::cout << " " << (*vit)->data(); +#endif // DEBUG_TRACES + // Vector of vertex construction for simplex_tree structure + vertexVector.push_back((*vit)->data()); + } + } +#ifdef DEBUG_TRACES + std::cout << std::endl; +#endif // DEBUG_TRACES + // Insert each simplex and its subfaces in the simplex tree - filtration is NaN + insert_simplex_and_subfaces(vertexVector, std::numeric_limits<double>::quiet_NaN()); + } + // -------------------------------------------------------------------------------------------- + + // -------------------------------------------------------------------------------------------- + // ### 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(get_point(vertex)); +#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 + Squared_Radius squared_radius = kernel_.compute_squared_radius_d_object(); + + alpha_complex_filtration = squared_radius(pointVector.begin(), pointVector.end()); + } + assign_filtration(f_simplex, 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); + } + } + } + // -------------------------------------------------------------------------------------------- + + // -------------------------------------------------------------------------------------------- + // As Alpha value is an approximation, we have to make filtration non decreasing while increasing the dimension + bool modified_filt = make_filtration_non_decreasing(); + // Remove all simplices that have a filtration value greater than max_alpha_square + // Remark: prune_above_filtration does not require initialize_filtration to be done before. + modified_filt |= prune_above_filtration(max_alpha_square); + if (modified_filt) { + initialize_filtration(); + } + // -------------------------------------------------------------------------------------------- + } + + 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 << " | --------------------------------------------------\n"; + std::cout << " | Tau "; + for (auto vertex : simplex_vertex_range(f_boundary)) { + std::cout << vertex << " "; + } + std::cout << "is a face of Sigma\n"; + 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); +#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; +#ifdef DEBUG_TRACES + Vertex_handle vertexForGabriel = Vertex_handle(); +#endif // DEBUG_TRACES + for (auto vertex : simplex_vertex_range(f_boundary)) { + pointVector.push_back(get_point(vertex)); + } + // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function + Point_d point_for_gabriel; + for (auto vertex : simplex_vertex_range(f_simplex)) { + point_for_gabriel = get_point(vertex); + if (std::find(pointVector.begin(), pointVector.end(), point_for_gabriel) == pointVector.end()) { +#ifdef DEBUG_TRACES + // vertex is not found in Tau + vertexForGabriel = vertex; +#endif // DEBUG_TRACES + // No need to continue loop + break; + } + } + // is_gabriel function initialization + Is_Gabriel is_gabriel = kernel_.side_of_bounded_sphere_d_object(); + bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), point_for_gabriel) + != CGAL::ON_BOUNDED_SIDE; +#ifdef DEBUG_TRACES + std::cout << " | Tau is_gabriel(Sigma)=" << is_gab << " - vertexForGabriel=" << vertexForGabriel << std::endl; +#endif // DEBUG_TRACES + // ### If Tau is not Gabriel of Sigma + if (false == is_gab) { + // ### filt(Tau) = filt(Sigma) + Filtration_value alpha_complex_filtration = filtration(f_simplex); + assign_filtration(f_boundary, alpha_complex_filtration); +#ifdef DEBUG_TRACES + std::cout << " | filt(Tau) = filt(Sigma) = " << filtration(f_boundary) << std::endl; +#endif // DEBUG_TRACES + } + } + } + } + } +}; + +} // namespace alphacomplex + +} // namespace Gudhi + +#endif // 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..80b39924 --- /dev/null +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -0,0 +1,243 @@ +/* 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_DYN_LINK +#define BOOST_TEST_MODULE "alpha_complex" +#include <boost/test/unit_test.hpp> + +#include <CGAL/Delaunay_triangulation.h> +#include <CGAL/Epick_d.h> + +#include <cmath> // float comparison +#include <limits> +#include <string> +#include <vector> + +#include <gudhi/Alpha_complex.h> + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel_d; +// The triangulation uses the default instantiation of the TriangulationDataStructure template parameter + +BOOST_AUTO_TEST_CASE(ALPHA_DOC_OFF_file) { + // ---------------------------------------------------------------------------- + // + // Init of an alpha-complex from a OFF file + // + // ---------------------------------------------------------------------------- + std::string off_file_name("alphacomplexdoc.off"); + double max_alpha_square_value = 60.0; + std::cout << "========== OFF FILE NAME = " << off_file_name << " - alpha²=" << + max_alpha_square_value << "==========" << std::endl; + + Gudhi::alphacomplex::Alpha_complex<Kernel_d> alpha_complex_from_file(off_file_name, max_alpha_square_value); + + const int DIMENSION = 2; + 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 = 7; + 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 = 25; + 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(ALPHA_DOC_OFF_file_filtered) { + // ---------------------------------------------------------------------------- + // + // Init of an alpha-complex from a OFF file + // + // ---------------------------------------------------------------------------- + std::string off_file_name("alphacomplexdoc.off"); + double max_alpha_square_value = 59.0; + std::cout << "========== OFF FILE NAME = " << off_file_name << " - alpha²=" << + max_alpha_square_value << "==========" << std::endl; + + // Use of the default dynamic kernel + Gudhi::alphacomplex::Alpha_complex<> alpha_complex_from_file(off_file_name, max_alpha_square_value); + + const int DIMENSION = 2; + 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 = 7; + 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 = 23; + 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(); +} + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dimension_tag<4> > Kernel_s; +typedef Kernel_s::Point_d Point; +typedef std::vector<Point> Vector_of_points; + + +bool is_point_in_list(Vector_of_points points_list, Point point) { + for (auto& point_in_list : points_list) { + if (point_in_list == point) { + return true; // point found + } + } + return false; // point not found +} + +BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { + // ---------------------------------------------------------------------------- + // Init of a list of points + // ---------------------------------------------------------------------------- + Vector_of_points points; + std::vector<double> coords = { 0.0, 0.0, 0.0, 1.0 }; + points.push_back(Point(coords.begin(), coords.end())); + coords = { 0.0, 0.0, 1.0, 0.0 }; + points.push_back(Point(coords.begin(), coords.end())); + coords = { 0.0, 1.0, 0.0, 0.0 }; + points.push_back(Point(coords.begin(), coords.end())); + coords = { 1.0, 0.0, 0.0, 0.0 }; + points.push_back(Point(coords.begin(), coords.end())); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from the list of points + // ---------------------------------------------------------------------------- + Gudhi::alphacomplex::Alpha_complex<Kernel_s> alpha_complex_from_points(points); + + std::cout << "========== Alpha_complex_from_points ==========" << std::endl; + + // Another way to check num_simplices + std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + int num_simplices = 0; + for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + num_simplices++; + 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; + } + BOOST_CHECK(num_simplices == 15); + 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.dimension()=" << alpha_complex_from_points.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_points.dimension() == 4); + 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; + } + } + + Point p0 = alpha_complex_from_points.get_point(0); + std::cout << "alpha_complex_from_points.get_point(0)=" << p0 << std::endl; + BOOST_CHECK(4 == p0.dimension()); + BOOST_CHECK(is_point_in_list(points, p0)); + + Point p1 = alpha_complex_from_points.get_point(1); + std::cout << "alpha_complex_from_points.get_point(1)=" << p1 << std::endl; + BOOST_CHECK(4 == p1.dimension()); + BOOST_CHECK(is_point_in_list(points, p1)); + + Point p2 = alpha_complex_from_points.get_point(2); + std::cout << "alpha_complex_from_points.get_point(2)=" << p2 << std::endl; + BOOST_CHECK(4 == p2.dimension()); + BOOST_CHECK(is_point_in_list(points, p2)); + + Point p3 = alpha_complex_from_points.get_point(3); + std::cout << "alpha_complex_from_points.get_point(3)=" << p3 << std::endl; + BOOST_CHECK(4 == p3.dimension()); + BOOST_CHECK(is_point_in_list(points, p3)); + + // Test to the limit + BOOST_CHECK_THROW (alpha_complex_from_points.get_point(4), std::out_of_range); + BOOST_CHECK_THROW (alpha_complex_from_points.get_point(-1), std::out_of_range); + BOOST_CHECK_THROW (alpha_complex_from_points.get_point(1234), std::out_of_range); + + // Test after prune_above_filtration + bool modified = alpha_complex_from_points.prune_above_filtration(0.6); + if (modified) { + alpha_complex_from_points.initialize_filtration(); + } + BOOST_CHECK(modified); + + // Another way to check num_simplices + std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + num_simplices = 0; + for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + num_simplices++; + 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; + } + BOOST_CHECK(num_simplices == 10); + std::cout << "alpha_complex_from_points.num_simplices()=" << alpha_complex_from_points.num_simplices() << std::endl; + BOOST_CHECK(alpha_complex_from_points.num_simplices() == 10); + + std::cout << "alpha_complex_from_points.dimension()=" << alpha_complex_from_points.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_points.dimension() == 4); + 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; + 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..e24588d7 --- /dev/null +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -0,0 +1,45 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIAlphaComplexTest) + +if (GCOVR_PATH) + # for gcovr to make coverage reports - Corbera Jenkins plugin + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage") +endif() +if (GPROF_PATH) + # for gprof to make coverage reports - Jenkins + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") +endif() + +# 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}.") + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + include_directories (BEFORE "../../include") + + add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) + target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(AlphaComplexUT ${TBB_RELEASE_LIBRARY}) + endif() + + # Do not forget to copy test files in current binary dir + file(COPY "${CMAKE_SOURCE_DIR}/data/points/alphacomplexdoc.off" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + + 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_complex/test/README b/src/Alpha_complex/test/README new file mode 100644 index 00000000..45b87d91 --- /dev/null +++ b/src/Alpha_complex/test/README @@ -0,0 +1,12 @@ +To compile: +*********** + +cmake . +make + +To launch with details: +*********************** + +./AlphaComplexUnitTest --report_level=detailed --log_level=all + + ==> echo $? returns 0 in case of success (non-zero otherwise) |
