Furthest_point_epsilon_net.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_FURTHEST_POINT_EPSILON_NET_H_
12 #define UTILS_FURTHEST_POINT_EPSILON_NET_H_
13 
14 #include <vector>
15 #include <algorithm> // for sort
16 
17 #include "utils/UI_utils.h"
18 
22 template<typename SkBlComplex> class Furthest_point_epsilon_net {
23  private:
24  SkBlComplex& complex_;
25  typedef typename SkBlComplex::Vertex_handle Vertex_handle;
26  typedef typename SkBlComplex::Edge_handle Edge_handle;
27 
37  struct Net_filtration_vertex {
38  Vertex_handle vertex_handle;
39  Vertex_handle meeting_vertex;
40  double radius;
41 
42  Net_filtration_vertex(Vertex_handle vertex_handle_,
43  Vertex_handle meeting_vertex_,
44  double radius_) :
45  vertex_handle(vertex_handle_), meeting_vertex(meeting_vertex_), radius(radius_) { }
46 
47  bool operator<(const Net_filtration_vertex& other) const {
48  return radius < other.radius;
49  }
50  };
51 
52  public:
53  std::vector<Net_filtration_vertex> net_filtration_;
54 
59  Furthest_point_epsilon_net(SkBlComplex& complex) :
60  complex_(complex) {
61  if (!complex.empty()) {
62  init_filtration();
63  for (std::size_t k = 2; k < net_filtration_.size(); ++k) {
64  update_radius_value(k);
65  }
66  }
67  }
68 
69  // xxx does not work if complex not full
70 
71  double radius(Vertex_handle v) {
72  return net_filtration_[v.vertex].radius;
73  }
74 
75  private:
76  void init_filtration() {
77  Vertex_handle v0 = *(complex_.vertex_range().begin());
78  net_filtration_.reserve(complex_.num_vertices());
79  for (auto v : complex_.vertex_range()) {
80  if (v != v0)
81  net_filtration_.push_back(Net_filtration_vertex(v,
82  Vertex_handle(-1),
83  squared_eucl_distance(v, v0)));
84  }
85  net_filtration_.push_back(Net_filtration_vertex(v0, Vertex_handle(-1), 1e10));
86  auto n = net_filtration_.size();
87  sort_filtration(n - 1);
88  }
89 
90  void update_radius_value(int k) {
91  int n = net_filtration_.size();
92  int index_to_update = n - k;
93  for (int i = 0; i < index_to_update; ++i) {
94  net_filtration_[i].radius = (std::min)(net_filtration_[i].radius,
95  squared_eucl_distance(net_filtration_[i].vertex_handle,
96  net_filtration_[index_to_update].vertex_handle));
97  }
98  sort_filtration(n - k);
99  }
100 
104  void sort_filtration(int i) {
105  std::sort(net_filtration_.begin(), net_filtration_.begin() + i);
106  }
107 
108  double squared_eucl_distance(Vertex_handle v1, Vertex_handle v2) const {
109  return std::sqrt(Geometry_trait::Squared_distance_d()(complex_.point(v1), complex_.point(v2)));
110  }
111 
112  void print_filtration() const {
113  for (auto v : net_filtration_) {
114  std::cerr << "v=" << v.vertex_handle << "-> d=" << v.radius << std::endl;
115  }
116  }
117 };
118 
119 #endif // UTILS_FURTHEST_POINT_EPSILON_NET_H_
Definition: Furthest_point_epsilon_net.h:22
Furthest_point_epsilon_net(SkBlComplex &complex)
Modify complex to be the expansion of the k-nearest neighbor symetric graph.
Definition: Furthest_point_epsilon_net.h:59
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Sun May 1 2022 09:19:32 for GUDHIdev by Doxygen 1.9.1