From 17fd245908ba07d6bad974efa0be1ec6093262ec Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 15 Jun 2015 09:31:02 +0000 Subject: Alpha_shapes renamed Alpha_complex git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@614 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: ede5d1c1175f9d314e23bc0b76f7376b3de90c93 --- src/Alpha_complex/test/CMakeLists.txt | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) create mode 100644 src/Alpha_complex/test/CMakeLists.txt (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt new file mode 100644 index 00000000..3cf97b71 --- /dev/null +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -0,0 +1,31 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIAlphaShapesTest) + +# need CGAL 4.7 +# cmake -DCGAL_DIR=~/workspace/CGAL-4.7-Ic-41 ../../.. +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + include_directories (BEFORE "../../include") + + add_definitions(-DDEBUG_TRACES) + add_executable ( AlphaShapesUnitTest Alpha_shapes_unit_test.cpp ) + target_link_libraries(AlphaShapesUnitTest ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + add_test(AlphaShapesUnitTest ${CMAKE_CURRENT_BINARY_DIR}/AlphaShapesUnitTest) + + 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() + +cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/Alpha_shapes/include/gudhi") -- cgit v1.2.3 From 77b57ae69fa2042b652d91d8015c1d9533176090 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 16 Jun 2015 13:30:27 +0000 Subject: Alpha_complex renamed. Compilation and tests are OK. bimap is stored in class. bimap is now on CGAL Vertex_iterator - instead of points. is_gabriel not computed when simplex dimension is 1. is_gabriel not computed when filt(Tau) is not NaN. Delaunay_triangulation is a pointer constructed in Delaunay_triangulation_off_io.h git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@617 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 4fa4a26ce47066efe22aed99734ff1dd821ad70b --- CMakeLists.txt | 6 +- data/points/generator/hypergenerator.cpp | 9 +- src/Alpha_complex/example/CMakeLists.txt | 3 + .../example/Delaunay_triangulation_off_rw.cpp | 4 +- .../Simplex_tree_from_delaunay_triangulation.cpp | 16 +- src/Alpha_complex/include/gudhi/Alpha_complex.h | 339 +++++++++++++++++++++ src/Alpha_complex/include/gudhi/Alpha_shapes.h | 311 ------------------- .../Alpha_shapes/Delaunay_triangulation_off_io.h | 50 ++- src/Alpha_complex/test/Alpha_complex_unit_test.cpp | 126 ++++++++ src/Alpha_complex/test/Alpha_shapes_unit_test.cpp | 126 -------- src/Alpha_complex/test/CMakeLists.txt | 14 +- src/CMakeLists.txt | 2 +- 12 files changed, 530 insertions(+), 476 deletions(-) create mode 100644 src/Alpha_complex/include/gudhi/Alpha_complex.h delete mode 100644 src/Alpha_complex/include/gudhi/Alpha_shapes.h create mode 100644 src/Alpha_complex/test/Alpha_complex_unit_test.cpp delete mode 100644 src/Alpha_complex/test/Alpha_shapes_unit_test.cpp (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/CMakeLists.txt b/CMakeLists.txt index 89440490..01108db9 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -69,7 +69,7 @@ else() message(STATUS "boost include dirs:" ${Boost_INCLUDE_DIRS}) include_directories(src/common/include/) - include_directories(src/Alpha_shapes/include/) + include_directories(src/Alpha_complex/include/) include_directories(src/Bottleneck/include/) include_directories(src/Contraction/include/) include_directories(src/Hasse_complex/include/) @@ -85,8 +85,8 @@ else() add_subdirectory(src/Skeleton_blocker/example) add_subdirectory(src/Contraction/example) add_subdirectory(src/Hasse_complex/example) - add_subdirectory(src/Alpha_shapes/example) - add_subdirectory(src/Alpha_shapes/test) + add_subdirectory(src/Alpha_complex/example) + add_subdirectory(src/Alpha_complex/test) add_subdirectory(src/Bottleneck/example) add_subdirectory(src/Bottleneck/test) diff --git a/data/points/generator/hypergenerator.cpp b/data/points/generator/hypergenerator.cpp index f4ea6b07..32ef450d 100644 --- a/data/points/generator/hypergenerator.cpp +++ b/data/points/generator/hypergenerator.cpp @@ -86,8 +86,13 @@ int main(int argc, char **argv) { } std::ofstream diagram_out(argv[3]); - diagram_out << "OFF" << std::endl; - diagram_out << points_number << " 0 0" << std::endl; + if (dimension == 3) { + diagram_out << "OFF" << std::endl; + diagram_out << points_number << " 0 0" << std::endl; + } else { + diagram_out << "nOFF" << std::endl; + diagram_out << dimension << " " << points_number << " 0 0" << std::endl; + } if (diagram_out.is_open()) { // Instanciate a random point generator diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt index 582a9322..258def49 100644 --- a/src/Alpha_complex/example/CMakeLists.txt +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -22,6 +22,9 @@ if(CGAL_FOUND) add_executable ( stfromdt Simplex_tree_from_delaunay_triangulation.cpp ) target_link_libraries(stfromdt ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + + add_executable ( template_off template_off.cpp ) + target_link_libraries(template_off ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) else() message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") endif() diff --git a/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp b/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp index fe889ec0..405b3cb9 100644 --- a/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp +++ b/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp @@ -63,7 +63,7 @@ int main(int argc, char **argv) { T dt(dimension); std::string offFileName(argv[1]); - Gudhi::alphashapes::Delaunay_triangulation_off_reader off_reader(offFileName, dt); + Gudhi::alphacomplex::Delaunay_triangulation_off_reader off_reader(offFileName, dt); if (!off_reader.is_valid()) { std::cerr << "Unable to read file " << offFileName << std::endl; exit(-1); // ----- >> @@ -73,7 +73,7 @@ int main(int argc, char **argv) { std::string outFileName(argv[3]); std::string offOutputFile(outFileName); - Gudhi::alphashapes::Delaunay_triangulation_off_writer off_writer(offOutputFile, dt); + Gudhi::alphacomplex::Delaunay_triangulation_off_writer off_writer(offOutputFile, dt); return 0; } \ No newline at end of file diff --git a/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp b/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp index 0a24fb56..f09e6121 100644 --- a/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp +++ b/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp @@ -22,7 +22,7 @@ // to construct a Delaunay_triangulation from a OFF file #include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" -#include "gudhi/Alpha_shapes.h" +#include "gudhi/Alpha_complex.h" // to construct a simplex_tree from Delaunay_triangulation #include "gudhi/graph_simplicial_complex.h" @@ -62,16 +62,16 @@ int main(int argc, char **argv) { // ---------------------------------------------------------------------------- // - // Init of an alpha-shape from a OFF file + // Init of an alpha-complex from a OFF file // // ---------------------------------------------------------------------------- - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_file(off_file_name); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); - std::cout << "alpha_shapes_from_file.dimension()=" << alpha_shapes_from_file.dimension() << std::endl; - std::cout << "alpha_shapes_from_file.filtration()=" << alpha_shapes_from_file.filtration() << std::endl; - std::cout << "alpha_shapes_from_file.num_simplices()=" << alpha_shapes_from_file.num_simplices() << std::endl; - std::cout << "alpha_shapes_from_file.num_vertices()=" << alpha_shapes_from_file.num_vertices() << std::endl; - //std::cout << alpha_shapes_from_file << std::endl; + std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; + std::cout << "alpha_complex_from_file.filtration()=" << alpha_complex_from_file.filtration() << std::endl; + std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; + std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; + std::cout << alpha_complex_from_file << std::endl; return 0; } \ No newline at end of file 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..ca84d6d9 --- /dev/null +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -0,0 +1,339 @@ +/* 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 . + */ + +#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ +#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ + +// to construct a Delaunay_triangulation from a OFF file +#include + +// to construct a simplex_tree from Delaunay_triangulation +#include +#include + +#include +#include +#include // isnan, fmax + +#include + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +namespace Gudhi { + +namespace alphacomplex { + +#define Kinit(f) =k.f() + +/** \defgroup alpha_complex Alpha complex in dimension N + * +
Implementations:
+ Alpha complex in dimension N are a subset of Delaunay Triangulation in dimension N. + + + * \author Vincent Rouvreau + * \version 1.0 + * \date 2015 + * \copyright GNU General Public License v3. + * @{ + */ + +/** + * \brief Alpha complex data structure. + * + * \details Every simplex \f$[v_0, \cdots ,v_d]\f$ admits a canonical orientation + * induced by the order relation on vertices \f$ v_0 < \cdots < v_d \f$. + * + * Details may be found in \cite boissonnatmariasimplextreealgorithmica. + * + * + */ +class Alpha_complex { + private: + // From Simplex_tree + /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ + typedef std::vector typeVectorVertex; + + typedef typename Gudhi::Simplex_tree<>::Simplex_handle Simplex_handle; + typedef typename std::pair Simplex_result; + + // From CGAL + /** \brief Kernel for the Delaunay_triangulation-> + * Dimension can be set dynamically. + */ + typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; + /** \brief Delaunay_triangulation type required to create an alpha-complex. + */ + typedef CGAL::Delaunay_triangulation Delaunay_triangulation; + + typedef typename Kernel::Compute_squared_radius_d Squared_Radius; + typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; + + /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ + typedef std::vector Vector_of_CGAL_points; + + typedef Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; + + typedef boost::bimap< CGAL_vertex_iterator, Vertex_handle > Bimap_vertex; + + private: + /** \brief Upper bound on the simplex tree of the simplicial complex.*/ + Gudhi::Simplex_tree<> st_; + Bimap_vertex cgal_simplextree; + Delaunay_triangulation* triangulation; + + public: + + Alpha_complex(std::string& off_file_name) + : triangulation(nullptr) { +#ifdef DEBUG_TRACES + char buffer[256]={0}; + sprintf(buffer,"%p", triangulation); + std::cout << "pointer=" << buffer << std::endl; +#endif // DEBUG_TRACES + Gudhi::alphacomplex::Delaunay_triangulation_off_reader off_reader(off_file_name); + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << off_file_name << std::endl; + exit(-1); // ----- >> + } + triangulation = off_reader.get_complex(); +#ifdef DEBUG_TRACES + //char buffer[256]={0}; + sprintf(buffer,"%p", triangulation); + std::cout << "pointer=" << buffer << std::endl; + std::cout << "number of vertices=" << triangulation->number_of_vertices() << std::endl; + std::cout << "number of full cells=" << triangulation->number_of_full_cells() << std::endl; + std::cout << "number of finite full cells=" << triangulation->number_of_finite_full_cells() << std::endl; +#endif // DEBUG_TRACES + init(); + } + + ~Alpha_complex() { + delete triangulation; + } + + private: + + void init() { + st_.set_dimension(triangulation->maximal_dimension()); + + // -------------------------------------------------------------------------------------------- + // bimap to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa + // Start to insert at handle = 0 - default integer value + Vertex_handle vertex_handle = Vertex_handle(); + // Loop on triangulation vertices list + for (CGAL_vertex_iterator vit = triangulation->vertices_begin(); vit != triangulation->vertices_end(); ++vit) { + cgal_simplextree.insert(Bimap_vertex::value_type(vit, vertex_handle)); + vertex_handle++; + } + // -------------------------------------------------------------------------------------------- + + // -------------------------------------------------------------------------------------------- + // Simplex_tree construction from loop on triangulation finite full cells list + for (auto cit = triangulation->finite_full_cells_begin(); cit != triangulation->finite_full_cells_end(); ++cit) { + typeVectorVertex vertexVector; +#ifdef DEBUG_TRACES + std::cout << "Simplex_tree insertion "; +#endif // DEBUG_TRACES + for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { +#ifdef DEBUG_TRACES + std::cout << " " << cgal_simplextree.left.at(*vit); +#endif // DEBUG_TRACES + // Vector of vertex construction for simplex_tree structure + vertexVector.push_back(cgal_simplextree.left.at(*vit)); + } +#ifdef DEBUG_TRACES + std::cout << std::endl; +#endif // DEBUG_TRACES + // Insert each simplex and its subfaces in the simplex tree - filtration is NaN + Simplex_result insert_result = st_.insert_simplex_and_subfaces(vertexVector, + std::numeric_limits::quiet_NaN()); + if (!insert_result.second) { + std::cerr << "Alpha_complex::init insert_simplex_and_subfaces failed" << std::endl; + } + } + // -------------------------------------------------------------------------------------------- + + Filtration_value filtration_max = 0.0; + // -------------------------------------------------------------------------------------------- + // ### For i : d -> 0 + for (int decr_dim = st_.dimension(); decr_dim >= 0; decr_dim--) { + // ### Foreach Sigma of dim i + for (auto f_simplex : st_.skeleton_simplex_range(decr_dim)) { + int f_simplex_dim = st_.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 : st_.simplex_vertex_range(f_simplex)) { + pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); +#ifdef DEBUG_TRACES + std::cout << " " << vertex; +#endif // DEBUG_TRACES + } +#ifdef DEBUG_TRACES + std::cout << std::endl; +#endif // DEBUG_TRACES + // ### If filt(Sigma) is NaN : filt(Sigma) = alpha(Sigma) + if (isnan(st_.filtration(f_simplex))) { + Filtration_value alpha_complex_filtration = 0.0; + // No need to compute squared_radius on a single point - alpha is 0.0 + if (f_simplex_dim > 0) { + // squared_radius function initialization + Kernel k; + Squared_Radius squared_radius Kinit(compute_squared_radius_d_object); + + alpha_complex_filtration = squared_radius(pointVector.begin(), pointVector.end()); + } + st_.assign_filtration(f_simplex, alpha_complex_filtration); + filtration_max = fmax(filtration_max, alpha_complex_filtration); +#ifdef DEBUG_TRACES + std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << st_.filtration(f_simplex) << std::endl; +#endif // DEBUG_TRACES + } + propagate_alpha_filtration(f_simplex, decr_dim); + } + } + } + // -------------------------------------------------------------------------------------------- + +#ifdef DEBUG_TRACES + std::cout << "filtration_max=" << filtration_max << std::endl; +#endif // DEBUG_TRACES + st_.set_filtration(filtration_max); + } + + template + void propagate_alpha_filtration(Simplex_handle f_simplex, int decr_dim) { + // ### Foreach Tau face of Sigma + for (auto f_boundary : st_.boundary_simplex_range(f_simplex)) { +#ifdef DEBUG_TRACES + std::cout << " | --------------------------------------------------" << std::endl; + std::cout << " | Tau "; + for (auto vertex : st_.simplex_vertex_range(f_boundary)) { + std::cout << vertex << " "; + } + std::cout << "is a face of Sigma" << std::endl; + std::cout << " | isnan(filtration(Tau)=" << isnan(st_.filtration(f_boundary)) << std::endl; +#endif // DEBUG_TRACES + // ### If filt(Tau) is not NaN + if (!isnan(st_.filtration(f_boundary))) { + // ### filt(Tau) = fmin(filt(Tau), filt(Sigma)) + Filtration_value alpha_complex_filtration = fmin(st_.filtration(f_boundary), st_.filtration(f_simplex)); + st_.assign_filtration(f_boundary, alpha_complex_filtration); + // No need to check for filtration_max, alpha_complex_filtration is a min of an existing filtration value +#ifdef DEBUG_TRACES + std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << st_.filtration(f_boundary) << std::endl; +#endif // DEBUG_TRACES + // ### Else + } else { + // No need to compute is_gabriel for dimension <= 2 + // i.e. : Sigma = (3,1) => Tau = 1 + if (decr_dim > 1) { + // insert the Tau points in a vector for is_gabriel function + Vector_of_CGAL_points pointVector; + Vertex_handle vertexForGabriel = Vertex_handle(); + for (auto vertex : st_.simplex_vertex_range(f_boundary)) { + pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); + } + // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function + for (auto vertex : st_.simplex_vertex_range(f_simplex)) { + if (std::find(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertex))->point()) + == pointVector.end()) { + // vertex is not found in Tau + vertexForGabriel = vertex; + // No need to continue loop + break; + } + } + // is_gabriel function initialization + Kernel k; + Is_Gabriel is_gabriel Kinit(side_of_bounded_sphere_d_object); +#ifdef DEBUG_TRACES + bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) + != CGAL::ON_BOUNDED_SIDE; + std::cout << " | Tau is_gabriel(Sigma)=" << is_gab << " - vertexForGabriel=" << vertexForGabriel << std::endl; +#endif // DEBUG_TRACES + // ### If Tau is not Gabriel of Sigma + if ((is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) + == CGAL::ON_BOUNDED_SIDE)) { + // ### filt(Tau) = filt(Sigma) + Filtration_value alpha_complex_filtration = st_.filtration(f_simplex); + st_.assign_filtration(f_boundary, alpha_complex_filtration); + // No need to check for filtration_max, alpha_complex_filtration is an existing filtration value +#ifdef DEBUG_TRACES + std::cout << " | filt(Tau) = filt(Sigma) = " << st_.filtration(f_boundary) << std::endl; +#endif // DEBUG_TRACES + } + } + } + } + } + public: + + /** \brief Returns the number of vertices in the complex. */ + size_t num_vertices() { + return st_.num_vertices(); + } + + /** \brief Returns the number of simplices in the complex. + * + * Does not count the empty simplex. */ + const unsigned int& num_simplices() const { + return st_.num_simplices(); + } + + /** \brief Returns an upper bound on the dimension of the simplicial complex. */ + int dimension() { + return st_.dimension(); + } + + /** \brief Returns an upper bound of the filtration values of the simplices. */ + Filtration_value filtration() { + return st_.filtration(); + } + + friend std::ostream& operator<<(std::ostream& os, const Alpha_complex & alpha_complex) { + // TODO: Program terminated with signal SIGABRT, Aborted - Maybe because of copy constructor + Gudhi::Simplex_tree<> st = alpha_complex.st_; + os << st << std::endl; + return os; + } +}; + +} // namespace alphacomplex + +} // namespace Gudhi + +#endif // SRC_ALPHA_COMPLEX_INCLUDE_GUDHI_ALPHA_COMPLEX_H_ diff --git a/src/Alpha_complex/include/gudhi/Alpha_shapes.h b/src/Alpha_complex/include/gudhi/Alpha_shapes.h deleted file mode 100644 index f23df51a..00000000 --- a/src/Alpha_complex/include/gudhi/Alpha_shapes.h +++ /dev/null @@ -1,311 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ -#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ - -// to construct a Delaunay_triangulation from a OFF file -#include - -// to construct a simplex_tree from Delaunay_triangulation -#include -#include - -#include -#include -#include // isnan, fmax - -#include - -#include -#include -#include -#include -#include - -#include -#include -#include -#include -#include -#include - -namespace Gudhi { - -namespace alphashapes { - -#define Kinit(f) =k.f() - -/** \defgroup alpha_shapes Alpha shapes in dimension N - * -
Implementations:
- Alpha shapes in dimension N are a subset of Delaunay Triangulation in dimension N. - - - * \author Vincent Rouvreau - * \version 1.0 - * \date 2015 - * \copyright GNU General Public License v3. - * @{ - */ - -/** - * \brief Alpha shapes data structure. - * - * \details Every simplex \f$[v_0, \cdots ,v_d]\f$ admits a canonical orientation - * induced by the order relation on vertices \f$ v_0 < \cdots < v_d \f$. - * - * Details may be found in \cite boissonnatmariasimplextreealgorithmica. - * - * \implements FilteredComplex - * - */ -class Alpha_shapes { - private: - // From Simplex_tree - /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ - typedef std::vector typeVectorVertex; - - typedef typename Gudhi::Simplex_tree<>::Simplex_handle Simplex_handle; - typedef typename std::pair Simplex_result; - - // From CGAL - /** \brief Kernel for the Delaunay_triangulation. - * Dimension can be set dynamically. - */ - typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - /** \brief Delaunay_triangulation type required to create an alpha-shape. - */ - typedef CGAL::Delaunay_triangulation Delaunay_triangulation; - - typedef typename Kernel::Compute_squared_radius_d Squared_Radius; - typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; - - /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ - typedef std::vector typeVectorPoint; - - private: - /** \brief Upper bound on the simplex tree of the simplicial complex.*/ - Gudhi::Simplex_tree<> st_; - - public: - - Alpha_shapes(std::string& off_file_name) { - // Construct a default Delaunay_triangulation (dim=0) - dim will be set in visitor reader init function - Delaunay_triangulation dt(2); - Gudhi::alphashapes::Delaunay_triangulation_off_reader off_reader(off_file_name, dt); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_name << std::endl; - exit(-1); // ----- >> - } -#ifdef DEBUG_TRACES - std::cout << "number of vertices=" << dt.number_of_vertices() << std::endl; - std::cout << "number of full cells=" << dt.number_of_full_cells() << std::endl; - std::cout << "number of finite full cells=" << dt.number_of_finite_full_cells() << std::endl; -#endif // DEBUG_TRACES - init(dt); - } - - template - Alpha_shapes(T& triangulation) { - init(triangulation); - } - - ~Alpha_shapes() { } - - private: - - template - void init(T& triangulation) { - st_.set_dimension(triangulation.maximal_dimension()); - - // -------------------------------------------------------------------------------------------- - // bimap to retrieve vertex handles from points and vice versa - typedef boost::bimap< Kernel::Point_d, Vertex_handle > bimap_points_vh; - bimap_points_vh points_to_vh; - // Start to insert at handle = 0 - default integer value - Vertex_handle vertex_handle = Vertex_handle(); - // Loop on triangulation vertices list - for (auto vit = triangulation.vertices_begin(); vit != triangulation.vertices_end(); ++vit) { - points_to_vh.insert(bimap_points_vh::value_type(vit->point(), vertex_handle)); - vertex_handle++; - } - // -------------------------------------------------------------------------------------------- - - // -------------------------------------------------------------------------------------------- - // Simplex_tree construction from loop on triangulation finite full cells list - for (auto cit = triangulation.finite_full_cells_begin(); cit != triangulation.finite_full_cells_end(); ++cit) { - typeVectorVertex vertexVector; -#ifdef DEBUG_TRACES - std::cout << "Simplex_tree insertion "; -#endif // DEBUG_TRACES - for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { -#ifdef DEBUG_TRACES - std::cout << " " << points_to_vh.left.at((*vit)->point()); -#endif // DEBUG_TRACES - // Vector of vertex construction for simplex_tree structure - vertexVector.push_back(points_to_vh.left.at((*vit)->point())); - } -#ifdef DEBUG_TRACES - std::cout << std::endl; -#endif // DEBUG_TRACES - // Insert each simplex and its subfaces in the simplex tree - filtration is NaN - Simplex_result insert_result = st_.insert_simplex_and_subfaces(vertexVector, - std::numeric_limits::quiet_NaN()); - if (!insert_result.second) { - std::cerr << "Alpha_shapes::init insert_simplex_and_subfaces failed" << std::endl; - } - } - // -------------------------------------------------------------------------------------------- - - Filtration_value filtration_max = 0.0; - - Kernel k; - Squared_Radius squared_radius Kinit(compute_squared_radius_d_object); - Is_Gabriel is_gabriel Kinit(side_of_bounded_sphere_d_object); - // -------------------------------------------------------------------------------------------- - // ### For i : d -> 0 - for (int decr_dim = st_.dimension(); decr_dim >= 0; decr_dim--) { - // ### Foreach Sigma of dim i - for (auto f_simplex : st_.skeleton_simplex_range(decr_dim)) { - int f_simplex_dim = st_.dimension(f_simplex); - if (decr_dim == f_simplex_dim) { - typeVectorPoint pointVector; -#ifdef DEBUG_TRACES - std::cout << "Sigma of dim " << decr_dim << " is"; -#endif // DEBUG_TRACES - for (auto vertex : st_.simplex_vertex_range(f_simplex)) { - pointVector.push_back(points_to_vh.right.at(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(st_.filtration(f_simplex))) { - Filtration_value alpha_shapes_filtration = 0.0; - // No need to compute squared_radius on a single point - alpha is 0.0 - if (f_simplex_dim > 0) { - alpha_shapes_filtration = squared_radius(pointVector.begin(), pointVector.end()); - } - st_.assign_filtration(f_simplex, alpha_shapes_filtration); - filtration_max = fmax(filtration_max, alpha_shapes_filtration); -#ifdef DEBUG_TRACES - std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << st_.filtration(f_simplex) << std::endl; -#endif // DEBUG_TRACES - } - - // ### Foreach Tau face of Sigma - for (auto f_boundary : st_.boundary_simplex_range(f_simplex)) { -#ifdef DEBUG_TRACES - std::cout << " | --------------------------------------------------" << std::endl; - std::cout << " | Tau "; - for (auto vertex : st_.simplex_vertex_range(f_boundary)) { - std::cout << vertex << " "; - } - std::cout << "is a face of Sigma" << std::endl; -#endif // DEBUG_TRACES - // insert the Tau points in a vector for is_gabriel function - typeVectorPoint pointVector; - Vertex_handle vertexForGabriel = Vertex_handle(); - for (auto vertex : st_.simplex_vertex_range(f_boundary)) { - pointVector.push_back(points_to_vh.right.at(vertex)); - } - // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function - for (auto vertex : st_.simplex_vertex_range(f_simplex)) { - if (std::find(pointVector.begin(), pointVector.end(), points_to_vh.right.at(vertex)) == pointVector.end()) { - // vertex is not found in Tau - vertexForGabriel = vertex; - // No need to continue loop - break; - } - } -#ifdef DEBUG_TRACES - std::cout << " | isnan(filtration(Tau)=" << isnan(st_.filtration(f_boundary)) << std::endl; - bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), points_to_vh.right.at(vertexForGabriel)) - != CGAL::ON_BOUNDED_SIDE; - std::cout << " | Tau is_gabriel(Sigma)=" << is_gab << " - vertexForGabriel=" << vertexForGabriel << std::endl; -#endif // DEBUG_TRACES - // ### If filt(Tau) is not NaN - // ### or Tau is not Gabriel of Sigma - if (!isnan(st_.filtration(f_boundary)) || - (is_gabriel(pointVector.begin(), pointVector.end(), points_to_vh.right.at(vertexForGabriel)) == CGAL::ON_BOUNDED_SIDE) - ) { - // ### filt(Tau) = fmin(filt(Tau), filt(Sigma)) - Filtration_value alpha_shapes_filtration = fmin(st_.filtration(f_boundary), st_.filtration(f_simplex)); - st_.assign_filtration(f_boundary, alpha_shapes_filtration); - filtration_max = fmax(filtration_max, alpha_shapes_filtration); -#ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << st_.filtration(f_boundary) << std::endl; -#endif // DEBUG_TRACES - } - } - } - } - } - // -------------------------------------------------------------------------------------------- - -#ifdef DEBUG_TRACES - std::cout << "filtration_max=" << filtration_max << std::endl; -#endif // DEBUG_TRACES - st_.set_filtration(filtration_max); - } - - public: - - /** \brief Returns the number of vertices in the complex. */ - size_t num_vertices() { - return st_.num_vertices(); - } - - /** \brief Returns the number of simplices in the complex. - * - * Does not count the empty simplex. */ - const unsigned int& num_simplices() const { - return st_.num_simplices(); - } - - /** \brief Returns an upper bound on the dimension of the simplicial complex. */ - int dimension() { - return st_.dimension(); - } - - /** \brief Returns an upper bound of the filtration values of the simplices. */ - Filtration_value filtration() { - return st_.filtration(); - } - - friend std::ostream& operator<<(std::ostream& os, const Alpha_shapes & alpha_shape) { - // TODO: Program terminated with signal SIGABRT, Aborted - Maybe because of copy constructor - Gudhi::Simplex_tree<> st = alpha_shape.st_; - os << st << std::endl; - return os; - } -}; - -} // namespace alphashapes - -} // namespace Gudhi - -#endif // SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ diff --git a/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h b/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h index a4e5e2fe..8bda23b7 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h +++ b/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h @@ -31,20 +31,22 @@ namespace Gudhi { -namespace alphashapes { +namespace alphacomplex { /** *@brief Off reader visitor with flag that can be passed to Off_reader to read a Delaunay_triangulation_complex. */ template class Delaunay_triangulation_off_visitor_reader { - Complex& complex_; + private: + Complex* _complex; typedef typename Complex::Point Point; public: - explicit Delaunay_triangulation_off_visitor_reader(Complex& complex) : - complex_(complex) { } + // Pass a Complex as a parameter is required, even if not used. Otherwise, compilation is KO. + Delaunay_triangulation_off_visitor_reader(Complex* _complex_ptr) + : _complex(nullptr) { } void init(int dim, int num_vertices, int num_faces, int num_edges) { #ifdef DEBUG_TRACES @@ -59,7 +61,8 @@ class Delaunay_triangulation_off_visitor_reader { std::cerr << "Delaunay_triangulation_off_visitor_reader::init edges are not taken into account from OFF " << "file for Delaunay triangulation - edges are computed." << std::endl; } - //complex_.set_current_dimension(dim); + // Complex construction with dimension from file + _complex = new Complex(dim); } void point(const std::vector& point) { @@ -70,7 +73,7 @@ class Delaunay_triangulation_off_visitor_reader { } std::cout << std::endl; #endif // DEBUG_TRACES - complex_.insert(Point(point.size(), point.begin(), point.end())); + _complex->insert(Point(point.size(), point.begin(), point.end())); } void maximal_face(const std::vector& face) { @@ -89,6 +92,10 @@ class Delaunay_triangulation_off_visitor_reader { std::cout << "Delaunay_triangulation_off_visitor_reader::done" << std::endl; #endif // DEBUG_TRACES } + + Complex* get_complex() { + return _complex; + } }; /** @@ -103,12 +110,15 @@ class Delaunay_triangulation_off_reader { * read_complex : complex that will receive the file content * read_only_points : specify true if only the points must be read */ - Delaunay_triangulation_off_reader(const std::string & name_file, Complex& read_complex) : valid_(false) { + Delaunay_triangulation_off_reader(const std::string & name_file) : valid_(false) { std::ifstream stream(name_file); if (stream.is_open()) { - Delaunay_triangulation_off_visitor_reader off_visitor(read_complex); + Delaunay_triangulation_off_visitor_reader off_visitor(_complex); Off_reader off_reader(stream); valid_ = off_reader.read(off_visitor); + if (valid_) { + _complex = off_visitor.get_complex(); + } } else { std::cerr << "Delaunay_triangulation_off_reader::Delaunay_triangulation_off_reader could not open file " << name_file << std::endl; @@ -123,8 +133,16 @@ class Delaunay_triangulation_off_reader { return valid_; } + Complex* get_complex() { + if (valid_) + return _complex; + return nullptr; + + } + private: bool valid_; + Complex* _complex; }; template @@ -137,20 +155,20 @@ class Delaunay_triangulation_off_writer { * save_complex : complex that be outputted in the file * for now only save triangles. */ - Delaunay_triangulation_off_writer(const std::string & name_file, const Complex& save_complex) { + Delaunay_triangulation_off_writer(const std::string & name_file, Complex* complex_ptr) { std::ofstream stream(name_file); if (stream.is_open()) { - if (save_complex.current_dimension() == 3) { + if (complex_ptr->current_dimension() == 3) { // OFF header stream << "OFF" << std::endl; // no endl on next line - don't know why... - stream << save_complex.number_of_vertices() << " " << save_complex.number_of_finite_full_cells() << " 0"; + stream << complex_ptr->number_of_vertices() << " " << complex_ptr->number_of_finite_full_cells() << " 0"; } else { // nOFF header stream << "nOFF" << std::endl; // no endl on next line - don't know why... - stream << save_complex.current_dimension() << " " << save_complex.number_of_vertices() << " " << - save_complex.number_of_finite_full_cells() << " 0"; + stream << complex_ptr->current_dimension() << " " << complex_ptr->number_of_vertices() << " " << + complex_ptr->number_of_finite_full_cells() << " 0"; } @@ -160,7 +178,7 @@ class Delaunay_triangulation_off_writer { int vertex_handle = int(); // Points list - for (auto vit = save_complex.vertices_begin(); vit != save_complex.vertices_end(); ++vit) { + for (auto vit = complex_ptr->vertices_begin(); vit != complex_ptr->vertices_end(); ++vit) { for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { stream << *Coord << " "; } @@ -169,7 +187,7 @@ class Delaunay_triangulation_off_writer { vertex_handle++; } - for (auto cit = save_complex.finite_full_cells_begin(); cit != save_complex.finite_full_cells_end(); ++cit) { + for (auto cit = complex_ptr->finite_full_cells_begin(); cit != complex_ptr->finite_full_cells_end(); ++cit) { std::vector vertexVector; stream << std::distance(cit->vertices_begin(), cit->vertices_end()) << " "; for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { @@ -185,7 +203,7 @@ class Delaunay_triangulation_off_writer { } }; -} // namespace alphashapes +} // namespace alphacomplex } // namespace Gudhi 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..38168f10 --- /dev/null +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -0,0 +1,126 @@ +/* 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 . + */ + +#define BOOST_TEST_MODULE alpha_complex +#include +#include +#include +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" +#include "gudhi/Alpha_complex.h" + +// to construct a simplex_tree from Delaunay_triangulation +#include "gudhi/graph_simplicial_complex.h" +#include "gudhi/Simplex_tree.h" + +#include +#include +#include +#include +#include + +#include +#include + +#include +#include +#include + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; +typedef CGAL::Delaunay_triangulation T; +// The triangulation uses the default instantiation of the +// TriangulationDataStructure template parameter + +BOOST_AUTO_TEST_CASE( OFF_file ) { + // ---------------------------------------------------------------------------- + // + // Init of an alpha-complex from a OFF file + // + // ---------------------------------------------------------------------------- + std::string off_file_name("S4_100.off"); + std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; + + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + + const int DIMENSION = 4; + std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); + + const double FILTRATION = 0.0; + std::cout << "alpha_complex_from_file.filtration()=" << alpha_complex_from_file.filtration() << std::endl; + BOOST_CHECK(alpha_complex_from_file.filtration() == FILTRATION); + + const int NUMBER_OF_VERTICES = 100; + std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); + + const int NUMBER_OF_SIMPLICES = 6779; + 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( Delaunay_triangulation ) { + // ---------------------------------------------------------------------------- + // + // Init of an alpha-complex from a Delaunay triangulation + // + // ---------------------------------------------------------------------------- + T dt; + std::string off_file_name("S8_10.off"); + std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; + + Gudhi::alphacomplex::Delaunay_triangulation_off_reader off_reader(off_file_name, dt); + std::cout << "off_reader.is_valid()=" << off_reader.is_valid() << std::endl; + BOOST_CHECK(off_reader.is_valid()); + + const int NUMBER_OF_VERTICES = 10; + std::cout << "dt.number_of_vertices()=" << dt.number_of_vertices() << std::endl; + BOOST_CHECK(dt.number_of_vertices() == NUMBER_OF_VERTICES); + + const int NUMBER_OF_FULL_CELLS = 30; + std::cout << "dt.number_of_full_cells()=" << dt.number_of_full_cells() << std::endl; + BOOST_CHECK(dt.number_of_full_cells() == NUMBER_OF_FULL_CELLS); + + const int NUMBER_OF_FINITE_FULL_CELLS = 6; + std::cout << "dt.number_of_finite_full_cells()=" << dt.number_of_finite_full_cells() << std::endl; + BOOST_CHECK(dt.number_of_finite_full_cells() == NUMBER_OF_FINITE_FULL_CELLS); + + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_dt(dt); + + const int DIMENSION = 8; + std::cout << "alpha_complex_from_dt.dimension()=" << alpha_complex_from_dt.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_dt.dimension() == DIMENSION); + + const double FILTRATION = 0.0; + std::cout << "alpha_complex_from_dt.filtration()=" << alpha_complex_from_dt.filtration() << std::endl; + BOOST_CHECK(alpha_complex_from_dt.filtration() == FILTRATION); + + std::cout << "alpha_complex_from_dt.num_vertices()=" << alpha_complex_from_dt.num_vertices() << std::endl; + BOOST_CHECK(alpha_complex_from_dt.num_vertices() == NUMBER_OF_VERTICES); + + const int NUMBER_OF_SIMPLICES = 997; + std::cout << "alpha_complex_from_dt.num_simplices()=" << alpha_complex_from_dt.num_simplices() << std::endl; + BOOST_CHECK(alpha_complex_from_dt.num_simplices() == NUMBER_OF_SIMPLICES); +} + diff --git a/src/Alpha_complex/test/Alpha_shapes_unit_test.cpp b/src/Alpha_complex/test/Alpha_shapes_unit_test.cpp deleted file mode 100644 index d5db3bfa..00000000 --- a/src/Alpha_complex/test/Alpha_shapes_unit_test.cpp +++ /dev/null @@ -1,126 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#define BOOST_TEST_MODULE alpha_shapes -#include -#include -#include -// to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" -#include "gudhi/Alpha_shapes.h" - -// to construct a simplex_tree from Delaunay_triangulation -#include "gudhi/graph_simplicial_complex.h" -#include "gudhi/Simplex_tree.h" - -#include -#include -#include -#include -#include - -#include -#include - -#include -#include -#include - -// Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; -typedef CGAL::Delaunay_triangulation T; -// The triangulation uses the default instanciation of the -// TriangulationDataStructure template parameter - -BOOST_AUTO_TEST_CASE( OFF_file ) { - // ---------------------------------------------------------------------------- - // - // Init of an alpha-shape from a OFF file - // - // ---------------------------------------------------------------------------- - std::string off_file_name("S4_100.off"); - std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_file(off_file_name, 4); - - const int DIMENSION = 4; - std::cout << "alpha_shapes_from_file.dimension()=" << alpha_shapes_from_file.dimension() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.dimension() == DIMENSION); - - const double FILTRATION = 0.0; - std::cout << "alpha_shapes_from_file.filtration()=" << alpha_shapes_from_file.filtration() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.filtration() == FILTRATION); - - const int NUMBER_OF_VERTICES = 100; - std::cout << "alpha_shapes_from_file.num_vertices()=" << alpha_shapes_from_file.num_vertices() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.num_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_SIMPLICES = 6779; - std::cout << "alpha_shapes_from_file.num_simplices()=" << alpha_shapes_from_file.num_simplices() << std::endl; - BOOST_CHECK(alpha_shapes_from_file.num_simplices() == NUMBER_OF_SIMPLICES); - -} - -BOOST_AUTO_TEST_CASE( Delaunay_triangulation ) { - // ---------------------------------------------------------------------------- - // - // Init of an alpha-shape from a Delauny triangulation - // - // ---------------------------------------------------------------------------- - T dt(8); - std::string off_file_name("S8_10.off"); - std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - - Gudhi::alphashapes::Delaunay_triangulation_off_reader off_reader(off_file_name, dt); - std::cout << "off_reader.is_valid()=" << off_reader.is_valid() << std::endl; - BOOST_CHECK(off_reader.is_valid()); - - const int NUMBER_OF_VERTICES = 10; - std::cout << "dt.number_of_vertices()=" << dt.number_of_vertices() << std::endl; - BOOST_CHECK(dt.number_of_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_FULL_CELLS = 30; - std::cout << "dt.number_of_full_cells()=" << dt.number_of_full_cells() << std::endl; - BOOST_CHECK(dt.number_of_full_cells() == NUMBER_OF_FULL_CELLS); - - const int NUMBER_OF_FINITE_FULL_CELLS = 6; - std::cout << "dt.number_of_finite_full_cells()=" << dt.number_of_finite_full_cells() << std::endl; - BOOST_CHECK(dt.number_of_finite_full_cells() == NUMBER_OF_FINITE_FULL_CELLS); - - Gudhi::alphashapes::Alpha_shapes alpha_shapes_from_dt(dt); - - const int DIMENSION = 8; - std::cout << "alpha_shapes_from_dt.dimension()=" << alpha_shapes_from_dt.dimension() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.dimension() == DIMENSION); - - const double FILTRATION = 0.0; - std::cout << "alpha_shapes_from_dt.filtration()=" << alpha_shapes_from_dt.filtration() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.filtration() == FILTRATION); - - std::cout << "alpha_shapes_from_dt.num_vertices()=" << alpha_shapes_from_dt.num_vertices() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.num_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_SIMPLICES = 997; - std::cout << "alpha_shapes_from_dt.num_simplices()=" << alpha_shapes_from_dt.num_simplices() << std::endl; - BOOST_CHECK(alpha_shapes_from_dt.num_simplices() == NUMBER_OF_SIMPLICES); -} - diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index 3cf97b71..72e8390a 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -1,5 +1,5 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHIAlphaShapesTest) +project(GUDHIAlphaComplexTest) # need CGAL 4.7 # cmake -DCGAL_DIR=~/workspace/CGAL-4.7-Ic-41 ../../.. @@ -16,16 +16,16 @@ if(CGAL_FOUND) include_directories (BEFORE "../../include") add_definitions(-DDEBUG_TRACES) - add_executable ( AlphaShapesUnitTest Alpha_shapes_unit_test.cpp ) - target_link_libraries(AlphaShapesUnitTest ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) - add_test(AlphaShapesUnitTest ${CMAKE_CURRENT_BINARY_DIR}/AlphaShapesUnitTest) + add_executable ( AlphaComplexUnitTest Alpha_complex_unit_test.cpp ) + target_link_libraries(AlphaComplexUnitTest ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + add_test(AlphaComplexUnitTest ${CMAKE_CURRENT_BINARY_DIR}/AlphaComplexUnitTest) else() - message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + 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 shapes feature. Version 4.6.0 is required.") + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha complex feature. Version 4.6.0 is required.") endif () endif() -cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/Alpha_shapes/include/gudhi") +cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/Alpha_complex/include/gudhi") diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index ceb993fa..e0d5ff28 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -37,7 +37,7 @@ else() add_subdirectory(example/Skeleton_blocker) add_subdirectory(example/Contraction) add_subdirectory(example/Hasse_complex) - add_subdirectory(example/Alpha_shapes) + add_subdirectory(example/Alpha_complex) add_subdirectory(example/Bottleneck) endif() -- cgit v1.2.3 From 56e89b6b7666dec86a70f6a30f08ef8b7960eb21 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 18 Jun 2015 14:21:31 +0000 Subject: Moved alphashapedoc.off in data/points Moved Delaunay triangulation OFF files read and write in src/common Delaunay triangulation OFF files read and write documentation, examples and tests git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@623 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e03902736a79436e97dbf77a88504f3faa8bd9c6 --- CMakeLists.txt | 9 +- data/points/alphashapedoc.off | 10 + src/Alpha_complex/example/CMakeLists.txt | 9 +- .../example/Delaunay_triangulation_off_rw.cpp | 79 ------ .../Simplex_tree_from_delaunay_triangulation.cpp | 27 +- src/Alpha_complex/example/alphashapedoc.off | 10 - src/Alpha_complex/include/gudhi/Alpha_complex.h | 70 +++-- .../Alpha_shapes/Delaunay_triangulation_off_io.h | 210 -------------- src/Alpha_complex/test/Alpha_complex_unit_test.cpp | 71 ++--- src/Alpha_complex/test/CMakeLists.txt | 2 +- src/Alpha_complex/test/README | 2 +- src/Alpha_complex/test/S4_100.off | 4 +- src/Alpha_complex/test/S8_10.off | 4 +- src/CMakeLists.txt | 1 + src/Doxyfile | 3 +- src/common/example/CMakeLists.txt | 26 ++ .../example/Delaunay_triangulation_off_rw.cpp | 55 ++++ .../include/gudhi/Delaunay_triangulation_off_io.h | 308 +++++++++++++++++++++ src/common/include/gudhi/Off_reader.h | 291 ++++++++++--------- src/common/test/CMakeLists.txt | 44 +++ src/common/test/README | 14 + src/common/test/dtoffrw_alphashapedoc_result.off | 15 + src/common/test/dtoffrw_alphashapedoc_result.txt | 3 + src/common/test/dtoffrw_unit_test.cpp | 91 ++++++ 24 files changed, 790 insertions(+), 568 deletions(-) create mode 100755 data/points/alphashapedoc.off delete mode 100644 src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp delete mode 100755 src/Alpha_complex/example/alphashapedoc.off delete mode 100644 src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h create mode 100644 src/common/example/CMakeLists.txt create mode 100644 src/common/example/Delaunay_triangulation_off_rw.cpp create mode 100644 src/common/include/gudhi/Delaunay_triangulation_off_io.h create mode 100644 src/common/test/CMakeLists.txt create mode 100644 src/common/test/README create mode 100644 src/common/test/dtoffrw_alphashapedoc_result.off create mode 100644 src/common/test/dtoffrw_alphashapedoc_result.txt create mode 100644 src/common/test/dtoffrw_unit_test.cpp (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/CMakeLists.txt b/CMakeLists.txt index 01108db9..86b4e2b6 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -42,6 +42,11 @@ if (PYTHON_PATH) message("python found in ${PYTHON_PATH}") endif() +FIND_PROGRAM( DIFF_PATH diff ) +if (DIFF_PATH) + message("diff found in ${DIFF_PATH}") +endif() + # Function to add_test cpplint on each header file of the Gudhi module function(cpplint_add_tests the_directory) if (PYTHON_PATH) @@ -77,9 +82,11 @@ else() include_directories(src/Simplex_tree/include/) include_directories(src/Skeleton_blocker/include/) + add_subdirectory(src/common/example) + add_subdirectory(src/common/test) add_subdirectory(src/Simplex_tree/test) add_subdirectory(src/Simplex_tree/example) - add_subdirectory(src/Persistent_cohomology/test) + #add_subdirectory(src/Persistent_cohomology/test) add_subdirectory(src/Persistent_cohomology/example) add_subdirectory(src/Skeleton_blocker/test) add_subdirectory(src/Skeleton_blocker/example) diff --git a/data/points/alphashapedoc.off b/data/points/alphashapedoc.off new file mode 100755 index 00000000..bb790193 --- /dev/null +++ b/data/points/alphashapedoc.off @@ -0,0 +1,10 @@ +nOFF +2 7 0 0 +1.0 1.0 +7.0 0.0 +4.0 6.0 +9.0 6.0 +0.0 14.0 +2.0 19.0 +9.0 17.0 + diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt index 258def49..9129fdcf 100644 --- a/src/Alpha_complex/example/CMakeLists.txt +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -14,17 +14,10 @@ if(CGAL_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) - add_definitions(-DDEBUG_TRACES) - - add_executable ( dtoffrw Delaunay_triangulation_off_rw.cpp ) - target_link_libraries(dtoffrw ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test(dtoffrw_tore3D ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off 3) - + #add_definitions(-DDEBUG_TRACES) add_executable ( stfromdt Simplex_tree_from_delaunay_triangulation.cpp ) target_link_libraries(stfromdt ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_executable ( template_off template_off.cpp ) - target_link_libraries(template_off ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) else() message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") endif() diff --git a/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp b/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp deleted file mode 100644 index 405b3cb9..00000000 --- a/src/Alpha_complex/example/Delaunay_triangulation_off_rw.cpp +++ /dev/null @@ -1,79 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Vincent Rouvreau - * - * Copyright (C) 2014 INRIA Saclay (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -// to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" - -#include -#include -#include -#include -#include - -#include -#include -#include - -#include -#include -#include - -// Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; -typedef CGAL::Delaunay_triangulation T; -// The triangulation uses the default instanciation of the -// TriangulationDataStructure template parameter - -void usage(char * const progName) { - std::cerr << "Usage: " << progName << " inputFile.off dimension outputFile.off" << std::endl; - exit(-1); // ----- >> -} - -int main(int argc, char **argv) { - if (argc != 4) { - std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; - usage(argv[0]); - } - - int dimension = 0; - int returnedScanValue = sscanf(argv[2], "%d", &dimension); - if ((returnedScanValue == EOF) || (dimension <= 0)) { - std::cerr << "Error: " << argv[2] << " is not correct" << std::endl; - usage(argv[0]); - } - - T dt(dimension); - std::string offFileName(argv[1]); - Gudhi::alphacomplex::Delaunay_triangulation_off_reader off_reader(offFileName, dt); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << offFileName << std::endl; - exit(-1); // ----- >> - } - - std::cout << "number_of_finite_full_cells= " << dt.number_of_finite_full_cells() << std::endl; - - std::string outFileName(argv[3]); - std::string offOutputFile(outFileName); - Gudhi::alphacomplex::Delaunay_triangulation_off_writer off_writer(offOutputFile, dt); - - return 0; -} \ No newline at end of file diff --git a/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp b/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp index f09e6121..1523372a 100644 --- a/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp +++ b/src/Alpha_complex/example/Simplex_tree_from_delaunay_triangulation.cpp @@ -21,19 +21,13 @@ */ // to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" +#include "gudhi/Delaunay_triangulation_off_io.h" #include "gudhi/Alpha_complex.h" // to construct a simplex_tree from Delaunay_triangulation #include "gudhi/graph_simplicial_complex.h" #include "gudhi/Simplex_tree.h" -#include -#include -#include -#include -#include - #include #include @@ -41,12 +35,6 @@ #include #include -// Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; -typedef CGAL::Delaunay_triangulation T; -// The triangulation uses the default instanciation of the -// TriangulationDataStructure template parameter - void usage(char * const progName) { std::cerr << "Usage: " << progName << " filename.off" << std::endl; exit(-1); // ----- >> @@ -62,7 +50,7 @@ int main(int argc, char **argv) { // ---------------------------------------------------------------------------- // - // Init of an alpha-complex from a OFF file + // Init of an alpha-complex from an OFF file // // ---------------------------------------------------------------------------- Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); @@ -71,7 +59,14 @@ int main(int argc, char **argv) { std::cout << "alpha_complex_from_file.filtration()=" << alpha_complex_from_file.filtration() << std::endl; std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; - std::cout << alpha_complex_from_file << std::endl; - + + std::cout << "Iterator on Simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : alpha_complex_from_file.filtration_simplex_range()) { + std::cout << " " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] "; + for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } return 0; } \ No newline at end of file diff --git a/src/Alpha_complex/example/alphashapedoc.off b/src/Alpha_complex/example/alphashapedoc.off deleted file mode 100755 index bb790193..00000000 --- a/src/Alpha_complex/example/alphashapedoc.off +++ /dev/null @@ -1,10 +0,0 @@ -nOFF -2 7 0 0 -1.0 1.0 -7.0 0.0 -4.0 6.0 -9.0 6.0 -0.0 14.0 -2.0 19.0 -9.0 17.0 - diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index ca84d6d9..d25c05cb 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -23,9 +23,6 @@ #ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ #define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_H_ -// to construct a Delaunay_triangulation from a OFF file -#include - // to construct a simplex_tree from Delaunay_triangulation #include #include @@ -46,8 +43,7 @@ #include #include #include -#include -#include +#include // NaN namespace Gudhi { @@ -82,59 +78,59 @@ class Alpha_complex { private: // From Simplex_tree /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ - typedef std::vector typeVectorVertex; + typedef std::vector Vector_vertex; + /** \brief Simplex_handle type from simplex_tree.*/ typedef typename Gudhi::Simplex_tree<>::Simplex_handle Simplex_handle; + /** \brief Simplex_result is the type returned from simplex_tree insert function.*/ typedef typename std::pair Simplex_result; + /** \brief Filtration_simplex_range type from simplex_tree.*/ + typedef typename Gudhi::Simplex_tree<>::Filtration_simplex_range Filtration_simplex_range; + + /** \brief Simplex_vertex_range type from simplex_tree.*/ + typedef typename Gudhi::Simplex_tree<>::Simplex_vertex_range Simplex_vertex_range; + // From CGAL - /** \brief Kernel for the Delaunay_triangulation-> - * Dimension can be set dynamically. - */ + /** \brief Kernel for the Delaunay_triangulation. Dimension can be set dynamically.*/ typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - /** \brief Delaunay_triangulation type required to create an alpha-complex. - */ + /** \brief Delaunay_triangulation type required to create an alpha-complex.*/ typedef CGAL::Delaunay_triangulation Delaunay_triangulation; typedef typename Kernel::Compute_squared_radius_d Squared_Radius; typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; - /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ + /** \brief Type required to compute squared radius, or side of bounded sphere on a vector of points.*/ typedef std::vector Vector_of_CGAL_points; + /** \brief Vertex_iterator type from CGAL.*/ typedef Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; + /** \brief Boost bimap type to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa.*/ typedef boost::bimap< CGAL_vertex_iterator, Vertex_handle > Bimap_vertex; private: - /** \brief Upper bound on the simplex tree of the simplicial complex.*/ + /** \brief Alpha complex is represented internally by a simplex tree.*/ Gudhi::Simplex_tree<> st_; + /** \brief Boost bimap to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa.*/ Bimap_vertex cgal_simplextree; + /** \brief Pointer on the CGAL Delaunay triangulation.*/ Delaunay_triangulation* triangulation; public: - Alpha_complex(std::string& off_file_name) : triangulation(nullptr) { -#ifdef DEBUG_TRACES - char buffer[256]={0}; - sprintf(buffer,"%p", triangulation); - std::cout << "pointer=" << buffer << std::endl; -#endif // DEBUG_TRACES - Gudhi::alphacomplex::Delaunay_triangulation_off_reader off_reader(off_file_name); + Gudhi::Delaunay_triangulation_off_reader off_reader(off_file_name); if (!off_reader.is_valid()) { std::cerr << "Unable to read file " << off_file_name << std::endl; exit(-1); // ----- >> } triangulation = off_reader.get_complex(); -#ifdef DEBUG_TRACES - //char buffer[256]={0}; - sprintf(buffer,"%p", triangulation); - std::cout << "pointer=" << buffer << std::endl; - std::cout << "number of vertices=" << triangulation->number_of_vertices() << std::endl; - std::cout << "number of full cells=" << triangulation->number_of_full_cells() << std::endl; - std::cout << "number of finite full cells=" << triangulation->number_of_finite_full_cells() << std::endl; -#endif // DEBUG_TRACES + init(); + } + + Alpha_complex(Delaunay_triangulation* triangulation_ptr) + : triangulation(triangulation_ptr) { init(); } @@ -142,6 +138,21 @@ class Alpha_complex { delete triangulation; } + Filtration_simplex_range filtration_simplex_range() { + return st_.filtration_simplex_range(); + } + + Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) { + return st_.simplex_vertex_range(sh); + } + + /** \brief Returns the filtration value of a simplex. + * + * Called on the null_simplex, returns INFINITY. */ + Gudhi::Simplex_tree<>::Filtration_value filtration(Simplex_handle sh) { + return st_.filtration(sh); + } + private: void init() { @@ -161,7 +172,7 @@ class Alpha_complex { // -------------------------------------------------------------------------------------------- // 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) { - typeVectorVertex vertexVector; + Vector_vertex vertexVector; #ifdef DEBUG_TRACES std::cout << "Simplex_tree insertion "; #endif // DEBUG_TRACES @@ -325,7 +336,6 @@ class Alpha_complex { } friend std::ostream& operator<<(std::ostream& os, const Alpha_complex & alpha_complex) { - // TODO: Program terminated with signal SIGABRT, Aborted - Maybe because of copy constructor Gudhi::Simplex_tree<> st = alpha_complex.st_; os << st << std::endl; return os; diff --git a/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h b/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h deleted file mode 100644 index 8bda23b7..00000000 --- a/src/Alpha_complex/include/gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h +++ /dev/null @@ -1,210 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ -#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ -#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ - -#include -#include -#include -#include - -#include "gudhi/Off_reader.h" - -namespace Gudhi { - -namespace alphacomplex { - -/** - *@brief Off reader visitor with flag that can be passed to Off_reader to read a Delaunay_triangulation_complex. - */ -template -class Delaunay_triangulation_off_visitor_reader { - private: - Complex* _complex; - typedef typename Complex::Point Point; - - public: - - // Pass a Complex as a parameter is required, even if not used. Otherwise, compilation is KO. - Delaunay_triangulation_off_visitor_reader(Complex* _complex_ptr) - : _complex(nullptr) { } - - void init(int dim, int num_vertices, int num_faces, int num_edges) { -#ifdef DEBUG_TRACES - std::cout << "Delaunay_triangulation_off_visitor_reader::init - dim=" << dim << " - num_vertices=" << - num_vertices << " - num_faces=" << num_faces << " - num_edges=" << num_edges << std::endl; -#endif // DEBUG_TRACES - if (num_faces > 0) { - std::cerr << "Delaunay_triangulation_off_visitor_reader::init faces are not taken into account from OFF " << - "file for Delaunay triangulation - faces are computed." << std::endl; - } - if (num_edges > 0) { - std::cerr << "Delaunay_triangulation_off_visitor_reader::init edges are not taken into account from OFF " << - "file for Delaunay triangulation - edges are computed." << std::endl; - } - // Complex construction with dimension from file - _complex = new Complex(dim); - } - - void point(const std::vector& point) { -#ifdef DEBUG_TRACES - std::cout << "Delaunay_triangulation_off_visitor_reader::point "; - for (auto coordinate : point) { - std::cout << coordinate << " | "; - } - std::cout << std::endl; -#endif // DEBUG_TRACES - _complex->insert(Point(point.size(), point.begin(), point.end())); - } - - void maximal_face(const std::vector& face) { - // For Delaunay Triangulation, only points are read -#ifdef DEBUG_TRACES - std::cout << "Delaunay_triangulation_off_visitor_reader::face "; - for (auto vertex : face) { - std::cout << vertex << " | "; - } - std::cout << std::endl; -#endif // DEBUG_TRACES - } - - void done() { -#ifdef DEBUG_TRACES - std::cout << "Delaunay_triangulation_off_visitor_reader::done" << std::endl; -#endif // DEBUG_TRACES - } - - Complex* get_complex() { - return _complex; - } -}; - -/** - *@brief Class that allows to load a Delaunay_triangulation_complex from an off file. - */ -template -class Delaunay_triangulation_off_reader { - public: - - /** - * name_file : file to read - * read_complex : complex that will receive the file content - * read_only_points : specify true if only the points must be read - */ - Delaunay_triangulation_off_reader(const std::string & name_file) : valid_(false) { - std::ifstream stream(name_file); - if (stream.is_open()) { - Delaunay_triangulation_off_visitor_reader off_visitor(_complex); - Off_reader off_reader(stream); - valid_ = off_reader.read(off_visitor); - if (valid_) { - _complex = off_visitor.get_complex(); - } - } else { - std::cerr << "Delaunay_triangulation_off_reader::Delaunay_triangulation_off_reader could not open file " << - name_file << std::endl; - } - - } - - /** - * return true if reading did not meet problems. - */ - bool is_valid() const { - return valid_; - } - - Complex* get_complex() { - if (valid_) - return _complex; - return nullptr; - - } - - private: - bool valid_; - Complex* _complex; -}; - -template -class Delaunay_triangulation_off_writer { - public: - typedef typename Complex::Point Point; - - /** - * name_file : file where the off will be written - * save_complex : complex that be outputted in the file - * for now only save triangles. - */ - Delaunay_triangulation_off_writer(const std::string & name_file, Complex* complex_ptr) { - std::ofstream stream(name_file); - if (stream.is_open()) { - if (complex_ptr->current_dimension() == 3) { - // OFF header - stream << "OFF" << std::endl; - // no endl on next line - don't know why... - stream << complex_ptr->number_of_vertices() << " " << complex_ptr->number_of_finite_full_cells() << " 0"; - } else { - // nOFF header - stream << "nOFF" << std::endl; - // no endl on next line - don't know why... - stream << complex_ptr->current_dimension() << " " << complex_ptr->number_of_vertices() << " " << - complex_ptr->number_of_finite_full_cells() << " 0"; - - } - - // bimap to retrieve vertex handles from points and vice versa - std::map< Point, int > points_to_vh; - // Start to insert at default handle value - int vertex_handle = int(); - - // Points list - for (auto vit = complex_ptr->vertices_begin(); vit != complex_ptr->vertices_end(); ++vit) { - for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { - stream << *Coord << " "; - } - stream << std::endl; - points_to_vh[vit->point()] = vertex_handle; - vertex_handle++; - } - - for (auto cit = complex_ptr->finite_full_cells_begin(); cit != complex_ptr->finite_full_cells_end(); ++cit) { - std::vector vertexVector; - stream << std::distance(cit->vertices_begin(), cit->vertices_end()) << " "; - for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { - stream << points_to_vh[(*vit)->point()] << " "; - } - stream << std::endl; - } - stream.close(); - } else { - std::cerr << "Delaunay_triangulation_off_writer::Delaunay_triangulation_off_writer could not open file " << - name_file << std::endl; - } - } -}; - -} // namespace alphacomplex - -} // namespace Gudhi - -#endif // SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ diff --git a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp index 38168f10..86d4d9c3 100644 --- a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -25,25 +25,10 @@ #include #include // to construct a Delaunay_triangulation from a OFF file -#include "gudhi/Alpha_shapes/Delaunay_triangulation_off_io.h" +#include "gudhi/Delaunay_triangulation_off_io.h" #include "gudhi/Alpha_complex.h" -// to construct a simplex_tree from Delaunay_triangulation -#include "gudhi/graph_simplicial_complex.h" -#include "gudhi/Simplex_tree.h" - -#include -#include -#include -#include -#include - -#include -#include - -#include -#include -#include +#include // float comparison // Use dynamic_dimension_tag for the user to be able to set dimension typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; @@ -51,7 +36,7 @@ typedef CGAL::Delaunay_triangulation T; // The triangulation uses the default instantiation of the // TriangulationDataStructure template parameter -BOOST_AUTO_TEST_CASE( OFF_file ) { +BOOST_AUTO_TEST_CASE( S4_100_OFF_file ) { // ---------------------------------------------------------------------------- // // Init of an alpha-complex from a OFF file @@ -66,61 +51,37 @@ BOOST_AUTO_TEST_CASE( OFF_file ) { std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); - const double FILTRATION = 0.0; - std::cout << "alpha_complex_from_file.filtration()=" << alpha_complex_from_file.filtration() << std::endl; - BOOST_CHECK(alpha_complex_from_file.filtration() == FILTRATION); - const int NUMBER_OF_VERTICES = 100; std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); - const int NUMBER_OF_SIMPLICES = 6779; + const int NUMBER_OF_SIMPLICES = 6879; std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; BOOST_CHECK(alpha_complex_from_file.num_simplices() == NUMBER_OF_SIMPLICES); } -BOOST_AUTO_TEST_CASE( Delaunay_triangulation ) { +BOOST_AUTO_TEST_CASE( S8_10_OFF_file ) { // ---------------------------------------------------------------------------- // - // Init of an alpha-complex from a Delaunay triangulation + // Init of an alpha-complex from a OFF file // // ---------------------------------------------------------------------------- - T dt; std::string off_file_name("S8_10.off"); std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - Gudhi::alphacomplex::Delaunay_triangulation_off_reader off_reader(off_file_name, dt); - std::cout << "off_reader.is_valid()=" << off_reader.is_valid() << std::endl; - BOOST_CHECK(off_reader.is_valid()); - - const int NUMBER_OF_VERTICES = 10; - std::cout << "dt.number_of_vertices()=" << dt.number_of_vertices() << std::endl; - BOOST_CHECK(dt.number_of_vertices() == NUMBER_OF_VERTICES); - - const int NUMBER_OF_FULL_CELLS = 30; - std::cout << "dt.number_of_full_cells()=" << dt.number_of_full_cells() << std::endl; - BOOST_CHECK(dt.number_of_full_cells() == NUMBER_OF_FULL_CELLS); - - const int NUMBER_OF_FINITE_FULL_CELLS = 6; - std::cout << "dt.number_of_finite_full_cells()=" << dt.number_of_finite_full_cells() << std::endl; - BOOST_CHECK(dt.number_of_finite_full_cells() == NUMBER_OF_FINITE_FULL_CELLS); - - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_dt(dt); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); const int DIMENSION = 8; - std::cout << "alpha_complex_from_dt.dimension()=" << alpha_complex_from_dt.dimension() << std::endl; - BOOST_CHECK(alpha_complex_from_dt.dimension() == DIMENSION); - - const double FILTRATION = 0.0; - std::cout << "alpha_complex_from_dt.filtration()=" << alpha_complex_from_dt.filtration() << std::endl; - BOOST_CHECK(alpha_complex_from_dt.filtration() == FILTRATION); + std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; + BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); - std::cout << "alpha_complex_from_dt.num_vertices()=" << alpha_complex_from_dt.num_vertices() << std::endl; - BOOST_CHECK(alpha_complex_from_dt.num_vertices() == NUMBER_OF_VERTICES); + const int NUMBER_OF_VERTICES = 10; + std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); - const int NUMBER_OF_SIMPLICES = 997; - std::cout << "alpha_complex_from_dt.num_simplices()=" << alpha_complex_from_dt.num_simplices() << std::endl; - BOOST_CHECK(alpha_complex_from_dt.num_simplices() == NUMBER_OF_SIMPLICES); -} + const int NUMBER_OF_SIMPLICES = 1007; + std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; + BOOST_CHECK(alpha_complex_from_file.num_simplices() == NUMBER_OF_SIMPLICES); +} diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index 72e8390a..4fe69ce5 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -15,7 +15,7 @@ if(CGAL_FOUND) include( ${EIGEN3_USE_FILE} ) include_directories (BEFORE "../../include") - add_definitions(-DDEBUG_TRACES) + #add_definitions(-DDEBUG_TRACES) add_executable ( AlphaComplexUnitTest Alpha_complex_unit_test.cpp ) target_link_libraries(AlphaComplexUnitTest ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) add_test(AlphaComplexUnitTest ${CMAKE_CURRENT_BINARY_DIR}/AlphaComplexUnitTest) diff --git a/src/Alpha_complex/test/README b/src/Alpha_complex/test/README index 244a2b84..45b87d91 100644 --- a/src/Alpha_complex/test/README +++ b/src/Alpha_complex/test/README @@ -7,6 +7,6 @@ make To launch with details: *********************** -./AlphaShapesUnitTest --report_level=detailed --log_level=all +./AlphaComplexUnitTest --report_level=detailed --log_level=all ==> echo $? returns 0 in case of success (non-zero otherwise) diff --git a/src/Alpha_complex/test/S4_100.off b/src/Alpha_complex/test/S4_100.off index 0a5dc58c..cd017e12 100644 --- a/src/Alpha_complex/test/S4_100.off +++ b/src/Alpha_complex/test/S4_100.off @@ -1,5 +1,5 @@ -OFF -100 0 0 +nOFF +4 100 0 0 0.562921 -0.735261 -0.256472 0.277007 -0.803733 -0.0527915 -0.315125 0.501918 -0.24946 -0.354982 -0.410773 -0.801887 diff --git a/src/Alpha_complex/test/S8_10.off b/src/Alpha_complex/test/S8_10.off index 1d67e10f..4e147c44 100644 --- a/src/Alpha_complex/test/S8_10.off +++ b/src/Alpha_complex/test/S8_10.off @@ -1,5 +1,5 @@ -OFF -10 0 0 +nOFF +8 10 0 0 0.440036 -0.574754 -0.200485 0.216537 -0.501251 -0.0329236 -0.196529 0.313023 -0.129367 -0.184089 -0.213021 -0.415848 0.783529 -0.0438025 0.317256 0.120749 0.132429 0.683748 -0.124536 -0.166133 -0.540695 -0.0887576 0.390234 -0.139031 diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index e0d5ff28..e2271efd 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -32,6 +32,7 @@ else() LINK_DIRECTORIES(${Boost_LIBRARY_DIRS}) include_directories(include/) + add_subdirectory(example/common) add_subdirectory(example/Simplex_tree) add_subdirectory(example/Persistent_cohomology) add_subdirectory(example/Skeleton_blocker) diff --git a/src/Doxyfile b/src/Doxyfile index 62412627..9d4bc9c8 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -811,7 +811,8 @@ EXCLUDE_SYMBOLS = # that contain example code fragments that are included (see the \include # command). -EXAMPLE_PATH = +EXAMPLE_PATH = common/example \ + common/test # If the value of the EXAMPLE_PATH tag contains directories, you can use the # EXAMPLE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp and diff --git a/src/common/example/CMakeLists.txt b/src/common/example/CMakeLists.txt new file mode 100644 index 00000000..ae30da54 --- /dev/null +++ b/src/common/example/CMakeLists.txt @@ -0,0 +1,26 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIDelaunayTriangulationOffFileReadWrite) + +# need CGAL 4.6 +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.6.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + + add_executable ( dtoffrw Delaunay_triangulation_off_rw.cpp ) + target_link_libraries(dtoffrw ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + add_test(dtoffrw ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw ${CMAKE_SOURCE_DIR}/data/points/alphashapedoc.off ${CMAKE_CURRENT_BINARY_DIR}/result.off) + + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") + endif () +endif() diff --git a/src/common/example/Delaunay_triangulation_off_rw.cpp b/src/common/example/Delaunay_triangulation_off_rw.cpp new file mode 100644 index 00000000..d1aa7988 --- /dev/null +++ b/src/common/example/Delaunay_triangulation_off_rw.cpp @@ -0,0 +1,55 @@ +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" + +#include +#include + +#include +#include +#include + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; +typedef CGAL::Delaunay_triangulation T; +// The triangulation uses the default instantiation of the +// TriangulationDataStructure template parameter + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << " inputFile.off outputFile.off" << std::endl; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if (argc != 3) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; + usage(argv[0]); + } + + std::string offInputFile(argv[1]); + // Read the OFF file (input file name given as parameter) and triangulates points + Gudhi::Delaunay_triangulation_off_reader off_reader(offInputFile); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << offInputFile << std::endl; + exit(-1); // ----- >> + } + + // Retrieve the triangulation + T* triangulation = off_reader.get_complex(); + // Operations on triangulation + std::cout << "Number of vertices= " << triangulation->number_of_vertices() << std::endl; + std::cout << "Number of finite full cells= " << triangulation->number_of_finite_full_cells() << std::endl; + + std::string outFileName(argv[2]); + std::string offOutputFile(outFileName); + // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces + Gudhi::Delaunay_triangulation_off_writer off_writer(offOutputFile, triangulation); + + // Check the write operation was correct + if (!off_writer.is_valid()) { + std::cerr << "Unable to write file " << offOutputFile << std::endl; + exit(-1); // ----- >> + } + + return 0; +} \ No newline at end of file diff --git a/src/common/include/gudhi/Delaunay_triangulation_off_io.h b/src/common/include/gudhi/Delaunay_triangulation_off_io.h new file mode 100644 index 00000000..de5fa2af --- /dev/null +++ b/src/common/include/gudhi/Delaunay_triangulation_off_io.h @@ -0,0 +1,308 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ +#ifndef SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ +#define SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ + +#include +#include +#include +#include + +#include "gudhi/Off_reader.h" + +namespace Gudhi { + +/** \brief OFF file visitor implementation according to Off_reader in order to construct a CGAL Delaunay triangulation. + * + * For more informations on CGAL Delaunay triangulation, please refer to the corresponding chapter in page + * http://doc.cgal.org/latest/Triangulation/ + */ +template +class Delaunay_triangulation_off_visitor_reader { + private: + Complex* _complex; + typedef typename Complex::Point Point; + + public: + + // TODO(VR) : Pass a Complex as a parameter is required, even if not used. Otherwise, compilation is KO. + + /** \brief Delaunay_triangulation_off_visitor_reader constructor + * + * @param[in] _complex_ptr pointer on a Delaunay triangulation. + */ + Delaunay_triangulation_off_visitor_reader(Complex* _complex_ptr) + : _complex(nullptr) { } + + /** \brief Off_reader visitor init implementation. + * + * The init parameters are set from OFF file header. + * Dimension value is required in order to construct Delaunay triangulation. + * + * @param[in] dim space dimension of vertices. + * @param[in] num_vertices number of vertices in the OFF file (not used). + * @param[in] num_faces number of faces in the OFF file (not used). + * @param[in] num_edges number of edges in the OFF file (not used). + */ + void init(int dim, int num_vertices, int num_faces, int num_edges) { +#ifdef DEBUG_TRACES + std::cout << "Delaunay_triangulation_off_visitor_reader::init - dim=" << dim << " - num_vertices=" << + num_vertices << " - num_faces=" << num_faces << " - num_edges=" << num_edges << std::endl; +#endif // DEBUG_TRACES + if (num_faces > 0) { + std::cerr << "Delaunay_triangulation_off_visitor_reader::init faces are not taken into account from OFF " << + "file for Delaunay triangulation - faces are computed." << std::endl; + } + if (num_edges > 0) { + std::cerr << "Delaunay_triangulation_off_visitor_reader::init edges are not taken into account from OFF " << + "file for Delaunay triangulation - edges are computed." << std::endl; + } + // Complex construction with dimension from file + _complex = new Complex(dim); + } + + /** \brief Off_reader visitor point implementation. + * + * The point function is called on each vertex line from OFF file. + * This function inserts the vertex in the Delaunay triangulation. + * + * @param[in] point vector of vertex coordinates. + */ + void point(const std::vector& point) { +#ifdef DEBUG_TRACES + std::cout << "Delaunay_triangulation_off_visitor_reader::point "; + for (auto coordinate : point) { + std::cout << coordinate << " | "; + } + std::cout << std::endl; +#endif // DEBUG_TRACES + _complex->insert(Point(point.size(), point.begin(), point.end())); + } + + // Off_reader visitor maximal_face implementation - not used + void maximal_face(const std::vector& face) { + // For Delaunay Triangulation, only points are read + } + + // Off_reader visitor done implementation - not used + void done() { + // Nothing to be done on end of OFF file read + } + + /** \brief Returns the constructed Delaunay triangulation. + * + * @return A pointer on the Delaunay triangulation. + * + * @warning The returned pointer can be nullptr. + */ + Complex* get_complex() const { + return _complex; + } +}; + +/** \brief OFF file reader implementation in order to construct a Delaunay triangulation. + * + * This class is using the Delaunay_triangulation_off_visitor_reader to visit the OFF file according to Off_reader. + * + * For more informations on CGAL Delaunay triangulation, please refer to the corresponding chapter in page + * http://doc.cgal.org/latest/Triangulation/ + * + * \section Example + * + * This example loads points from an OFF file and builds the Delaunay triangulation. + * Then, it is asked to display the number of vertices and finites full cells from the Delaunay triangulation. + * + * \include Delaunay_triangulation_off_rw.cpp + * + * When launching: + * + * \code $> ./dtoffrw ../../data/points/alphashapedoc.off triangulated.off + * \endcode + * + * the program output is: + * + * \include dtoffrw_alphashapedoc_result.txt + */ +template +class Delaunay_triangulation_off_reader { + public: + + /** \brief Reads the OFF file and constructs the Delaunay triangulation from the points + * that are in the OFF file. + * + * @param[in] name_file OFF file to read. + * + * @warning Check with is_valid() function to see if read operation was successful. + */ + Delaunay_triangulation_off_reader(const std::string & name_file) + : valid_(false) { + std::ifstream stream(name_file); + if (stream.is_open()) { + Delaunay_triangulation_off_visitor_reader off_visitor(_complex); + Off_reader off_reader(stream); + valid_ = off_reader.read(off_visitor); + if (valid_) { + _complex = off_visitor.get_complex(); + if (_complex == nullptr) { + std::cerr << "Delaunay_triangulation_off_reader::Delaunay_triangulation_off_reader off_visitor returns an empty pointer" << std::endl; + valid_ = false; + } + } + } else { + std::cerr << "Delaunay_triangulation_off_reader::Delaunay_triangulation_off_reader could not open file " << + name_file << std::endl; + } + + } + + /** \brief Returns if the OFF file read operation was successful or not. + * + * @return OFF file read status. + */ + bool is_valid() const { + return valid_; + } + + /** \brief Returns the constructed Delaunay triangulation. + * + * @return A pointer on the Delaunay triangulation. + * + * @warning The returned pointer can be nullptr. + */ + Complex* get_complex() const { + if (valid_) + return _complex; + return nullptr; + + } + + private: + /** \brief OFF file read status.*/ + bool valid_; + /** \brief A pointer on the Delaunay triangulation.*/ + Complex* _complex; +}; + +/** \brief OFF file writer from a Delaunay triangulation. + * + * This class constructs the OFF file header according to http://www.geomview.org/docs/html/OFF.html + * + * The header is followed by the list of points coordinates (Delaunay triangulation vertices) + * + * And finally is followed by the list of faces (Delaunay triangulation finite full cells) + * + * For more informations on CGAL Delaunay triangulation, please refer to the corresponding chapter in page + * http://doc.cgal.org/latest/Triangulation/ + * + * \section Example + * + * This example loads points from an OFF file and builds the Delaunay triangulation. + * Then, the Delaunay triangulation is saved in a new file including the triangulation as a list of faces. + * + * \include Delaunay_triangulation_off_rw.cpp + * + * When launching: + * + * \code $> ./dtoffrw ../../data/points/alphashapedoc.off triangulated.off + * \endcode + * + * The result will be an OFF file of dimension 2 with the 7 points from alphashapedoc.off followed by the 6 + * triangulations of dimension 3 (the first value on each faces): + * \include dtoffrw_alphashapedoc_result.off + */ +template +class Delaunay_triangulation_off_writer { + public: + typedef typename Complex::Point Point; + + /** \brief Writes the OFF file from the Delaunay triangulation + * + * @param[in] name_file OFF file to write. + * @param[in] complex_ptr pointer on a Delaunay triangulation. + * + * @warning Check with is_valid() function to see if write operation was successful. + */ + Delaunay_triangulation_off_writer(const std::string & name_file, Complex* complex_ptr) + : valid_(false) { + std::ofstream stream(name_file); + if (stream.is_open()) { + if (complex_ptr->current_dimension() == 3) { + // OFF header + stream << "OFF" << std::endl; + // no endl on next line - don't know why... + stream << complex_ptr->number_of_vertices() << " " << complex_ptr->number_of_finite_full_cells() << " 0"; + } else { + // nOFF header + stream << "nOFF" << std::endl; + // no endl on next line - don't know why... + stream << complex_ptr->current_dimension() << " " << complex_ptr->number_of_vertices() << " " << + complex_ptr->number_of_finite_full_cells() << " 0"; + + } + + // bimap to retrieve vertex handles from points and vice versa + std::map< Point, int > points_to_vh; + // Start to insert at default handle value + int vertex_handle = int(); + + // Points list + for (auto vit = complex_ptr->vertices_begin(); vit != complex_ptr->vertices_end(); ++vit) { + for (auto Coord = vit->point().cartesian_begin(); Coord != vit->point().cartesian_end(); ++Coord) { + stream << *Coord << " "; + } + stream << std::endl; + points_to_vh[vit->point()] = vertex_handle; + vertex_handle++; + } + + for (auto cit = complex_ptr->finite_full_cells_begin(); cit != complex_ptr->finite_full_cells_end(); ++cit) { + std::vector vertexVector; + stream << std::distance(cit->vertices_begin(), cit->vertices_end()) << " "; + for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { + stream << points_to_vh[(*vit)->point()] << " "; + } + stream << std::endl; + } + stream.close(); + valid_ = true; + } else { + std::cerr << "Delaunay_triangulation_off_writer::Delaunay_triangulation_off_writer could not open file " << + name_file << std::endl; + } + } + + /** \brief Returns if the OFF write operation was successful or not. + * + * @return OFF file write status. + */ + bool is_valid() const { + return valid_; + } + + private: + /* \brief OFF file write status. */ + bool valid_; +}; + +} // namespace Gudhi + +#endif // SRC_ALPHA_SHAPES_INCLUDE_GUDHI_ALPHA_SHAPES_DELAUNAY_TRIANGULATION_OFF_IO_H_ diff --git a/src/common/include/gudhi/Off_reader.h b/src/common/include/gudhi/Off_reader.h index 618d1b4d..a8abb507 100644 --- a/src/common/include/gudhi/Off_reader.h +++ b/src/common/include/gudhi/Off_reader.h @@ -36,163 +36,150 @@ namespace Gudhi { -/** - * Read an off file and calls a visitor methods while reading it. - * An off file must have its first/snd line in this format : - * OFF - * num_vert num_faces num_edges - * - * A noff file must have its first/snd line in this format : - * nOFF - * dim num_vert num_faces num_edges - * - * The number of edges num_edges is optional and can be left to zero. +/** \brief OFF file reader top class visitor. + * + * OFF file must be conform to format described here : + * http://www.geomview.org/docs/html/OFF.html */ -class Off_reader{ -public: - Off_reader(std::ifstream& stream):stream_(stream){ - } -// Off_reader(const std::string& name):stream_(name){ -// if(!stream_.is_open()) -// std::cerr <<"could not open file \n"; -// } - - ~Off_reader(){ - stream_.close(); - } - - /** - * read an off file and calls the following methods : - * void init(int dim,int num_vertices,int num_faces,int num_edges); //num_edges may not be set - * void point(const std::vector& point); - * void maximal_face(const std::list& face); - * void done(); - * of the visitor when reading a point or a maximal face. - */ - template - bool read(OffVisitor& off_visitor){ - bool success_read_off_preambule = read_off_preambule(off_visitor); - if(!success_read_off_preambule) { - std::cerr <<"could not read off preambule\n"; - return false; - } - - bool success_read_off_points = read_off_points(off_visitor); - if(!success_read_off_points) { - std::cerr <<"could not read off points\n"; - return false; - } - - bool success_read_off_faces = read_off_faces(off_visitor); - if(!success_read_off_faces) { - std::cerr <<"could not read off faces\n"; - return false; - } - - off_visitor.done(); - return success_read_off_preambule && success_read_off_points && success_read_off_faces; - } - -private: - std::ifstream& stream_; - - struct Off_info{ - int dim; - int num_vertices; - int num_edges; - int num_faces; - }; - - Off_info off_info_; - - template - bool read_off_preambule(OffVisitor& off_visitor){ - std::string line; - if(!goto_next_uncomment_line(line)) return false; - - bool is_off_file = (line.find("OFF") != std::string::npos); - bool is_noff_file = (line.find("nOFF") != std::string::npos); - - if(!is_off_file && !is_noff_file) { - std::cerr << line<> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)){ - std::cerr << "incorrect number of vertices/faces/edges\n"; - return false; - } - } - else - if(!(iss >> off_info_.dim >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)){ - std::cerr << "incorrect number of vertices/faces/edges\n"; - return false; - } - off_visitor.init(off_info_.dim,off_info_.num_vertices,off_info_.num_faces,off_info_.num_edges); - - return true; - } - - bool goto_next_uncomment_line(std::string& uncomment_line){ - uncomment_line.clear(); - do - std::getline(stream_, uncomment_line); - while(uncomment_line[0] == '%');// || uncomment_line.empty()); - return (uncomment_line.size()>0 && uncomment_line[0] != '%'); - } - - - template - bool read_off_points(OffVisitor& visitor){ - int num_vertices_to_read = off_info_.num_vertices; - while(num_vertices_to_read--){ - std::string line; - if(!goto_next_uncomment_line(line)) return false; - std::vector point; - std::istringstream iss(line); - point.assign(std::istream_iterator(iss),std::istream_iterator()); -// if(point.size() != off_info_.dim) return false; - visitor.point(point); - } - return true; - } - - template - bool read_off_faces(OffVisitor& visitor){ - std::string line; - while(goto_next_uncomment_line(line)){ - std::istringstream iss(line); - int num_face_vertices; - iss >> num_face_vertices; - std::vector face; - face.assign(std::istream_iterator(iss),std::istream_iterator()); - if(!face.size() == off_info_.num_vertices) return false; - visitor.maximal_face(face); - } - return true; - } +class Off_reader { + public: + + Off_reader(std::ifstream& stream) : stream_(stream) { } + + ~Off_reader() { + stream_.close(); + } + + /** \brief + * Read an OFF file and calls the following methods : + * + * void init(int dim,int num_vertices,int num_faces,int num_edges); // from file header - num_edges may not be set + * + * void point(const std::vector& point); // for each point read + * + * void maximal_face(const std::list& face); // for each face read + * + * void done(); // upon file read is finished + * + * of the visitor when reading a point or a maximal face. Edges are not taken into account. + */ + template + bool read(OffVisitor& off_visitor) { + bool success_read_off_preambule = read_off_preambule(off_visitor); + if (!success_read_off_preambule) { + std::cerr << "could not read off preambule\n"; + return false; + } + + bool success_read_off_points = read_off_points(off_visitor); + if (!success_read_off_points) { + std::cerr << "could not read off points\n"; + return false; + } + + bool success_read_off_faces = read_off_faces(off_visitor); + if (!success_read_off_faces) { + std::cerr << "could not read off faces\n"; + return false; + } + + off_visitor.done(); + return success_read_off_preambule && success_read_off_points && success_read_off_faces; + } + + private: + std::ifstream& stream_; + + struct Off_info { + int dim; + int num_vertices; + int num_edges; + int num_faces; + }; + + Off_info off_info_; + + template + bool read_off_preambule(OffVisitor& off_visitor) { + std::string line; + if (!goto_next_uncomment_line(line)) return false; + + bool is_off_file = (line.find("OFF") != std::string::npos); + bool is_noff_file = (line.find("nOFF") != std::string::npos); + + if (!is_off_file && !is_noff_file) { + std::cerr << line << std::endl; + std::cerr << "missing off header\n"; + return false; + } + + if (!goto_next_uncomment_line(line)) return false; + std::istringstream iss(line); + if ((is_off_file) && (!is_noff_file)) { + off_info_.dim = 3; + if (!(iss >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)) { + std::cerr << "incorrect number of vertices/faces/edges\n"; + return false; + } + } else + if (!(iss >> off_info_.dim >> off_info_.num_vertices >> off_info_.num_faces >> off_info_.num_edges)) { + std::cerr << "incorrect number of vertices/faces/edges\n"; + return false; + } + off_visitor.init(off_info_.dim, off_info_.num_vertices, off_info_.num_faces, off_info_.num_edges); + + return true; + } + + bool goto_next_uncomment_line(std::string& uncomment_line) { + uncomment_line.clear(); + do + std::getline(stream_, uncomment_line); while (uncomment_line[0] == '%'); + return (uncomment_line.size() > 0 && uncomment_line[0] != '%'); + } + + template + bool read_off_points(OffVisitor& visitor) { + int num_vertices_to_read = off_info_.num_vertices; + while (num_vertices_to_read--) { + std::string line; + if (!goto_next_uncomment_line(line)) return false; + std::vector point; + std::istringstream iss(line); + point.assign(std::istream_iterator(iss), std::istream_iterator()); + // if(point.size() != off_info_.dim) return false; + visitor.point(point); + } + return true; + } + + template + bool read_off_faces(OffVisitor& visitor) { + std::string line; + while (goto_next_uncomment_line(line)) { + std::istringstream iss(line); + int num_face_vertices; + iss >> num_face_vertices; + std::vector face; + face.assign(std::istream_iterator(iss), std::istream_iterator()); + if (!face.size() == off_info_.num_vertices) return false; + visitor.maximal_face(face); + } + return true; + } }; - template -void read_off(const std::string& name_file_off,OFFVisitor& vis){ - std::ifstream stream(name_file_off); - if(!stream.is_open()) - std::cerr <<"could not open file \n"; - else{ - Off_reader off_reader(stream); - off_reader.read(vis); - } +void read_off(const std::string& name_file_off, OFFVisitor& vis) { + std::ifstream stream(name_file_off); + if (!stream.is_open()) + std::cerr << "could not open file \n"; + else { + Off_reader off_reader(stream); + off_reader.read(vis); + } } - - } // namespace Gudhi - -#endif /* GUDHI_OFF_READER_H_ */ +#endif // GUDHI_OFF_READER_H_ diff --git a/src/common/test/CMakeLists.txt b/src/common/test/CMakeLists.txt new file mode 100644 index 00000000..22783caf --- /dev/null +++ b/src/common/test/CMakeLists.txt @@ -0,0 +1,44 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHIDelaunayTriangulationOffFileReadWriteUT) + +if(NOT MSVC) + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} --coverage") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} --coverage") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} --coverage") +endif() + +# need CGAL 4.6 +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.6.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + + add_executable ( dtoffrw_UT dtoffrw_unit_test.cpp ) + target_link_libraries(dtoffrw_UT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + + # Unitary tests + add_test(dtoffrw_UT ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_UT) + + if (DIFF_PATH) + add_test(diff_files_UT ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/UT.off ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_alphashapedoc_result.off) + endif() + + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") + endif () +endif() + + + + + +cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/common/include/gudhi") diff --git a/src/common/test/README b/src/common/test/README new file mode 100644 index 00000000..f2a7eb5a --- /dev/null +++ b/src/common/test/README @@ -0,0 +1,14 @@ +To compile: +*********** + +cmake . +make + +To launch with details: +*********************** + +./dtoffrw_UT --report_level=detailed --log_level=all + + ==> echo $? returns 0 in case of success (non-zero otherwise) + + diff --git a/src/common/test/dtoffrw_alphashapedoc_result.off b/src/common/test/dtoffrw_alphashapedoc_result.off new file mode 100644 index 00000000..13c255c6 --- /dev/null +++ b/src/common/test/dtoffrw_alphashapedoc_result.off @@ -0,0 +1,15 @@ +nOFF +2 7 6 0 +1 1 +7 0 +4 6 +9 6 +0 14 +2 19 +9 17 +3 1 2 3 +3 4 3 2 +3 5 1 3 +3 5 3 7 +3 7 3 4 +3 6 5 7 diff --git a/src/common/test/dtoffrw_alphashapedoc_result.txt b/src/common/test/dtoffrw_alphashapedoc_result.txt new file mode 100644 index 00000000..57761d14 --- /dev/null +++ b/src/common/test/dtoffrw_alphashapedoc_result.txt @@ -0,0 +1,3 @@ +Number of vertices= 7 +Number of finite full cells= 6 + diff --git a/src/common/test/dtoffrw_unit_test.cpp b/src/common/test/dtoffrw_unit_test.cpp new file mode 100644 index 00000000..4905d845 --- /dev/null +++ b/src/common/test/dtoffrw_unit_test.cpp @@ -0,0 +1,91 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2015 INRIA Saclay (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#define BOOST_TEST_MODULE DelaunayTriangulationOffFileReadWrite test + +// to construct a Delaunay_triangulation from a OFF file +#include "gudhi/Delaunay_triangulation_off_io.h" + +#include +#include + +#include +#include +#include + +#include +#include +//#include + +// Use dynamic_dimension_tag for the user to be able to set dimension +typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > K; +typedef CGAL::Delaunay_triangulation T; + +BOOST_AUTO_TEST_CASE( Delaunay_triangulation_doc_test ) +{ + // Read the OFF file (input file name given as parameter) and triangulates points + Gudhi::Delaunay_triangulation_off_reader off_reader("../../../data/points/alphashapedoc.off"); + // Check the read operation was correct + BOOST_CHECK(off_reader.is_valid()); + + // Retrieve the triangulation + T* triangulation = off_reader.get_complex(); + BOOST_CHECK(triangulation != nullptr); + // Operations on triangulation + BOOST_CHECK(triangulation->number_of_vertices() == 7); + BOOST_CHECK(triangulation->number_of_finite_full_cells() == 6); + + // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces + Gudhi::Delaunay_triangulation_off_writer off_writer("UT.off", triangulation); + + // Check the write operation was correct + BOOST_CHECK(off_writer.is_valid()); + + delete triangulation; +} + +BOOST_AUTO_TEST_CASE( Delaunay_triangulation_unexisting_file_read_test ) +{ + Gudhi::Delaunay_triangulation_off_reader off_reader("pouetpouet_tralala.off"); + // Check the read operation was correct + BOOST_CHECK(!off_reader.is_valid()); + T* triangulation = off_reader.get_complex(); + BOOST_CHECK(triangulation == nullptr); +} + +BOOST_AUTO_TEST_CASE( Delaunay_triangulation_unexisting_file_write_test ) +{ + // Read the OFF file (input file name given as parameter) and triangulates points + Gudhi::Delaunay_triangulation_off_reader off_reader("../../../data/points/alphashapedoc.off"); + + // Retrieve the triangulation + T* triangulation = off_reader.get_complex(); + + // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces + Gudhi::Delaunay_triangulation_off_writer off_writer("/pouetpouet_tralala/pouetpouet_tralala/pouetpouet_tralala.off", triangulation); + + // Check the write operation was correct + BOOST_CHECK(!off_writer.is_valid()); + + delete triangulation; +} + -- cgit v1.2.3 From 9e7a221884346501d5bcb06ad184e08f96938315 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 18 Jun 2015 14:58:02 +0000 Subject: From trunk, cpplint was removed git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@626 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 404ea81f038969fb4d96945cfb9856b8ee4ac12a --- src/Alpha_complex/test/CMakeLists.txt | 1 - src/common/test/CMakeLists.txt | 5 ----- 2 files changed, 6 deletions(-) (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index 4fe69ce5..0bd55433 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -28,4 +28,3 @@ if(CGAL_FOUND) endif () endif() -cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/Alpha_complex/include/gudhi") diff --git a/src/common/test/CMakeLists.txt b/src/common/test/CMakeLists.txt index 22783caf..e4ac6c7b 100644 --- a/src/common/test/CMakeLists.txt +++ b/src/common/test/CMakeLists.txt @@ -37,8 +37,3 @@ if(CGAL_FOUND) endif () endif() - - - - -cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/common/include/gudhi") -- cgit v1.2.3 From ea986c68192c7536716d139e5a5f0a30a76f0fc1 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 19 Jun 2015 11:08:21 +0000 Subject: Alpha complex documetation - 1st part git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@630 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b64e860b0fb6d60e706784605f699349ea17a869 --- biblio/bibliography.bib | 16 ++ .../example/Alpha_complex_from_off.cpp | 22 --- src/Alpha_complex/include/gudhi/Alpha_complex.h | 207 +++++++++++---------- src/Alpha_complex/test/CMakeLists.txt | 8 +- src/Alpha_complex/test/alphaoffreader_for_doc.txt | 27 +++ src/Doxyfile | 5 +- src/common/test/CMakeLists.txt | 6 +- 7 files changed, 163 insertions(+), 128 deletions(-) create mode 100644 src/Alpha_complex/test/alphaoffreader_for_doc.txt (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 3fd1c10a..859696b4 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -897,6 +897,22 @@ language={English} bibsource = {DBLP, http://dblp.uni-trier.de} } +@ARTICLE{AlphaShapesDefinition, + author = {N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke, and C. Varela}, + title = {\href{http://pub.ist.ac.at/~edels/Papers/1995-P-06-AlphaShapesSoftware.pdf}{Alpha shapes: definition and software}}, + journal = {Proc. Internat. Comput. Geom. Software Workshop 1995}, + year = {1995}, + bibsource = {http://pub.ist.ac.at} +} + +@ARTICLE{AlphaShapesIntroduction, + author = {Kaspar Fischer}, + title = {\href{http://www.cs.uu.nl/docs/vakken/ddm/texts/Delaunay/alphashapes.pdf}{Introduction to Alpha Shapes}}, + journal = {Unknown}, + year = {Unknown}, + bibsource = {http://www.cs.uu.nl} +} + misc{buddha_stanford_scan, author = "", title = "The Stanford 3D Scanning Repository", diff --git a/src/Alpha_complex/example/Alpha_complex_from_off.cpp b/src/Alpha_complex/example/Alpha_complex_from_off.cpp index d129ebf7..0d7af117 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_off.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_off.cpp @@ -1,25 +1,3 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Vincent Rouvreau - * - * Copyright (C) 2014 INRIA Saclay (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - // to construct a Delaunay_triangulation from a OFF file #include "gudhi/Delaunay_triangulation_off_io.h" #include "gudhi/Alpha_complex.h" diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index d25c05cb..44741e3b 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -52,17 +52,37 @@ namespace alphacomplex { #define Kinit(f) =k.f() /** \defgroup alpha_complex Alpha complex in dimension N - * -
Implementations:
- Alpha complex in dimension N are a subset of Delaunay Triangulation in dimension N. - - - * \author Vincent Rouvreau - * \version 1.0 - * \date 2015 - * \copyright GNU General Public License v3. * @{ + * \author Vincent Rouvreau + * + * \section Definition + * + * Alpha_complex is a Simplex_tree constructed from each finite cell of a Delaunay Triangulation in dimension N. + * + * The filtration value of each simplex is computed from the alpha value of the simplex if it is Gabriel or + * from the alpha value of the simplex coface that makes the simplex not Gabriel. + * + * Please refer to \cite AlphaShapesDefinition for the alpha complex definition or to + * \cite AlphaShapesIntroduction for alpha complex concept vulgarization. + * + * \section Example + * + * This example loads points from an OFF file, builds the Delaunay triangulation, and finally initialize the + * alpha complex with it. + * Then, it is asked to display information about the alpha complex. + * + * \include Alpha_complex_from_off.cpp + * + * When launching: + * + * \code $> ./alphaoffreader ../../data/points/alphashapedoc.off + * \endcode + * + * the program output is: + * + * \include alphaoffreader_for_doc.txt */ +/** @} */ // end defgroup alpha_complex /** * \brief Alpha complex data structure. @@ -74,89 +94,107 @@ namespace alphacomplex { * * */ -class Alpha_complex { +template +class Alpha_complex : public Simplex_tree<> { private: // From Simplex_tree - /** \brief Type required to insert into a simplex_tree (with or without subfaces).*/ + // Type required to insert into a simplex_tree (with or without subfaces). typedef std::vector Vector_vertex; - /** \brief Simplex_handle type from simplex_tree.*/ - typedef typename Gudhi::Simplex_tree<>::Simplex_handle Simplex_handle; - /** \brief Simplex_result is the type returned from simplex_tree insert function.*/ + // Simplex_result is the type returned from simplex_tree insert function. typedef typename std::pair Simplex_result; - /** \brief Filtration_simplex_range type from simplex_tree.*/ - typedef typename Gudhi::Simplex_tree<>::Filtration_simplex_range Filtration_simplex_range; - - /** \brief Simplex_vertex_range type from simplex_tree.*/ - typedef typename Gudhi::Simplex_tree<>::Simplex_vertex_range Simplex_vertex_range; - // From CGAL - /** \brief Kernel for the Delaunay_triangulation. Dimension can be set dynamically.*/ + // Kernel for the Delaunay_triangulation. Dimension can be set dynamically. typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - /** \brief Delaunay_triangulation type required to create an alpha-complex.*/ + + // Delaunay_triangulation type required to create an alpha-complex. typedef CGAL::Delaunay_triangulation Delaunay_triangulation; typedef typename Kernel::Compute_squared_radius_d Squared_Radius; typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; - /** \brief Type required to compute squared radius, or side of bounded sphere on a vector of points.*/ + // Type required to compute squared radius, or side of bounded sphere on a vector of points. typedef std::vector Vector_of_CGAL_points; - /** \brief Vertex_iterator type from CGAL.*/ + // Vertex_iterator type from CGAL. typedef Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; - /** \brief Boost bimap type to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa.*/ + // Boost bimap type to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa. typedef boost::bimap< CGAL_vertex_iterator, Vertex_handle > Bimap_vertex; - + private: - /** \brief Alpha complex is represented internally by a simplex tree.*/ - Gudhi::Simplex_tree<> st_; /** \brief Boost bimap to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa.*/ Bimap_vertex cgal_simplextree; /** \brief Pointer on the CGAL Delaunay triangulation.*/ Delaunay_triangulation* triangulation; public: + /** \brief Alpha_complex constructor from an OFF file name. + * Uses the Delaunay_triangulation_off_reader to construct the Delaunay triangulation required to initialize + * the Alpha_complex. + * + * @param[in] off_file_name OFF file [path and] name. + */ Alpha_complex(std::string& off_file_name) - : triangulation(nullptr) { + : triangulation(nullptr) { Gudhi::Delaunay_triangulation_off_reader off_reader(off_file_name); if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_name << std::endl; + std::cerr << "Alpha_complex - Unable to read file " << off_file_name << std::endl; exit(-1); // ----- >> } triangulation = off_reader.get_complex(); init(); } + /** \brief Alpha_complex constructor from a Delaunay triangulation. + * + * @param[in] triangulation_ptr Pointer on a Delaunay triangulation. + */ Alpha_complex(Delaunay_triangulation* triangulation_ptr) - : triangulation(triangulation_ptr) { + : triangulation(triangulation_ptr) { init(); } + /** \brief Alpha_complex destructor from a Delaunay triangulation. + * + * @warning Deletes the Delaunay triangulation. + */ ~Alpha_complex() { delete triangulation; } - Filtration_simplex_range filtration_simplex_range() { - return st_.filtration_simplex_range(); - } - - Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) { - return st_.simplex_vertex_range(sh); - } - - /** \brief Returns the filtration value of a simplex. - * - * Called on the null_simplex, returns INFINITY. */ - Gudhi::Simplex_tree<>::Filtration_value filtration(Simplex_handle sh) { - return st_.filtration(sh); - } - private: - + /** \brief Initialize the Alpha_complex from the Delaunay triangulation. + * + * @warning Delaunay triangulation must be already constructed with at least one vertex and dimension must be more + * than 0. + * + * Initialization can be launched once. + */ void init() { - st_.set_dimension(triangulation->maximal_dimension()); + if (triangulation == nullptr) { + std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation" << std::endl; + return; // ----- >> + } + if (triangulation->number_of_vertices() < 1) { + std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices" << std::endl; + return; // ----- >> + } + if (triangulation->maximal_dimension() < 1) { + std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation" << std::endl; + return; // ----- >> + } + if (num_vertices() > 0) { + std::cerr << "Alpha_complex init - Cannot init twice" << std::endl; + return; // ----- >> + } + + set_dimension(triangulation->maximal_dimension()); // -------------------------------------------------------------------------------------------- // bimap to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa @@ -187,7 +225,7 @@ class Alpha_complex { std::cout << std::endl; #endif // DEBUG_TRACES // Insert each simplex and its subfaces in the simplex tree - filtration is NaN - Simplex_result insert_result = st_.insert_simplex_and_subfaces(vertexVector, + Simplex_result insert_result = insert_simplex_and_subfaces(vertexVector, std::numeric_limits::quiet_NaN()); if (!insert_result.second) { std::cerr << "Alpha_complex::init insert_simplex_and_subfaces failed" << std::endl; @@ -198,16 +236,16 @@ class Alpha_complex { Filtration_value filtration_max = 0.0; // -------------------------------------------------------------------------------------------- // ### For i : d -> 0 - for (int decr_dim = st_.dimension(); decr_dim >= 0; decr_dim--) { + for (int decr_dim = dimension(); decr_dim >= 0; decr_dim--) { // ### Foreach Sigma of dim i - for (auto f_simplex : st_.skeleton_simplex_range(decr_dim)) { - int f_simplex_dim = st_.dimension(f_simplex); + 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 : st_.simplex_vertex_range(f_simplex)) { + for (auto vertex : simplex_vertex_range(f_simplex)) { pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); #ifdef DEBUG_TRACES std::cout << " " << vertex; @@ -217,20 +255,20 @@ class Alpha_complex { std::cout << std::endl; #endif // DEBUG_TRACES // ### If filt(Sigma) is NaN : filt(Sigma) = alpha(Sigma) - if (isnan(st_.filtration(f_simplex))) { + if (isnan(filtration(f_simplex))) { Filtration_value alpha_complex_filtration = 0.0; // No need to compute squared_radius on a single point - alpha is 0.0 if (f_simplex_dim > 0) { // squared_radius function initialization Kernel k; Squared_Radius squared_radius Kinit(compute_squared_radius_d_object); - + alpha_complex_filtration = squared_radius(pointVector.begin(), pointVector.end()); } - st_.assign_filtration(f_simplex, alpha_complex_filtration); + assign_filtration(f_simplex, alpha_complex_filtration); filtration_max = fmax(filtration_max, alpha_complex_filtration); #ifdef DEBUG_TRACES - std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << st_.filtration(f_simplex) << std::endl; + std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << filtration(f_simplex) << std::endl; #endif // DEBUG_TRACES } propagate_alpha_filtration(f_simplex, decr_dim); @@ -242,30 +280,30 @@ class Alpha_complex { #ifdef DEBUG_TRACES std::cout << "filtration_max=" << filtration_max << std::endl; #endif // DEBUG_TRACES - st_.set_filtration(filtration_max); + set_filtration(filtration_max); } template void propagate_alpha_filtration(Simplex_handle f_simplex, int decr_dim) { // ### Foreach Tau face of Sigma - for (auto f_boundary : st_.boundary_simplex_range(f_simplex)) { + for (auto f_boundary : boundary_simplex_range(f_simplex)) { #ifdef DEBUG_TRACES std::cout << " | --------------------------------------------------" << std::endl; std::cout << " | Tau "; - for (auto vertex : st_.simplex_vertex_range(f_boundary)) { + for (auto vertex : simplex_vertex_range(f_boundary)) { std::cout << vertex << " "; } std::cout << "is a face of Sigma" << std::endl; - std::cout << " | isnan(filtration(Tau)=" << isnan(st_.filtration(f_boundary)) << std::endl; + std::cout << " | isnan(filtration(Tau)=" << isnan(filtration(f_boundary)) << std::endl; #endif // DEBUG_TRACES // ### If filt(Tau) is not NaN - if (!isnan(st_.filtration(f_boundary))) { + if (!isnan(filtration(f_boundary))) { // ### filt(Tau) = fmin(filt(Tau), filt(Sigma)) - Filtration_value alpha_complex_filtration = fmin(st_.filtration(f_boundary), st_.filtration(f_simplex)); - st_.assign_filtration(f_boundary, alpha_complex_filtration); + Filtration_value alpha_complex_filtration = fmin(filtration(f_boundary), filtration(f_simplex)); + assign_filtration(f_boundary, alpha_complex_filtration); // No need to check for filtration_max, alpha_complex_filtration is a min of an existing filtration value #ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << st_.filtration(f_boundary) << std::endl; + std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << filtration(f_boundary) << std::endl; #endif // DEBUG_TRACES // ### Else } else { @@ -275,11 +313,11 @@ class Alpha_complex { // insert the Tau points in a vector for is_gabriel function Vector_of_CGAL_points pointVector; Vertex_handle vertexForGabriel = Vertex_handle(); - for (auto vertex : st_.simplex_vertex_range(f_boundary)) { + for (auto vertex : simplex_vertex_range(f_boundary)) { pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); } // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function - for (auto vertex : st_.simplex_vertex_range(f_simplex)) { + for (auto vertex : simplex_vertex_range(f_simplex)) { if (std::find(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertex))->point()) == pointVector.end()) { // vertex is not found in Tau @@ -300,46 +338,17 @@ class Alpha_complex { if ((is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) == CGAL::ON_BOUNDED_SIDE)) { // ### filt(Tau) = filt(Sigma) - Filtration_value alpha_complex_filtration = st_.filtration(f_simplex); - st_.assign_filtration(f_boundary, alpha_complex_filtration); + Filtration_value alpha_complex_filtration = filtration(f_simplex); + assign_filtration(f_boundary, alpha_complex_filtration); // No need to check for filtration_max, alpha_complex_filtration is an existing filtration value #ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = filt(Sigma) = " << st_.filtration(f_boundary) << std::endl; + std::cout << " | filt(Tau) = filt(Sigma) = " << filtration(f_boundary) << std::endl; #endif // DEBUG_TRACES } } } } } - public: - - /** \brief Returns the number of vertices in the complex. */ - size_t num_vertices() { - return st_.num_vertices(); - } - - /** \brief Returns the number of simplices in the complex. - * - * Does not count the empty simplex. */ - const unsigned int& num_simplices() const { - return st_.num_simplices(); - } - - /** \brief Returns an upper bound on the dimension of the simplicial complex. */ - int dimension() { - return st_.dimension(); - } - - /** \brief Returns an upper bound of the filtration values of the simplices. */ - Filtration_value filtration() { - return st_.filtration(); - } - - friend std::ostream& operator<<(std::ostream& os, const Alpha_complex & alpha_complex) { - Gudhi::Simplex_tree<> st = alpha_complex.st_; - os << st << std::endl; - return os; - } }; } // namespace alphacomplex diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index 0bd55433..79300790 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -16,9 +16,11 @@ if(CGAL_FOUND) include_directories (BEFORE "../../include") #add_definitions(-DDEBUG_TRACES) - add_executable ( AlphaComplexUnitTest Alpha_complex_unit_test.cpp ) - target_link_libraries(AlphaComplexUnitTest ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) - add_test(AlphaComplexUnitTest ${CMAKE_CURRENT_BINARY_DIR}/AlphaComplexUnitTest) + add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) + target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + add_test(AlphaComplexUT ${CMAKE_CURRENT_BINARY_DIR}/AlphaComplexUT + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/AlphaComplexUT.xml --log_level=test_suite --report_level=no) else() message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha complex feature.") diff --git a/src/Alpha_complex/test/alphaoffreader_for_doc.txt b/src/Alpha_complex/test/alphaoffreader_for_doc.txt new file mode 100644 index 00000000..1153f097 --- /dev/null +++ b/src/Alpha_complex/test/alphaoffreader_for_doc.txt @@ -0,0 +1,27 @@ +Alpha complex is of dimension 2 - 25 simplices - 7 vertices. +Iterator on alpha complex simplices in the filtration order, with [filtration value]: + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 7 ) -> [0] + ( 4 3 ) -> [6.25] + ( 6 5 ) -> [7.25] + ( 3 1 ) -> [8.5] + ( 2 1 ) -> [9.25] + ( 4 2 ) -> [10] + ( 3 2 ) -> [11.25] + ( 4 3 2 ) -> [12.5] + ( 3 2 1 ) -> [12.9959] + ( 7 6 ) -> [13.25] + ( 5 3 ) -> [20] + ( 7 5 ) -> [22.7367] + ( 7 6 5 ) -> [22.7367] + ( 7 4 ) -> [30.25] + ( 7 3 ) -> [36.5] + ( 7 4 3 ) -> [36.5] + ( 7 5 3 ) -> [37.2449] + ( 5 1 ) -> [59.7107] + ( 5 3 1 ) -> [59.7107] diff --git a/src/Doxyfile b/src/Doxyfile index 9d4bc9c8..49ec4768 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -812,8 +812,9 @@ EXCLUDE_SYMBOLS = # command). EXAMPLE_PATH = common/example \ - common/test - + common/test \ + Alpha_complex/example \ + Alpha_complex/test \ # If the value of the EXAMPLE_PATH tag contains directories, you can use the # EXAMPLE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp and # *.h) to filter out the source-files in the directories. If left blank all diff --git a/src/common/test/CMakeLists.txt b/src/common/test/CMakeLists.txt index e4ac6c7b..1b4dd6e0 100644 --- a/src/common/test/CMakeLists.txt +++ b/src/common/test/CMakeLists.txt @@ -23,10 +23,12 @@ if(CGAL_FOUND) target_link_libraries(dtoffrw_UT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) # Unitary tests - add_test(dtoffrw_UT ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_UT) + add_test(dtoffrw_UT ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_UT + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/dtoffrw_UT.xml --log_level=test_suite --report_level=no) if (DIFF_PATH) - add_test(diff_files_UT ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/UT.off ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_alphashapedoc_result.off) + add_test(dtoffrw_diff_files_UT ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/UT.off ${CMAKE_CURRENT_BINARY_DIR}/dtoffrw_alphashapedoc_result.off) endif() else() -- cgit v1.2.3 From d6c4c80e50d558034958f8fab0289d4cfb1a31b8 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Wed, 5 Aug 2015 15:03:29 +0000 Subject: Debug traces in DEBUG mode Alpha complex from delaunay triangulation in static dimension git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@725 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 9dda5a16874ae009c24be39c5a9c9d4124a29063 --- .../example/Alpha_complex_from_off.cpp | 3 +- .../example/Alpha_complex_from_points.cpp | 2 +- src/Alpha_complex/example/CMakeLists.txt | 5 +- src/Alpha_complex/include/gudhi/Alpha_complex.h | 85 +++++++++++++--------- src/Alpha_complex/test/Alpha_complex_unit_test.cpp | 27 ++++--- src/Alpha_complex/test/CMakeLists.txt | 5 +- src/Persistent_cohomology/example/CMakeLists.txt | 7 +- 7 files changed, 81 insertions(+), 53 deletions(-) (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/src/Alpha_complex/example/Alpha_complex_from_off.cpp b/src/Alpha_complex/example/Alpha_complex_from_off.cpp index ce278419..a17155de 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_off.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_off.cpp @@ -22,7 +22,8 @@ int main(int argc, char **argv) { // ---------------------------------------------------------------------------- // Init of an alpha complex from an OFF file // ---------------------------------------------------------------------------- - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); // ---------------------------------------------------------------------------- // Display information about the alpha complex diff --git a/src/Alpha_complex/example/Alpha_complex_from_points.cpp b/src/Alpha_complex/example/Alpha_complex_from_points.cpp index fc0e2460..33680a40 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_points.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_points.cpp @@ -49,7 +49,7 @@ int main(int argc, char **argv) { // ---------------------------------------------------------------------------- // Init of an alpha complex from the list of points // ---------------------------------------------------------------------------- - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_points(3, points.size(), points.begin(), points.end()); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_points(3, points.size(), points.begin(), points.end()); // ---------------------------------------------------------------------------- // Display information about the alpha complex diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt index 2e64e4db..04fc34af 100644 --- a/src/Alpha_complex/example/CMakeLists.txt +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -13,8 +13,11 @@ if(CGAL_FOUND) if (EIGEN3_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) + if (CMAKE_BUILD_TYPE MATCHES Debug) + # For programs to be more verbose + add_definitions(-DDEBUG_TRACES) + endif() - #add_definitions(-DDEBUG_TRACES) add_executable ( alphaoffreader Alpha_complex_from_off.cpp ) target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 16781563..5834e3df 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -43,8 +43,8 @@ #include #include #include -#include // NaN -#include // std::iterator +#include // NaN +#include // std::iterator namespace Gudhi { @@ -61,6 +61,7 @@ namespace alphacomplex { * Please refer to \ref alpha_complex for examples. * */ +template class Alpha_complex : public Simplex_tree<> { private: // From Simplex_tree @@ -72,35 +73,43 @@ class Alpha_complex : public Simplex_tree<> { // From CGAL // Kernel for the Delaunay_triangulation. Dimension can be set dynamically. - typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; + //typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; // Delaunay_triangulation type required to create an alpha-complex. - typedef CGAL::Delaunay_triangulation Delaunay_triangulation; + typedef typename CGAL::Delaunay_triangulation Delaunay_triangulation; typedef typename Kernel::Compute_squared_radius_d Squared_Radius; typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; + typedef typename Kernel::Point_d Point_d; + // Type required to compute squared radius, or side of bounded sphere on a vector of points. - typedef std::vector Vector_of_CGAL_points; + typedef typename std::vector Vector_of_CGAL_points; // Vertex_iterator type from CGAL. - typedef Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; + typedef typename Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; - // Boost bimap type to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa. - typedef boost::bimap< CGAL_vertex_iterator, Vertex_handle > Bimap_vertex; - // size_type type from CGAL. - typedef Delaunay_triangulation::size_type size_type; + typedef typename Delaunay_triangulation::size_type size_type; + + // Boost bimap type to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa. + //typedef typename boost::bimap< CGAL_vertex_iterator, Vertex_handle > Bimap_vertex; + //typedef typename Bimap_vertex::value_type value_type; + typedef typename std::map< CGAL_vertex_iterator, Vertex_handle > Map_vertex_iterator_to_handle; + typedef typename std::map< Vertex_handle, CGAL_vertex_iterator > Map_vertex_handle_to_iterator; private: - /** \brief Boost bimap to switch from CGAL vertex iterator to simplex tree vertex handle and vice versa.*/ - Bimap_vertex cgal_simplextree; + /** \brief Map to switch from CGAL vertex iterator to simplex tree vertex handle.*/ + Map_vertex_iterator_to_handle vertex_iterator_to_handle; + /** \brief Map to switch from simplex tree vertex handle to CGAL vertex iterator.*/ + Map_vertex_handle_to_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. @@ -140,9 +149,9 @@ class Alpha_complex : public Simplex_tree<> { Alpha_complex(int dimension, size_type size, ForwardIterator firstPoint, ForwardIterator lastPoint) : triangulation(nullptr) { triangulation = new Delaunay_triangulation(dimension); - Delaunay_triangulation::size_type inserted = triangulation->insert(firstPoint, lastPoint); + size_type inserted = triangulation->insert(firstPoint, lastPoint); if (inserted != size) { - std::cerr << "Alpha_complex - insertion failed " << inserted << " != " << size<< std::endl; + std::cerr << "Alpha_complex - insertion failed " << inserted << " != " << size << std::endl; exit(-1); // ----- >> } init(); @@ -161,18 +170,20 @@ class Alpha_complex : public Simplex_tree<> { * @param[in] vertex Vertex handle of the point to retrieve. * @return The founded point. */ - Kernel::Point_d get_point(Vertex_handle vertex) { - Kernel::Point_d point; + Point_d get_point(Vertex_handle vertex) { + Point_d point; try { - point = cgal_simplextree.right.at(vertex)->point(); - } - catch(...) { + if (vertex_handle_to_iterator[vertex] != nullptr) { + point = vertex_handle_to_iterator[vertex]->point(); + } + } catch (...) { std::cerr << "Alpha_complex - getPoint not found on vertex " << vertex << std::endl; } return point; } - + private: + /** \brief Initialize the Alpha_complex from the Delaunay triangulation. * * @warning Delaunay triangulation must be already constructed with at least one vertex and dimension must be more @@ -197,7 +208,7 @@ class Alpha_complex : public Simplex_tree<> { std::cerr << "Alpha_complex init - Cannot init twice" << std::endl; return; // ----- >> } - + set_dimension(triangulation->maximal_dimension()); // -------------------------------------------------------------------------------------------- @@ -206,7 +217,11 @@ class Alpha_complex : public Simplex_tree<> { Vertex_handle vertex_handle = Vertex_handle(); // Loop on triangulation vertices list for (CGAL_vertex_iterator vit = triangulation->vertices_begin(); vit != triangulation->vertices_end(); ++vit) { - cgal_simplextree.insert(Bimap_vertex::value_type(vit, vertex_handle)); +#ifdef DEBUG_TRACES + std::cout << "Vertex insertion - " << vertex_handle << " -> " << vit->point() << std::endl; +#endif // DEBUG_TRACES + vertex_iterator_to_handle[vit] = vertex_handle; + vertex_handle_to_iterator[vertex_handle] = vit; vertex_handle++; } // -------------------------------------------------------------------------------------------- @@ -219,18 +234,20 @@ class Alpha_complex : public Simplex_tree<> { 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 << " " << cgal_simplextree.left.at(*vit); + std::cout << " " << vertex_iterator_to_handle[*vit]; #endif // DEBUG_TRACES - // Vector of vertex construction for simplex_tree structure - vertexVector.push_back(cgal_simplextree.left.at(*vit)); + // Vector of vertex construction for simplex_tree structure + vertexVector.push_back(vertex_iterator_to_handle[*vit]); + } } #ifdef DEBUG_TRACES std::cout << std::endl; #endif // DEBUG_TRACES // Insert each simplex and its subfaces in the simplex tree - filtration is NaN Simplex_result insert_result = insert_simplex_and_subfaces(vertexVector, - std::numeric_limits::quiet_NaN()); + std::numeric_limits::quiet_NaN()); if (!insert_result.second) { std::cerr << "Alpha_complex::init insert_simplex_and_subfaces failed" << std::endl; } @@ -250,7 +267,7 @@ class Alpha_complex : public Simplex_tree<> { std::cout << "Sigma of dim " << decr_dim << " is"; #endif // DEBUG_TRACES for (auto vertex : simplex_vertex_range(f_simplex)) { - pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); + pointVector.push_back(get_point(vertex)); #ifdef DEBUG_TRACES std::cout << " " << vertex; #endif // DEBUG_TRACES @@ -265,7 +282,7 @@ class Alpha_complex : public Simplex_tree<> { 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); @@ -317,12 +334,11 @@ class Alpha_complex : public Simplex_tree<> { Vector_of_CGAL_points pointVector; Vertex_handle vertexForGabriel = Vertex_handle(); for (auto vertex : simplex_vertex_range(f_boundary)) { - pointVector.push_back((cgal_simplextree.right.at(vertex))->point()); + pointVector.push_back(get_point(vertex)); } // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function for (auto vertex : simplex_vertex_range(f_simplex)) { - if (std::find(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertex))->point()) - == pointVector.end()) { + if (std::find(pointVector.begin(), pointVector.end(), get_point(vertex)) == pointVector.end()) { // vertex is not found in Tau vertexForGabriel = vertex; // No need to continue loop @@ -331,14 +347,13 @@ class Alpha_complex : public Simplex_tree<> { } // is_gabriel function initialization Is_Gabriel is_gabriel = kernel.side_of_bounded_sphere_d_object(); -#ifdef DEBUG_TRACES - bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) + bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), get_point(vertexForGabriel)) != 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 ((is_gabriel(pointVector.begin(), pointVector.end(), (cgal_simplextree.right.at(vertexForGabriel))->point()) - == CGAL::ON_BOUNDED_SIDE)) { + if (false == is_gab) { // ### filt(Tau) = filt(Sigma) Filtration_value alpha_complex_filtration = filtration(f_simplex); assign_filtration(f_boundary, alpha_complex_filtration); diff --git a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp index b55b5e2e..4202c9e9 100644 --- a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -35,11 +35,9 @@ #include // Use dynamic_dimension_tag for the user to be able to set dimension -typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; -typedef Kernel::Point_d Point; -typedef std::vector Vector_of_points; +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(S4_100_OFF_file) { // ---------------------------------------------------------------------------- // @@ -49,7 +47,7 @@ BOOST_AUTO_TEST_CASE(S4_100_OFF_file) { std::string off_file_name("S4_100.off"); std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); const int DIMENSION = 4; std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; @@ -74,7 +72,7 @@ BOOST_AUTO_TEST_CASE(S8_10_OFF_file) { std::string off_file_name("S8_10.off"); std::cout << "========== OFF FILE NAME = " << off_file_name << " ==========" << std::endl; - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name); const int DIMENSION = 8; std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; @@ -88,11 +86,17 @@ BOOST_AUTO_TEST_CASE(S8_10_OFF_file) { 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::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 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) { @@ -101,6 +105,7 @@ bool is_point_in_list(Vector_of_points points_list, Point point) { } return false; // point not found } + BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { // ---------------------------------------------------------------------------- @@ -109,6 +114,7 @@ BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { Vector_of_points points; std::vector coords; + points.clear(); coords.clear(); coords.push_back(0.0); coords.push_back(0.0); @@ -137,12 +143,12 @@ BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { // ---------------------------------------------------------------------------- // Init of an alpha complex from the list of points // ---------------------------------------------------------------------------- - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_points(3, points.size(), points.begin(), points.end()); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_points(3, points.size(), points.begin(), points.end()); std::cout << "========== Alpha_complex_from_points ==========" << std::endl; std::cout << "alpha_complex_from_points.dimension()=" << alpha_complex_from_points.dimension() << std::endl; - BOOST_CHECK(alpha_complex_from_points.dimension() == 3); + BOOST_CHECK(alpha_complex_from_points.dimension() == 4); std::cout << "alpha_complex_from_points.num_simplices()=" << alpha_complex_from_points.num_simplices() << std::endl; BOOST_CHECK(alpha_complex_from_points.num_simplices() == 15); std::cout << "alpha_complex_from_points.num_vertices()=" << alpha_complex_from_points.num_vertices() << std::endl; @@ -190,17 +196,14 @@ BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { Point p5 = alpha_complex_from_points.get_point(5); std::cout << "alpha_complex_from_points.get_point(5)=" << p5 << std::endl; - BOOST_CHECK(0 == p5.dimension()); BOOST_CHECK(!is_point_in_list(points, p5)); Point p0 = alpha_complex_from_points.get_point(0); std::cout << "alpha_complex_from_points.get_point(0)=" << p0 << std::endl; - BOOST_CHECK(0 == p0.dimension()); BOOST_CHECK(!is_point_in_list(points, p0)); Point p1234 = alpha_complex_from_points.get_point(1234); std::cout << "alpha_complex_from_points.get_point(1234)=" << p1234.dimension() << std::endl; - BOOST_CHECK(0 == p1234.dimension()); BOOST_CHECK(!is_point_in_list(points, p1234)); } diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index 79300790..87b05a3a 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -14,8 +14,11 @@ if(CGAL_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) include_directories (BEFORE "../../include") + if (CMAKE_BUILD_TYPE MATCHES Debug) + # For programs to be more verbose + add_definitions(-DDEBUG_TRACES) + endif() - #add_definitions(-DDEBUG_TRACES) add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) add_test(AlphaComplexUT ${CMAKE_CURRENT_BINARY_DIR}/AlphaComplexUT diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt index 9487cce6..3276989d 100644 --- a/src/Persistent_cohomology/example/CMakeLists.txt +++ b/src/Persistent_cohomology/example/CMakeLists.txt @@ -28,8 +28,11 @@ if (NOT MSVC) target_link_libraries(performance_rips_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) if(CGAL_FOUND) - # uncomment to display debug traces - # add_definitions(-DDEBUG_TRACES) + if (CMAKE_BUILD_TYPE MATCHES Debug) + # For programs to be more verbose + add_definitions(-DDEBUG_TRACES) + endif() + add_executable(alpha_shapes_persistence alpha_shapes_persistence.cpp) target_link_libraries(alpha_shapes_persistence ${Boost_SYSTEM_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES} ${CGAL_LIBRARY}) add_test(alpha_shapes_persistence_2_0_5 ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_persistence ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 2 0.5) -- cgit v1.2.3 From c972b77524faec5d6f297d442539f65b9351654e Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 13 Nov 2015 16:41:12 +0000 Subject: Utils.h -> Debug_utils.h More verbose in debug mode (use NDEBUG instead of DEBUG_TRACES) GUDHI_CHECK function to throw in debug or ignore in release mode git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@911 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 250dc0c0f5146f0b9e3fce0e9a8ca0da6af7cf98 --- CMakeLists.txt | 21 +++-- src/Alpha_complex/example/CMakeLists.txt | 4 - src/Alpha_complex/include/gudhi/Alpha_complex.h | 96 +++++++++------------- src/Alpha_complex/test/CMakeLists.txt | 4 - src/CMakeLists.txt | 13 ++- .../policies/Link_condition_valid_contraction.h | 2 +- src/Contraction/include/gudhi/Edge_contraction.h | 2 +- .../include/gudhi/Skeleton_blocker_contractor.h | 2 +- src/Simplex_tree/include/gudhi/Simplex_tree.h | 40 ++++----- .../include/gudhi/Skeleton_blocker.h | 2 +- .../Skeleton_blocker_sub_complex.h | 2 +- .../Skeleton_blockers_simplices_iterators.h | 2 +- .../include/gudhi/Skeleton_blocker_complex.h | 2 +- .../gudhi/Skeleton_blocker_geometric_complex.h | 2 +- .../include/gudhi/Skeleton_blocker_link_complex.h | 2 +- .../test/TestSkeletonBlockerComplex.cpp | 2 +- .../example/Delaunay_triangulation_off_rw.cpp | 5 ++ src/common/include/gudhi/Debug_utils.h | 53 ++++++++++++ .../include/gudhi/Delaunay_triangulation_off_io.h | 19 ++--- src/common/include/gudhi/Utils.h | 46 ----------- 20 files changed, 162 insertions(+), 159 deletions(-) create mode 100644 src/common/include/gudhi/Debug_utils.h delete mode 100644 src/common/include/gudhi/Utils.h (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/CMakeLists.txt b/CMakeLists.txt index 460196d7..b7fb4540 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -2,17 +2,26 @@ cmake_minimum_required(VERSION 2.6) project(GUDHIdev) include(CMakeGUDHIVersion.txt) -# Generate GUDHI official version file -configure_file(GUDHIVersion.cmake.in "${PROJECT_BINARY_DIR}/GUDHIVersion.cmake" @ONLY) -find_package(Boost REQUIRED COMPONENTS system filesystem unit_test_framework chrono timer program_options thread REQUIRED) +if (NOT CMAKE_BUILD_TYPE) + # Set default build type to Release + set(CMAKE_BUILD_TYPE "Release") +endif() + +if (CMAKE_BUILD_TYPE MATCHES Debug) + # For programs to be more verbose + add_definitions(-DNDEBUG) +endif() + +enable_testing() set(CMAKE_PREFIX_PATH "${CMAKE_SOURCE_DIR}/src/cmake/modules/") -set(CMAKE_MODULE_PATH "${CMAKE_SOURCE_DIR}/src/cmake/modules/") -message("CMAKE_PREFIX_PATH = ${CMAKE_PREFIX_PATH}") message("CMAKE_MODULE_PATH = ${CMAKE_MODULE_PATH}") -enable_testing() +# Generate GUDHI official version file +configure_file(GUDHIVersion.cmake.in "${PROJECT_BINARY_DIR}/GUDHIVersion.cmake" @ONLY) + +find_package(Boost REQUIRED COMPONENTS system filesystem unit_test_framework chrono timer program_options thread REQUIRED) if(MSVC) # Turn off some VC++ warnings diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt index 24f3a9dc..47e42b72 100644 --- a/src/Alpha_complex/example/CMakeLists.txt +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -29,10 +29,6 @@ if(CGAL_FOUND) if (EIGEN3_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) - if (CMAKE_BUILD_TYPE MATCHES Debug) - # For programs to be more verbose - add_definitions(-DDEBUG_TRACES) - endif() add_executable ( alphaoffreader Alpha_complex_from_off.cpp ) target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 10b290b5..2cc93a0a 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -26,6 +26,7 @@ // to construct a simplex_tree from Delaunay_triangulation #include #include +#include #include #include // isnan, fmax @@ -39,6 +40,7 @@ #include // NaN #include #include // std::pair +#include namespace Gudhi { @@ -112,7 +114,7 @@ class Alpha_complex : public Simplex_tree<> { : triangulation_(nullptr) { Gudhi::Delaunay_triangulation_off_reader off_reader(off_file_name); if (!off_reader.is_valid()) { - std::cerr << "Alpha_complex - Unable to read file " << off_file_name << std::endl; + std::cerr << "Alpha_complex - Unable to read file " << off_file_name; exit(-1); // ----- >> } triangulation_ = off_reader.get_complex(); @@ -137,6 +139,8 @@ class Alpha_complex : public Simplex_tree<> { * * The type InputPointRange must be a range for which std::begin and * std::end return input iterators on a Kernel::Point_d. + * \warning In debug mode, the exception std::invalid_argument is thrown if an empty input point range is passed as + * argument. */ template Alpha_complex(const InputPointRange& points, @@ -144,18 +148,24 @@ class Alpha_complex : public Simplex_tree<> { : triangulation_(nullptr) { auto first = std::begin(points); auto last = std::end(points); - // point_dimension function initialization - Point_Dimension point_dimension = kernel_.point_dimension_d_object(); + + GUDHI_CHECK((first == last), + std::invalid_argument ("Alpha_complex::Alpha_complex(InputPointRange) - Empty input point range")); + + if (first != last) { + // point_dimension function initialization + Point_Dimension point_dimension = kernel_.point_dimension_d_object(); - // Delaunay triangulation is point dimension minus one. - triangulation_ = new Delaunay_triangulation(point_dimension(*first) - 1); + // Delaunay triangulation is point dimension minus one. + triangulation_ = new Delaunay_triangulation(point_dimension(*first) - 1); - size_type inserted = triangulation_->insert(first, last); - if (inserted != (last -first)) { - std::cerr << "Alpha_complex - insertion failed " << inserted << " != " << (last -first) << std::endl; - exit(-1); // ----- >> + size_type inserted = triangulation_->insert(first, last); + if (inserted != (last -first)) { + std::cerr << "Alpha_complex - insertion failed " << inserted << " != " << (last -first); + exit(-1); // ----- >> + } + init(max_alpha_square); } - init(max_alpha_square); } /** \brief Alpha_complex destructor from a Delaunay triangulation. @@ -188,23 +198,25 @@ class Alpha_complex : public Simplex_tree<> { */ void init(Filtration_value max_alpha_square) { if (triangulation_ == nullptr) { - std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation" << std::endl; + std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation"; return; // ----- >> } if (triangulation_->number_of_vertices() < 1) { - std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices" << std::endl; + std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices"; return; // ----- >> } if (triangulation_->maximal_dimension() < 1) { - std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation" << std::endl; + std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation"; return; // ----- >> } if (num_vertices() > 0) { - std::cerr << "Alpha_complex init - Cannot init twice" << std::endl; + std::cerr << "Alpha_complex init - Cannot init twice"; return; // ----- >> } set_dimension(triangulation_->maximal_dimension()); + // set_filtration to +inf for prune_above_filtration to be done (if necessary) + set_filtration(std::numeric_limits::infinity()); // -------------------------------------------------------------------------------------------- // double map to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa @@ -213,9 +225,9 @@ class Alpha_complex : public Simplex_tree<> { // 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 - " << vertex_handle << " -> " << vit->point() << std::endl; -#endif // DEBUG_TRACES + DBGMSG("Vertex insertion - ", vertex_handle); + DBGMSG(" -> ", vit->point()); + vertex_iterator_to_handle_.emplace(vit, vertex_handle); vertex_handle_to_iterator_.push_back(vit); vertex_handle++; @@ -227,21 +239,12 @@ class Alpha_complex : public Simplex_tree<> { // 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 << " " << vertex_iterator_to_handle_[*vit]; -#endif // DEBUG_TRACES // Vector of vertex construction for simplex_tree structure vertexVector.push_back(vertex_iterator_to_handle_[*vit]); } } -#ifdef DEBUG_TRACES - std::cout << std::endl; -#endif // DEBUG_TRACES // Insert each simplex and its subfaces in the simplex tree - filtration is NaN Simplex_result insert_result = insert_simplex_and_subfaces(vertexVector, std::numeric_limits::quiet_NaN()); @@ -256,18 +259,11 @@ class Alpha_complex : public Simplex_tree<> { 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 + DBGMSG("Sigma of dim ", decr_dim); 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 + DBGCONT(simplex_vertex_range(f_simplex)); // ### If filt(Sigma) is NaN : filt(Sigma) = alpha(Sigma) if (isnan(filtration(f_simplex))) { Filtration_value alpha_complex_filtration = 0.0; @@ -279,9 +275,7 @@ class Alpha_complex : public Simplex_tree<> { 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 + DBGMSG("filt(Sigma) is NaN : filt(Sigma) =", filtration(f_simplex)); } propagate_alpha_filtration(f_simplex, decr_dim); } @@ -301,23 +295,16 @@ class Alpha_complex : public Simplex_tree<> { 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 + DBG("------------- TAU -------------"); + DBGCONT(simplex_vertex_range(f_boundary)); + DBG("is a face of Sigma"); + DBGMSG("isnan(filtration(Tau)=", isnan(filtration(f_boundary))); // ### 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 + DBGMSG("filt(Tau) = fmin(filt(Tau), filt(Sigma)) = ", filtration(f_boundary)); // ### Else } else { // No need to compute is_gabriel for dimension <= 2 @@ -344,17 +331,14 @@ class Alpha_complex : public Simplex_tree<> { 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 + DBGMSG("Tau is_gabriel(Sigma)=", is_gab); + DBGMSG(" - vertexForGabriel=", vertexForGabriel); // ### 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 + DBGMSG("filt(Tau) = filt(Sigma) = ", filtration(f_boundary)); } } } diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index 847581aa..fa24e1b1 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -14,10 +14,6 @@ if(CGAL_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) include_directories (BEFORE "../../include") - if (CMAKE_BUILD_TYPE MATCHES Debug) - # For programs to be more verbose - add_definitions(-DDEBUG_TRACES) - endif() add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index cd7f4991..0f946e3b 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -3,15 +3,22 @@ project(GUDHI) include("CMakeGUDHIVersion.txt") +if (NOT CMAKE_BUILD_TYPE) + # Set default build type to Release + set(CMAKE_BUILD_TYPE "Release") +endif() + +if (CMAKE_BUILD_TYPE MATCHES Debug) + # For programs to be more verbose + add_definitions(-DNDEBUG) +endif() + enable_testing() list(APPEND CMAKE_MODULE_PATH "${CMAKE_SOURCE_DIR}/cmake/modules/") find_package(Boost REQUIRED COMPONENTS system filesystem program_options chrono timer REQUIRED) -if (NOT CMAKE_BUILD_TYPE) - set(CMAKE_BUILD_TYPE "Release") -endif() if(MSVC) SET (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4267 /wd4668 /wd4311 /wd4800 /wd4820 /wd4503 /wd4244 /wd4345 /wd4996 /wd4396 /wd4018") else() diff --git a/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h index 919df243..250bba27 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h @@ -23,8 +23,8 @@ #ifndef CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ #define CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ -#include #include +#include namespace Gudhi { diff --git a/src/Contraction/include/gudhi/Edge_contraction.h b/src/Contraction/include/gudhi/Edge_contraction.h index 349bb7d8..011ca9bd 100644 --- a/src/Contraction/include/gudhi/Edge_contraction.h +++ b/src/Contraction/include/gudhi/Edge_contraction.h @@ -30,7 +30,7 @@ #include #include #include -#include +#include namespace Gudhi { diff --git a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h index 2759b540..47d798c0 100644 --- a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h +++ b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h @@ -37,7 +37,7 @@ #include #include -#include +#include #include diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 8c1beaef..dc8591fc 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -30,6 +30,7 @@ #include #include +#include #include #include @@ -39,7 +40,8 @@ #include #include #include // for greater<> -#include // for numeric_limits infinity +#include +#include // Inf namespace Gudhi { /** \defgroup simplex_tree Filtered Complexes @@ -717,7 +719,7 @@ class Simplex_tree { } else if (the_simplex.size() == 1) { // When reaching the end of recursivity, vector of simplices shall be empty and filled on back recursive if ((to_be_inserted.size() != 0) || (to_be_propagated.size() != 0)) { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty" << std::endl; + std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty"; exit(-1); } std::vector first_simplex(1, the_simplex.back()); @@ -726,7 +728,7 @@ class Simplex_tree { insert_result = insert_vertex_vector(first_simplex, filtration); } else { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error" << std::endl; + std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error"; exit(-1); } return insert_result; @@ -1099,22 +1101,23 @@ class Simplex_tree { os << filtration(sh) << " \n"; } } - + public: /** \brief Browse the simplex tree to ensure the filtration is not decreasing. - * @return The filtration modification information in order to trigger initialize_filtration. - * \warning initialize_filtration is launched again in case of filtration modification change. + * The simplex tree is browsed starting from the root until the leaf, and the filtration values are set with their + * parent value (increased), in case the values are decreasing. + * @return The filtration modification information. + * \warning Some simplex tree functions require the filtration to be valid. `make_filtration_non_decreasing()` + * function is not launching `initialize_filtration()` but returns the filtration modification information. If the + * complex has changed , please call `initialize_filtration()` to recompute it. */ bool make_filtration_non_decreasing() { bool modified = false; for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { if (has_children(sh)) { - modified = modified || rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); + modified |= rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); } } - if (modified) { - initialize_filtration(); - } return modified; } @@ -1134,7 +1137,7 @@ class Simplex_tree { sh->second.assign_filtration(upper_filtration); } if (has_children(sh)) { - modified = modified || rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); + modified |= rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); } } // Make the modified information to be traced by upper call @@ -1150,8 +1153,8 @@ class Simplex_tree { * call `initialize_filtration()` to recompute it. */ void prune_above_filtration(Filtration_value filtration) { - threshold_ = filtration; - if (filtration != std::numeric_limits::infinity()) { + if (filtration < threshold_) { + threshold_ = filtration; // Initialize filtration_vect_ if required if (filtration_vect_.empty()) { initialize_filtration(); @@ -1168,16 +1171,15 @@ class Simplex_tree { } } - private: /** \brief Remove a maximal simplex. * @param[in] sh Simplex handle on the maximal simplex to remove. - * \warning Exception std::invalid_argument is thrown in sh has children. + * \warning In debug mode, the exception std::invalid_argument is thrown if sh has children. */ void remove_maximal_simplex(Simplex_handle sh) { - // Guarantee the simplex is maximal - if (has_children(sh)) { - throw std::invalid_argument ("Simplex_tree::remove_maximal_simplex - argument is not a maximal simplex"); - } + // Guarantee the simplex has no children + GUDHI_CHECK(has_children(sh), + std::invalid_argument ("Simplex_tree::remove_maximal_simplex - argument is not a maximal simplex")); + // Simplex is a leaf, it means the child is the Siblings owning the leaf. Siblings* child = sh->second.children(); if (child->size() > 1) { diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 3be480fd..20df93eb 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -31,7 +31,7 @@ #include #include -#include // xxx +#include namespace Gudhi { diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index b33b9606..1b1fe3f0 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -25,7 +25,7 @@ #include #include -#include +#include #include #include diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h index 4d71b3f5..27411fc1 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -25,7 +25,7 @@ #include #include #include -#include +#include #include diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index d26d12b0..dc2d9e29 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -33,7 +33,7 @@ #include #include -#include +#include #include #include diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h index b8395251..3725b7a2 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -22,9 +22,9 @@ #ifndef SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ #define SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ -#include #include #include +#include namespace Gudhi { diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h index 95d8fa97..3d0039a1 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h @@ -22,8 +22,8 @@ #ifndef SKELETON_BLOCKER_LINK_COMPLEX_H_ #define SKELETON_BLOCKER_LINK_COMPLEX_H_ -#include #include +#include namespace Gudhi { diff --git a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp index 319e3c43..d56a5c91 100644 --- a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp +++ b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp @@ -24,7 +24,7 @@ #include #include #include -#include "gudhi/Utils.h" +#include "gudhi/Debug_utils.h" #include "gudhi/Test.h" #include "gudhi/Skeleton_blocker.h" //#include "gudhi/Skeleton_blocker_link_complex.h" diff --git a/src/common/example/Delaunay_triangulation_off_rw.cpp b/src/common/example/Delaunay_triangulation_off_rw.cpp index 75e4fafb..12accd10 100644 --- a/src/common/example/Delaunay_triangulation_off_rw.cpp +++ b/src/common/example/Delaunay_triangulation_off_rw.cpp @@ -24,6 +24,11 @@ int main(int argc, char **argv) { usage(argv[0]); } + +#ifdef GUDHI_NDEBUG + std::cout << "pouet pouet !!" << std::endl; +#endif + std::string offInputFile(argv[1]); // Read the OFF file (input file name given as parameter) and triangulates points Gudhi::Delaunay_triangulation_off_reader off_reader(offInputFile); diff --git a/src/common/include/gudhi/Debug_utils.h b/src/common/include/gudhi/Debug_utils.h new file mode 100644 index 00000000..c479d435 --- /dev/null +++ b/src/common/include/gudhi/Debug_utils.h @@ -0,0 +1,53 @@ +/* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 . + */ +#ifndef DEBUG_UTILS_H_ +#define DEBUG_UTILS_H_ + +#include + +#ifdef NDEBUG + // GUDHI_NDEBUG is the Gudhi official flag for debug mode. + #define GUDHI_NDEBUG +#endif + +#define PRINT(a) std::cerr << #a << ": " << (a) << " (DISP)" << std::endl + +#ifdef GUDHI_NDEBUG + #define DBG(a) std::cout << "DBG: " << (a) << std::endl + #define DBGMSG(a, b) std::cout << "DBG: " << a << b << std::endl + #define DBGVALUE(a) std::cout << "DBG: " << #a << ": " << a << std::endl + #define DBGCONT(a) std::cout << "DBG: container " << #a << " -> "; for (auto x : a) std::cout << x << ","; std::cout << std::endl +#else + #define DBG(a) (void) 0 + #define DBGMSG(a, b) (void) 0 + #define DBGVALUE(a) (void) 0 + #define DBGCONT(a) (void) 0 +#endif + +// GUDHI_CHECK throw an exception on condition in debug mode, but does nothing in release mode +#ifdef GUDHI_NDEBUG + #define GUDHI_CHECK(cond, excpt) if (cond) throw excpt +#else + #define GUDHI_CHECK(cond, excpt) (void) 0 +#endif + +#endif // DEBUG_UTILS_H_ diff --git a/src/common/include/gudhi/Delaunay_triangulation_off_io.h b/src/common/include/gudhi/Delaunay_triangulation_off_io.h index 4d26bb71..dfa70e40 100644 --- a/src/common/include/gudhi/Delaunay_triangulation_off_io.h +++ b/src/common/include/gudhi/Delaunay_triangulation_off_io.h @@ -22,6 +22,8 @@ #ifndef DELAUNAY_TRIANGULATION_OFF_IO_H_ #define DELAUNAY_TRIANGULATION_OFF_IO_H_ +#include + #include #include #include @@ -64,10 +66,10 @@ class Delaunay_triangulation_off_visitor_reader { * @param[in] num_edges number of edges in the OFF file (not used). */ void init(int dim, int num_vertices, int num_faces, int num_edges) { -#ifdef DEBUG_TRACES - std::cout << "Delaunay_triangulation_off_visitor_reader::init - dim=" << dim << " - num_vertices=" << - num_vertices << " - num_faces=" << num_faces << " - num_edges=" << num_edges << std::endl; -#endif // DEBUG_TRACES + DBGMSG("Delaunay_triangulation_off_visitor_reader::init - dim=", dim); + DBGMSG(" - num_vertices=", num_vertices); + DBGMSG(" - num_faces=", num_faces); + DBGMSG(" - num_edges=", num_edges); if (num_faces > 0) { std::cerr << "Delaunay_triangulation_off_visitor_reader::init faces are not taken into account from OFF " << "file for Delaunay triangulation - faces are computed." << std::endl; @@ -88,13 +90,8 @@ class Delaunay_triangulation_off_visitor_reader { * @param[in] point vector of vertex coordinates. */ void point(const std::vector& point) { -#ifdef DEBUG_TRACES - std::cout << "Delaunay_triangulation_off_visitor_reader::point "; - for (auto coordinate : point) { - std::cout << coordinate << " | "; - } - std::cout << std::endl; -#endif // DEBUG_TRACES + DBG("Delaunay_triangulation_off_visitor_reader::point"); + DBGCONT(point); complex_->insert(Point(point.size(), point.begin(), point.end())); } diff --git a/src/common/include/gudhi/Utils.h b/src/common/include/gudhi/Utils.h deleted file mode 100644 index 43916f11..00000000 --- a/src/common/include/gudhi/Utils.h +++ /dev/null @@ -1,46 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 . - */ -#ifndef UTILS_H_ -#define UTILS_H_ - - -#define PRINT(a) std::cerr << #a << ": " << (a) << " (DISP)" << std::endl - -// #define DBG_VERBOSE -#ifdef DBG_VERBOSE -#define DBG(a) std::cerr << "DBG: " << (a) << std::endl -#define DBGMSG(a, b) std::cerr << "DBG: " << a << b << std::endl -#define DBGVALUE(a) std::cerr << "DBG: " << #a << ": " << a << std::endl -#define DBGCONT(a) std::cerr << "DBG: container " << #a << " -> "; for (auto x : a) std::cerr << x << ","; std::cerr << -std::endl -#else -// #define DBG(a) a -// #define DBGMSG(a,b) b -// #define DBGVALUE(a) a -// #define DBGCONT(a) a -#define DBG(a) -#define DBGMSG(a, b) -#define DBGVALUE(a) -#define DBGCONT(a) -#endif - -#endif // UTILS_H_ -- cgit v1.2.3 From f9b5b9b3306f3f00f5bfa2724cbfa087d5161fcb Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 11 Dec 2015 15:41:39 +0000 Subject: Commit code and doc review Still issue and lot of logs in simplex_tree::prune_above_filtration git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@945 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: cd4f60ddcacb0444e0eb3b9323d8042eb49b132e --- CMakeLists.txt | 4 +- biblio/bibliography.bib | 16 -- src/Alpha_complex/doc/Intro_alpha_complex.h | 8 +- src/Alpha_complex/doc/alpha_complex_doc.ipe | 24 +- src/Alpha_complex/doc/alpha_complex_doc.png | Bin 46746 -> 49973 bytes src/Alpha_complex/doc/alpha_complex_doc_135.ipe | 88 +++---- src/Alpha_complex/doc/alpha_complex_doc_135.png | Bin 127130 -> 80794 bytes .../doc/alpha_complex_representation.png | Bin 0 -> 16737 bytes .../example/Alpha_complex_from_points.cpp | 22 +- src/Alpha_complex/include/gudhi/Alpha_complex.h | 6 +- src/Alpha_complex/test/CMakeLists.txt | 2 + src/Simplex_tree/include/gudhi/Simplex_tree.h | 95 ++++++-- .../gudhi/Simplex_tree/Simplex_tree_siblings.h | 4 + src/Simplex_tree/test/simplex_tree_unit_test.cpp | 266 ++++++++++++++++++++- .../example/dtoffrw_alphashapedoc_result.off | 15 ++ .../example/dtoffrw_alphashapedoc_result.txt | 1 - .../include/gudhi/Delaunay_triangulation_off_io.h | 2 +- src/common/test/dtoffrw_unit_test.cpp | 4 +- 18 files changed, 436 insertions(+), 121 deletions(-) create mode 100644 src/Alpha_complex/doc/alpha_complex_representation.png create mode 100644 src/common/example/dtoffrw_alphashapedoc_result.off (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/CMakeLists.txt b/CMakeLists.txt index d42f7af7..d0770dd7 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -22,8 +22,8 @@ if(MSVC) # Turn off some VC++ warnings SET (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4267 /wd4668 /wd4311 /wd4800 /wd4820 /wd4503 /wd4244 /wd4345 /wd4996 /wd4396 /wd4018") else() - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -Wall -Wpedantic -Wsign-compare") - set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -O0") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -fsanitize=memory -fno-omit-frame-pointer -Wall -Wpedantic -Wsign-compare") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -O1") set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE}") endif() diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 859696b4..3fd1c10a 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -897,22 +897,6 @@ language={English} bibsource = {DBLP, http://dblp.uni-trier.de} } -@ARTICLE{AlphaShapesDefinition, - author = {N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke, and C. Varela}, - title = {\href{http://pub.ist.ac.at/~edels/Papers/1995-P-06-AlphaShapesSoftware.pdf}{Alpha shapes: definition and software}}, - journal = {Proc. Internat. Comput. Geom. Software Workshop 1995}, - year = {1995}, - bibsource = {http://pub.ist.ac.at} -} - -@ARTICLE{AlphaShapesIntroduction, - author = {Kaspar Fischer}, - title = {\href{http://www.cs.uu.nl/docs/vakken/ddm/texts/Delaunay/alphashapes.pdf}{Introduction to Alpha Shapes}}, - journal = {Unknown}, - year = {Unknown}, - bibsource = {http://www.cs.uu.nl} -} - misc{buddha_stanford_scan, author = "", title = "The Stanford 3D Scanning Repository", diff --git a/src/Alpha_complex/doc/Intro_alpha_complex.h b/src/Alpha_complex/doc/Intro_alpha_complex.h index 685a4c2f..12d62ac0 100644 --- a/src/Alpha_complex/doc/Intro_alpha_complex.h +++ b/src/Alpha_complex/doc/Intro_alpha_complex.h @@ -37,10 +37,10 @@ namespace alphacomplex { * \section definition Definition * * Alpha_complex is a simplicial complex - * constructed from each finite cell of a Delaunay Triangulation. + * constructed from the finite cells of a Delaunay Triangulation. * - * The filtration value of each simplex is computed from the alpha square value of the simplex if it is Gabriel or - * from the alpha value of the simplex coface that makes the simplex not Gabriel. + * The filtration value of each simplex is computed from the circumradius of the simplex if it is Gabriel or + * from the alpha value of the simplex cofaces that make it not Gabriel. * * All simplices that have a filtration value strictly greater than a given alpha square value are not inserted into * the simplex. @@ -78,7 +78,7 @@ namespace alphacomplex { * * \subsection datastructure Data structure * - * In order to build the alpha complex, first, a Simplex tree is build from the cells of a Delaunay Triangulation. + * 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" * diff --git a/src/Alpha_complex/doc/alpha_complex_doc.ipe b/src/Alpha_complex/doc/alpha_complex_doc.ipe index b5601143..e74f9bc4 100644 --- a/src/Alpha_complex/doc/alpha_complex_doc.ipe +++ b/src/Alpha_complex/doc/alpha_complex_doc.ipe @@ -1,7 +1,7 @@ - - + + @@ -202,13 +202,13 @@ h + + - - @@ -232,14 +232,7 @@ h - - - - - - - - + 320 580 m 350 520 l 290 530 l @@ -434,5 +427,12 @@ h 280 610 m 170 610 l + + + + + + + diff --git a/src/Alpha_complex/doc/alpha_complex_doc.png b/src/Alpha_complex/doc/alpha_complex_doc.png index 601ac051..c9eab275 100644 Binary files a/src/Alpha_complex/doc/alpha_complex_doc.png and b/src/Alpha_complex/doc/alpha_complex_doc.png differ diff --git a/src/Alpha_complex/doc/alpha_complex_doc_135.ipe b/src/Alpha_complex/doc/alpha_complex_doc_135.ipe index 28b893b8..5d1d29d4 100644 --- a/src/Alpha_complex/doc/alpha_complex_doc_135.ipe +++ b/src/Alpha_complex/doc/alpha_complex_doc_135.ipe @@ -1,7 +1,7 @@ - - + + @@ -202,13 +202,13 @@ h + + - - @@ -232,14 +232,7 @@ h - - - - - - - - + 320 580 m 350 520 l 290 530 l @@ -288,19 +281,11 @@ h 77.2727 0 0 77.2727 243.636 591.818 e - 243.428 591.569 m 186.061 643.28 l $\alpha_{420}$ - - - - - - - 320 580 m 350 520 l @@ -325,7 +310,6 @@ h modified (NaN) 0 -1 2 3 4 @@ -357,18 +341,10 @@ modified (NaN) 29.1548 0 0 29.1548 305 555 e - 304.883 555.015 m 334.509 555.015 l - - - - - - - 320 580 m 350 520 l @@ -391,10 +367,7 @@ modified (NaN) [0,4] is not Gabriel $\rightarrow$ $\alpha_{40} = \alpha_{420}$ 0 -1 -2 3 -4 5 6 @@ -420,16 +393,6 @@ modified (NaN) 290 530 m 280 660 l - -65.192 0 0 65.192 285 595 e - - - - - - - - 320 580 m 350 520 l @@ -483,7 +446,6 @@ modified (NaN) 44.5799 0 0 44.5799 425.934 457.774 e - 425.854 457.774 m 470.795 457.774 l @@ -505,10 +467,48 @@ modified (NaN) For all faces of [4,2,0] N.B. : is Gabriel on a single point has no sense. Dimension =2 - $\sigma$ = [4,2,0] - 247.333 430.892 m 311.764 430.892 l + + + + + + + + + + + + + +1 + + + + + +4 + + +1 + + +2 + +65.192 0 0 65.192 285 595 e + + + + + + + + + + + diff --git a/src/Alpha_complex/doc/alpha_complex_doc_135.png b/src/Alpha_complex/doc/alpha_complex_doc_135.png index 5dce5edd..ef7187f7 100644 Binary files a/src/Alpha_complex/doc/alpha_complex_doc_135.png and b/src/Alpha_complex/doc/alpha_complex_doc_135.png differ diff --git a/src/Alpha_complex/doc/alpha_complex_representation.png b/src/Alpha_complex/doc/alpha_complex_representation.png new file mode 100644 index 00000000..06e54c06 Binary files /dev/null and b/src/Alpha_complex/doc/alpha_complex_representation.png differ diff --git a/src/Alpha_complex/example/Alpha_complex_from_points.cpp b/src/Alpha_complex/example/Alpha_complex_from_points.cpp index 62f594d1..00e988a6 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_points.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_points.cpp @@ -30,21 +30,13 @@ int main(int argc, char **argv) { // Init of a list of points // ---------------------------------------------------------------------------- Vector_of_points points; - - std::vector coords = { 1.0, 1.0 }; - points.push_back(Point(coords.begin(), coords.end())); - coords = { 7.0, 0.0 }; - points.push_back(Point(coords.begin(), coords.end())); - coords = { 4.0, 6.0 }; - points.push_back(Point(coords.begin(), coords.end())); - coords = { 9.0, 6.0 }; - points.push_back(Point(coords.begin(), coords.end())); - coords = { 0.0, 14.0 }; - points.push_back(Point(coords.begin(), coords.end())); - coords = { 2.0, 19.0 }; - points.push_back(Point(coords.begin(), coords.end())); - coords = { 9.0, 17.0 }; - points.push_back(Point(coords.begin(), coords.end())); + 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 diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 2dae4028..9f931066 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -125,7 +125,9 @@ class Alpha_complex : public Simplex_tree<> { /** \brief Alpha_complex constructor from a Delaunay triangulation. * - * @param[in] triangulation_ptr Pointer on a Delaunay triangulation. + * @param[in] triangulation_ptr Pointer on a + * CGAL::Delaunay_triangulation \cite cgal:hdj-t-15b. * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. */ Alpha_complex(Delaunay_triangulation* triangulation_ptr, @@ -170,7 +172,7 @@ class Alpha_complex : public Simplex_tree<> { } } - /** \brief Alpha_complex destructor from a Delaunay triangulation. + /** \brief Alpha_complex destructor. * * @warning Deletes the Delaunay triangulation. */ diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index fa24e1b1..d7c13da0 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -18,6 +18,8 @@ if(CGAL_FOUND) add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + add_executable ( cerr cerr.cpp ) + # 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}/) diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 3adf06d3..4b04e75a 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -530,7 +530,7 @@ class Simplex_tree { return dimension_; } - /** \brief Returns true iff the node in the simplex tree pointed by + /** \brief Returns true if the node in the simplex tree pointed by * sh has children.*/ bool has_children(Simplex_handle sh) const { return (sh->second.children()->parent() == sh->first); @@ -1134,7 +1134,6 @@ class Simplex_tree { if (sh->second.filtration() < upper_filtration) { // Store the filtration modification information modified = true; - std::cout << "modified" << std::endl; sh->second.assign_filtration(upper_filtration); } if (has_children(sh)) { @@ -1154,21 +1153,51 @@ class Simplex_tree { * call `initialize_filtration()` to recompute it. */ void prune_above_filtration(Filtration_value filtration) { - if (filtration < threshold_) { - threshold_ = filtration; - // Initialize filtration_vect_ if required - if (filtration_vect_.empty()) { - initialize_filtration(); - } +std::cout << "prune_above_filtration - filtration=" << filtration << std::endl; + // No action if filtration is not stored + if (Options::store_filtration) { + if (filtration < threshold_) { + threshold_ = filtration; + // Initialize filtration_vect_ if required + if (filtration_vect_.empty()) { +std::cout << "prune_above_filtration - initialize_filtration" << std::endl; + initialize_filtration(); + } + +std::cout << "prune_above_filtration - after initialize_filtration "; +for(auto sh : filtration_vect_) { +for (auto vertex : simplex_vertex_range(sh)) { +std::cout << (int) vertex << ", "; +} +std::cout << " - filtration=" << sh->second.filtration() << " - " << &(sh->second) << std::endl; +} - // Loop in reverse mode until threshold is reached - auto f_simplex = filtration_vect_.rbegin(); - for (; f_simplex != filtration_vect_.rend() && ((*f_simplex)->second.filtration() > threshold_); f_simplex++) { - remove_maximal_simplex(*f_simplex); + + // Loop in reverse mode until threshold is reached + auto f_simplex = filtration_vect_.rbegin(); + for (; (f_simplex != filtration_vect_.rend()) && ((*f_simplex)->second.filtration() > threshold_); f_simplex++) { + +std::cout << "prune_above_filtration - remove "; +for (auto vertex : simplex_vertex_range(*f_simplex)) { +std::cout << (int) vertex << ", "; +} +std::cout << " - " << &((*f_simplex)->second) << std::endl; + + remove_maximal_simplex(*f_simplex); + } +std::cout << "prune_above_filtration - remove STOPPED ON "; +for (auto vertex : simplex_vertex_range(*f_simplex)) { +std::cout << (int) vertex << ", "; +} +std::cout << " - filtration=" << (*f_simplex)->second.filtration() << " - " << &(*f_simplex->second) << std::endl; + if (f_simplex != filtration_vect_.rbegin()) { + // Do not forget to update filtration_vect_ - resize is enough + std::size_t new_size = filtration_vect_.size() - (f_simplex - filtration_vect_.rbegin()); +std::cout << "prune_above_filtration - resize" << new_size << std::endl; + filtration_vect_.resize(new_size); + } + } - // Do not forget to update filtration_vect_ - resize is enough - std::size_t new_size = filtration_vect_.size() - (f_simplex - filtration_vect_.rbegin()); - filtration_vect_.resize(new_size); } } @@ -1187,14 +1216,46 @@ class Simplex_tree { if ((child->size() > 1) || (child == root())) { // Not alone, just remove it from members // Special case when child is the root of the simplex tree, just remove it from members - child->members().erase(sh->first); +std::cout << "remove_maximal_simplex - members removal" << std::endl; + child->erase(sh->first); } else { // Sibling is emptied : must be deleted, and its parent must point on his own Sibling +std::cout << "remove_maximal_simplex - members is empty" << std::endl; child->oncles()->members().at(child->parent()).assign_children(child->oncles()); delete child; } } - +/***************************************************************************************************************/ + public: + /** \brief Prints the simplex_tree hierarchically. + * Since it prints the vertices recursively, one can watch its tree shape. + */ + void print_tree() { + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { + std::cout << sh->first << " "; + if (has_children(sh)) { + std::cout << "("; + rec_print(sh->second.children()); + std::cout << ")"; + } + std::cout << std::endl; + } + } + + + /** \brief Recursively prints the simplex_tree, using depth first search. */ + private: + void rec_print(Siblings * sib) { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { + std::cout << " " << sh->first << " "; + if (has_children(sh)) { + std::cout << "("; + rec_print(sh->second.children()); + std::cout << ")"; + } + } + } +/*****************************************************************************************************************/ private: Vertex_handle null_vertex_; /** \brief Upper bound on the filtration values of the simplices.*/ diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h index 158ee1f7..c1ff8bf2 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h @@ -116,6 +116,10 @@ class Simplex_tree_siblings { return members_.size(); } + void erase(const Vertex_handle vh) { + members_.erase(vh); + } + Simplex_tree_siblings * oncles_; Vertex_handle parent_; Dictionary members_; diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 00cf69bc..f6bd5411 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -362,7 +362,9 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { } -bool sort_in_decr_order (Vertex_handle i,Vertex_handle j) { return (i>j); } +bool sort_in_decr_order(Vertex_handle i, Vertex_handle j) { + return (i > j); +} BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { std::cout << "********************************************************************" << std::endl; @@ -476,7 +478,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { BOOST_CHECK(vertex == SimplexVector6[position]); position++; } - + /* Inserted simplex: */ /* 1 6 */ /* o---o */ @@ -720,14 +722,268 @@ BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { // Check there is a new simplex tree reference BOOST_CHECK(&st_move != &st_copy); BOOST_CHECK(&st_move != &st); - + typeST st_empty; // Check st has been emptied by the move BOOST_CHECK(st == st_empty); BOOST_CHECK(st.filtration() == 0); BOOST_CHECK(st.dimension() == -1); BOOST_CHECK(st.num_simplices() == 0); - BOOST_CHECK(st.num_vertices() == (size_t)0); - + BOOST_CHECK(st.num_vertices() == (size_t) 0); + std::cout << "Printing st once again- address = " << &st << std::endl; } + +BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { + std::cout << "********************************************************************" << std::endl; + std::cout << "MAKE FILTRATION NON DECREASING" << std::endl; + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); + st.insert_simplex_and_subfaces({3, 0}, 3.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 4.0 + // to 1.0 + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + // FIXME + st.set_dimension(3); + + // Copy constructor + typeST st_copy = st; + + // Check default insertion ensures the filtration values are non decreasing + BOOST_CHECK(!st.make_filtration_non_decreasing()); + // Check the simplex tree is not modified by the function + BOOST_CHECK(st == st_copy); + + // Make { 0, 1 } decreasing + st.assign_filtration(st.find({0, 1}), 0.5); + // Make { 1, 6, 7 } decreasing + st.assign_filtration(st.find({1, 6, 7}), 0.4); + // Make { 3, 4 } decreasing + st.assign_filtration(st.find({3, 4}), 0.3); + // Make { 4, 5 } decreasing + st.assign_filtration(st.find({4, 5}), 0.1); + + // Check the filtration values were decreasing + BOOST_CHECK(st.make_filtration_non_decreasing()); + // Check the simplex tree has been modified by the function to retrieve the initial simplex tree + BOOST_CHECK(st == st_copy); + + // Change { 0, 3 }, but still non decreasing + st.assign_filtration(st.find({0, 3}), 1.01); + // Change { 0, 1, 6, 7 }, but still non decreasing + st.assign_filtration(st.find({0, 1, 6, 7}), 1.201); + // Change { 1, 2 }, but still non decreasing + st.assign_filtration(st.find({1, 2}), 1.05); + // Change { 4 }, but still non decreasing + st.assign_filtration(st.find({4}), 1.123); + + // Check the filtration values are non decreasing + BOOST_CHECK(!st.make_filtration_non_decreasing()); + // Check the simplex tree has been modified from the original + BOOST_CHECK(st != st_copy); + +} + +struct MyOptions : Simplex_tree_options_full_featured { + // Not doing persistence, so we don't need those + static const bool store_key = false; + static const bool store_filtration = false; + // I have few vertices + typedef short Vertex_handle; +}; +typedef Simplex_tree miniST; + +/*BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { + std::cout << "********************************************************************" << std::endl; + std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl; + + miniST st; + + // FIXME + st.set_dimension(3); + + st.insert_simplex_and_subfaces({0, 1, 6, 7}); + st.insert_simplex_and_subfaces({3, 4, 5}); + + // Constructs a copy at this state for further test purpose + miniST st_pruned = st; + + st.insert_simplex_and_subfaces({3, 0}); + st.insert_simplex_and_subfaces({2, 1, 0}); + + // Constructs a copy at this state for further test purpose + miniST st_complete = st; + // st_complete and st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + // st_pruned: + // 1 6 + // o---o + // \7/ + // o o---o + // 0 3\X/4 + // o + // 5 + +#ifdef GUDHI_DEBUG + std::cout << "Check exception throw in debug mode" << std::endl; + // throw excpt because sh has children + BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({0, 1, 6})), std::invalid_argument); + BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({3})), std::invalid_argument); + BOOST_CHECK(st == st_complete); +#endif + + st.remove_maximal_simplex(st.find({0, 2})); + st.remove_maximal_simplex(st.find({0, 1, 2})); + st.remove_maximal_simplex(st.find({1, 2})); + st.remove_maximal_simplex(st.find({2})); + st.remove_maximal_simplex(st.find({0, 3})); + + BOOST_CHECK(st == st_pruned); + // Remove all, but as the simplex tree is not storing filtration, there is no modification + st.prune_above_filtration(0.0); + BOOST_CHECK(st == st_pruned); + + miniST st_wo_seven; + // FIXME + st_wo_seven.set_dimension(3); + + st_wo_seven.insert_simplex_and_subfaces({0, 1, 6}); + st_wo_seven.insert_simplex_and_subfaces({3, 4, 5}); + // st_wo_seven: + // 1 6 + // o---o + // \X/ + // o o---o + // 0 3\X/4 + // o + // 5 + + // Remove all 7 to test the both remove_maximal_simplex cases (when _members is empty or not) + st.remove_maximal_simplex(st.find({0, 1, 6, 7})); + st.remove_maximal_simplex(st.find({0, 1, 7})); + st.remove_maximal_simplex(st.find({0, 6, 7})); + st.remove_maximal_simplex(st.find({0, 7})); + st.remove_maximal_simplex(st.find({1, 6, 7})); + st.remove_maximal_simplex(st.find({1, 7})); + st.remove_maximal_simplex(st.find({6, 7})); + st.remove_maximal_simplex(st.find({7})); + + BOOST_CHECK(st == st_wo_seven); +}*/ + +BOOST_AUTO_TEST_CASE(prune_above_filtration) { + std::cout << "********************************************************************" << std::endl; + std::cout << "PRUNE ABOVE FILTRATION" << std::endl; + typeST st; + + // FIXME + st.set_dimension(3); + + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + st.set_filtration(6.0); + + // Constructs a copy at this state for further test purpose + typeST st_pruned = st; + st_pruned.initialize_filtration(); // reset + + st.insert_simplex_and_subfaces({3, 0}, 3.0); + st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); + + // Constructs a copy at this state for further test purpose + typeST st_complete = st; + // st_complete and st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + // st_pruned: + // 1 6 + // o---o + // \7/ + // o o---o + // 0 3\X/4 + // o + // 5 + + // Check the no action cases + // greater than initial filtration value + st.prune_above_filtration(10.0); + BOOST_CHECK(st == st_complete); + // equal to initial filtration value + st.prune_above_filtration(6.0); + BOOST_CHECK(st == st_complete); + // lower than initial filtration value, but still greater than the maximum filtration value + st_complete.set_filtration(5.0); + st.prune_above_filtration(5.0); + BOOST_CHECK(st == st_complete); + + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + // Check the pruned cases + // Set the st_pruned filtration for operator== + st_pruned.set_filtration(2.5); + st.prune_above_filtration(2.5); + /*BOOST_CHECK(st == st_pruned); + + st_pruned.set_filtration(2.0); + st.prune_above_filtration(2.0); + BOOST_CHECK(st == st_pruned); +*/ +/* std::cout << "The complex contains " << st.num_simplices() << " simplices --------------------------" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + st.print_tree(); + + std::cout << "The pruned complex contains " << st_pruned.num_simplices() << " simplices --------------------------" << std::endl; + std::cout << " - dimension " << st_pruned.dimension() << " - filtration " << st_pruned.filtration() << std::endl; + st_pruned.print_tree(); + + typeST st_empty; + // FIXME + st_empty.set_dimension(3); + st.prune_above_filtration(0.0); + */ + /*BOOST_CHECK(st == st_empty); + + // Test case to the limit + st.prune_above_filtration(-1.0); + st_empty.set_filtration(-1.0); + BOOST_CHECK(st == st_empty); +*/ +} + +/*BOOST_AUTO_TEST_CASE(sanitizer) { + int a[2] = {1, 0}; + int b=a[2]; +}*/ diff --git a/src/common/example/dtoffrw_alphashapedoc_result.off b/src/common/example/dtoffrw_alphashapedoc_result.off new file mode 100644 index 00000000..03b7ca75 --- /dev/null +++ b/src/common/example/dtoffrw_alphashapedoc_result.off @@ -0,0 +1,15 @@ +nOFF +2 7 6 0 +1 1 +7 0 +4 6 +9 6 +0 14 +2 19 +9 17 +3 0 1 2 +3 3 2 1 +3 4 0 2 +3 4 2 6 +3 6 2 3 +3 5 4 6 diff --git a/src/common/example/dtoffrw_alphashapedoc_result.txt b/src/common/example/dtoffrw_alphashapedoc_result.txt index 57761d14..8e659740 100644 --- a/src/common/example/dtoffrw_alphashapedoc_result.txt +++ b/src/common/example/dtoffrw_alphashapedoc_result.txt @@ -1,3 +1,2 @@ Number of vertices= 7 Number of finite full cells= 6 - diff --git a/src/common/include/gudhi/Delaunay_triangulation_off_io.h b/src/common/include/gudhi/Delaunay_triangulation_off_io.h index 6335d243..b3f4a299 100644 --- a/src/common/include/gudhi/Delaunay_triangulation_off_io.h +++ b/src/common/include/gudhi/Delaunay_triangulation_off_io.h @@ -135,7 +135,7 @@ class Delaunay_triangulation_off_visitor_reader { * * When launching: * - * \code $> ./dtoffrw ../../data/points/alphashapedoc.off triangulated.off + * \code $> ./dtoffrw ../../data/points/alphacomplexdoc triangulated.off * \endcode * * the program output is: diff --git a/src/common/test/dtoffrw_unit_test.cpp b/src/common/test/dtoffrw_unit_test.cpp index 20094229..f682df1a 100644 --- a/src/common/test/dtoffrw_unit_test.cpp +++ b/src/common/test/dtoffrw_unit_test.cpp @@ -64,7 +64,7 @@ BOOST_AUTO_TEST_CASE( Delaunay_triangulation_doc_test ) BOOST_AUTO_TEST_CASE( Delaunay_triangulation_unexisting_file_read_test ) { - Gudhi::Delaunay_triangulation_off_reader off_reader("pouetpouet_tralala.off"); + Gudhi::Delaunay_triangulation_off_reader off_reader("some_impossible_weird_file_name.off"); // Check the read operation was correct BOOST_CHECK(!off_reader.is_valid()); T* triangulation = off_reader.get_complex(); @@ -80,7 +80,7 @@ BOOST_AUTO_TEST_CASE( Delaunay_triangulation_unexisting_file_write_test ) T* triangulation = off_reader.get_complex(); // Write the OFF file (output file name given as parameter) with the points and triangulated cells as faces - Gudhi::Delaunay_triangulation_off_writer off_writer("/pouetpouet_tralala/pouetpouet_tralala/pouetpouet_tralala.off", triangulation); + Gudhi::Delaunay_triangulation_off_writer off_writer("/some_impossible_weird_directory_name/another_weird_directory_name/some_impossible_weird_file_name.off", triangulation); // Check the write operation was correct BOOST_CHECK(!off_writer.is_valid()); -- cgit v1.2.3 From 11b195d4e26d48cdc56883957cbad16e298e43ca Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 12 Jan 2016 16:07:10 +0000 Subject: Fix alpha complex remarks and bugs git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@957 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: fa837fd1a4373c2322db16353d98767907f34c79 --- CMakeLists.txt | 4 +- biblio/how_to_cite_cgal.bib | 947 +++++++++++++++++++++ src/Alpha_complex/test/CMakeLists.txt | 2 - src/GudhUI/alpha_complex_persistence.cpp | 78 -- src/GudhUI/utils/Bar_code_persistence.h | 3 +- src/GudhUI/utils/Persistence_compute.h | 15 +- src/Persistent_cohomology/example/CMakeLists.txt | 100 ++- .../example/alpha_complex_persistence.cpp | 92 +- .../example/rips_persistence.cpp | 3 +- src/Simplex_tree/include/gudhi/Simplex_tree.h | 81 +- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 56 +- src/common/include/gudhi/distance_functions.h | 4 +- src/common/include/gudhi/reader_utils.h | 4 +- 13 files changed, 1140 insertions(+), 249 deletions(-) create mode 100644 biblio/how_to_cite_cgal.bib delete mode 100644 src/GudhUI/alpha_complex_persistence.cpp (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/CMakeLists.txt b/CMakeLists.txt index d0770dd7..54e86f72 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -10,7 +10,7 @@ endif() enable_testing() -set(CMAKE_PREFIX_PATH "${CMAKE_SOURCE_DIR}/src/cmake/modules/") +set(CMAKE_MODULE_PATH "${CMAKE_SOURCE_DIR}/src/cmake/modules/") message("CMAKE_MODULE_PATH = ${CMAKE_MODULE_PATH}") # Generate GUDHI official version file @@ -22,7 +22,7 @@ if(MSVC) # Turn off some VC++ warnings SET (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4267 /wd4668 /wd4311 /wd4800 /wd4820 /wd4503 /wd4244 /wd4345 /wd4996 /wd4396 /wd4018") else() - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -fsanitize=memory -fno-omit-frame-pointer -Wall -Wpedantic -Wsign-compare") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -Wall -Wpedantic -Wsign-compare") set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -O1") set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE}") endif() diff --git a/biblio/how_to_cite_cgal.bib b/biblio/how_to_cite_cgal.bib new file mode 100644 index 00000000..7336ee81 --- /dev/null +++ b/biblio/how_to_cite_cgal.bib @@ -0,0 +1,947 @@ +@book{ cgal:eb-15b +, title = "{CGAL} User and Reference Manual" +, author = "{The CGAL Project}" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, year = 2015 +, url = "http://doc.cgal.org/4.7/Manual/packages.html" +} +@incollection{cgal:h-af-15b +, author = "Michael Hemmer" +, title = "Algebraic Foundations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgAlgebraicFoundationsSummary" +, year = 2015 +} + +@incollection{cgal:hhkps-nt-15b +, author = "Michael Hemmer and Susan Hert and Sylvain Pion and Stefan Schirra" +, title = "Number Types" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgNumberTypesSummary" +, year = 2015 +} + +@incollection{cgal:h-ma-15b +, author = "Michael Hemmer and Sylvain Pion" +, title = "Modular Arithmetic" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgModularArithmeticSummary" +, year = 2015 +} + +@incollection{cgal:h-p-15b +, author = "Michael Hemmer" +, title = "Polynomial" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPolynomialSummary" +, year = 2015 +} + +@incollection{cgal:bht-ak-15b +, author = "Eric Berberich and Michael Hemmer and Michael Kerber and Sylvain Lazard and Luis Pe{\~n}aranda and Monique Teillaud" +, title = "Algebraic Kernel" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgAlgebraicKerneldSummary" +, year = 2015 +} + +@incollection{cgal:h-msms-15b +, author = "Michael Hoffmann" +, title = "Monotone and Sorted Matrix Search" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgMatrixSearchSummary" +, year = 2015 +} + +@incollection{cgal:fgsw-lqps-15b +, author = "Kaspar Fischer and Bernd G{\"a}rtner and Sven Sch{\"o}nherr and Frans Wessendorp" +, title = "Linear and Quadratic Programming Solver" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgQPSolverSummary" +, year = 2015 +} + +@incollection{cgal:bfghhkps-lgk23-15b +, author = "Herv{\'e} Br{\"o}nnimann and Andreas Fabri and Geert-Jan Giezeman and Susan Hert and Michael Hoffmann and Lutz Kettner and Sylvain Pion and Stefan Schirra" +, title = "{2D} and {3D} Linear Geometry Kernel" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgKernel23Summary" +, year = 2015 +} + +@incollection{cgal:s-gkd-15b +, author = "Michael Seel" +, title = "{dD} Geometry Kernel" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgKernelDSummary" +, year = 2015 +} + +@incollection{cgal:cpt-cgk2-15b +, author = "Pedro Machado Manh{\~a}es de Castro and Sylvain Pion and Monique Teillaud" +, title = "{2D} Circular Geometry Kernel" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgCircularKernel2Summary" +, year = 2015 +} + +@incollection{cgal:cclt-sgk3-15b +, author = "Pedro Machado Manh{\~a}es de Castro and Fr{\'e}d{\'e}ric Cazals and S{\'e}bastien Loriot and Monique Teillaud" +, title = "{3D} Spherical Geometry Kernel" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSphericalKernel3Summary" +, year = 2015 +} + +@incollection{cgal:hs-chep2-15b +, author = "Susan Hert and Stefan Schirra" +, title = "{2D} Convex Hulls and Extreme Points" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgConvexHull2Summary" +, year = 2015 +} + +@incollection{cgal:hs-ch3-15b +, author = "Susan Hert and Stefan Schirra" +, title = "{3D} Convex Hulls" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgConvexHull3Summary" +, year = 2015 +} + +@incollection{cgal:hs-chdt3-15b +, author = "Susan Hert and Michael Seel" +, title = "{dD} Convex Hulls and Delaunay Triangulations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgConvexHullDSummary" +, year = 2015 +} + +@incollection{cgal:gw-p2-15b +, author = "Geert-Jan Giezeman and Wieger Wesselink" +, title = "{2D} Polygons" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPolygon2Summary" +, year = 2015 +} + +@incollection{cgal:fwzh-rbso2-15b +, author = "Efi Fogel and Ophir Setter and Ron Wein and Guy Zucker and Baruch Zukerman and Dan Halperin" +, title = "{2D} Regularized Boolean Set-Operations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgBooleanSetOperations2Summary" +, year = 2015 +} + +@incollection{cgal:s-bonp2-15b +, author = "Michael Seel" +, title = "{2D} Boolean Operations on Nef Polygons" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgNef2Summary" +, year = 2015 +} + +@incollection{cgal:hk-bonpes2-15b +, author = "Peter Hachenberger and Lutz Kettner" +, title = "{2D} Boolean Operations on Nef Polygons Embedded on the Sphere" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgNefS2Summary" +, year = 2015 +} + +@incollection{cgal:h-pp2-15b +, author = "Susan Hert" +, title = "{2D} Polygon Partitioning" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPolygonPartitioning2Summary" +, year = 2015 +} + +@incollection{cgal:c-sspo2-15b +, author = "Fernando Cacciola" +, title = "{2D} Straight Skeleton and Polygon Offsetting" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgStraightSkeleton2Summary" +, year = 2015 +} + +@incollection{cgal:w-rms2-15b +, author = "Ron Wein and Alon Baram and Eyal Flato and Efi Fogel and Michael Hemmer and Sebastian Morr" +, title = "{2D} Minkowski Sums" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgMinkowskiSum2Summary" +, year = 2015 +} + +@incollection{cgal:f-ps2-15b +, author = "Andreas Fabri" +, title = "{2D} Polyline Simplification" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPolylineSimplification2Summary" +, year = 2015 +} + +@incollection{hhb-visibility-2-15b +, author = "Michael Hemmer and Kan Huang and Francisc Bungiu and Ning Xu" +, title = "{2D} Visibility Computation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgVisibility_2Summary" +, year = 2015 +} + +@incollection{cgal:k-ps-15b +, author = "Lutz Kettner" +, title = "{3D} Polyhedral Surface" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPolyhedronSummary" +, year = 2015 +} + +@incollection{cgal:k-hds-15b +, author = "Lutz Kettner" +, title = "Halfedge Data Structures" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgHDSSummary" +, year = 2015 +} + +@incollection{cgal:bsmf-sm-15b +, author = "Mario Botsch and Daniel Sieger and Philipp Moeller and Andreas Fabri" +, title = "Surface Mesh" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceMeshSummary" +, year = 2015 +} + +@incollection{cgal:d-cm-15b +, author = "Guillaume Damiand" +, title = "Combinatorial Maps" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgCombinatorialMapsSummary" +, year = 2015 +} + +@incollection{cgal:d-lcc-12-15b +, author = "Guillaume Damiand" +, title = "Linear Cell Complex" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgLinearCellComplexSummary" +, year = 2015 +} + +@incollection{cgal:hk-bonp3-15b +, author = "Peter Hachenberger and Lutz Kettner" +, title = "{3D} Boolean Operations on Nef Polyhedra" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgNef3Summary" +, year = 2015 +} + +@incollection{cgal:h-emspe-15b +, author = "Peter Hachenberger" +, title = "Convex Decomposition of Polyhedra" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgConvexDecomposition3Summary" +, year = 2015 +} + +@incollection{cgal:h-msp3-15b +, author = "Peter Hachenberger" +, title = "{3D} Minkowski Sum of Polyhedra" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgMinkowskiSum3Summary" +, year = 2015 +} + +@incollection{cgal:wfzh-a2-15b +, author = "Ron Wein and Eric Berberich and Efi Fogel and Dan Halperin and Michael Hemmer and Oren Salzman and Baruch Zukerman" +, title = "{2D} Arrangements" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgArrangement2Summary" +, year = 2015 +} + +@incollection{cgal:wfz-ic2-15b +, author = "Baruch Zukerman and Ron Wein and Efi Fogel" +, title = "{2D} Intersection of Curves" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgIntersectionOfCurves2Summary" +, year = 2015 +} + +@incollection{cgal:p-sr2-15b +, author = "Eli Packer" +, title = "{2D} Snap Rounding" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSnapRounding2Summary" +, year = 2015 +} + +@incollection{cgal:w-e2-15b +, author = "Ron Wein" +, title = "{2D} Envelopes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgEnvelope2Summary" +, year = 2015 +} + +@incollection{cgal:mwz-e3-15b +, author = "Dan Halperin and Michal Meyerovitch and Ron Wein and Baruch Zukerman" +, title = "{3D} Envelopes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgEnvelope3Summary" +, year = 2015 +} + +@incollection{cgal:y-t2-15b +, author = "Mariette Yvinec" +, title = "{2D} Triangulation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgTriangulation2Summary" +, year = 2015 +} + +@incollection{cgal:py-tds2-15b +, author = "Sylvain Pion and Mariette Yvinec" +, title = "{2D} Triangulation Data Structure" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgTDS2Summary" +, year = 2015 +} + +@incollection{cgal:k-pt2-13-15b +, author = "Nico Kruithof" +, title = "{2D} Periodic Triangulations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPeriodic2Triangulation2Summary" +, year = 2015 +} + +@incollection{cgal:pt-t3-15b +, author = "Cl{\'e}ment Jamin and Sylvain Pion and Monique Teillaud" +, title = "{3D} Triangulations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgTriangulation3Summary" +, year = 2015 +} + +@incollection{cgal:pt-tds3-15b +, author = "Cl{\'e}ment Jamin and Sylvain Pion and Monique Teillaud" +, title = "{3D} Triangulation Data Structure" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgTDS3Summary" +, year = 2015 +} + +@incollection{cgal:ct-pt3-15b +, author = "Manuel Caroli and Monique Teillaud" +, title = "{3D} Periodic Triangulations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPeriodic3Triangulation3Summary" +, year = 2015 +} + +@incollection{cgal:hdj-t-15b +, author = "Samuel Hornus and Olivier Devillers and Cl{\'e}ment Jamin" +, title = "{dD} Triangulations" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgTriangulationsSummary" +, year = 2015 +} + +@incollection{cgal:d-as2-15b +, author = "Tran Kai Frank Da" +, title = "{2D} Alpha Shapes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgAlphaShape2Summary" +, year = 2015 +} + +@incollection{cgal:dy-as3-15b +, author = "Tran Kai Frank Da and S{\'e}bastien Loriot and Mariette Yvinec" +, title = "{3D} Alpha Shapes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgAlphaShapes3Summary" +, year = 2015 +} + +@incollection{cgal:k-sdg2-15b +, author = "Menelaos Karavelas" +, title = "{2D} Segment Delaunay Graphs" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSegmentDelaunayGraph2Summary" +, year = 2015 +} + +@incollection{cgal:cdp-sdglinf2-15b +, author = "Panagiotis Cheilaris and Sandeep Kumar Dey and Evanthia Papadopoulou" +, title = "L Infinity Segment Delaunay Graphs" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSDGLinfSummary" +, year = 2015 +} + +@incollection{cgal:ky-ag2-15b +, author = "Menelaos Karavelas and Mariette Yvinec" +, title = "{2D} Apollonius Graphs (Delaunay Graphs of Disks)" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgApolloniusGraph2Summary" +, year = 2015 +} + +@incollection{cgal:k-vda2-15b +, author = "Menelaos Karavelas" +, title = "{2D} Voronoi Diagram Adaptor" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgVoronoiDiagramAdaptor2Summary" +, year = 2015 +} + +@incollection{cgal:r-ctm2-15b +, author = "Laurent Rineau" +, title = "{2D} Conforming Triangulations and Meshes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgMesh2Summary" +, year = 2015 +} + +@incollection{cgal:ry-smg-15b +, author = "Laurent Rineau and Mariette Yvinec" +, title = "{3D} Surface Mesh Generation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceMesher3Summary" +, year = 2015 +} + +@incollection{cgal:asg-srps-15b +, author = "Pierre Alliez and Laurent Saboret and Ga{\"e}l Guennebaud" +, title = "Surface Reconstruction from Point Sets" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceReconstructionFromPointSetsSummary" +, year = 2015 +} + +@incollection{cgal:ssr3-15b +, author = "Thijs van Lankveld" +, title = "Scale-Space Surface Reconstruction" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgScaleSpaceReconstruction3Summary" +, year = 2015 +} + +@incollection{cgal:dc-afsr-15b +, author = "Tran Kai Frank Da and David Cohen-Steiner" +, title = "Advancing Front Surface Reconstruction" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgAdvancingFrontSurfaceReconstructionSummary" +, year = 2015 +} + +@incollection{cgal:k-ssm3-15b +, author = "Nico Kruithof" +, title = "{3D} Skin Surface Meshing" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSkinSurface3Summary" +, year = 2015 +} + +@incollection{cgal:rty-m3-15b +, author = "Pierre Alliez and Cl{\'e}ment Jamin and Laurent Rineau and St{\'e}phane Tayeb and Jane Tournois and Mariette Yvinec" +, title = "{3D} Mesh Generation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgMesh_3Summary" +, year = 2015 +} + +@incollection{cgal:lty-pmp-15b +, author = "S{\'e}bastien Loriot and Jane Tournois and Ilker O. Yaz" +, title = "Polygon Mesh Processing" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPolygonMeshProcessingSummary" +, year = 2015 +} + +@incollection{cgal:s-ssm2-15b +, author = "Le-Jeng Andy Shiue" +, title = "{3D} Surface Subdivision Methods" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceSubdivisionMethods3Summary" +, year = 2015 +} + +@incollection{cgal:y-smsimpl-15b +, author = "Ilker O. Yaz and S{\'e}bastien Loriot" +, title = "Triangulated Surface Mesh Segmentation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceSegmentationSummary" +, year = 2015 +} + +@incollection{cgal:c-tsms-12-15b +, author = "Fernando Cacciola" +, title = "Triangulated Surface Mesh Simplification" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceMeshSimplificationSummary" +, year = 2015 +} + +@incollection{cgal:lsxy-tsmd-15b +, author = "S{\'e}bastien Loriot and Olga Sorkine-Hornung and Yin Xu and Ilker O. Yaz" +, title = "Triangulated Surface Mesh Deformation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceModelingSummary" +, year = 2015 +} + +@incollection{cgal:sal-pptsm2-15b +, author = "Laurent Saboret and Pierre Alliez and Bruno L{\'e}vy" +, title = "Planar Parameterization of Triangulated Surface Meshes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceParameterizationSummary" +, year = 2015 +} + +@incollection{cgal:klcdv-tsmsp-15b +, author = "Stephen Kiazyk and S{\'e}bastien Loriot and {\'E}ric Colin de Verdi{\`e}re" +, title = "Triangulated Surface Mesh Shortest Paths" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSurfaceMeshShortestPathSummary" +, year = 2015 +} + +@incollection{cgal:glt-tsms-15b +, author = "Xiang Gao and S{\'e}bastien Loriot and Andrea Tagliasacchi" +, title = "Triangulated Surface Mesh Skeletonization" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgMeanCurvatureSkeleton3Summary" +, year = 2015 +} + +@incollection{cgal:cp-arutsm-15b +, author = "Marc Pouget and Fr{\'e}d{\'e}ric Cazals" +, title = "Approximation of Ridges and Umbilics on Triangulated Surface Meshes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgRidges_3Summary" +, year = 2015 +} + +@incollection{cgal:pc-eldp-15b +, author = "Marc Pouget and Fr{\'e}d{\'e}ric Cazals" +, title = "Estimation of Local Differential Properties of Point-Sampled Surfaces" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgJet_fitting_3Summary" +, year = 2015 +} + +@incollection{cgal:ass-psp-15b +, author = "Pierre Alliez and Cl{\'e}ment Jamin and Quentin M{\'e}rigot and Jocelyn Meyron and Laurent Saboret and Nader Salman and Shihao Wu" +, title = "Point Set Processing" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPointSetProcessingSummary" +, year = 2015 +} + +@incollection{cgal:ovja-pssd-15b +, author = "Sven Oesau and Yannick Verdie and Cl{\'e}ment Jamin and Pierre Alliez" +, title = "Point Set Shape Detection" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPointSetShapeDetection3Summary" +, year = 2015 +} + +@incollection{cgal:m-ps-15b +, author = "Abdelkrim Mebarki" +, title = "{2D} Placement of Streamlines" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPlacementOfStreamlines2Summary" +, year = 2015 +} + +@incollection{cgal:b-ss2-15b +, author = "Matthias B{\"a}sken" +, title = "{2D} Range and Neighbor Search" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPointSet2Summary" +, year = 2015 +} + +@incollection{cgal:f-isl-15b +, author = "Andreas Fabri" +, title = "Interval Skip List" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgIntervalSkipListSummary" +, year = 2015 +} + +@incollection{cgal:tf-ssd-15b +, author = "Hans Tangelder and Andreas Fabri" +, title = "{dD} Spatial Searching" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSpatialSearchingDSummary" +, year = 2015 +} + +@incollection{cgal:n-rstd-15b +, author = "Gabriele Neyer" +, title = "{dD} Range and Segment Trees" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgRangeSegmentTreesDSummary" +, year = 2015 +} + +@incollection{cgal:kmz-isiobd-15b +, author = "Lutz Kettner and Andreas Meyer and Afra Zomorodian" +, title = "Intersecting Sequences of {dD} Iso-oriented Boxes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgBoxIntersectionDSummary" +, year = 2015 +} + +@incollection{cgal:atw-aabb-15b +, author = "Pierre Alliez and St{\'e}phane Tayeb and Camille Wormser" +, title = "{3D} Fast Intersection and Distance Computation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgAABB_treeSummary" +, year = 2015 +} + +@incollection{cgal:dd-ss-15b +, author = "Christophe Delage and Olivier Devillers" +, title = "Spatial Sorting" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgSpatialSortingSummary" +, year = 2015 +} + +@incollection{cgal:fghhs-bv-15b +, author = "Kaspar Fischer and Bernd G{\"a}rtner and Thomas Herrmann and Michael Hoffmann and Sven Sch{\"o}nherr" +, title = "Bounding Volumes" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgBoundingVolumesSummary" +, year = 2015 +} + +@incollection{cgal:hp-ia-15b +, author = "Michael Hoffmann and Eli Packer" +, title = "Inscribed Areas" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgInscribedAreasSummary" +, year = 2015 +} + +@incollection{cgal:fghhs-od-15b +, author = "Kaspar Fischer and Bernd G{\"a}rtner and Thomas Herrmann and Michael Hoffmann and Sven Sch{\"o}nherr" +, title = "Optimal Distances" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgOptimalDistancesSummary" +, year = 2015 +} + +@incollection{cgal:ap-pcad-15b +, author = "Pierre Alliez and Sylvain Pion and Ankit Gupta" +, title = "Principal Component Analysis" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgPrincipalComponentAnalysisDSummary" +, year = 2015 +} + +@incollection{cgal:f-i-15b +, author = "Julia Fl{\"o}totto" +, title = "{2D} and Surface Function Interpolation" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgInterpolation2Summary" +, year = 2015 +} + +@incollection{cgal:abha-gbc-15b +, author = "Dmitry Anisimov and David Bommes and Kai Hormann and Pierre Alliez" +, title = "{2D} Generalized Barycentric Coordinates" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgBarycentric_coordinates_2Summary" +, year = 2015 +} + +@incollection{cgal:r-kds-15b +, author = "Daniel Russel" +, title = "Kinetic Data Structures" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgKdsSummary" +, year = 2015 +} + +@incollection{cgal:r-kdsf-15b +, author = "Daniel Russel" +, title = "Kinetic Framework" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgKdsFrameworkSummary" +, year = 2015 +} + +@incollection{cgal:hkpw-se-15b +, author = "Michael Hoffmann and Lutz Kettner and Sylvain Pion and Ron Wein" +, title = "STL Extensions for {CGAL}" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgStlExtensionSummary" +, year = 2015 +} + +@incollection{cgal:cfw-cbgl-15b +, author = "Andreas Fabri and Fernando Cacciola and Philipp Moeller and Ron Wein" +, title = "{CGAL} and the {Boost} Graph Library" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgBGLSummary" +, year = 2015 +} + +@incollection{cgal:fs-cbpm-15b +, author = "Andreas Fabri and Laurent Saboret" +, title = "{CGAL} and {Boost} Property Maps" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgProperty_mapSummary" +, year = 2015 +} + +@incollection{cgal:dksy-hc-15b +, author = "Olivier Devillers and Lutz Kettner and Sylvain Pion and Michael Seel and Mariette Yvinec" +, title = "Handles and Circulators" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgHandlesAndCirculatorsSummary" +, year = 2015 +} + +@incollection{cgal:dhhk-gog-15b +, author = "Pedro M. M. de Castro and Olivier Devillers and Susan Hert and Michael Hoffmann and Lutz Kettner and Sven Sch{\"o}nherr and Alexandru Tifrea" +, title = "Geometric Object Generators" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgGeneratorsSummary" +, year = 2015 +} + +@incollection{cgal:kps-pthum-15b +, author = "Lutz Kettner and Sylvain Pion and Michael Seel" +, title = "Profiling tools, Hash Map, Union-find, Modifiers" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgProfilingToolsSummary" +, year = 2015 +} + +@incollection{cgal:fgk-ios-12-15b +, author = "Andreas Fabri and Geert-Jan Giezeman and Lutz Kettner" +, title = "IO Streams" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgIOstreamsSummary" +, year = 2015 +} + +@incollection{cgal:fp-gv-15b +, author = "Andreas Fabri and Sylvain Pion" +, title = "Geomview" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgGeomviewSummary" +, year = 2015 +} + +@incollection{cgal:fr-cqgvf-15b +, author = "Andreas Fabri and Laurent Rineau" +, title = "{CGAL} and the {Qt} Graphics View Framework" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgGraphicsViewSummary" +, year = 2015 +} + +@incollection{cgal:lp-gi-15b +, author = "Olivier Devillers and S{\'e}bastien Loriot and Sylvain Pion" +, title = "{CGAL} Ipelets" +, publisher = "{CGAL Editorial Board}" +, edition = "{4.7}" +, booktitle = "{CGAL} User and Reference Manual" +, url = "http://doc.cgal.org/4.7/Manual/packages.html#PkgCGALIpeletsSummary" +, year = 2015 +} diff --git a/src/Alpha_complex/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index d7c13da0..fa24e1b1 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -18,8 +18,6 @@ if(CGAL_FOUND) add_executable ( AlphaComplexUT Alpha_complex_unit_test.cpp ) target_link_libraries(AlphaComplexUT ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) - add_executable ( cerr cerr.cpp ) - # 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}/) diff --git a/src/GudhUI/alpha_complex_persistence.cpp b/src/GudhUI/alpha_complex_persistence.cpp deleted file mode 100644 index 4f85459a..00000000 --- a/src/GudhUI/alpha_complex_persistence.cpp +++ /dev/null @@ -1,78 +0,0 @@ -#include -#include - - -#include - -// to construct a Delaunay_triangulation from a OFF file -#include -#include -#include - -#include "utils/Bar_code_persistence.h" - -void usage(char * const progName) { - std::cerr << "Usage: " << progName << " filename.off " << // alpha_square_max_value[double] " << - "coeff_field_characteristic[integer > 0] min_persistence[double >= -1.0]" << std::endl; - std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0 2 0.02" << std::endl; - exit(-1); // ----- >> -} - -int main(int argc, char **argv) { - if (argc != 4) { - std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; - usage(argv[0]); - } - - QApplication qtapp(argc, argv); - - std::string off_file_name(argv[1]); - // double alpha_square_max_value = atof(argv[2]); - double alpha_square_max_value = 1e20; - int coeff_field_characteristic = atoi(argv[2]); // argv[3] - double min_persistence = atof(argv[3]); // argv[4] - - // ---------------------------------------------------------------------------- - // Init of an alpha complex from an OFF file - // ---------------------------------------------------------------------------- - typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name, alpha_square_max_value); - - // ---------------------------------------------------------------------------- - // Display information about the alpha complex - // ---------------------------------------------------------------------------- - std::cout << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << - " - " << alpha_complex_from_file.num_simplices() << " simplices - " << - alpha_complex_from_file.num_vertices() << " vertices." << std::endl; - - // Sort the simplices in the order of the filtration - alpha_complex_from_file.initialize_filtration(); - - std::cout << "Simplex_tree dim: " << alpha_complex_from_file.dimension() << std::endl; - // Compute the persistence diagram of the complex - Gudhi::persistent_cohomology::Persistent_cohomology< Gudhi::alphacomplex::Alpha_complex, - Gudhi::persistent_cohomology::Field_Zp > pcoh(alpha_complex_from_file); - - std::cout << "coeff_field_characteristic " << coeff_field_characteristic << - " - min_persistence " << min_persistence << std::endl; - - // initializes the coefficient field for homology - pcoh.init_coefficients(coeff_field_characteristic); - - pcoh.compute_persistent_cohomology(min_persistence); - - pcoh.output_diagram(); - - std::vector> persistence_vector; - pcoh.get_persistence(persistence_vector); - - Bar_code_persistence bc_persistence; - - for (auto persistence : persistence_vector) { - bc_persistence.insert(persistence.first, persistence.second); - } - - bc_persistence.show(); - - return qtapp.exec(); -} diff --git a/src/GudhUI/utils/Bar_code_persistence.h b/src/GudhUI/utils/Bar_code_persistence.h index a1a46ea8..a4cd8156 100644 --- a/src/GudhUI/utils/Bar_code_persistence.h +++ b/src/GudhUI/utils/Bar_code_persistence.h @@ -39,7 +39,7 @@ class Bar_code_persistence { max_death = death; } - void show() { + void show(const std::string& window_title) { // Create a view, put a scene in it QGraphicsView * view = new QGraphicsView(); QGraphicsScene * scene = new QGraphicsScene(); @@ -78,6 +78,7 @@ class Bar_code_persistence { QGraphicsTextItem* dimText = scene->addText(scale_value, QFont("Helvetica", 8)); dimText->setPos(scale - (3.0 * scale_value.size()), height + 9.0 * (modulo % 2)); } + view->setWindowTitle(window_title.c_str()); // Show the view view->show(); } diff --git a/src/GudhUI/utils/Persistence_compute.h b/src/GudhUI/utils/Persistence_compute.h index 0b9961d3..1f04cc6b 100644 --- a/src/GudhUI/utils/Persistence_compute.h +++ b/src/GudhUI/utils/Persistence_compute.h @@ -46,10 +46,6 @@ struct Persistence_params { * Show persistence into output stream */ template class Persistence_compute { - private: - SkBlComplex& complex_; - std::ostream& stream_; - public: typedef typename SkBlComplex::Vertex_handle Vertex_handle; typedef typename SkBlComplex::Edge_handle Edge_handle; @@ -61,9 +57,7 @@ template class Persistence_compute { * double threshold * int p for coefficient Z_p */ - Persistence_compute(SkBlComplex& complex, std::ostream& stream, const Persistence_params& params) : - // double threshold = 0.5,unsigned dim_max = 8): - complex_(complex), stream_(stream) { + Persistence_compute(SkBlComplex& complex, std::ostream& stream, const Persistence_params& params) { // for now everything is copied, todo boost adapt iterators to points of SkBlComplex instead of copying to an // initial vector typedef std::vector Point_t; @@ -87,10 +81,11 @@ template class Persistence_compute { pcoh.init_coefficients(params.p); // put params.min_pers pcoh.compute_persistent_cohomology(params.min_pers); - stream_ << "persistence: \n"; - stream_ << "p dimension birth death: \n"; + stream << "persistence: \n"; + stream << "p dimension birth death: \n"; - pcoh.output_diagram(stream_); + pcoh.output_diagram(stream); + } }; diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt index eb4ee3e3..9e96adc0 100644 --- a/src/Persistent_cohomology/example/CMakeLists.txt +++ b/src/Persistent_cohomology/example/CMakeLists.txt @@ -22,63 +22,61 @@ add_executable(persistence_from_file persistence_from_file.cpp) target_link_libraries(persistence_from_file ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) add_test(persistence_from_file_3_2_0 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 2 -m 0) add_test(persistence_from_file_3_3_100 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 3 -m 100) - -if(GMPXX_FOUND AND GMP_FOUND) - message("GMPXX_LIBRARIES = ${GMPXX_LIBRARIES}") - message("GMP_LIBRARIES = ${GMP_LIBRARIES}") - - add_executable(rips_multifield_persistence rips_multifield_persistence.cpp ) - target_link_libraries(rips_multifield_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) - add_test(rips_multifield_persistence_2_71 ${CMAKE_CURRENT_BINARY_DIR}/rips_multifield_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.25 -d 3 -p 2 -q 71 -m 100) - - add_executable ( performance_rips_persistence performance_rips_persistence.cpp ) - target_link_libraries(performance_rips_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) - - if(CGAL_FOUND) - add_executable(alpha_shapes_persistence alpha_shapes_persistence.cpp) - target_link_libraries(alpha_shapes_persistence ${Boost_SYSTEM_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES} ${CGAL_LIBRARY}) - add_test(alpha_shapes_persistence_2_0_5 ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_persistence ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 2 0.5) - #add_test(alpha_shapes_persistence_3_3_100 ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_persistence ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 3 -m 100) - - - - if (NOT CGAL_VERSION VERSION_LESS 4.7.0) - message(STATUS "CGAL version: ${CGAL_VERSION}.") - - include( ${CGAL_USE_FILE} ) - # In CMakeLists.txt, when include(${CGAL_USE_FILE}), CXX_FLAGS are overwritten. - # cf. http://doc.cgal.org/latest/Manual/installation.html#title40 - # A workaround is to add "-std=c++11" again. - # A fix would be to use https://cmake.org/cmake/help/v3.1/prop_gbl/CMAKE_CXX_KNOWN_FEATURES.html - # or even better https://cmake.org/cmake/help/v3.1/variable/CMAKE_CXX_STANDARD.html - # but it implies to use cmake version 3.1 at least. - if(NOT MSVC) - include(CheckCXXCompilerFlag) - CHECK_CXX_COMPILER_FLAG(-std=c++11 COMPILER_SUPPORTS_CXX11) - if(COMPILER_SUPPORTS_CXX11) - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") +if(GMPXX_FOUND AND GMP_FOUND) + message("GMPXX_LIBRARIES = ${GMPXX_LIBRARIES}") + message("GMP_LIBRARIES = ${GMP_LIBRARIES}") + + add_executable(rips_multifield_persistence rips_multifield_persistence.cpp ) + target_link_libraries(rips_multifield_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) + add_test(rips_multifield_persistence_2_71 ${CMAKE_CURRENT_BINARY_DIR}/rips_multifield_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.25 -d 3 -p 2 -q 71 -m 100) + + add_executable ( performance_rips_persistence performance_rips_persistence.cpp ) + target_link_libraries(performance_rips_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) + + if(CGAL_FOUND) + add_executable(alpha_shapes_persistence alpha_shapes_persistence.cpp) + target_link_libraries(alpha_shapes_persistence ${Boost_SYSTEM_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES} ${CGAL_LIBRARY}) + add_test(alpha_shapes_persistence_2_0_5 ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_persistence ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 2 0.5) + #add_test(alpha_shapes_persistence_3_3_100 ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_persistence ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 3 -m 100) + + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + # In CMakeLists.txt, when include(${CGAL_USE_FILE}), CXX_FLAGS are overwritten. + # cf. http://doc.cgal.org/latest/Manual/installation.html#title40 + # A workaround is to add "-std=c++11" again. + # A fix would be to use https://cmake.org/cmake/help/v3.1/prop_gbl/CMAKE_CXX_KNOWN_FEATURES.html + # or even better https://cmake.org/cmake/help/v3.1/variable/CMAKE_CXX_STANDARD.html + # but it implies to use cmake version 3.1 at least. + if(NOT MSVC) + include(CheckCXXCompilerFlag) + CHECK_CXX_COMPILER_FLAG(-std=c++11 COMPILER_SUPPORTS_CXX11) + if(COMPILER_SUPPORTS_CXX11) + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") + endif() endif() - endif() - # - End of workaround + # - End of workaround - find_package(Eigen3 3.1.0) - if (EIGEN3_FOUND) - message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") - include( ${EIGEN3_USE_FILE} ) + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) - add_executable (alphacomplexpersistence alpha_complex_persistence.cpp) - target_link_libraries(alphacomplexpersistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + add_executable (alpha_complex_persistence alpha_complex_persistence.cpp) + target_link_libraries(alpha_complex_persistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + endif() else() - message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") - endif() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") + endif () else() - message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") - endif () - - - - endif() + # message(WARNING "CGAL not found.") + endif() +else() + # message(WARNING "GMP not found.") endif() diff --git a/src/Persistent_cohomology/example/alpha_complex_persistence.cpp b/src/Persistent_cohomology/example/alpha_complex_persistence.cpp index fbadf673..0dabdeac 100644 --- a/src/Persistent_cohomology/example/alpha_complex_persistence.cpp +++ b/src/Persistent_cohomology/example/alpha_complex_persistence.cpp @@ -1,34 +1,35 @@ #include #include +#include + // to construct a Delaunay_triangulation from a OFF file #include #include #include -void usage(char * const progName) { - std::cerr << "Usage: " << progName << " filename.off alpha_square_max_value[double] " << - "coeff_field_characteristic[integer > 0] min_persistence[double >= -1.0]" << std::endl; - std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0 2 0.02" << std::endl; - exit(-1); // ----- >> -} +void program_options(int argc, char * argv[] + , std::string & off_file_points + , std::string & output_file_diag + , Filtration_value & alpha_square_max_value + , int & coeff_field_characteristic + , Filtration_value & min_persistence); int main(int argc, char **argv) { - if (argc != 5) { - std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; - usage(argv[0]); - } + std::string off_file_points; + std::string output_file_diag; + Filtration_value alpha_square_max_value; + int coeff_field_characteristic; + Filtration_value min_persistence; + + program_options(argc, argv, off_file_points, output_file_diag, alpha_square_max_value, coeff_field_characteristic, min_persistence); - std::string off_file_name(argv[1]); - double alpha_square_max_value = atof(argv[2]); - int coeff_field_characteristic = atoi(argv[3]); - double min_persistence = atof(argv[4]); // ---------------------------------------------------------------------------- // Init of an alpha complex from an OFF file // ---------------------------------------------------------------------------- typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_name, alpha_square_max_value); + Gudhi::alphacomplex::Alpha_complex alpha_complex_from_file(off_file_points, alpha_square_max_value); // ---------------------------------------------------------------------------- // Display information about the alpha complex @@ -49,7 +50,66 @@ int main(int argc, char **argv) { pcoh.compute_persistent_cohomology(min_persistence); - pcoh.output_diagram(); + // Output the diagram in filediag + if (output_file_diag.empty()) { + pcoh.output_diagram(); + } else { + std::cout << "Result in file: " << output_file_diag << std::endl; + std::ofstream out(output_file_diag); + pcoh.output_diagram(out); + out.close(); + } return 0; } + +void program_options(int argc, char * argv[] + , std::string & off_file_points + , std::string & output_file_diag + , Filtration_value & alpha_square_max_value + , int & coeff_field_characteristic + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value(&off_file_points), + "Name of file containing a point set. Format is one point per line: X1 ... Xd "); + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("output-file,o", po::value(&output_file_diag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-alpha-square-value,r", po::value(&alpha_square_max_value)->default_value(std::numeric_limits::infinity()), + "Maximal alpha square value for the Alpha complex construction.") + ("field-charac,p", po::value(&coeff_field_characteristic)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value(&min_persistence), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals"); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of an Alpha complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/src/Persistent_cohomology/example/rips_persistence.cpp b/src/Persistent_cohomology/example/rips_persistence.cpp index 9b1ef42f..fa0449a8 100644 --- a/src/Persistent_cohomology/example/rips_persistence.cpp +++ b/src/Persistent_cohomology/example/rips_persistence.cpp @@ -30,6 +30,7 @@ #include #include +#include // infinity using namespace Gudhi; using namespace Gudhi::persistent_cohomology; @@ -114,7 +115,7 @@ void program_options(int argc, char * argv[] ("help,h", "produce help message") ("output-file,o", po::value(&filediag)->default_value(std::string()), "Name of file in which the persistence diagram is written. Default print in std::cout") - ("max-edge-length,r", po::value(&threshold)->default_value(0), + ("max-edge-length,r", po::value(&threshold)->default_value(std::numeric_limits::infinity()), "Maximal length of an edge for the Rips complex construction.") ("cpx-dimension,d", po::value(&dim_max)->default_value(1), "Maximal dimension of the Rips complex we want to compute.") diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 4b04e75a..d4f9aeae 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1160,43 +1160,28 @@ std::cout << "prune_above_filtration - filtration=" << filtration << std::endl; threshold_ = filtration; // Initialize filtration_vect_ if required if (filtration_vect_.empty()) { -std::cout << "prune_above_filtration - initialize_filtration" << std::endl; initialize_filtration(); } - -std::cout << "prune_above_filtration - after initialize_filtration "; -for(auto sh : filtration_vect_) { -for (auto vertex : simplex_vertex_range(sh)) { -std::cout << (int) vertex << ", "; -} -std::cout << " - filtration=" << sh->second.filtration() << " - " << &(sh->second) << std::endl; -} - + std::vector> simplex_list_to_removed; // Loop in reverse mode until threshold is reached - auto f_simplex = filtration_vect_.rbegin(); - for (; (f_simplex != filtration_vect_.rend()) && ((*f_simplex)->second.filtration() > threshold_); f_simplex++) { - -std::cout << "prune_above_filtration - remove "; -for (auto vertex : simplex_vertex_range(*f_simplex)) { -std::cout << (int) vertex << ", "; -} -std::cout << " - " << &((*f_simplex)->second) << std::endl; - - remove_maximal_simplex(*f_simplex); + // Do not erase while looping, because removing is shifting data in a flat_map + for (auto f_simplex = filtration_vect_.rbegin(); + (f_simplex != filtration_vect_.rend()) && ((*f_simplex)->second.filtration() > threshold_); + f_simplex++) { + std::vector simplex_to_remove; + for (auto vertex : simplex_vertex_range(*f_simplex)) + simplex_to_remove.insert(simplex_to_remove.begin(), vertex); + simplex_list_to_removed.push_back(simplex_to_remove); } -std::cout << "prune_above_filtration - remove STOPPED ON "; -for (auto vertex : simplex_vertex_range(*f_simplex)) { -std::cout << (int) vertex << ", "; -} -std::cout << " - filtration=" << (*f_simplex)->second.filtration() << " - " << &(*f_simplex->second) << std::endl; - if (f_simplex != filtration_vect_.rbegin()) { - // Do not forget to update filtration_vect_ - resize is enough - std::size_t new_size = filtration_vect_.size() - (f_simplex - filtration_vect_.rbegin()); -std::cout << "prune_above_filtration - resize" << new_size << std::endl; - filtration_vect_.resize(new_size); + for (auto simplex_to_remove : simplex_list_to_removed) { + Simplex_handle sh = find_simplex(simplex_to_remove); + if (sh != null_simplex()) + remove_maximal_simplex(sh); } - + // Re-initialize filtration_vect_ if dta were removed, because removing is shifting data in a flat_map + if (simplex_list_to_removed.size() > 0) + initialize_filtration(); } } } @@ -1205,6 +1190,7 @@ std::cout << "prune_above_filtration - resize" << new_size << std::endl; * @param[in] sh Simplex handle on the maximal simplex to remove. * \pre Please check the simplex has no coface before removing it. * \warning In debug mode, the exception std::invalid_argument is thrown if sh has children. + * \warning Be aware that removing is shifting data in a flat_map (initialize_filtration to be done). */ void remove_maximal_simplex(Simplex_handle sh) { // Guarantee the simplex has no children @@ -1213,49 +1199,18 @@ std::cout << "prune_above_filtration - resize" << new_size << std::endl; // Simplex is a leaf, it means the child is the Siblings owning the leaf Siblings* child = sh->second.children(); + if ((child->size() > 1) || (child == root())) { // Not alone, just remove it from members // Special case when child is the root of the simplex tree, just remove it from members -std::cout << "remove_maximal_simplex - members removal" << std::endl; child->erase(sh->first); } else { // Sibling is emptied : must be deleted, and its parent must point on his own Sibling -std::cout << "remove_maximal_simplex - members is empty" << std::endl; child->oncles()->members().at(child->parent()).assign_children(child->oncles()); delete child; } } -/***************************************************************************************************************/ - public: - /** \brief Prints the simplex_tree hierarchically. - * Since it prints the vertices recursively, one can watch its tree shape. - */ - void print_tree() { - for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { - std::cout << sh->first << " "; - if (has_children(sh)) { - std::cout << "("; - rec_print(sh->second.children()); - std::cout << ")"; - } - std::cout << std::endl; - } - } - - /** \brief Recursively prints the simplex_tree, using depth first search. */ - private: - void rec_print(Siblings * sib) { - for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { - std::cout << " " << sh->first << " "; - if (has_children(sh)) { - std::cout << "("; - rec_print(sh->second.children()); - std::cout << ")"; - } - } - } -/*****************************************************************************************************************/ private: Vertex_handle null_vertex_; /** \brief Upper bound on the filtration values of the simplices.*/ diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index f6bd5411..0d73d347 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -351,7 +351,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // Display the Simplex_tree - Can not be done in the middle of 2 inserts std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { @@ -549,7 +549,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Display the Simplex_tree - Can not be done in the middle of 2 inserts std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { @@ -805,7 +805,7 @@ struct MyOptions : Simplex_tree_options_full_featured { }; typedef Simplex_tree miniST; -/*BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { +BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { std::cout << "********************************************************************" << std::endl; std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl; @@ -887,7 +887,7 @@ typedef Simplex_tree miniST; st.remove_maximal_simplex(st.find({7})); BOOST_CHECK(st == st_wo_seven); -}*/ +} BOOST_AUTO_TEST_CASE(prune_above_filtration) { std::cout << "********************************************************************" << std::endl; @@ -939,10 +939,10 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { st.prune_above_filtration(5.0); BOOST_CHECK(st == st_complete); - // Display the Simplex_tree - Can not be done in the middle of 2 inserts + // Display the Simplex_tree std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { @@ -955,35 +955,45 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { // Set the st_pruned filtration for operator== st_pruned.set_filtration(2.5); st.prune_above_filtration(2.5); - /*BOOST_CHECK(st == st_pruned); + BOOST_CHECK(st == st_pruned); + + // Display the Simplex_tree + std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } st_pruned.set_filtration(2.0); st.prune_above_filtration(2.0); BOOST_CHECK(st == st_pruned); -*/ -/* std::cout << "The complex contains " << st.num_simplices() << " simplices --------------------------" << std::endl; - std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - st.print_tree(); - std::cout << "The pruned complex contains " << st_pruned.num_simplices() << " simplices --------------------------" << std::endl; - std::cout << " - dimension " << st_pruned.dimension() << " - filtration " << st_pruned.filtration() << std::endl; - st_pruned.print_tree(); - typeST st_empty; // FIXME st_empty.set_dimension(3); st.prune_above_filtration(0.0); - */ - /*BOOST_CHECK(st == st_empty); + + // Display the Simplex_tree + std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + BOOST_CHECK(st == st_empty); // Test case to the limit st.prune_above_filtration(-1.0); st_empty.set_filtration(-1.0); BOOST_CHECK(st == st_empty); -*/ } - -/*BOOST_AUTO_TEST_CASE(sanitizer) { - int a[2] = {1, 0}; - int b=a[2]; -}*/ diff --git a/src/common/include/gudhi/distance_functions.h b/src/common/include/gudhi/distance_functions.h index e5c79ded..cd518581 100644 --- a/src/common/include/gudhi/distance_functions.h +++ b/src/common/include/gudhi/distance_functions.h @@ -23,6 +23,8 @@ #ifndef DISTANCE_FUNCTIONS_H_ #define DISTANCE_FUNCTIONS_H_ +#include // for std::sqrt + /* Compute the Euclidean distance between two Points given * by a range of coordinates. The points are assumed to have * the same dimension. */ @@ -35,7 +37,7 @@ double euclidean_distance(Point &p1, Point &p2) { double tmp = *it1 - *it2; dist += tmp*tmp; } - return sqrt(dist); + return std::sqrt(dist); } #endif // DISTANCE_FUNCTIONS_H_ diff --git a/src/common/include/gudhi/reader_utils.h b/src/common/include/gudhi/reader_utils.h index e05714c7..da2c2c36 100644 --- a/src/common/include/gudhi/reader_utils.h +++ b/src/common/include/gudhi/reader_utils.h @@ -58,7 +58,9 @@ inline void read_points(std::string file_name, std::vector< std::vector< double while (iss >> x) { point.push_back(x); } - points.push_back(point); + // Check for empty lines + if (!point.empty()) + points.push_back(point); } in_file.close(); } -- cgit v1.2.3 From 74dcaacda1c887b008ea8c95b28962de1c02a2d0 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 2 Feb 2016 15:24:51 +0000 Subject: alpha off reader test strategy modification git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@995 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: aa4ba97eecefb03e01a53ae1e2b50248a0857043 --- src/Alpha_complex/doc/Intro_alpha_complex.h | 2 +- .../example/Alpha_complex_from_off.cpp | 33 +++++++++++++++------- .../example/Alpha_complex_from_points.cpp | 2 +- src/Alpha_complex/example/CMakeLists.txt | 19 +++++++++++-- .../example/alphaoffreader_for_doc_32.txt | 26 ++++++++--------- src/Alpha_complex/test/CMakeLists.txt | 14 +++++++++ src/Simplex_tree/include/gudhi/Simplex_tree.h | 15 ++++++---- 7 files changed, 78 insertions(+), 33 deletions(-) (limited to 'src/Alpha_complex/test/CMakeLists.txt') diff --git a/src/Alpha_complex/doc/Intro_alpha_complex.h b/src/Alpha_complex/doc/Intro_alpha_complex.h index 12d62ac0..8eea6ba7 100644 --- a/src/Alpha_complex/doc/Intro_alpha_complex.h +++ b/src/Alpha_complex/doc/Intro_alpha_complex.h @@ -67,7 +67,7 @@ namespace alphacomplex { * * When launching: * - * \code $> ./alphapoints 60.0 + * \code $> ./alphapoints * \endcode * * the program output is: diff --git a/src/Alpha_complex/example/Alpha_complex_from_off.cpp b/src/Alpha_complex/example/Alpha_complex_from_off.cpp index 780f904b..80445a22 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_off.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_off.cpp @@ -5,14 +5,14 @@ #include void usage(char * const progName) { - std::cerr << "Usage: " << progName << " filename.off alpha_square_max_value" << std::endl; - std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0" << std::endl; + 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) { - std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; + if ((argc != 3) && (argc != 4)) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct\n"; usage(argv[0]); } @@ -25,21 +25,34 @@ int main(int argc, char **argv) { typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; Gudhi::alphacomplex::Alpha_complex 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 // ---------------------------------------------------------------------------- - std::cout << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << + 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; - std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << 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()) { - std::cout << " ( "; + output_stream << " ( "; for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; + output_stream << vertex << " "; } - std::cout << ") -> " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] "; - std::cout << std::endl; + 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 index dab161c9..815e40d7 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_points.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_points.cpp @@ -10,7 +10,7 @@ typedef Kernel::Point_d Point; typedef std::vector Vector_of_points; int main(int argc, char **argv) { - double alpha_square_max_value = 32.0; + double alpha_square_max_value = 60.0; // ---------------------------------------------------------------------------- // Init of a list of points diff --git a/src/Alpha_complex/example/CMakeLists.txt b/src/Alpha_complex/example/CMakeLists.txt index 33ff6805..d93dd436 100644 --- a/src/Alpha_complex/example/CMakeLists.txt +++ b/src/Alpha_complex/example/CMakeLists.txt @@ -27,12 +27,25 @@ if(CGAL_FOUND) if (EIGEN3_FOUND) message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") include( ${EIGEN3_USE_FILE} ) - - add_executable ( alphaoffreader Alpha_complex_from_off.cpp ) - target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) add_executable ( alphapoints Alpha_complex_from_points.cpp ) target_link_libraries(alphapoints ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + 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}/) + # 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_executable ( alphaoffreader Alpha_complex_from_off.cpp ) + target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + 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) + 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() diff --git a/src/Alpha_complex/example/alphaoffreader_for_doc_32.txt b/src/Alpha_complex/example/alphaoffreader_for_doc_32.txt index 553431a9..13183e86 100644 --- a/src/Alpha_complex/example/alphaoffreader_for_doc_32.txt +++ b/src/Alpha_complex/example/alphaoffreader_for_doc_32.txt @@ -7,16 +7,16 @@ Iterator on alpha complex simplices in the filtration order, with [filtration va ( 4 ) -> [0] ( 5 ) -> [0] ( 6 ) -> [0] - ( 5 4 ) -> [6.25] - ( 4 1 ) -> [20] - ( 4 2 ) -> [8.5] - ( 6 2 ) -> [9.25] - ( 6 5 ) -> [10] - ( 6 4 ) -> [11.25] - ( 6 5 4 ) -> [12.5] - ( 6 4 2 ) -> [12.9959] - ( 3 0 ) -> [13.25] - ( 4 1 ) -> [20] - ( 1 0 ) -> [22.7367] - ( 3 1 0 ) -> [22.7367] - ( 5 0 ) -> [30.25] + ( 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/test/CMakeLists.txt b/src/Alpha_complex/test/CMakeLists.txt index fa24e1b1..52ec0a78 100644 --- a/src/Alpha_complex/test/CMakeLists.txt +++ b/src/Alpha_complex/test/CMakeLists.txt @@ -8,6 +8,20 @@ if(CGAL_FOUND) message(STATUS "CGAL version: ${CGAL_VERSION}.") include( ${CGAL_USE_FILE} ) + # In CMakeLists.txt, when include(${CGAL_USE_FILE}), CXX_FLAGS are overwritten. + # cf. http://doc.cgal.org/latest/Manual/installation.html#title40 + # A workaround is to add "-std=c++11" again. + # A fix would be to use https://cmake.org/cmake/help/v3.1/prop_gbl/CMAKE_CXX_KNOWN_FEATURES.html + # or even better https://cmake.org/cmake/help/v3.1/variable/CMAKE_CXX_STANDARD.html + # but it implies to use cmake version 3.1 at least. + if(NOT MSVC) + include(CheckCXXCompilerFlag) + CHECK_CXX_COMPILER_FLAG(-std=c++11 COMPILER_SUPPORTS_CXX11) + if(COMPILER_SUPPORTS_CXX11) + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") + endif() + endif() + # - End of workaround find_package(Eigen3 3.1.0) if (EIGEN3_FOUND) diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index dbef8517..3911f497 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -307,7 +307,8 @@ class Simplex_tree { * of the simplex. * * @param[in] sh Simplex for which the boundary is computed. */ - Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) { + template + Boundary_simplex_range boundary_simplex_range(DictionaryIterator sh) { return Boundary_simplex_range(Boundary_simplex_iterator(this, sh), Boundary_simplex_iterator(this)); } @@ -528,7 +529,11 @@ class Simplex_tree { /** \brief Returns true if the node in the simplex tree pointed by * sh has children.*/ - bool has_children(Simplex_handle sh) const { + /*bool has_children(Simplex_handle sh) const { + return (sh->second.children()->parent() == sh->first); + }*/ + template + bool has_children(DictionaryIterator sh) const { return (sh->second.children()->parent() == sh->first); } @@ -1128,7 +1133,7 @@ class Simplex_tree { bool make_filtration_non_decreasing() { bool modified = false; // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree - for (auto sh = (root_.members().end() - 1); sh >= root_.members().begin(); --sh) { + for (auto sh = root_.members().rbegin(); sh != root_.members().rend(); ++sh) { if (has_children(sh)) { modified |= rec_make_filtration_non_decreasing(sh->second.children()); } @@ -1144,10 +1149,11 @@ class Simplex_tree { bool rec_make_filtration_non_decreasing(Siblings * sib) { bool modified = false; + // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { // Find the maximum filtration value in the border Boundary_simplex_range boundary = boundary_simplex_range(sh); - Boundary_simplex_iterator max_border = std::max_element( std::begin(boundary), std::end(boundary), + Boundary_simplex_iterator max_border = std::max_element(std::begin(boundary), std::end(boundary), [](Simplex_handle sh1, Simplex_handle sh2) { return filtration(sh1) < filtration(sh2); } ); @@ -1175,7 +1181,6 @@ class Simplex_tree { * call `initialize_filtration()` to recompute it. */ void prune_above_filtration(Filtration_value filtration) { -std::cout << "prune_above_filtration - filtration=" << filtration << std::endl; // No action if filtration is not stored if (Options::store_filtration) { if (filtration < threshold_) { -- cgit v1.2.3