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
21template<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 Tue Aug 16 2022 14:01:50 for GUDHIdev by Doxygen 1.9.4