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