23 #ifndef NEIGHBORS_FINDER_H_ 24 #define NEIGHBORS_FINDER_H_ 27 #include <CGAL/Kd_tree.h> 28 #include <CGAL/Search_traits.h> 30 #include <gudhi/Persistence_graph.h> 31 #include <gudhi/Internal_point.h> 33 #include <unordered_set> 39 namespace persistence_diagram {
44 typedef CGAL::Dimension_tag<2> D;
45 typedef Internal_point Point_d;
47 bool contains(Point_d p)
const {
48 return std::max(std::abs(p.x()-c.x()), std::abs(p.y()-c.y())) <= size;
50 bool inner_range_intersects(CGAL::Kd_tree_rectangle<FT, D>
const&r)
const {
52 r.max_coord(0) >= c.x() - size &&
53 r.min_coord(0) <= c.x() + size &&
54 r.max_coord(1) >= c.y() - size &&
55 r.min_coord(1) <= c.y() + size;
57 bool outer_range_contains(CGAL::Kd_tree_rectangle<FT, D>
const&r)
const {
59 r.min_coord(0) >= c.x() - size &&
60 r.max_coord(0) <= c.x() + size &&
61 r.min_coord(1) >= c.y() - size &&
62 r.max_coord(1) <= c.y() + size;
76 class Neighbors_finder {
77 typedef CGAL::Dimension_tag<2> D;
78 typedef CGAL::Search_traits<double, Internal_point, const double*, Construct_coord_iterator, D> Traits;
79 typedef CGAL::Kd_tree<Traits> Kd_tree;
83 Neighbors_finder(
const Persistence_graph& g,
double r);
85 void add(
int v_point_index);
88 int pull_near(
int u_point_index);
90 std::vector<int> pull_all_near(
int u_point_index);
93 const Persistence_graph& g;
96 std::unordered_set<int> projections_f;
107 class Layered_neighbors_finder {
110 Layered_neighbors_finder(
const Persistence_graph& g,
double r);
112 void add(
int v_point_index,
int vlayer);
115 int pull_near(
int u_point_index,
int vlayer);
117 int vlayers_number()
const;
120 const Persistence_graph& g;
122 std::vector<std::unique_ptr<Neighbors_finder>> neighbors_finder;
125 inline Neighbors_finder::Neighbors_finder(
const Persistence_graph& g,
double r) :
126 g(g), r(r), kd_t(), projections_f() { }
128 inline void Neighbors_finder::add(
int v_point_index) {
129 if (g.on_the_v_diagonal(v_point_index))
130 projections_f.emplace(v_point_index);
132 kd_t.insert(g.get_v_point(v_point_index));
135 inline int Neighbors_finder::pull_near(
int u_point_index) {
137 int c = g.corresponding_point_in_v(u_point_index);
138 if (g.on_the_u_diagonal(u_point_index) && !projections_f.empty()) {
140 tmp = *projections_f.cbegin();
141 projections_f.erase(tmp);
142 }
else if (projections_f.count(c) && (g.distance(u_point_index, c) <= r)) {
145 projections_f.erase(tmp);
148 Internal_point u_point = g.get_u_point(u_point_index);
149 auto neighbor = kd_t.search_any_point(Square_query{u_point, r});
151 return null_point_index();
152 tmp = neighbor->point_index;
153 auto point = g.get_v_point(tmp);
154 int idx = point.point_index;
155 kd_t.remove(point, [idx](Internal_point
const&p){
return p.point_index == idx;});
160 inline std::vector<int> Neighbors_finder::pull_all_near(
int u_point_index) {
161 std::vector<int> all_pull;
162 int last_pull = pull_near(u_point_index);
163 while (last_pull != null_point_index()) {
164 all_pull.emplace_back(last_pull);
165 last_pull = pull_near(u_point_index);
170 inline Layered_neighbors_finder::Layered_neighbors_finder(
const Persistence_graph& g,
double r) :
171 g(g), r(r), neighbors_finder() { }
173 inline void Layered_neighbors_finder::add(
int v_point_index,
int vlayer) {
174 for (
int l = neighbors_finder.size(); l <= vlayer; l++)
175 neighbors_finder.emplace_back(std::unique_ptr<Neighbors_finder>(
new Neighbors_finder(g, r)));
176 neighbors_finder.at(vlayer)->add(v_point_index);
179 inline int Layered_neighbors_finder::pull_near(
int u_point_index,
int vlayer) {
180 if (static_cast<int> (neighbors_finder.size()) <= vlayer)
181 return null_point_index();
182 return neighbors_finder.at(vlayer)->pull_near(u_point_index);
185 inline int Layered_neighbors_finder::vlayers_number()
const {
186 return static_cast<int> (neighbors_finder.size());
193 #endif // NEIGHBORS_FINDER_H_ Definition: SimplicialComplexForAlpha.h:26