Edge_collapsor.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): David Salinas
4  *
5  * Copyright (C) 2014 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef UTILS_EDGE_COLLAPSOR_H_
12 #define UTILS_EDGE_COLLAPSOR_H_
13 
14 #include <list>
15 #include "utils/Edge_contractor.h"
16 #include "utils/UI_utils.h"
17 
21 template<typename SkBlComplex> class Edge_collapsor {
22  private:
23  SkBlComplex& complex_;
24  unsigned num_collapses_;
25 
26  public:
27  typedef typename SkBlComplex::Vertex_handle Vertex_handle;
28  typedef typename SkBlComplex::Edge_handle Edge_handle;
29 
35  Edge_collapsor(SkBlComplex& complex, unsigned num_collapses) :
36  complex_(complex), num_collapses_(num_collapses) {
37  std::list<Edge_handle> edges;
38  edges.insert(edges.begin(), complex_.edge_range().begin(), complex_.edge_range().end());
39 
40  edges.sort(
41  [&](Edge_handle e1, Edge_handle e2) {
42  return squared_edge_length(e1) < squared_edge_length(e2);
43  });
44 
45  collapse_edges(edges);
46  }
47 
48  private:
49  void collapse_edges(std::list<Edge_handle>& edges) {
50  while (!edges.empty() && num_collapses_--) {
51  Edge_handle current_edge = edges.front();
52  edges.pop_front();
53  if (is_link_reducible(current_edge))
54  complex_.remove_edge(current_edge);
55  }
56  }
57 
58  bool is_link_reducible(Edge_handle e) {
59  auto link = complex_.link(e);
60 
61  if (link.empty())
62  return false;
63 
64  if (link.is_cone())
65  return true;
66 
67  if (link.num_connected_components() > 1)
68  return false;
69 
70  Edge_contractor<SkBlComplex> contractor(link, link.num_vertices() - 1);
71 
72  return (link.num_vertices() == 1);
73  }
74 
75  double squared_edge_length(Edge_handle e) const {
76  return squared_eucl_distance(complex_.point(complex_.first_vertex(e)), complex_.point(complex_.second_vertex(e)));
77  }
78 
79  double squared_eucl_distance(const Point& p1, const Point& p2) const {
80  return Geometry_trait::Squared_distance_d()(p1, p2);
81  }
82 };
83 
84 #endif // UTILS_EDGE_COLLAPSOR_H_
Definition: Edge_collapsor.h:21
Edge_collapsor(SkBlComplex &complex, unsigned num_collapses)
Collapse num_collapses edges. If num_collapses<0 then it collapses all possible edges....
Definition: Edge_collapsor.h:35
Definition: Edge_contractor.h:24
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Jan 14 2022 18:28:42 for GUDHIdev by Doxygen 1.9.1