71 Point_range
const &input_pts,
72 std::size_t final_size,
73 std::size_t starting_point,
74 PointOutputIterator output_it,
75 DistanceOutputIterator dist_it = {}) {
76 std::size_t nb_points = boost::size(input_pts);
77 if (final_size > nb_points)
78 final_size = nb_points;
86 std::random_device rd;
87 std::mt19937 gen(rd());
88 std::uniform_int_distribution<std::size_t> dis(0, nb_points - 1);
89 starting_point = dis(gen);
94 static_assert(std::numeric_limits<FT>::has_infinity,
"the number type needs to support infinity()");
96 *output_it++ = input_pts[starting_point];
97 *dist_it++ = std::numeric_limits<FT>::infinity();
98 if (final_size == 1)
return;
100 std::vector<std::size_t> points(nb_points);
101 std::vector< FT > dist_to_L(nb_points);
102 for(std::size_t i = 0; i < nb_points; ++i) {
104 dist_to_L[i] = dist(input_pts[i], input_pts[starting_point]);
113 std::size_t curr_max_w = starting_point;
115 for (std::size_t current_number_of_landmarks = 1; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
116 std::size_t latest_landmark = points[curr_max_w];
119 std::size_t last = points.size() - 1;
120 if (curr_max_w != last) {
121 points[curr_max_w] = points[last];
122 dist_to_L[curr_max_w] = dist_to_L[last];
128 for (
auto p : points) {
129 FT curr_dist = dist(input_pts[p], input_pts[latest_landmark]);
130 if (curr_dist < dist_to_L[i])
131 dist_to_L[i] = curr_dist;
136 FT curr_max_dist = dist_to_L[curr_max_w];
137 for (i = 1; i < points.size(); i++)
138 if (dist_to_L[i] > curr_max_dist) {
139 curr_max_dist = dist_to_L[i];
142 *output_it++ = input_pts[points[curr_max_w]];
143 *dist_it++ = dist_to_L[curr_max_w];
204 Point_range
const &input_pts,
205 std::size_t final_size,
206 std::size_t starting_point,
207 PointOutputIterator output_it,
208 DistanceOutputIterator dist_it = {}) {
209 std::size_t nb_points = boost::size(input_pts);
210 if (final_size > nb_points)
211 final_size = nb_points;
219 std::random_device rd;
220 std::mt19937 gen(rd());
221 std::uniform_int_distribution<std::size_t> dis(0, nb_points - 1);
222 starting_point = dis(gen);
227 static_assert(std::numeric_limits<FT>::has_infinity,
"the number type needs to support infinity()");
229 *output_it++ = input_pts[starting_point];
230 *dist_it++ = std::numeric_limits<FT>::infinity();
231 if (final_size == 1)
return;
233 auto dist = [&](std::size_t a, std::size_t b){
return dist_(input_pts[a], input_pts[b]); };
235 std::vector<Landmark_info<FT>> landmarks(nb_points);
236 radius_priority_ds<FT> radius_priority(&landmarks);
238 auto compute_radius = [&](std::size_t i)
240 FT r = -std::numeric_limits<FT>::infinity();
241 std::size_t jmax = -1;
242 for(
auto [ j, d ] : landmarks[i].voronoi) {
248 landmarks[i].radius = r;
249 landmarks[i].far = jmax;
251 auto update_radius = [&](std::size_t i)
254 radius_priority.decrease(landmarks[i].position_in_queue);
259 auto& ini = landmarks[starting_point];
260 ini.voronoi.reserve(nb_points - 1);
261 for (std::size_t i = 0; i < nb_points; ++i)
262 if (i != starting_point)
263 ini.voronoi.emplace_back(i, dist(starting_point, i));
264 compute_radius(starting_point);
265 ini.position_in_queue = radius_priority.push(starting_point);
268 std::vector<std::size_t> modified_neighbors;
269 boost::unordered_set<std::size_t> l_neighbors;
270 for (std::size_t current_number_of_landmarks = 1; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
271 std::size_t l_parent = radius_priority.top();
272 auto& parent_info = landmarks[l_parent];
273 std::size_t l = parent_info.far;
274 FT radius = parent_info.radius;
275 auto& info = landmarks[l];
276 *output_it++ = input_pts[l];
279 modified_neighbors.clear();
282 auto max_dist = [](FT a, FT b){
return a + b + std::max(a, b); };
284 auto handle_neighbor_voronoi = [&](std::size_t ngb)
286 auto& ngb_info = landmarks[ngb];
287 auto it = std::remove_if(ngb_info.voronoi.begin(), ngb_info.voronoi.end(), [&](
auto wd)
289 std::size_t w = wd.first;
291 FT newd = dist(l, w);
294 info.voronoi.emplace_back(w, newd);
299 if (it != ngb_info.voronoi.end()) {
300 ngb_info.voronoi.erase(it, ngb_info.voronoi.end());
301 modified_neighbors.push_back(ngb);
310 auto handle_neighbor_neighbors = [&](std::size_t ngb)
312 auto& ngb_info = landmarks[ngb];
313 std::remove_if(ngb_info.neighbors.begin(), ngb_info.neighbors.end(), [&](
auto near_){
314 std::size_t near = near_.first;
317 if (d <= 3 * radius) { l_neighbors.insert(near); }
319 return d >= max_dist(ngb_info.radius, landmarks[near].radius);
326 handle_neighbor_voronoi(l_parent);
328 for (
auto ngb_ : parent_info.neighbors) {
329 std::size_t ngb = ngb_.first;
333 if(dist(l, ngb) < 2 * landmarks[ngb].radius)
334 handle_neighbor_voronoi(ngb);
339 for (std::size_t ngb : modified_neighbors)
340 handle_neighbor_neighbors(ngb);
343 info.position_in_queue = radius_priority.push(l);
345 l_neighbors.insert(l_parent);
346 for (std::size_t ngb : l_neighbors) {
348 if (d < max_dist(info.radius, landmarks[ngb].radius)) {
349 info.neighbors.emplace_back(ngb, d);
350 landmarks[ngb].neighbors.emplace_back(l, d);