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

65.7

/outline_bridges.cpp

/*
 * This file is part of pcb2gcode.
 * 
 * Copyright (C) 2015 Nicola Corna <nicola@corna.info>
 *
 * pcb2gcode is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * pcb2gcode is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with pcb2gcode.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "outline_bridges.hpp"

#include "bg_operators.hpp"
#include <map>
#include <list>
#include <set>

using std::vector;
using std::pair;
using std::set;
using std::map;
using std::list;

namespace boost { namespace geometry { namespace model { namespace d2 {

static inline bool operator<(const list<point_type_fp>::const_iterator& lhs,
                             const list<point_type_fp>::const_iterator& rhs) {
  return *lhs < *rhs;
}
}}}}

namespace outline_bridges {

//This function returns the intermediate point between p0 and p1.
//With position=0 it returns p0, with position=1 it returns p1, with
//values between 0 and 1 it returns the relative position between p0 and p1
static point_type_fp intermediatePoint(point_type_fp p0, point_type_fp p1, double position) {
  return point_type_fp(p0.x() + (p1.x() - p0.x()) * position,
                       p0.y() + (p1.y() - p0.y()) * position);
}

/* Find where to insert a point that is offset distance away from the
 * point at path[index].  Return the index of the newly inserted
 * point. */
static list<point_type_fp>::const_iterator insertPoint(list<point_type_fp>& path, list<point_type_fp>::const_iterator p, double offset) {
  if (offset == 0) {
    return path.insert(p, *p);
  }
  if (offset < 0) {
    // Backwards.
    if (p != path.cbegin()) {
      auto d = bg::distance(*p, *(std::prev(p)));
      if (offset < -d) {
        // Need to go back beyond the point.
        return insertPoint(path, std::prev(p), offset + d);
      } else {
        auto new_point = intermediatePoint(*p, *(std::prev(p)), -offset/d);
        return path.insert(p, new_point);
      }
    } else {
      // index is 0.
      if (*p == path.back()) {
        return insertPoint(path, std::prev(path.cend()), offset);
      } else {
        // Not a ring so just insert at the start. This might make a
        // bridge that is too short in the rare case where the outline
        // isn't a loop.
        return path.insert(path.begin(), *p);
      }
    }
  } else {
    // Forward.
    if (p != std::prev(path.cend())) {
      auto d = bg::distance(*p, *(std::next(p)));
      if (offset > d) {
        // Need to go forward beyond the point.
        return insertPoint(path, std::next(p), offset - d);
      } else {
        auto new_point = intermediatePoint(*p, *std::next(p), offset/d);
        return path.insert(std::next(p), new_point);
      }
    } else {
      // index is at the end.
      if (*p == path.front()) {
        return insertPoint(path, path.cbegin(), offset);
      } else {
        // Not enough room so just insert at the end.
        return path.insert(path.cend(), *p);
      }
    }
  }
}

/* This function takes the segments where the bridges must be built (in the form
 * of set<size_t>, see findBridgeSegments), inserts them in the path and
 * returns an array containing the indexes of each bridge's start.
 */
static vector<size_t> insertBridges(linestring_type_fp& path, const set<size_t>& bridges, double length) {
  list<point_type_fp> path_list(path.cbegin(), path.cend());
  set<pair<list<point_type_fp>::const_iterator, double>> bridge_pointers;
  {
    auto p = path_list.cbegin();
    size_t i = 0;
    for (; p != path_list.cend(); i++, p++) {
      if (bridges.count(i) > 0) {
        bridge_pointers.insert(make_pair(p, bg::distance(path.at(i), path.at(i+1))));
      }
    }
  }

  set<list<point_type_fp>::const_iterator> bridge_segments;
  for(const auto& bridge_pointer : bridge_pointers) {
    //Insert the bridges in the path.
    auto bridge_start = insertPoint(path_list, bridge_pointer.first, bridge_pointer.second/2 - length/2);
    auto bridge_end = insertPoint(path_list, bridge_pointer.first, bridge_pointer.second/2 + length/2);
    for (auto seg = bridge_start; seg != bridge_end; seg++) {
      if (seg == path_list.cend()) {
        seg = path_list.cbegin();
      }
      bridge_segments.insert(seg);
    }
  }

  linestring_type_fp new_path;
  vector<size_t> output;
  {
    int i = 0;
    for (auto p = path_list.cbegin(); p != path_list.cend(); p++, i++) {
      new_path.push_back(*p);
      if (bridge_segments.count(p) > 0) {
        output.push_back(i);
      }
    }
  }
  path = new_path;
  return output;
}

// Computes the distance between the two closest points in the clique.  The
// locations of the elements of the clique are in the locations input.  The two
// points that are closest together are set in closest.
static double min_clique_distance(const set<size_t>& clique,
                                  const map<size_t, point_type_fp>& locations,
                                  vector<size_t>& closest) {
  auto current_score = std::numeric_limits<double>::infinity();
  for (auto i = clique.cbegin(); i != clique.cend(); i++) {
    for (auto j = std::next(i); j != clique.cend(); j++) {
      auto distance = boost::geometry::distance(locations.at(*i), locations.at(*j));
      if (distance < current_score) {
        current_score = distance;
        closest[0] = *i;
        closest[1] = *j;
      }
    }
  }
  return current_score;
}

// Computes the minimum of the distances from the given point to all
// the other points in the clique, not including the same point
// because it would be distance 0.
static inline vector<double> min_distance_to_clique(point_type_fp point,
                                                    const vector<size_t>& excluded_points,
                                                    const set<size_t>& clique,
                                                    const map<size_t, point_type_fp>& locations) {
  vector<double> current_score(excluded_points.size(), std::numeric_limits<double>::infinity());
  for (const auto& clique_point : clique) {
    auto distance = boost::geometry::distance(point, locations.at(clique_point));
    for (size_t i = 0; i < excluded_points.size(); i++) {
      if (clique_point == excluded_points[i]) {
        continue;
      }
      if (distance < current_score[i]) {
        current_score[i] = distance;
      }
    }
  }
  return current_score;
}


/* This function finds the segments for putting bridges.
 *
 * It starts by finding the longest segments.  Then it iteratively
 * picks one segment at a time to try to replace elsewhere, searching
 * for a swap that will maximize the minimum distance between
 * segments.  It continues until no improvement can be made.  It may
 * return fewer than the "number" requested if not enough place can be
 * found to place bridges.
 *
 * Returns the positions in path of the segments that need to be modified.
 */
static set<size_t> findBridgeSegments(const linestring_type_fp& path, size_t number, double length) {
  if (number < 1) {
    return {};
  }

  // All the potential bridge segments and their locations.
  map<size_t, point_type_fp> candidates;
  for (size_t i = 0; i < path.size() - 1; i++) {
    auto current_distance = bg::distance(path.at(i), path.at(i+1));
    if (current_distance < length) {
      continue;
    }
    candidates[i] = intermediatePoint(path.at(i),
                                      path.at(i + 1),
                                      0.5);
  }
  if (candidates.size() < number) {
    // We didn't find enough places to put bridges with the length
    // restriction so try again but this time allow small edges, too.
    candidates.clear();
    for (size_t i = 0; i < path.size() - 1; i++) {
      candidates[i] = intermediatePoint(path.at(i),
                                        path.at(i + 1),
                                        0.5);
    }
  }

  // Make a set of bridges that we will output.  They must be unique.  For now
  // just take the first few.
  set<size_t> output;
  for (const auto& candidate : candidates) {
    if (output.size() >= number) {
      break;
    }
    output.insert(candidate.first);
  }

  vector<size_t> closest = {0,0};
  double best_score;
  // Can we do better?

  // Try to improve the score by moving one of the two closest points.
  do {
    best_score = min_clique_distance(output, candidates, closest);
    bool improvement = false;
    auto new_score = best_score;
    size_t swap_from;
    size_t swap_to;
    for (const auto& candidate : candidates) {
      if (output.count(candidate.first) > 0) {
        // This is already in the output so we can't reuse it.
        continue;
      }
      // What happens to the score if we move one of the closest to this new candidate?
      auto current_score = min_distance_to_clique(candidate.second, closest, output, candidates);
      for (size_t i = 0; i < closest.size(); i++) {
        if (current_score[i] > new_score) {
          swap_from = closest[i];
          swap_to = candidate.first;
          new_score = current_score[i];
          improvement = true;
        }
      }
    }
    if (!improvement) {
      break;
    }
    output.erase(swap_from);
    output.insert(swap_to);
  } while(true);
  return output;
}

vector<size_t> makeBridges(linestring_type_fp& path, size_t number, double length) {
  return insertBridges(path, findBridgeSegments(path, number, length), length);
}

} // namespace outline_bridges

1	/*
2	* This file is part of pcb2gcode.
3	*
4	* Copyright (C) 2015 Nicola Corna <nicola@corna.info>
5	*
6	* pcb2gcode is free software: you can redistribute it and/or modify
7	* it under the terms of the GNU General Public License as published by
8	* the Free Software Foundation, either version 3 of the License, or
9	* (at your option) any later version.
10	*
11	* pcb2gcode is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the GNU General Public License
17	* along with pcb2gcode. If not, see <http://www.gnu.org/licenses/>.
18	*/
19
20	#include "outline_bridges.hpp"
21
22	#include "bg_operators.hpp"
23	#include <map>
24	#include <list>
25	#include <set>
26
27	using std::vector;
28	using std::pair;
29	using std::set;
30	using std::map;
31	using std::list;
32
33	namespace boost { namespace geometry { namespace model { namespace d2 {
34
35	static inline bool operator<(const list<point_type_fp>::const_iterator& lhs,
36	const list<point_type_fp>::const_iterator& rhs) {
37	return lhs < rhs;	190!
38	}
39	}}}}
40
41	namespace outline_bridges {
42
43	//This function returns the intermediate point between p0 and p1.
44	//With position=0 it returns p0, with position=1 it returns p1, with
45	//values between 0 and 1 it returns the relative position between p0 and p1
46	static point_type_fp intermediatePoint(point_type_fp p0, point_type_fp p1, double position) {
47	return point_type_fp(p0.x() + (p1.x() - p0.x()) * position,	32✔
48	p0.y() + (p1.y() - p0.y()) * position);	32✔
49	}
50
51	/* Find where to insert a point that is offset distance away from the
52	* point at path[index]. Return the index of the newly inserted
53	* point. */
54	static list<point_type_fp>::const_iterator insertPoint(list<point_type_fp>& path, list<point_type_fp>::const_iterator p, double offset) {	33✔
55	if (offset == 0) {	33!
56	return path.insert(p, *p);	×
57	}
58	if (offset < 0) {	33✔
59	// Backwards.
60	if (p != path.cbegin()) {	2!
61	auto d = bg::distance(p, (std::prev(p)));	2✔
62	if (offset < -d) {	2!
63	// Need to go back beyond the point.
64	return insertPoint(path, std::prev(p), offset + d);	×
65	} else {
66	auto new_point = intermediatePoint(p, (std::prev(p)), -offset/d);	2✔
67	return path.insert(p, new_point);	2✔
68	}
69	} else {
70	// index is 0.
71	if (*p == path.back()) {
72	return insertPoint(path, std::prev(path.cend()), offset);	×
73	} else {
74	// Not a ring so just insert at the start. This might make a
75	// bridge that is too short in the rare case where the outline
76	// isn't a loop.
77	return path.insert(path.begin(), *p);	×
78	}
79	}
80	} else {
81	// Forward.
82	if (p != std::prev(path.cend())) {	31✔
83	auto d = bg::distance(p, (std::next(p)));
84	if (offset > d) {	30✔
85	// Need to go forward beyond the point.
86	return insertPoint(path, std::next(p), offset - d);	24✔
87	} else {
88	auto new_point = intermediatePoint(p, std::next(p), offset/d);	36✔
89	return path.insert(std::next(p), new_point);	18✔
90	}
91	} else {
92	// index is at the end.
93	if (*p == path.front()) {
94	return insertPoint(path, path.cbegin(), offset);	1✔
95	} else {
96	// Not enough room so just insert at the end.
97	return path.insert(path.cend(), *p);	×
98	}
99	}
100	}
101	}
102
103	/* This function takes the segments where the bridges must be built (in the form
104	* of set<size_t>, see findBridgeSegments), inserts them in the path and
105	* returns an array containing the indexes of each bridge's start.
106	*/
107	static vector<size_t> insertBridges(linestring_type_fp& path, const set<size_t>& bridges, double length) {	3✔
108	list<point_type_fp> path_list(path.cbegin(), path.cend());	3✔
109	set<pair<list<point_type_fp>::const_iterator, double>> bridge_pointers;
110	{
111	auto p = path_list.cbegin();
112	size_t i = 0;	3✔
113	for (; p != path_list.cend(); i++, p++) {	18✔
114	if (bridges.count(i) > 0) {
115	bridge_pointers.insert(make_pair(p, bg::distance(path.at(i), path.at(i+1))));	20!
116	}
117	}
118	}
119
120	set<list<point_type_fp>::const_iterator> bridge_segments;
121	for(const auto& bridge_pointer : bridge_pointers) {	13✔
122	//Insert the bridges in the path.
123	auto bridge_start = insertPoint(path_list, bridge_pointer.first, bridge_pointer.second/2 - length/2);	10!
124	auto bridge_end = insertPoint(path_list, bridge_pointer.first, bridge_pointer.second/2 + length/2);	10!
125	for (auto seg = bridge_start; seg != bridge_end; seg++) {	25✔
126	if (seg == path_list.cend()) {	15✔
127	seg = path_list.cbegin();	1✔
128	}
129	bridge_segments.insert(seg);	15!
130	}
131	}
132
133	linestring_type_fp new_path;
134	vector<size_t> output;
135	{
136	int i = 0;
137	for (auto p = path_list.cbegin(); p != path_list.cend(); p++, i++) {	38✔
138	new_path.push_back(*p);	35!
139	if (bridge_segments.count(p) > 0) {
140	output.push_back(i);	15!
141	}
142	}
143	}
144	path = new_path;
145	return output;	3✔
146	}	×
147
148	// Computes the distance between the two closest points in the clique. The
149	// locations of the elements of the clique are in the locations input. The two
150	// points that are closest together are set in closest.
151	static double min_clique_distance(const set<size_t>& clique,	3✔
152	const map<size_t, point_type_fp>& locations,
153	vector<size_t>& closest) {
154	auto current_score = std::numeric_limits<double>::infinity();
155	for (auto i = clique.cbegin(); i != clique.cend(); i++) {	13✔
156	for (auto j = std::next(i); j != clique.cend(); j++) {	23✔
157	auto distance = boost::geometry::distance(locations.at(i), locations.at(j));	13✔
158	if (distance < current_score) {	13✔
159	current_score = distance;
160	closest[0] = *i;	4✔
161	closest[1] = *j;	4✔
162	}
163	}
164	}
165	return current_score;	3✔
166	}
167
168	// Computes the minimum of the distances from the given point to all
169	// the other points in the clique, not including the same point
170	// because it would be distance 0.
171	static inline vector<double> min_distance_to_clique(point_type_fp point,	×
172	const vector<size_t>& excluded_points,
173	const set<size_t>& clique,
174	const map<size_t, point_type_fp>& locations) {
175	vector<double> current_score(excluded_points.size(), std::numeric_limits<double>::infinity());	×
176	for (const auto& clique_point : clique) {	×
177	auto distance = boost::geometry::distance(point, locations.at(clique_point));	×
178	for (size_t i = 0; i < excluded_points.size(); i++) {	×
179	if (clique_point == excluded_points[i]) {	×
180	continue;	×
181	}
182	if (distance < current_score[i]) {	×
183	current_score[i] = distance;	×
184	}
185	}
186	}
187	return current_score;	×
188	}	×
189
190
191	/* This function finds the segments for putting bridges.
192	*
193	* It starts by finding the longest segments. Then it iteratively
194	* picks one segment at a time to try to replace elsewhere, searching
195	* for a swap that will maximize the minimum distance between
196	* segments. It continues until no improvement can be made. It may
197	* return fewer than the "number" requested if not enough place can be
198	* found to place bridges.
199	*
200	* Returns the positions in path of the segments that need to be modified.
201	*/
202	static set<size_t> findBridgeSegments(const linestring_type_fp& path, size_t number, double length) {	3✔
203	if (number < 1) {	3!
204	return {};	×
205	}
206
207	// All the potential bridge segments and their locations.
208	map<size_t, point_type_fp> candidates;
209	for (size_t i = 0; i < path.size() - 1; i++) {	15✔
210	auto current_distance = bg::distance(path.at(i), path.at(i+1));	12!
211	if (current_distance < length) {	12✔
212	continue;	4✔
213	}
214	candidates[i] = intermediatePoint(path.at(i),	8!
215	path.at(i + 1),	8!
216	0.5);
217	}
218	if (candidates.size() < number) {	3✔
219	// We didn't find enough places to put bridges with the length
220	// restriction so try again but this time allow small edges, too.
221	candidates.clear();
222	for (size_t i = 0; i < path.size() - 1; i++) {	5✔
223	candidates[i] = intermediatePoint(path.at(i),	4!
224	path.at(i + 1),	4!
225	0.5);
226	}
227	}
228
229	// Make a set of bridges that we will output. They must be unique. For now
230	// just take the first few.
231	set<size_t> output;
232	for (const auto& candidate : candidates) {	13✔
233	if (output.size() >= number) {	10!
234	break;
235	}
236	output.insert(candidate.first);	10!
237	}
238
239	vector<size_t> closest = {0,0};	3!
240	double best_score;
241	// Can we do better?
242
243	// Try to improve the score by moving one of the two closest points.
244	do {
245	best_score = min_clique_distance(output, candidates, closest);	3!
246	bool improvement = false;
247	auto new_score = best_score;
248	size_t swap_from;
249	size_t swap_to;
250	for (const auto& candidate : candidates) {	13✔
251	if (output.count(candidate.first) > 0) {	10!
252	// This is already in the output so we can't reuse it.
253	continue;	10✔
254	}
255	// What happens to the score if we move one of the closest to this new candidate?
256	auto current_score = min_distance_to_clique(candidate.second, closest, output, candidates);	×
257	for (size_t i = 0; i < closest.size(); i++) {	×
258	if (current_score[i] > new_score) {	×
259	swap_from = closest[i];	×
260	swap_to = candidate.first;	×
261	new_score = current_score[i];
262	improvement = true;
263	}
264	}
265	}	×
266	if (!improvement) {	3!
267	break;
268	}
269	output.erase(swap_from);
270	output.insert(swap_to);	×
271	} while(true);	×
272	return output;
273	}	3✔
274
275	vector<size_t> makeBridges(linestring_type_fp& path, size_t number, double length) {	3✔
276	return insertBridges(path, findBridgeSegments(path, number, length), length);	6!
277	}
278
279	} // namespace outline_bridges

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