• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

pcb2gcode / pcb2gcode / 23511030556

24 Mar 2026 08:36PM UTC coverage: 91.163% (-0.05%) from 91.208%
23511030556

push

github

web-flow
Merge pull request #863 from eyal0/single_threaded_coverage

build: Disable multi-threading for coverage.

7585 of 8671 branches covered (87.48%)

Branch coverage included in aggregate %.

4 of 4 new or added lines in 2 files covered. (100.0%)

4 existing lines in 2 files now uncovered.

6640 of 6933 relevant lines covered (95.77%)

40361588.65 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.45
/src/path_finding.cpp
1
#include <vector>
2
using std::vector;
3

4
#include <unordered_map>
5
using std::unordered_map;
6

7
#include <unordered_set>
8
using std::unordered_set;
9

10
#include <queue>
11
using std::priority_queue;
12

13
#include <utility>
14
using std::pair;
15
using std::make_pair;
16

17
#include <boost/graph/adjacency_list.hpp>
18
#include <boost/graph/astar_search.hpp>
19
#include <boost/optional.hpp>
20

21
#include "path_finding.hpp"
22
#include "options.hpp"
23
#include "geometry.hpp"
24
#include "bg_operators.hpp"
25
#include "bg_helpers.hpp"
26
#include "segment_tree.hpp"
27

28
namespace path_finding {
29

30
using boost::optional;
31
using boost::make_optional;
32

33
Neighbors::iterator Neighbors::iterator::operator++() {
1,526,880✔
34
  const auto& all_vertices_size = neighbors->vertices.size();
1,526,880✔
35
  do {
3,051,520✔
36
    // Move to a new valid point, even if it isn't a neighbor.
37
    point_index++;
3,051,520✔
38
  } while (point_index < all_vertices_size + 2 &&
3,052,234✔
39
           !neighbors->is_neighbor(**this));
3,051,462✔
40
  return *this;
1,450,922✔
41
}
1,450,536✔
42

43
bool Neighbors::iterator::operator!=(const Neighbors::iterator& other) const {
1,452,744✔
44
  return (point_index != other.point_index);
1,452,744✔
45
}
1,452,322✔
46

47
bool Neighbors::iterator::operator==(const Neighbors::iterator& other) const {
1,444,304✔
48
  return !(*this != other);
1,520,320!
49
}
1,444,304✔
50

51
const point_type_fp& Neighbors::iterator::operator*() const {
4,577,960✔
52
  if (point_index == 0) {
4,577,960✔
53
    return neighbors->start;
1,521,040✔
54
  } else if (point_index == 1) {
3,056,920✔
55
    return neighbors->goal;
1,520,600✔
56
  } else {
1,459,504✔
57
    return neighbors->vertices[point_index-2];
1,536,320✔
58
  }
1,459,504✔
59
}
4,349,062✔
60

61
Neighbors::Neighbors(const point_type_fp& start, const point_type_fp& goal,
76,016✔
62
                     const point_type_fp& current,
63
                     const coordinate_type_fp& max_path_length,
64
                     const std::vector<point_type_fp>& vertices,
65
                     PathFindingSurfaceWithTries* pfs) :
76,016✔
66
    start(start),
1,520,320✔
67
    goal(goal),
1,520,320✔
68
    current(current),
1,520,320✔
69
    max_path_length_squared(max_path_length),
1,520,320✔
70
    vertices(vertices),
1,520,320✔
71
    pfs(pfs) {}
1,520,320✔
72

73
// Returns a valid neighbor index that is either the one provided or
74
// the next higher valid one.
75
inline bool Neighbors::is_neighbor(const point_type_fp p) {
4,570,680✔
76
  if (p == current) {
4,722,892✔
77
    return false;
1,444,532✔
78
  }
1,444,532✔
79
  pfs->decrement_tries();
3,050,120✔
80
  if (bg::distance(current, p) + bg::distance(p, goal) > max_path_length_squared) {
2,974,162✔
81
    return false;
761,824✔
82
  }
761,824✔
83
  if (!pfs->in_surface(current, p)) {
2,172,242✔
84
    return false;
685,672✔
85
  }
685,672✔
86
  return true;
1,450,118✔
87
}
2,135,790✔
88

89
Neighbors::iterator Neighbors::begin() {
1,520,320✔
90
  auto ret = iterator(this, 0);
1,520,320!
91
  if (ret == end()) {
1,520,320✔
92
    // Can't dereferfence the end.
93
    return ret;
×
94
  }
95
  if (is_neighbor(*ret)) {
1,520,320✔
96
    // This is a valid begin.
97
    return ret;
720✔
98
  } else {
1,443,620✔
99
    // This position is invalid but we can increment to get to a valid one.
100
    ++ret;
1,519,600✔
101
    return ret;
1,443,644✔
102
  }
1,443,620✔
103
}
1,444,304✔
104

105
Neighbors::iterator Neighbors::end() {
1,521,520✔
106
  return iterator(this, vertices.size()+2);
1,521,520!
107
}
1,445,444✔
108

109
vector<pair<point_type_fp, point_type_fp>> get_all_segments(
364✔
110
    const vector<vector<std::reference_wrapper<const ring_type_fp>>>& all_rings) {
6,916✔
111
  vector<pair<point_type_fp, point_type_fp>> ret;
7,280✔
112
  for (const auto& x0 : all_rings) {
68,284✔
113
    for (auto x1 : x0) {
71,476✔
114
      for (size_t i = 0; i+1 < x1.get().size(); i++) {
14,124,560✔
115
        ret.emplace_back(x1.get()[i], x1.get()[i+1]);
14,056,480✔
116
      }
13,353,656✔
117
    }
64,676✔
118
  }
64,524✔
119
  return ret;
7,280✔
120
}
6,916✔
121

122
vector<std::reference_wrapper<const ring_type_fp>> get_all_rings(const multi_polygon_type_fp& mpolys) {
67,920✔
123
  vector<std::reference_wrapper<const ring_type_fp>> ret;
67,920✔
124
  for (const auto& poly : mpolys) {
71,396✔
125
    ret.push_back(poly.outer());
68,000✔
126
    for (const auto& inner : poly.inners()) {
68,004✔
127
      ret.push_back(inner);
80✔
128
    }
76✔
129
  }
64,600✔
130
  return ret;
67,920✔
131
}
64,524✔
132

133
vector<vector<std::reference_wrapper<const ring_type_fp>>> get_all_rings(
364✔
134
    const nested_multipolygon_type_fp& mpolys) {
6,916✔
135
  vector<vector<std::reference_wrapper<const ring_type_fp>>> ret;
7,280✔
136
  for (const auto& poly : mpolys) {
28,284✔
137
    ret.push_back(get_all_rings(poly.outer()));
29,316✔
138
    for (const auto& inner: poly.inners()) {
41,396✔
139
      ret.push_back(get_all_rings(inner));
42,000✔
140
    }
38,000✔
141
  }
26,524✔
142
  return ret;
7,280✔
143
}
6,916✔
144

145
PathFindingSurface::PathFindingSurface(const optional<multi_polygon_type_fp>& keep_in,
364✔
146
                                       const multi_polygon_type_fp& keep_out,
147
                                       const coordinate_type_fp tolerance) {
7,280✔
148
  if (keep_in) {
7,280✔
149
    multi_polygon_type_fp total_keep_in = *keep_in - keep_out;
5,720✔
150

151
    total_keep_in_grown.emplace();
5,720✔
152
    for (const auto& poly : total_keep_in) {
13,806✔
153
      all_vertices.emplace_back();
13,520✔
154
      all_vertices.back().emplace_back(poly.outer().cbegin(), poly.outer().cend());
13,520✔
155
      total_keep_in_grown->emplace_back(bg_helpers::buffer_miter(poly.outer(), tolerance));
13,520✔
156
      for (const auto& inner : poly.inners()) {
27,716✔
157
        all_vertices.back().emplace_back(inner.cbegin(), inner.cend());
27,040✔
158
        // Because the inner is reversed, we need to reverse it so
159
        // that the buffer algorithm won't get confused.
160
        auto temp_inner = inner;
27,040✔
161
        bg::reverse(temp_inner);
27,040✔
162
        // tolerance needs to be inverted because growing a shape
163
        // shrinks the holes in it.
164
        total_keep_in_grown->back().inners().push_back(bg_helpers::buffer_miter(temp_inner, -tolerance));
28,392✔
165
      }
27,040✔
166
    }
12,844✔
167
  } else {
5,720✔
168
    for (const auto& poly : keep_out){
14,478✔
169
      all_vertices.emplace_back();
14,400✔
170
      all_vertices.back().emplace_back(poly.outer().cbegin(), poly.outer().cend());
14,400✔
171
      keep_out_shrunk.emplace_back(bg_helpers::buffer_miter(poly.outer(), -tolerance));
14,400✔
172
      for (const auto& inner : poly.inners()) {
15,048✔
173
        all_vertices.back().emplace_back(inner.cbegin(), inner.cend());
12,960✔
174
        // Because the inner is reversed, we need to reverse it so
175
        // that the buffer algorithm won't get confused.
176
        auto temp_inner = inner;
12,960✔
177
        bg::reverse(temp_inner);
12,960✔
178
        // tolerance needs to be inverted because shrinking a shape
179
        // grows the holes in it.
180
        keep_out_shrunk.back().inners().push_back(bg_helpers::buffer_miter(temp_inner, tolerance));
13,608✔
181
      }
12,960✔
182
    }
13,680✔
183
  }
1,482✔
184
  const nested_multipolygon_type_fp& poly_to_search = total_keep_in_grown ? *total_keep_in_grown : keep_out_shrunk;
7,280✔
185
  const vector<vector<std::reference_wrapper<const ring_type_fp>>>& all_rings = get_all_rings(poly_to_search);
7,280✔
186
  const auto& all_segments = get_all_segments(all_rings);
7,280✔
187
  segment_tree::SegmentTree x(all_segments);
7,280✔
188
  tree = std::move(x);
7,280✔
189

190
  for (auto av : all_vertices) {
28,284✔
191
    sort(av.begin(), av.end());
27,920✔
192
    av.erase(std::unique(av.begin(), av.end()), av.end());
27,920✔
193
  }
27,920✔
194
}
7,280!
195

196
boost::optional<MPRingIndices> inside_multipolygon(const point_type_fp& p,
222,522✔
197
                                                   const multi_polygon_type_fp& mp) {
4,227,918✔
198
  for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {
8,596,120✔
199
    const auto& poly = mp[poly_index];
4,450,680✔
200
    if (point_in_ring(p, poly.outer())) {
4,450,680✔
201
      // Might be part of this shape but only if the point isn't in
202
      // the inners.
203
      MPRingIndices ring_indices{{poly_index, {0}}};
320,544!
204
      for (size_t inner_index = 0; inner_index < poly.inners().size(); inner_index++) {
305,720✔
205
        const auto& inner = poly.inners()[inner_index];
720✔
206
        if (!point_in_ring(p, inner)) {
720✔
207
          // We'll have to make sure not to cross this inner.
208
          ring_indices.back().second.emplace_back(inner_index+1);
440✔
209
        } else {
418✔
210
          break; // We're inside one of the inners so give up.
266✔
211
        }
266✔
212
      }
684✔
213
      if (ring_indices.back().second.size() == poly.inners().size() + 1) {
305,280✔
214
        // We never hit the break so we're inside this shape so we're
215
        // done.
216
        return {ring_indices};
305,000✔
217
      }
289,750✔
218
      // We're inside the outer but also inside an inner!  There might
219
      // be another shape inside this hold so we'll ignore this one
220
      // and keep searching.
221
    }
305,280✔
222
  }
4,228,146✔
223
  return boost::none;
4,145,440✔
224
}
4,273,710✔
225

226
boost::optional<MPRingIndices> outside_multipolygon(const point_type_fp& p,
178,052✔
227
                                                    const multi_polygon_type_fp& mp) {
3,382,988✔
228
  MPRingIndices ring_indices;
3,561,040✔
229
  for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {
6,939,920✔
230
    const auto& poly = mp[poly_index];
3,541,320✔
231
    if (point_in_ring(p, poly.outer())) {
3,541,320✔
232
      // We're inside the outer, maybe we're in an inner?  If not, we
233
      // aren't outside at all and we'll just give up.
234
      bool in_any_inner = false;
162,690✔
235
      for (size_t i = 0; i < poly.inners().size(); i++) {
162,880✔
236
        const auto& inner = poly.inners()[i];
440✔
237
        if (point_in_ring(p, inner)) {
440✔
238
          in_any_inner = true;
240✔
239
          ring_indices.emplace_back(poly_index, vector<size_t>{i+1});
240✔
240
          break;
240✔
241
        }
228✔
242
      }
418✔
243
      if (!in_any_inner) {
154,558✔
244
        // We're inside the outer but not in any of the inners, so
245
        // we're in the shape, but we want to be outside the shape, so
246
        // we've failed.
247
        return boost::none;
162,440✔
248
      }
154,318✔
249
    } else {
3,209,708✔
250
      // We need to keep out of this outer.
251
      ring_indices.emplace_back(poly_index, vector<size_t>{0});
3,378,640✔
252
      // No need to examine the inners which we can't possibly be inside.
253
    }
3,209,708✔
254
  }
3,364,254✔
255
  return {ring_indices};
3,398,600✔
256
}
3,561,040✔
257

258
boost::optional<RingIndices> inside_multipolygons(
7,596✔
259
    const point_type_fp& p,
260
    const nested_multipolygon_type_fp& mp) {
144,324✔
261
  for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {
3,317,240✔
262
    const auto& poly = mp[poly_index];
3,311,400✔
263
    boost::optional<MPRingIndices> inside_mp = inside_multipolygon(p, poly.outer());
3,311,400✔
264
    if (inside_mp) {
3,311,400✔
265
      // Might be part of this shape but only if the point isn't in
266
      // the inners.
267
      RingIndices ring_indices{{poly_index, {{0, *inside_mp}}}};
262,154!
268
      for (size_t inner_index = 0; inner_index < poly.inners().size(); inner_index++) {
1,790,400✔
269
        const auto& inner = poly.inners()[inner_index];
1,644,320✔
270
        auto outside_mp = outside_multipolygon(p, inner);
1,644,320✔
271
        if (outside_mp) {
1,644,320✔
272
          // We'll have to make sure not to cross this inner.
273
          ring_indices.back().second.emplace_back(inner_index+1, *outside_mp);
1,562,440!
274
        } else {
1,484,318✔
275
          break; // We're inside one of the inners so give up.
77,786✔
276
        }
77,786✔
277
      }
1,644,320✔
278
      if (ring_indices.back().second.size() == poly.inners().size() + 1) {
227,960✔
279
        // We never hit the break so we're inside this shape so we're
280
        // done.
281
        return {ring_indices};
146,080✔
282
      }
138,776✔
283
      // We're inside the outer but also inside an inner!  It might
284
      // be an outer in an inner so we'll ignore this one and keep
285
      // searching.
286
    }
227,960✔
287
  }
3,311,400✔
288
  return boost::none;
5,840✔
289
}
189,916!
290

291
boost::optional<RingIndices> outside_multipolygons(
3,850✔
292
    const point_type_fp& p,
293
    const nested_multipolygon_type_fp& mp) {
73,150✔
294
  RingIndices ring_indices;
77,000✔
295
  for (size_t poly_index = 0; poly_index < mp.size(); poly_index++) {
1,989,720✔
296
    const auto& poly = mp[poly_index];
1,916,240✔
297
    auto outside_mp = outside_multipolygon(p, poly.outer());
1,916,240✔
298
    if (!outside_mp) {
1,916,240✔
299
      // We're inside the outer, maybe we're in an inner?  If not, we
300
      // aren't outside at all and we'll just give up.
301
      bool in_any_inner = false;
133,446✔
302
      for (size_t inner_index = 0; inner_index < poly.inners().size(); inner_index++) {
1,142,080✔
303
        const auto& inner = poly.inners()[inner_index];
1,138,560✔
304
        auto inside_mp = inside_multipolygon(p, inner);
1,138,560✔
305
        if (inside_mp) {
1,138,560✔
306
          in_any_inner = true;
76,840✔
307
          ring_indices.emplace_back(poly_index, vector<pair<size_t, MPRingIndices>>{{inner_index + 1, *inside_mp}});
84,524!
308
          break;
76,840!
309
        }
72,998✔
310
      }
1,134,718✔
311
      if (!in_any_inner) {
80,184✔
312
        // We're inside the outer but not in any of the inners, so
313
        // we're in the shape, but we want to be outside the shape, so
314
        // we've failed.
315
        return boost::none;
3,520!
316
      }
3,344✔
317
    } else {
1,744,086✔
318
      // We need to keep out of this outer.
319
      ring_indices.emplace_back(poly_index, vector<pair<size_t, MPRingIndices>>{{0, *outside_mp}});
2,019,468!
320
    }
1,744,086✔
321
  }
1,916,240✔
322
  return {ring_indices};
73,480✔
323
}
172,636✔
324

325
/* Given a point, determine if the point is in the search surface.  If
326
   so, return a non-default value, otherwise default value.  If two
327
   points return the same value, there is a path between them in the
328
   surface.  If not then there cannot be a path between them.  The
329
   value will actually be a vector of size_t that indicates which
330
   rings in the stored polygon should be used for the generated points
331
   in the path and also for the collision detection. */
332
const boost::optional<SearchKey>& PathFindingSurface::in_surface(point_type_fp p) const {
2,293,680✔
333
  auto memoized_result = point_in_surface_memo.find(p);
2,293,680✔
334
  if (memoized_result != point_in_surface_memo.cend()) {
2,293,680✔
335
    return memoized_result->second;
2,064,760✔
336
  }
1,961,522✔
337
  boost::optional<RingIndices> maybe_ring_indices;
228,920✔
338
  if (total_keep_in_grown) {
228,920✔
339
    maybe_ring_indices = inside_multipolygons(p, *total_keep_in_grown);
166,820✔
340
  } else {
144,324✔
341
    maybe_ring_indices = outside_multipolygons(p, keep_out_shrunk);
84,524✔
342
  }
73,150✔
343
  if (!maybe_ring_indices) {
228,920✔
344
    return point_in_surface_memo.emplace(p, boost::none).first->second;
9,360✔
345
  }
8,892✔
346
  const auto& ring_indices = *maybe_ring_indices;
219,560✔
347
  // Check if this one is already in the cache.
348
  const auto& find_result = ring_indices_lookup.find(std::cref(ring_indices));
219,560✔
349
  if (find_result != ring_indices_lookup.cend()) {
219,560✔
350
    // Found in the cache so we can use that.
351
    return point_in_surface_memo.emplace(p, find_result->second).first->second;
194,120✔
352
  }
184,414✔
353
  // Not found so we need to add it to the cache.
354
  ring_indices_cache.push_back(ring_indices);
25,440✔
355
  ring_indices_lookup.emplace(ring_indices_cache.back(), ring_indices_cache.size()-1);
25,440✔
356
  return point_in_surface_memo.emplace(p, ring_indices_cache.size()-1).first->second;
25,440!
357
}
220,028✔
358

359
// Return true if this edge from a to b is part of the path finding surface.
360
bool PathFindingSurface::in_surface(
131,162✔
361
    const point_type_fp& a, const point_type_fp& b) const {
2,492,078✔
362
  if (b < a) {
2,623,240✔
363
    return in_surface(b, a);
250,600✔
364
  }
238,070✔
365
  const auto key = make_pair(a, b);
2,372,640✔
366
  auto memoized_result = edge_in_surface_memo.find(key);
2,372,640✔
367
  if (memoized_result != edge_in_surface_memo.cend()) {
2,372,640✔
368
    return memoized_result->second;
1,458,280✔
369
  }
1,385,366✔
370
  auto found_intersection = tree.intersects(a, b);
914,360✔
371
  edge_in_surface_memo.emplace(key, !found_intersection);
914,360✔
372
  return !found_intersection;
914,360✔
373
}
2,254,008✔
374

375
// Return a path from the start to the current.  Always return at
376
// least two points.
377
linestring_type_fp build_path(
14✔
378
    point_type_fp current,
379
    const unordered_map<point_type_fp, point_type_fp>& came_from) {
266✔
380
  linestring_type_fp result;
280✔
381
  while (came_from.count(current)) {
1,000✔
382
    result.push_back(current);
720✔
383
    current = came_from.at(current);
720✔
384
  }
684✔
385
  result.push_back(current);
280✔
386
  bg::reverse(result);
280✔
387
  return result;
280✔
388
}
266✔
389

390
optional<linestring_type_fp> PathFindingSurface::find_path(
72,210✔
391
    const point_type_fp& start, const point_type_fp& goal,
392
    const coordinate_type_fp& max_path_length,
393
    const boost::optional<size_t>& max_tries,
394
    SearchKey search_key) const {
1,371,990✔
395
  if (max_tries && *max_tries == 0) {
1,444,200✔
396
    return boost::none;
×
397
  }
398
  PathFindingSurfaceWithTries pfs_with_tries(*this, max_tries);
1,444,200✔
399
  return pfs_with_tries.find_path(start, goal, max_path_length, search_key);
1,444,200✔
400
}
1,371,990✔
401

402
optional<linestring_type_fp> PathFindingSurface::find_path(
73,828✔
403
    const point_type_fp& start, const point_type_fp& goal,
404
    const coordinate_type_fp& max_path_length,
405
    const boost::optional<size_t>& max_tries) const {
1,402,732✔
406
  if (max_tries && *max_tries == 0) {
1,476,560✔
407
    return boost::none;
40✔
408
  }
38✔
409
  PathFindingSurfaceWithTries pfs_with_tries(*this, max_tries);
1,476,520✔
410

411
  auto ring_indices = in_surface(start);
1,476,520✔
412
  if (!ring_indices) {
1,476,520✔
413
    // Start is not in the surface.
414
    return boost::none;
747,720✔
415
  }
710,334✔
416
  if (ring_indices != in_surface(goal)) {
765,240✔
417
    // Either goal is not in the surface or it's in a region unreachable by start.
418
    return boost::none;
529,400✔
419
  }
502,930✔
420
  return pfs_with_tries.find_path(start, goal, max_path_length, *ring_indices);
199,400✔
421
}
692,360✔
422

423
const std::vector<point_type_fp>&
424
PathFindingSurface::vertices(SearchKey search_key) const {
1,520,320✔
425
  auto memoized_result = vertices_memo.find(search_key);
1,520,320✔
426
  if (memoized_result != vertices_memo.cend()) {
1,520,320✔
427
    return memoized_result->second;
1,516,400✔
428
  }
1,440,580✔
429
  std::vector<point_type_fp> ret;
3,920✔
430
  const auto& vertices = all_vertices;
3,920✔
431
  const auto& ring_indices = ring_indices_cache.at(search_key);
3,920✔
432
  for (size_t poly_index = 0; poly_index < ring_indices.size() ; poly_index++) {
26,720✔
433
    // This is the poly to look at.
434
    const auto& poly_ring_index = ring_indices[poly_index];
22,800✔
435
    // These are the vertices for that poly.
436
    const auto& poly_vertices = vertices[poly_ring_index.first];
22,800✔
437
    for (size_t ring_index = 0; ring_index < poly_ring_index.second.size(); ring_index++) {
66,360✔
438
      const auto& ring_ring_index = poly_ring_index.second[ring_index];
43,560✔
439
      const auto& ring_vertices = poly_vertices[ring_ring_index.first];
43,560✔
440
      ret.insert(ret.cend(), ring_vertices.cbegin(), ring_vertices.cend());
43,560✔
441
    }
41,382✔
442
  }
21,660✔
443
  return vertices_memo.emplace(search_key, ret).first->second;
3,920✔
444
}
1,444,500✔
445

446
optional<linestring_type_fp> PathFindingSurfaceWithTries::find_path(
82,180✔
447
    const point_type_fp& start, const point_type_fp& goal,
448
    const coordinate_type_fp& max_path_length,
449
    SearchKey search_key) {
1,561,420✔
450
  // Connect if a direct connection is possible.  This also takes care
451
  // of the case where start == goal.
452
  try {
1,643,600✔
453
    if (in_surface(start, goal)) {
1,643,600✔
454
      decrement_tries();
124,160✔
455
      if (bg::comparable_distance(start, goal) < max_path_length * max_path_length) {
124,160✔
456
        // in_surface builds up some structures that are only efficient if
457
        // we're doing many tries.
458
        return {{start, goal}};
80,720✔
459
      } else {
76,684✔
460
        // If the straight line was too long then there is no way to connect.
461
        return boost::none;
43,440✔
462
      }
41,268✔
463
    }
117,952✔
464
  } catch (GiveUp g) {
1,561,420!
465
    return boost::none;
×
466
  }
×
467
  // Do astar.
468
  priority_queue<pair<coordinate_type_fp, point_type_fp>,
1,519,440✔
469
                 vector<pair<coordinate_type_fp, point_type_fp>>,
1,443,468✔
470
                 std::greater<pair<coordinate_type_fp, point_type_fp>>> open_set;
1,519,440✔
471
  open_set.emplace(bg::distance(start, goal), start);
1,519,440✔
472
  unordered_set<point_type_fp> closed_set;
1,519,440✔
473
  unordered_map<point_type_fp, point_type_fp> came_from;
1,519,440✔
474
  unordered_map<point_type_fp, coordinate_type_fp> g_score; // Empty should be considered infinity.
1,519,440✔
475
  g_score[start] = 0;
1,519,440✔
476
  while (!open_set.empty()) {
1,520,600✔
477
    const auto current = open_set.top().second;
1,520,600✔
478
    open_set.pop();
1,520,600✔
479
    if (current == goal) {
1,520,600✔
480
      // We're done.
481
      return boost::make_optional(build_path(current, came_from));
280✔
482
    }
266✔
483
    if (closed_set.count(current) > 0) {
1,520,320✔
484
      // Skip this because we already "removed it", sort of.
485
      continue;
×
486
    }
487
    try {
1,520,320✔
488
      auto current_neighbors = neighbors(
1,596,336✔
489
          start, goal,
1,444,304✔
490
          max_path_length - g_score.at(current),
1,520,320✔
491
          search_key,
1,444,304✔
492
          current);
1,444,304✔
493
      for (const auto& neighbor : current_neighbors) {
1,520,684✔
494
        const auto tentative_g_score = g_score.at(current) + bg::distance(current, neighbor);
7,280✔
495
        if (g_score.count(neighbor) == 0 || tentative_g_score < g_score.at(neighbor)) {
7,280✔
496
          // This path to neighbor is better than any previous one.
497
          came_from[neighbor] = current;
2,560✔
498
          g_score[neighbor] = tentative_g_score;
2,560✔
499
          open_set.emplace(tentative_g_score + bg::distance(neighbor, goal), neighbor);
2,560✔
500
        }
2,432✔
501
      }
6,916✔
502
    } catch (GiveUp g) {
1,520,262!
503
      return boost::none;
1,519,160✔
504
    }
1,519,160✔
505
    // Because we can't delete from the open_set, we'll just marked
506
    // items as closed and ignore them later.
507
    closed_set.insert(current);
1,160✔
508
  }
1,102✔
UNCOV
509
  return boost::none;
×
510
}
1,671,384✔
511

512
} //namespace path_finding
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc