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 
20 template<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 Fri Jan 14 2022 18:28:42 for GUDHIdev by Doxygen 1.9.1