19811714133

Committed 24 Nov 2025 02:34PM UTC coverage: 59.007% (-15.0%) from 74.006%

Build # 19811714133

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #730 from mar0x/master

Enable windows build in CI

Run Details

2199 of 4409 branches covered (49.88%)

Branch coverage included in aggregate %.

1902 of 2541 relevant lines covered (74.85%)

117318.67 hits per line

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

86.05

/backtrack.cpp

#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_map>

#include "geometry.hpp"
#include "bg_operators.hpp"

#include "backtrack.hpp"

namespace backtrack {

using std::vector;
using std::pair;
using std::tuple;
using std::tie;
using std::unordered_map;
using std::set;
using std::make_pair;
using std::priority_queue;
using std::max;
using std::sort;
using std::get;
using std::greater;

struct VertexDegree {
  size_t in;
  size_t out;
  size_t bidi;

  // Returns true if an edge pointing into here would decrease the
  // number of eulerian paths needed.
  bool can_end() const {
    if (out > in + bidi) {
      // There are more out paths than all the possible in paths so this
      // must be a start of some path.
      return true;
    }
    if (in > out + bidi) {
      // We already have too many paths inward.  More would be worse.
      return false;
    }
    // By this point, out - in <= bidi and out - in >= -bidi so
    // abs(out-in) <= bidi If number of unmatched bidi edges is odd then
    // this can be an end.  (bidi - abs(out - in)) % 2 works but we
    // can avoid the abs by just addings.
    return (bidi + out + in) % 2 == 1;
  }

  // Returns true if an edge pointing out of here would decrease the
  // number of eulerian paths needed.
  bool can_start() const {
    if (out > in + bidi) {
      // There are more out paths than all the possible in paths so this
      // can't be the end of some path.
      return false;
    }
    if (in > out + bidi) {
      // Too many inward paths so we could use with another outward path.
      return true;
    }
    // By this point, out - in <= bidi and out - in >= -bidi so
    // abs(out-in) <= bidi If number of unmatched bidi edges is odd then
    // this can be an end.  (bidi - abs(out - in)) % 2 works but we
    // can avoid the abs by just addings.
    return (bidi + out + in) % 2 == 1;
  }
};

// Use Dijkstra's algorithm to find the shortest path from the start
// vertex to any of the vertices in the set of possible end vertices.
// The result is the length of a path and the vector of linestrings
// that make a path from the start to the end vertex, in the order
// that they should be used, in the direction that they should be
// used.
static inline pair<long double, vector<pair<linestring_type_fp, bool>>> find_nearest_vertex(
    const unordered_map<point_type_fp, vector<pair<linestring_type_fp, bool>>>& graph,
    point_type_fp start,
    const unordered_map<point_type_fp, VertexDegree>& vertex_degrees,
    const double g1_speed,
    const double up_time,
    const double g0_speed,
    const double down_time,
    const double in_per_sec) {
  if (!vertex_degrees.at(start).can_start()) {
    // Starting from here isn't useful.
    return {0, {}};
  }
  // unordered_map from vertex to the best-so-far distance to get to the
  // vertex, along with the edge that gets you there.  The edge
  // might be reversed.
  unordered_map<point_type_fp, pair<long double, pair<linestring_type_fp, bool>>> distances;
  distances[start] = make_pair(0, make_pair(linestring_type_fp{}, true));
  priority_queue<pair<long double, point_type_fp>,
                 vector<pair<long double, point_type_fp>>,
                 greater<pair<long double, point_type_fp>>> to_search;
  set<point_type_fp> done;
  to_search.push(make_pair(0, start));
  while (to_search.size() > 0) {
    auto current_vertex = to_search.top().second;
    to_search.pop();
    if (start != current_vertex &&
        vertex_degrees.count(current_vertex) > 0 &&
        vertex_degrees.at(current_vertex).can_end()) {
      // Found the nearest solution.  Return the edges in the right
      // order with the right directionality.
      vector<pair<linestring_type_fp, bool>> reverse_path;
      for (auto v = current_vertex; v != start;) {
        const auto& e = distances.at(v).second;
        reverse_path.emplace_back(e);
        if (e.second && v == e.first.front()) {
          // Bidi edge and it was reversed.
          std::reverse(reverse_path.back().first.begin(), reverse_path.back().first.end());
        }
        v = reverse_path.back().first.front();
      }
      std::reverse(reverse_path.begin(), reverse_path.end());
      return {distances[current_vertex].first, reverse_path};
    }
    if (done.count(current_vertex)) {
      continue; // We already completed this one.
    }
    for (const auto& edge : graph.at(current_vertex)) {
      // Get end that isn't the current_vertex.
      point_type_fp new_vertex = edge.first.back();
      if (edge.second && current_vertex == new_vertex) {
        // Reversible and this was the wrong end.
        new_vertex = edge.first.front();
      }
      if (done.count(new_vertex)) {
        continue;
      }
      long double new_distance = distances[current_vertex].first + bg::length(edge.first);
      const auto max_manhattan = max(abs(new_vertex.x() - start.x()), abs(new_vertex.y() - start.y()));
      double time_with_backtrack = new_distance / g1_speed;
      double time_without_backtrack = up_time + max_manhattan / g0_speed  + down_time;
      double time_saved = time_without_backtrack - time_with_backtrack;
      if (time_saved < 0 || new_distance / time_saved > in_per_sec) {
        continue; // This is already too far away to be useful.
      }
      const auto old_distance_pair = distances.find(new_vertex);
      if (old_distance_pair == distances.cend() || old_distance_pair->second.first > new_distance) {
        distances[new_vertex] = make_pair(new_distance, edge);
      }
      to_search.push(make_pair(distances[new_vertex].first, new_vertex));
    }
    done.insert(current_vertex);
  }
  return {0, {}};
}

// Find paths in the input that, if doubled so that they could be
// traversed twice, would decrease the milling time overall.  The
// input is a list of paths and the reversibility of each one.  The
// output is just the paths that need to be added to decrease the
// overall milling time.
vector<pair<linestring_type_fp, bool>> backtrack(
    const vector<pair<linestring_type_fp, bool>>& paths,
    const double g1_speed, const double up_time, const double g0_speed, const double down_time,
    const double in_per_sec) {
  if (in_per_sec == 0) {
    return {};
  }
  // Convert the paths structure to a unordered_map from vector to edges that
  // meet there.
  unordered_map<point_type_fp, vector<pair<linestring_type_fp, bool>>> graph;
  // Find the in, out, and bidi degree of all vertices.  We can't just
  // use the graph because we will modify this as we go.
  unordered_map<point_type_fp, VertexDegree> vertex_degrees;
  for (const auto& ls : paths) {
    graph[ls.first.front()].push_back(ls);
    graph[ls.first.back()]; // Create this element even if there are no edges from it.
    if (ls.second) {
      // bi-directional
      graph[ls.first.back()].push_back(ls);
      vertex_degrees[ls.first.front()].bidi++;
      vertex_degrees[ls.first.back()].bidi++;
    } else {
      // directional
      vertex_degrees[ls.first.front()].out++;
      vertex_degrees[ls.first.back()].in++;
    }
  }

  vector<pair<linestring_type_fp, bool>> backtracks;
  // best_backtracks stores the total length, the start, the end,
  // and a list of paths to take to get there, in the right order
  // and with the right directionality.
  vector<pair<long double,
              vector<pair<linestring_type_fp, bool>>>> best_backtracks;

  // For each odd-degree vertex, find the nearest odd-degree vertex
  // using the distance function on the edge.
  for (const auto& v : vertex_degrees) {
    // Get the length and path to the nearest element.
    // find_nearest_vertex returns 0 if there is none that is close
    // enough or if the start vertex is not can_start(), that is, it
    // has so many paths out already that it shouldn't get anymore.
    auto length_and_path = find_nearest_vertex(graph, v.first, vertex_degrees, g1_speed, up_time, g0_speed, down_time, in_per_sec);
    if (length_and_path.first > 0) {
      best_backtracks.push_back(length_and_path);
    }
  }
  // Now sort so that the shortest backtracks are first.
  make_heap(best_backtracks.begin(), best_backtracks.end(), greater<>());
  // Select backtracks one-at-a-time, best first.  Every time that a
  // backtrack is used, we may need to recalculate the nearest vertex.
  // Because adding a backtrack can only possibly remove the can_start
  // or can_end, there is no possibility that the new search will find
  // an even shorter backtrack so we don't need to start from the
  // beginning.
  while (best_backtracks.size() > 0) {
    const auto& i = best_backtracks.cbegin();
    if (vertex_degrees[i->second.front().first.front()].can_start() &&
        vertex_degrees[i->second.back().first.back()].can_end()) {
      for (const auto& p : i->second) {
        backtracks.emplace_back(p);
      }
      if (i->second.front().second) {
        // Start is reversible.
        vertex_degrees[i->second.front().first.front()].bidi++;
      } else {
        // Start is not reversible.
        vertex_degrees[i->second.front().first.front()].out++;
      }
      if (i->second.back().second) {
        // End is reversible.
        vertex_degrees[i->second.back().first.back()].bidi++;
      } else {
        // End is not reversible.
        vertex_degrees[i->second.back().first.back()].in++;
      }
    }
    // Because this vertex used to have a backtrack, it might still
    // have one so look for it.
    auto length_and_path = find_nearest_vertex(
        graph, i->second.front().first.front(), vertex_degrees, g1_speed,
        up_time, g0_speed, down_time, in_per_sec);
    // Now we can remove the used one and perhaps put a new one instead.
    pop_heap(best_backtracks.begin(), best_backtracks.end(), greater<>());
    best_backtracks.pop_back();
    if (length_and_path.first > 0) {
      best_backtracks.push_back(length_and_path);
      push_heap(best_backtracks.begin(), best_backtracks.end(), greater<>());
    }
  }
  return backtracks;
}

} // namespace backtrack

1	#include <vector>
2	#include <utility>
3	#include <algorithm>
4	#include <unordered_map>
5
6	#include "geometry.hpp"
7	#include "bg_operators.hpp"
8
9	#include "backtrack.hpp"
10
11	namespace backtrack {
12
13	using std::vector;
14	using std::pair;
15	using std::tuple;
16	using std::tie;
17	using std::unordered_map;
18	using std::set;
19	using std::make_pair;
20	using std::priority_queue;
21	using std::max;
22	using std::sort;
23	using std::get;
24	using std::greater;
25
26	struct VertexDegree {
27	size_t in;
28	size_t out;
29	size_t bidi;
30
31	// Returns true if an edge pointing into here would decrease the
32	// number of eulerian paths needed.
33	bool can_end() const {
34	if (out > in + bidi) {	598✔
35	// There are more out paths than all the possible in paths so this
36	// must be a start of some path.
37	return true;
38	}
39	if (in > out + bidi) {	596!
40	// We already have too many paths inward. More would be worse.
41	return false;
42	}
43	// By this point, out - in <= bidi and out - in >= -bidi so
44	// abs(out-in) <= bidi If number of unmatched bidi edges is odd then
45	// this can be an end. (bidi - abs(out - in)) % 2 works but we
46	// can avoid the abs by just addings.
47	return (bidi + out + in) % 2 == 1;	596✔
48	}
49
50	// Returns true if an edge pointing out of here would decrease the
51	// number of eulerian paths needed.
52	bool can_start() const {
53	if (out > in + bidi) {	362!
54	// There are more out paths than all the possible in paths so this
55	// can't be the end of some path.
56	return false;
57	}
58	if (in > out + bidi) {	360✔
59	// Too many inward paths so we could use with another outward path.
60	return true;
61	}
62	// By this point, out - in <= bidi and out - in >= -bidi so
63	// abs(out-in) <= bidi If number of unmatched bidi edges is odd then
64	// this can be an end. (bidi - abs(out - in)) % 2 works but we
65	// can avoid the abs by just addings.
66	return (bidi + out + in) % 2 == 1;	356✔
67	}
68	};
69
70	// Use Dijkstra's algorithm to find the shortest path from the start
71	// vertex to any of the vertices in the set of possible end vertices.
72	// The result is the length of a path and the vector of linestrings
73	// that make a path from the start to the end vertex, in the order
74	// that they should be used, in the direction that they should be
75	// used.
76	static inline pair<long double, vector<pair<linestring_type_fp, bool>>> find_nearest_vertex(	262✔
77	const unordered_map<point_type_fp, vector<pair<linestring_type_fp, bool>>>& graph,
78	point_type_fp start,
79	const unordered_map<point_type_fp, VertexDegree>& vertex_degrees,
80	const double g1_speed,
81	const double up_time,
82	const double g0_speed,
83	const double down_time,
84	const double in_per_sec) {
85	if (!vertex_degrees.at(start).can_start()) {	257✔
86	// Starting from here isn't useful.
87	return {0, {}};	158✔
88	}
89	// unordered_map from vertex to the best-so-far distance to get to the
90	// vertex, along with the edge that gets you there. The edge
91	// might be reversed.
92	unordered_map<point_type_fp, pair<long double, pair<linestring_type_fp, bool>>> distances;
93	distances[start] = make_pair(0, make_pair(linestring_type_fp{}, true));	208!
94	priority_queue<pair<long double, point_type_fp>,
95	vector<pair<long double, point_type_fp>>,
96	greater<pair<long double, point_type_fp>>> to_search;
97	set<point_type_fp> done;
98	to_search.push(make_pair(0, start));	104!
99	while (to_search.size() > 0) {	640✔
100	auto current_vertex = to_search.top().second;	636✔
101	to_search.pop();	636✔
102	if (start != current_vertex &&	636✔
103	vertex_degrees.count(current_vertex) > 0 &&	1,167✔
104	vertex_degrees.at(current_vertex).can_end()) {
105	// Found the nearest solution. Return the edges in the right
106	// order with the right directionality.
107	vector<pair<linestring_type_fp, bool>> reverse_path;
108	for (auto v = current_vertex; v != start;) {	295✔
109	const auto& e = distances.at(v).second;	195✔
110	reverse_path.emplace_back(e);	195!
111	if (e.second && v == e.first.front()) {	195✔
112	// Bidi edge and it was reversed.
113	std::reverse(reverse_path.back().first.begin(), reverse_path.back().first.end());	111✔
114	}
115	v = reverse_path.back().first.front();	195✔
116	}
117	std::reverse(reverse_path.begin(), reverse_path.end());	100!
118	return {distances[current_vertex].first, reverse_path};
119	}	100✔
120	if (done.count(current_vertex)) {	79✔
121	continue; // We already completed this one.	79✔
122	}
123	for (const auto& edge : graph.at(current_vertex)) {	1,741✔
124	// Get end that isn't the current_vertex.
125	point_type_fp new_vertex = edge.first.back();	1,284✔
126	if (edge.second && current_vertex == new_vertex) {	1,284✔
127	// Reversible and this was the wrong end.
128	new_vertex = edge.first.front();	615✔
129	}
130	if (done.count(new_vertex)) {	427✔
131	continue;	427✔
132	}
133	long double new_distance = distances[current_vertex].first + bg::length(edge.first);	857✔
134	const auto max_manhattan = max(abs(new_vertex.x() - start.x()), abs(new_vertex.y() - start.y()));	857✔
135	double time_with_backtrack = new_distance / g1_speed;	857✔
136	double time_without_backtrack = up_time + max_manhattan / g0_speed + down_time;	857✔
137	double time_saved = time_without_backtrack - time_with_backtrack;	857✔
138	if (time_saved < 0 \|\| new_distance / time_saved > in_per_sec) {	857!
139	continue; // This is already too far away to be useful.	×
140	}
141	const auto old_distance_pair = distances.find(new_vertex);
142	if (old_distance_pair == distances.cend() \|\| old_distance_pair->second.first > new_distance) {	1,038!
143	distances[new_vertex] = make_pair(new_distance, edge);	676✔
144	}
145	to_search.push(make_pair(distances[new_vertex].first, new_vertex));	857!
146	}
147	done.insert(current_vertex);	457!
148	}
149	return {0, {}};	4✔
150	}
151
152	// Find paths in the input that, if doubled so that they could be
153	// traversed twice, would decrease the milling time overall. The
154	// input is a list of paths and the reversibility of each one. The
155	// output is just the paths that need to be added to decrease the
156	// overall milling time.
157	vector<pair<linestring_type_fp, bool>> backtrack(	15✔
158	const vector<pair<linestring_type_fp, bool>>& paths,
159	const double g1_speed, const double up_time, const double g0_speed, const double down_time,
160	const double in_per_sec) {
161	if (in_per_sec == 0) {	15!
162	return {};	×
163	}
164	// Convert the paths structure to a unordered_map from vector to edges that
165	// meet there.
166	unordered_map<point_type_fp, vector<pair<linestring_type_fp, bool>>> graph;
167	// Find the in, out, and bidi degree of all vertices. We can't just
168	// use the graph because we will modify this as we go.
169	unordered_map<point_type_fp, VertexDegree> vertex_degrees;
170	for (const auto& ls : paths) {	232✔
171	graph[ls.first.front()].push_back(ls);	217!
172	graph[ls.first.back()]; // Create this element even if there are no edges from it.
173	if (ls.second) {	217✔
174	// bi-directional
175	graph[ls.first.back()].push_back(ls);	206!
176	vertex_degrees[ls.first.front()].bidi++;	206!
177	vertex_degrees[ls.first.back()].bidi++;	206✔
178	} else {
179	// directional
180	vertex_degrees[ls.first.front()].out++;	11!
181	vertex_degrees[ls.first.back()].in++;	11✔
182	}
183	}
184
185	vector<pair<linestring_type_fp, bool>> backtracks;
186	// best_backtracks stores the total length, the start, the end,
187	// and a list of paths to take to get there, in the right order
188	// and with the right directionality.
189	vector<pair<long double,
190	vector<pair<linestring_type_fp, bool>>>> best_backtracks;
191
192	// For each odd-degree vertex, find the nearest odd-degree vertex
193	// using the distance function on the edge.
194	for (const auto& v : vertex_degrees) {	177✔
195	// Get the length and path to the nearest element.
196	// find_nearest_vertex returns 0 if there is none that is close
197	// enough or if the start vertex is not can_start(), that is, it
198	// has so many paths out already that it shouldn't get anymore.
199	auto length_and_path = find_nearest_vertex(graph, v.first, vertex_degrees, g1_speed, up_time, g0_speed, down_time, in_per_sec);	162!
200	if (length_and_path.first > 0) {	162✔
201	best_backtracks.push_back(length_and_path);	73!
202	}
203	}
204	// Now sort so that the shortest backtracks are first.
205	make_heap(best_backtracks.begin(), best_backtracks.end(), greater<>());	15✔
206	// Select backtracks one-at-a-time, best first. Every time that a
207	// backtrack is used, we may need to recalculate the nearest vertex.
208	// Because adding a backtrack can only possibly remove the can_start
209	// or can_end, there is no possibility that the new search will find
210	// an even shorter backtrack so we don't need to start from the
211	// beginning.
212	while (best_backtracks.size() > 0) {	115✔
213	const auto& i = best_backtracks.cbegin();
214	if (vertex_degrees[i->second.front().first.front()].can_start() &&	164✔
215	vertex_degrees[i->second.back().first.back()].can_end()) {
216	for (const auto& p : i->second) {	111✔
217	backtracks.emplace_back(p);	74!
218	}
219	if (i->second.front().second) {	37✔
220	// Start is reversible.
221	vertex_degrees[i->second.front().first.front()].bidi++;	36✔
222	} else {
223	// Start is not reversible.
224	vertex_degrees[i->second.front().first.front()].out++;	1✔
225	}
226	if (i->second.back().second) {	37✔
227	// End is reversible.
228	vertex_degrees[i->second.back().first.back()].bidi++;	36✔
229	} else {
230	// End is not reversible.
231	vertex_degrees[i->second.back().first.back()].in++;	1✔
232	}
233	}
234	// Because this vertex used to have a backtrack, it might still
235	// have one so look for it.
236	auto length_and_path = find_nearest_vertex(
237	graph, i->second.front().first.front(), vertex_degrees, g1_speed,
238	up_time, g0_speed, down_time, in_per_sec);	100!
239	// Now we can remove the used one and perhaps put a new one instead.
240	pop_heap(best_backtracks.begin(), best_backtracks.end(), greater<>());	100✔
241	best_backtracks.pop_back();
242	if (length_and_path.first > 0) {	100✔
243	best_backtracks.push_back(length_and_path);	27!
244	push_heap(best_backtracks.begin(), best_backtracks.end(), greater<>());	27✔
245	}
246	}
247	return backtracks;
248	}	15✔
249
250	} // namespace backtrack

pcb2gcode / pcb2gcode / 19811714133

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

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