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