From 52bca1c4334e8abe965d616e1ef8a92280013a9b Mon Sep 17 00:00:00 2001 From: salinasd Date: Thu, 29 Jan 2015 09:09:18 +0000 Subject: test is manifold git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@437 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: a515b3216d21c8a5736744842fdcf09644f5c7b1 --- src/GudhUI/utils/Critical_points.h | 137 +++++++++++++++++++++++++++++++++++++ src/GudhUI/utils/Edge_collapsor.h | 9 +-- src/GudhUI/utils/Is_manifold.h | 104 ++++++++++++++++++++++++++++ 3 files changed, 246 insertions(+), 4 deletions(-) create mode 100644 src/GudhUI/utils/Critical_points.h create mode 100644 src/GudhUI/utils/Is_manifold.h (limited to 'src/GudhUI/utils') diff --git a/src/GudhUI/utils/Critical_points.h b/src/GudhUI/utils/Critical_points.h new file mode 100644 index 00000000..92392d4a --- /dev/null +++ b/src/GudhUI/utils/Critical_points.h @@ -0,0 +1,137 @@ +/* + * Critical_points.h + * Created on: Jan 27, 2015 + * 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-Méditerranée (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * 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 CRITICAL_POINTS_H_ +#define CRITICAL_POINTS_H_ + +#include +#include "utils/Edge_contractor.h" + +/** + * Iteratively tries to anticollapse smallest edge non added so far. + * If its link is contractible then no topological change and else possible topological change. + * + * todo do a sparsification with some parameter eps while growing + */ +template class Critical_points{ +private: + SkBlComplex filled_complex_; + const SkBlComplex& input_complex_; + double max_length_; + std::ostream& stream_; +public: + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + typedef typename std::pair Edge; + + /** + * @brief check all pair of points with length smaller than max_length + */ + Critical_points(const SkBlComplex& input_complex,std::ostream& stream,double max_length): + input_complex_(input_complex),max_length_(max_length),stream_(stream) + { + + std::deque edges; + auto vertices = input_complex.vertex_range(); + for(auto p = vertices.begin(); p!= vertices.end(); ++p){ + filled_complex_.add_vertex(input_complex.point(*p)); + for (auto q = p; ++q != vertices.end(); /**/) + if (squared_eucl_distance(input_complex.point(*p),input_complex.point(*q)) < max_length_*max_length_) + edges.emplace_back(*p,*q); + } + + std::sort(edges.begin(),edges.end(), + [&](Edge e1,Edge e2){ + return squared_edge_length(e1) < squared_edge_length(e2); + }); + + anti_collapse_edges(edges); + + } + +private: + double squared_eucl_distance(const Point& p1,const Point& p2) const{ + return Geometry_trait::Squared_distance_d()(p1,p2); + } + + + void anti_collapse_edges(const std::deque& edges){ + unsigned pos = 0; + for(Edge e : edges){ + std::cout<<"edge "< not + //1 -> yes + //2 -> maybe + int is_link_reducible(Edge_handle e){ + auto link = filled_complex_.link(e); + + if(link.empty()) return 0; + + Edge_contractor contractor(link,link.num_vertices()-1); + + if(link.num_connected_components()>1) return 0; //one than more CC -> not contractible + + if (link.num_vertices()==1) return 1; //reduced to one point -> contractible + else return 2; //we dont know + } + + + double squared_edge_length(Edge_handle e) const{ + return squared_eucl_distance(input_complex_.point(input_complex_.first_vertex(e)),input_complex_.point(input_complex_.second_vertex(e))); + } + + double squared_edge_length(Edge e) const{ + return squared_eucl_distance(input_complex_.point(e.first),input_complex_.point(e.second)); + } + + + +}; + + + + + +#endif /* CRITICAL_POINTS_H_ */ diff --git a/src/GudhUI/utils/Edge_collapsor.h b/src/GudhUI/utils/Edge_collapsor.h index 9cf880e0..4dcd18ac 100644 --- a/src/GudhUI/utils/Edge_collapsor.h +++ b/src/GudhUI/utils/Edge_collapsor.h @@ -10,6 +10,7 @@ #include #include "utils/Edge_contractor.h" +#include "utils/UI_utils.h" /** * Iteratively puts every vertex at the center of its neighbors @@ -23,8 +24,9 @@ public: typedef typename SkBlComplex::Edge_handle Edge_handle; /** - * @brief Modify complex to be the expansion of the k-nearest neighbor - * symetric graph. + * @brief Collapse num_collapses edges. If num_collapses<0 then it collapses all possible edges. + * Largest edges are collapsed first. + * */ Edge_collapsor(SkBlComplex& complex,unsigned num_collapses): complex_(complex),num_collapses_(num_collapses) @@ -43,7 +45,6 @@ public: private: - void collapse_edges(std::list& edges){ while(!edges.empty() && num_collapses_--){ Edge_handle current_edge = edges.front(); @@ -63,7 +64,7 @@ private: if(link.num_connected_components()>1) return false; - Edge_contractor contractor(link,link.num_vertices()-1); + Edge_contractor contractor(link,link.num_vertices()-1); return (link.num_vertices()==1); } diff --git a/src/GudhUI/utils/Is_manifold.h b/src/GudhUI/utils/Is_manifold.h new file mode 100644 index 00000000..e708a6a4 --- /dev/null +++ b/src/GudhUI/utils/Is_manifold.h @@ -0,0 +1,104 @@ +/* + * Is_manifold.h + * Created on: Jan 28, 2015 + * 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-Méditerranée (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * 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 IS_MANIFOLD_H_ +#define IS_MANIFOLD_H_ + +#include "utils/UI_utils.h" + +#include "utils/Edge_contractor.h" + +/** + * Iteratively tries to anticollapse smallest edge non added so far. + * If its link is contractible then no topological change and else possible topological change. + * + * todo do a sparsification with some parameter eps while growing + */ +template class Is_manifold{ +private: + const SkBlComplex& input_complex_; + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + + +public: + /* + * return dim the maximum dimension around one simplex and res which is true if the complex is a manifold. + * If the complex has dimension <= 3 then if res is false, the complex is not a manifold. + * For d-manifold with d>=4, res may be false while the complex is a manifold. + */ + Is_manifold(const SkBlComplex& input_complex,unsigned& dim,bool & res):input_complex_(input_complex){ + res = true; + dim = -1; + if(!input_complex_.empty()){ + for(auto v : input_complex_.vertex_range()){ + dim = local_dimension(v); + break; + } + //check that the link of every vertex is a dim-1 sphere + for(auto v : input_complex_.vertex_range()){ + if(!is_k_sphere(v,dim-1)) { + res = false; + break; + } + } + } + } + +private: + unsigned local_dimension(Vertex_handle v){ + unsigned dim = 0; + for(const auto& s: input_complex_.simplex_range(v)) + dim = (std::max)(dim,(unsigned)s.dimension()); + return dim; + } + + bool is_k_sphere(Vertex_handle v,int k){ + auto link = input_complex_.link(v); + Edge_contractor contractor(link,link.num_vertices()-1); + return (is_sphere_simplex(link)==k); + } + + // A minimal sphere is a complex that contains vertices v1...vn and all faces + // made upon this set except the face {v1,...,vn} + // return -2 if not a minimal sphere + // and d otherwise if complex is a d minimal sphere + template + int is_sphere_simplex(const SubComplex& complex){ + if(complex.empty()) return -1; + if(complex.num_blockers()!=1) return -2; + + //necessary and sufficient condition : there exists a unique blocker that passes through all vertices + auto first_blocker = *(complex.const_blocker_range().begin()); + + if (first_blocker->dimension()+1 != complex.num_vertices()) + return -2; + else + return (first_blocker->dimension()-1); + } +}; + +#endif /* IS_MANIFOLD_H_ */ -- cgit v1.2.3