11 #ifndef UTILS_FURTHEST_POINT_EPSILON_NET_H_
12 #define UTILS_FURTHEST_POINT_EPSILON_NET_H_
17 #include "utils/UI_utils.h"
24 SkBlComplex& complex_;
25 typedef typename SkBlComplex::Vertex_handle Vertex_handle;
26 typedef typename SkBlComplex::Edge_handle Edge_handle;
37 struct Net_filtration_vertex {
38 Vertex_handle vertex_handle;
39 Vertex_handle meeting_vertex;
42 Net_filtration_vertex(Vertex_handle vertex_handle_,
43 Vertex_handle meeting_vertex_,
45 vertex_handle(vertex_handle_), meeting_vertex(meeting_vertex_), radius(radius_) { }
47 bool operator<(
const Net_filtration_vertex& other)
const {
48 return radius < other.radius;
53 std::vector<Net_filtration_vertex> net_filtration_;
61 if (!complex.empty()) {
63 for (std::size_t k = 2; k < net_filtration_.size(); ++k) {
64 update_radius_value(k);
72 return net_filtration_[v.vertex].radius;
76 void init_filtration() {
78 net_filtration_.reserve(complex_.num_vertices());
79 for (
auto v : complex_.vertex_range()) {
81 net_filtration_.push_back(Net_filtration_vertex(v,
83 squared_eucl_distance(v, v0)));
85 net_filtration_.push_back(Net_filtration_vertex(v0,
Vertex_handle(-1), 1e10));
86 auto n = net_filtration_.size();
87 sort_filtration(n - 1);
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));
98 sort_filtration(n - k);
104 void sort_filtration(
int i) {
105 std::sort(net_filtration_.begin(), net_filtration_.begin() + i);
109 return std::sqrt(Geometry_trait::Squared_distance_d()(complex_.point(v1), complex_.point(v2)));
112 void print_filtration()
const {
113 for (
auto v : net_filtration_) {
114 std::cerr <<
"v=" << v.vertex_handle <<
"-> d=" << v.radius << std::endl;
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