1 // Copyright (c) 2018-2019 GeometryFactory (France).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Optimal_bounding_box/include/CGAL/Optimal_bounding_box/internal/population.h $
7 // $Id: population.h e9d41d7 2020-04-21T10:03:00+02:00 Maxime Gimeno
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s)     : Mael Rouxel-Labbé
12 //                 Konstantinos Katrioplas
13 //
14 #ifndef CGAL_OPTIMAL_BOUNDING_BOX_POPULATION_H
15 #define CGAL_OPTIMAL_BOUNDING_BOX_POPULATION_H
16 
17 #include <CGAL/license/Optimal_bounding_box.h>
18 
19 #include <CGAL/Optimal_bounding_box/internal/fitness_function.h>
20 
21 #include <CGAL/assertions.h>
22 #include <CGAL/Random.h>
23 
24 #include <utility>
25 #include <vector>
26 
27 namespace CGAL {
28 namespace Optimal_bounding_box {
29 namespace internal {
30 
31 template<typename Traits>
32 struct Vertex_with_fitness
33 {
34   typedef typename Traits::FT                                 FT;
35   typedef typename Traits::Matrix                             Matrix;
36 
Vertex_with_fitnessVertex_with_fitness37   Vertex_with_fitness() { CGAL_assertion_code(m_is_val_initialized = false;) }
Vertex_with_fitnessVertex_with_fitness38   Vertex_with_fitness(const Matrix m, const FT v) : m_mat(std::move(m)), m_val(v)
39   {
40     CGAL_assertion_code(m_is_val_initialized = true;)
41   }
42 
43   template <typename PointRange>
Vertex_with_fitnessVertex_with_fitness44   Vertex_with_fitness(const Matrix m,
45                       const PointRange& points,
46                       const Traits& traits)
47     :
48       m_mat(std::move(m))
49   {
50     m_val = compute_fitness(m, points, traits);
51     CGAL_assertion_code(m_is_val_initialized = true;)
52   }
53 
matrixVertex_with_fitness54   Matrix& matrix() { return m_mat; }
matrixVertex_with_fitness55   const Matrix& matrix() const { return m_mat; }
fitnessVertex_with_fitness56   FT& fitness() { return m_val; }
fitnessVertex_with_fitness57   FT fitness() const { CGAL_assertion(m_is_val_initialized); return m_val; }
58 
59 private:
60   Matrix m_mat;
61   FT m_val;
62   CGAL_assertion_code(bool m_is_val_initialized;)
63 };
64 
65 template<typename Traits>
66 class Population
67 {
68 public:
69   typedef typename Traits::FT                                 FT;
70   typedef typename Traits::Matrix                             Matrix;
71 
72   typedef Vertex_with_fitness<Traits>                         Vertex;
73   typedef std::array<Vertex, 4>                               Simplex;
74   typedef std::vector<Simplex>                                Simplex_container;
75 
76 public:
Population(const Traits & traits)77   Population(const Traits& traits) : m_traits(traits) { }
78 
79   // Access
size()80   std::size_t size() const { return m_simplices.size(); }
81   Simplex& operator[](const std::size_t i) { CGAL_assertion(i < m_simplices.size()); return m_simplices[i]; }
82   const Simplex& operator[](const std::size_t i) const { CGAL_assertion(i < m_simplices.size()); return m_simplices[i]; }
simplices()83   Simplex_container& simplices() { return m_simplices; }
84 
85 private:
create_random_matrix(CGAL::Random & rng)86   Matrix create_random_matrix(CGAL::Random& rng) const
87   {
88     Matrix m;
89 
90     for(std::size_t i=0; i<3; ++i)
91       for(std::size_t j=0; j<3; ++j)
92         m.set(i, j, FT(rng.get_double()));
93 
94     return m;
95   }
96 
97 public:
98   template <typename PointRange>
create_simplex(const PointRange & points,CGAL::Random & rng)99   Simplex create_simplex(const PointRange& points,
100                          CGAL::Random& rng) const
101   {
102     Simplex s;
103     for(std::size_t i=0; i<4; ++i)
104       s[i] = Vertex{m_traits.get_Q(create_random_matrix(rng)), points, m_traits};
105 
106     return s;
107   }
108 
109   // create random population
110   template <typename PointRange>
initialize(const std::size_t population_size,const PointRange & points,CGAL::Random & rng)111   void initialize(const std::size_t population_size,
112                   const PointRange& points,
113                   CGAL::Random& rng)
114   {
115     m_simplices.clear();
116     m_simplices.reserve(population_size);
117     for(std::size_t i=0; i<population_size; ++i)
118       m_simplices.emplace_back(create_simplex(points, rng));
119   }
120 
get_best_vertex()121   Vertex& get_best_vertex()
122   {
123     std::size_t simplex_id = static_cast<std::size_t>(-1), vertex_id = static_cast<std::size_t>(-1);
124     FT best_fitness = FT{(std::numeric_limits<double>::max)()};
125     for(std::size_t i=0, ps=m_simplices.size(); i<ps; ++i)
126     {
127       for(std::size_t j=0; j<4; ++j)
128       {
129         const Vertex& vertex = m_simplices[i][j];
130         const FT fitness = vertex.fitness();
131         if(fitness < best_fitness)
132         {
133           simplex_id = i;
134           vertex_id = j;
135           best_fitness = fitness;
136         }
137       }
138     }
139 
140     return m_simplices[simplex_id][vertex_id];
141   }
142 
143   // Debug
144 #ifdef CGAL_OPTIMAL_BOUNDING_BOX_DEBUG
show_population()145   void show_population() const
146   {
147     std::size_t id = 0;
148     for(const Simplex& s : m_simplices)
149     {
150       std::cout << "Simplex: " << id++ << std::endl;
151       for(const Matrix& m : s)
152         std::cout << m << "\n\n";
153       std:: cout << std:: endl;
154     }
155   }
156 #endif
157 
158 private:
159   std::vector<Simplex> m_simplices;
160 
161   const Traits& m_traits;
162 };
163 
164 } // namespace internal
165 } // namespace Optimal_bounding_box
166 } // namespace CGAL
167 
168 #endif // CGAL_OPTIMAL_BOUNDING_BOX_POPULATION_H
169