Neighbors_finder.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: Francois Godi
4  *
5  * Copyright (C) 2015 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef NEIGHBORS_FINDER_H_
12 #define NEIGHBORS_FINDER_H_
13 
14 // Inclusion order is important for CGAL patch
15 #include <CGAL/Kd_tree.h>
16 #include <CGAL/Search_traits.h>
17 
18 #include <gudhi/Persistence_graph.h>
19 #include <gudhi/Internal_point.h>
20 
21 #include <unordered_set>
22 #include <vector>
23 #include <algorithm> // for std::max
24 #include <cmath> // for std::abs
25 
26 namespace Gudhi {
27 
28 namespace persistence_diagram {
29 
32 struct Square_query {
33  typedef CGAL::Dimension_tag<2> D;
34  typedef Internal_point Point_d;
35  typedef double FT;
36  bool contains(Point_d p) const {
37  return (std::max)(std::abs(p.x()-c.x()), std::abs(p.y()-c.y())) <= size;
38  }
39  bool inner_range_intersects(CGAL::Kd_tree_rectangle<FT, D> const&r) const {
40  return
41  r.max_coord(0) >= c.x() - size &&
42  r.min_coord(0) <= c.x() + size &&
43  r.max_coord(1) >= c.y() - size &&
44  r.min_coord(1) <= c.y() + size;
45  }
46  bool outer_range_contains(CGAL::Kd_tree_rectangle<FT, D> const&r) const {
47  return
48  r.min_coord(0) >= c.x() - size &&
49  r.max_coord(0) <= c.x() + size &&
50  r.min_coord(1) >= c.y() - size &&
51  r.max_coord(1) <= c.y() + size;
52  }
53  Point_d c;
54  FT size;
55 };
56 
65 class Neighbors_finder {
66  typedef CGAL::Dimension_tag<2> D;
67  typedef CGAL::Search_traits<double, Internal_point, const double*, Construct_coord_iterator, D> Traits;
68  typedef CGAL::Kd_tree<Traits> Kd_tree;
69 
70  public:
72  Neighbors_finder(const Persistence_graph& g, double r);
74  void add(int v_point_index);
77  int pull_near(int u_point_index);
79  std::vector<int> pull_all_near(int u_point_index);
80 
81  private:
82  const Persistence_graph& g;
83  const double r;
84  Kd_tree kd_t;
85  std::unordered_set<int> projections_f;
86 };
87 
96 class Layered_neighbors_finder {
97  public:
99  Layered_neighbors_finder(const Persistence_graph& g, double r);
101  void add(int v_point_index, int vlayer);
104  int pull_near(int u_point_index, int vlayer);
106  int vlayers_number() const;
107 
108  private:
109  const Persistence_graph& g;
110  const double r;
111  std::vector<std::unique_ptr<Neighbors_finder>> neighbors_finder;
112 };
113 
114 inline Neighbors_finder::Neighbors_finder(const Persistence_graph& g, double r) :
115  g(g), r(r), kd_t(), projections_f() { }
116 
117 inline void Neighbors_finder::add(int v_point_index) {
118  if (g.on_the_v_diagonal(v_point_index))
119  projections_f.emplace(v_point_index);
120  else
121  kd_t.insert(g.get_v_point(v_point_index));
122 }
123 
124 inline int Neighbors_finder::pull_near(int u_point_index) {
125  int tmp;
126  int c = g.corresponding_point_in_v(u_point_index);
127  if (g.on_the_u_diagonal(u_point_index) && !projections_f.empty()) {
128  // Any pair of projection is at distance 0
129  tmp = *projections_f.cbegin();
130  projections_f.erase(tmp);
131  } else if (projections_f.count(c) && (g.distance(u_point_index, c) <= r)) {
132  // Is the query point near to its projection ?
133  tmp = c;
134  projections_f.erase(tmp);
135  } else {
136  // Is the query point near to a V point in the plane ?
137  Internal_point u_point = g.get_u_point(u_point_index);
138  auto neighbor = kd_t.search_any_point(Square_query{u_point, r});
139  if (!neighbor)
140  return null_point_index();
141  tmp = neighbor->point_index;
142  auto point = g.get_v_point(tmp);
143  int idx = point.point_index;
144  kd_t.remove(point, [idx](Internal_point const&p){return p.point_index == idx;});
145  }
146  return tmp;
147 }
148 
149 inline std::vector<int> Neighbors_finder::pull_all_near(int u_point_index) {
150  std::vector<int> all_pull;
151  int last_pull = pull_near(u_point_index);
152  while (last_pull != null_point_index()) {
153  all_pull.emplace_back(last_pull);
154  last_pull = pull_near(u_point_index);
155  }
156  return all_pull;
157 }
158 
159 inline Layered_neighbors_finder::Layered_neighbors_finder(const Persistence_graph& g, double r) :
160  g(g), r(r), neighbors_finder() { }
161 
162 inline void Layered_neighbors_finder::add(int v_point_index, int vlayer) {
163  for (int l = neighbors_finder.size(); l <= vlayer; l++)
164  neighbors_finder.emplace_back(std::unique_ptr<Neighbors_finder>(new Neighbors_finder(g, r)));
165  neighbors_finder.at(vlayer)->add(v_point_index);
166 }
167 
168 inline int Layered_neighbors_finder::pull_near(int u_point_index, int vlayer) {
169  if (static_cast<int> (neighbors_finder.size()) <= vlayer)
170  return null_point_index();
171  return neighbors_finder.at(vlayer)->pull_near(u_point_index);
172 }
173 
174 inline int Layered_neighbors_finder::vlayers_number() const {
175  return static_cast<int> (neighbors_finder.size());
176 }
177 
178 } // namespace persistence_diagram
179 
180 } // namespace Gudhi
181 
182 #endif // NEIGHBORS_FINDER_H_
GUDHI  Version 3.0.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Dec 10 2019 13:33:51 for GUDHI by Doxygen 1.8.16