diff options
Diffstat (limited to 'trunk/src/GudhUI/utils/Furthest_point_epsilon_net.h')
-rw-r--r-- | trunk/src/GudhUI/utils/Furthest_point_epsilon_net.h | 132 |
1 files changed, 132 insertions, 0 deletions
diff --git a/trunk/src/GudhUI/utils/Furthest_point_epsilon_net.h b/trunk/src/GudhUI/utils/Furthest_point_epsilon_net.h new file mode 100644 index 00000000..98346daa --- /dev/null +++ b/trunk/src/GudhUI/utils/Furthest_point_epsilon_net.h @@ -0,0 +1,132 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + */ + +#ifndef UTILS_FURTHEST_POINT_EPSILON_NET_H_ +#define UTILS_FURTHEST_POINT_EPSILON_NET_H_ + +#include <vector> +#include <algorithm> // for sort + +#include "utils/UI_utils.h" + +/** + * Computes an epsilon net with furthest point strategy. + */ +template<typename SkBlComplex> class Furthest_point_epsilon_net { + private: + SkBlComplex& complex_; + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + + /** + * Let V be the set of vertices. + * Initially v0 is one arbitrarly vertex and the set V0 is {v0}. + * Then Vk is computed as follows. + * First we compute the vertex pk that is the furthest from Vk + * then Vk = Vk \cup pk. + * The radius of pk is its distance to Vk and its meeting vertex + * is the vertex of Vk for which this distance is achieved. + */ + struct Net_filtration_vertex { + Vertex_handle vertex_handle; + Vertex_handle meeting_vertex; + double radius; + + Net_filtration_vertex(Vertex_handle vertex_handle_, + Vertex_handle meeting_vertex_, + double radius_) : + vertex_handle(vertex_handle_), meeting_vertex(meeting_vertex_), radius(radius_) { } + + bool operator<(const Net_filtration_vertex& other) const { + return radius < other.radius; + } + }; + + public: + std::vector<Net_filtration_vertex> net_filtration_; + + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + Furthest_point_epsilon_net(SkBlComplex& complex) : + complex_(complex) { + if (!complex.empty()) { + init_filtration(); + for (std::size_t k = 2; k < net_filtration_.size(); ++k) { + update_radius_value(k); + } + } + } + + // xxx does not work if complex not full + + double radius(Vertex_handle v) { + return net_filtration_[v.vertex].radius; + } + + private: + void init_filtration() { + Vertex_handle v0 = *(complex_.vertex_range().begin()); + net_filtration_.reserve(complex_.num_vertices()); + for (auto v : complex_.vertex_range()) { + if (v != v0) + net_filtration_.push_back(Net_filtration_vertex(v, + Vertex_handle(-1), + squared_eucl_distance(v, v0))); + } + net_filtration_.push_back(Net_filtration_vertex(v0, Vertex_handle(-1), 1e10)); + auto n = net_filtration_.size(); + sort_filtration(n - 1); + } + + void update_radius_value(int k) { + int n = net_filtration_.size(); + int index_to_update = n - k; + for (int i = 0; i < index_to_update; ++i) { + net_filtration_[i].radius = (std::min)(net_filtration_[i].radius, + squared_eucl_distance(net_filtration_[i].vertex_handle, + net_filtration_[index_to_update].vertex_handle)); + } + sort_filtration(n - k); + } + + /** + * sort all i first elements. + */ + void sort_filtration(int i) { + std::sort(net_filtration_.begin(), net_filtration_.begin() + i); + } + + double squared_eucl_distance(Vertex_handle v1, Vertex_handle v2) const { + return std::sqrt(Geometry_trait::Squared_distance_d()(complex_.point(v1), complex_.point(v2))); + } + + void print_filtration() const { + for (auto v : net_filtration_) { + std::cerr << "v=" << v.vertex_handle << "-> d=" << v.radius << std::endl; + } + } +}; + +#endif // UTILS_FURTHEST_POINT_EPSILON_NET_H_ |