Lloyd_builder.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_LLOYD_BUILDER_H_
12#define UTILS_LLOYD_BUILDER_H_
13
14#include <vector>
15#include <list>
16
20template<typename SkBlComplex> class Lloyd_builder {
21 private:
22 SkBlComplex& complex_;
23 int dim;
24
25 public:
26 typedef typename SkBlComplex::Vertex_handle Vertex_handle;
27
32 Lloyd_builder(SkBlComplex& complex, unsigned num_iterations) : complex_(complex), dim(-1) {
33 if (!complex_.empty()) {
34 dim = get_dimension();
35 while (num_iterations--) {
36 std::list<Point> new_points;
37 for (auto v : complex.vertex_range())
38 new_points.push_back(barycenter_neighbors(v));
39
40 auto new_points_it = new_points.begin();
41 for (auto v : complex.vertex_range())
42 complex_.point(v) = *(new_points_it++);
43 }
44 }
45 }
46
47 private:
48 int get_dimension() {
49 assert(!complex_.empty());
50 for (auto v : complex_.vertex_range())
51 return complex_.point(v).dimension();
52 return -1;
53 }
54
55 Point barycenter_neighbors(Vertex_handle v) const {
56 if (complex_.degree(v) == 0)
57 return complex_.point(v);
58
59 std::vector<double> res(dim, 0);
60 unsigned num_points = 0;
61 for (auto nv : complex_.vertex_range(v)) {
62 ++num_points;
63 const Point& point = complex_.point(nv);
64 assert(point.dimension() == dim);
65 for (int i = 0; i < point.dimension(); ++i)
66 res[i] += point[i];
67 }
68 for (auto& x : res)
69 x /= num_points;
70 return Point(dim, res.begin(), res.end());
71 }
72
73 double squared_eucl_distance(const Point& p1, const Point& p2) const {
74 return Geometry_trait::Squared_distance_d()(p1, p2);
75 }
76};
77
78#endif // UTILS_LLOYD_BUILDER_H_
Definition: Lloyd_builder.h:20
Lloyd_builder(SkBlComplex &complex, unsigned num_iterations)
Modify complex to be the expansion of the k-nearest neighbor symetric graph.
Definition: Lloyd_builder.h:32
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