158797379

Build Type

push

github

Committed by GitHub

Commit Message

Merge pull request #467 from eyal0/remove_icoords

Run Details

4565 of 7927 branches covered (57.59%)

Branch coverage included in aggregate %.

103 of 112 new or added lines in 12 files covered. (91.96%)

3 existing lines in 2 files now uncovered.

3130 of 3382 relevant lines covered (92.55%)

239162.62 hits per line

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

83.89

/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 <boost/assign/list_of.hpp>
#include <boost/geometry/algorithms/distance.hpp>
#include <cmath>
#include <queue>
#include <set>
#include <map>

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

//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
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);
}

/* 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.
 */
vector<size_t> insertBridges(linestring_type_fp& path, const set<size_t>& bridges, double length) {
  vector<size_t> chosenSegments(bridges.cbegin(), bridges.cend());
  path.reserve(path.size() + chosenSegments.size() * 2);  //Just to avoid unnecessary reallocations
  std::sort(chosenSegments.begin(), chosenSegments.end()); //Sort it (lower index -> higher index)

  vector<size_t> output;
  for(size_t i = 0; i < chosenSegments.size(); i++) {
    //Each time we insert a bridge all following indexes have a offset of 2, we
    auto segment_index = chosenSegments[i] + 2 * i;
    auto segment_start = path.at(segment_index);
    auto segment_end = path.at(segment_index + 1);
    auto segment_length = bg::distance(segment_start, segment_end);
    //Insert the bridges in the path
    path.insert(path.begin() + segment_index + 1,
                { intermediatePoint(segment_start,
                                    segment_end,
                                    0.5 - (length / segment_length) / 2),
                  intermediatePoint(segment_start,
                                    segment_end,
                                    0.5 + (length / segment_length) / 2) });
    output.push_back(segment_index + 1);    //Add the bridges indexes to output
  }

  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 inline 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 points 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 or until one second has passed.  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.
 */
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);
  }

  // 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);
    best_score = min_clique_distance(output, candidates, closest);
  } while(true);
  return output;
}

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

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 <boost/assign/list_of.hpp>
23	#include <boost/geometry/algorithms/distance.hpp>
24	#include <cmath>
25	#include <queue>
26	#include <set>
27	#include <map>
28
29	using std::vector;
30	using std::pair;
31	using std::set;
32	using std::map;
33
34	//This function returns the intermediate point between p0 and p1.
35	//With position=0 it returns p0, with position=1 it returns p1,
36	//with values between 0 and 1 it returns the relative position between p0 and p1
NEW 37	point_type_fp intermediatePoint(point_type_fp p0, point_type_fp p1, double position) {	×
38	return point_type_fp(p0.x() + (p1.x() - p0.x()) * position,	366✔
39	p0.y() + (p1.y() - p0.y()) * position);	366✔
40	}
41
42	/* This function takes the segments where the bridges must be built (in the form
43	* of set<size_t>, see findBridgeSegments), inserts them in the path and
44	* returns an array containing the indexes of each bridge's start.
45	*/
46	vector<size_t> insertBridges(linestring_type_fp& path, const set<size_t>& bridges, double length) {	57✔
47	vector<size_t> chosenSegments(bridges.cbegin(), bridges.cend());	57✔
48	path.reserve(path.size() + chosenSegments.size() * 2); //Just to avoid unnecessary reallocations	171!
49	std::sort(chosenSegments.begin(), chosenSegments.end()); //Sort it (lower index -> higher index)	57✔
50
51	vector<size_t> output;
52	for(size_t i = 0; i < chosenSegments.size(); i++) {	244✔
53	//Each time we insert a bridge all following indexes have a offset of 2, we
54	auto segment_index = chosenSegments[i] + 2 * i;	65!
55	auto segment_start = path.at(segment_index);	65✔
56	auto segment_end = path.at(segment_index + 1);	65!
57	auto segment_length = bg::distance(segment_start, segment_end);
58	//Insert the bridges in the path
59	path.insert(path.begin() + segment_index + 1,
60	{ intermediatePoint(segment_start,
61	segment_end,
62	0.5 - (length / segment_length) / 2),	130✔
63	intermediatePoint(segment_start,
64	segment_end,
65	0.5 + (length / segment_length) / 2) });	130!
66	output.push_back(segment_index + 1); //Add the bridges indexes to output	65!
67	}
68
69	return output;	57✔
70	}
71
72	// Computes the distance between the two closest points in the clique. The
73	// locations of the elements of the clique are in the locations input. The two
74	// points that are closest together are set in closest.
75	static inline double min_clique_distance(const set<size_t>& clique,	87✔
76	const map<size_t, point_type_fp>& locations,
77	vector<size_t>& closest) {
78	auto current_score = std::numeric_limits<double>::infinity();
79	for (auto i = clique.cbegin(); i != clique.cend(); i++) {	434✔
80	for (auto j = std::next(i); j != clique.cend(); j++) {	897✔
81	auto distance = boost::geometry::distance(locations.at(i), locations.at(j));	550!
82	if (distance < current_score) {	550✔
83	current_score = distance;
84	closest[0] = *i;	151✔
85	closest[1] = *j;	151✔
86	}
87	}
88	}
89	return current_score;	87✔
90	}
91
92	// Computes the minimum of the distances from the given points to all the other
93	// points in the clique, not including the same point because it would be distance 0.
94	static inline vector<double> min_distance_to_clique(point_type_fp point,	987✔
95	const vector<size_t>& excluded_points,
96	const set<size_t>& clique,
97	const map<size_t, point_type_fp>& locations) {
98	vector<double> current_score(excluded_points.size(), std::numeric_limits<double>::infinity());	1,974✔
99	for (const auto& clique_point : clique) {	4,978✔
100	auto distance = boost::geometry::distance(point, locations.at(clique_point));	3,991!
101	for (size_t i = 0; i < excluded_points.size(); i++) {	15,964✔
102	if (clique_point == excluded_points[i]) {	15,964✔
103	continue;
104	}
105	if (distance < current_score[i]) {	12,016✔
106	current_score[i] = distance;	3,775✔
107	}
108	}
109	}
110	return current_score;	987✔
111	}
112
113
114	/* This function finds the segments for putting bridges.
115	*
116	* It starts by finding the longest segments. Then it iteratively picks one
117	* segment at a time to try to replace elsewhere, searching for a swap that will
118	* maximize the minimum distance between segments. It continues until no
119	* improvement can be made or until one second has passed. It may return fewer
120	* than the "number" requested if not enough place can be found to place
121	* bridges.
122	*
123	* Returns the positions in path of the segments that need to be modified.
124	*/
125	set<size_t> findBridgeSegments(const linestring_type_fp& path, size_t number, double length) {	57✔
126	if (number < 1) {	57✔
127	return {};	40✔
128	}
129
130	// All the potential bridge segments and their locations.
131	map<size_t, point_type_fp> candidates;
132	for (size_t i = 0; i < path.size() - 1; i++) {	722✔
133	auto current_distance = bg::distance(path.at(i), path.at(i+1));	705!
134	if (current_distance < length) {	705✔
135	continue;
136	}
137	candidates[i] = intermediatePoint(path.at(i),	236!
138	path.at(i + 1),	236!
139	0.5);	236✔
140	}
141
142	// Make a set of bridges that we will output. They must be unique. For now
143	// just take the first few.
144	set<size_t> output;
145	for (const auto& candidate : candidates) {	82✔
146	if (output.size() >= number) {	74✔
147	break;
148	}
149	output.insert(candidate.first);	65!
150	}
151
152	vector<size_t> closest = {0,0};	17!
153	double best_score;
154	// Can we do better?
155
156	// Try to improve the score by moving one of the two closest points.
157	do {
158	best_score = min_clique_distance(output, candidates, closest);	52!
159	bool improvement = false;
160	auto new_score = best_score;
161	size_t swap_from;
162	size_t swap_to;
163	for (const auto& candidate : candidates) {	1,245✔
164	if (output.count(candidate.first) > 0) {
165	// This is already in the output so we can't reuse it.
166	continue;	206✔
167	}
168	// What happens to the score if we move one of the closest to this new candidate?
169	auto current_score = min_distance_to_clique(candidate.second, closest, output, candidates);	987!
170	for (size_t i = 0; i < closest.size(); i++) {	3,948✔
171	if (current_score[i] > new_score) {	3,948✔
172	swap_from = closest[i];	215✔
173	swap_to = candidate.first;	215✔
174	new_score = current_score[i];
175	improvement = true;
176	}
177	}
178	}
179	if (!improvement) {	52✔
180	break;
181	}
182	output.erase(swap_from);
183	output.insert(swap_to);
184	best_score = min_clique_distance(output, candidates, closest);	35!
185	} while(true);
186	return output;
187	}
188
189	vector<size_t> outline_bridges::makeBridges(linestring_type_fp& path, size_t number, double length) {	57✔
190	return insertBridges(path, findBridgeSegments(path, number, length), length);	114!
191	}

pcb2gcode / pcb2gcode / 158797379

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