21021097492

Committed 15 Jan 2026 05:42AM UTC coverage: 70.124% (+10.1%) from 60.064%

Build # 21021097492

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #752 from eyal0/integration_tests_in_ci

ci: Include integration tests as part of coverage.

Run Details

4430 of 7541 branches covered (58.75%)

Branch coverage included in aggregate %.

3710 of 4067 relevant lines covered (91.22%)

15236187.44 hits per line

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

65.48

/segment_tree.cpp

#include <vector>
using std::vector;

#include <utility>
using std::pair;

#include <boost/optional.hpp>

#include "bg_operators.hpp"

#include "segment_tree.hpp"
#include "value_ptr.hpp"
using smart_ptr::value_ptr;
using smart_ptr::make_value;

namespace segment_tree {

template <bool on_x, bool less_than>
value_ptr<Node> make_node(vector<segment_t>::iterator segments_begin,
                          vector<segment_t>::iterator segments_end) {
  if (segments_end - segments_begin == 1) {
    // We're done.
    return make_value<Node>(*segments_begin);
  }
  // Sort the segments as specified by on_x and less_than.
  coordinate_type_fp (segment_t::*corner_axis_selector)() const;
  coordinate_type_fp factor;
  if (less_than && on_x) {
    corner_axis_selector = &segment_t::max_x;
    factor = 1;
  } else if (less_than && !on_x) {
    corner_axis_selector = &segment_t::max_y;
    factor = 1;
  } else if (!less_than && on_x) {
    corner_axis_selector = &segment_t::min_x;
    factor = -1;
  } else if (!less_than && !on_x) {
    corner_axis_selector = &segment_t::min_y;
    factor = -1;
  }
  std::sort(segments_begin, segments_end,
            [&](const segment_t& s0,
                const segment_t& s1) {
              return factor * (s0.*corner_axis_selector)() < factor * (s1.*corner_axis_selector)();
            });
  // Find the middle.  It will round down.  You can't add begin and
  // end, it might overflow.  Behavior is undefined.
  auto mid = segments_begin + (segments_end - segments_begin)/2;

  const auto new_intercept = ((*mid).*corner_axis_selector)();
  constexpr auto new_on_x = less_than ^ on_x;
  constexpr auto new_less_than = !less_than;
  // mid will get changed below so we neeed to store the intercept.
  return make_value<Node>(new_intercept,
                          make_node<new_on_x, new_less_than>(segments_begin, mid),
                          make_node<new_on_x, new_less_than>(mid, segments_end));
}

constexpr bool START_ON_X = true;
constexpr bool START_LESS_THAN = true;

SegmentTree::SegmentTree(const vector<std::pair<point_type_fp, point_type_fp>>& segments_in) {
  // For each segment, find the bounding box.
  vector<segment_t> segments;
  segments.reserve(segments_in.size());
  for (const auto& segment : segments_in) {
    segments.emplace_back(segment.first, segment.second);
  }
  if (segments.size() > 0) {
    root = make_node<START_ON_X, START_LESS_THAN>(segments.begin(), segments.end());
  }
}

// is_left(): tests if a point is Left|On|Right of an infinite line.
//    Input:  three points p0, p1, and p2
//    Return: >0 for p2 left of the line through p0 and p1
//            =0 for p2 on the line
//            <0 for p2 right of the line
//    See: Algorithm 1 "Area of Triangles and Polygons"
//    This is p0p1 cross p0p2.
static inline coordinate_type_fp is_left(point_type_fp p0, point_type_fp p1, point_type_fp p2) {
  return ((p1.x() - p0.x()) * (p2.y() - p0.y()) -
          (p2.x() - p0.x()) * (p1.y() - p0.y()));
}

// Is x between a and b, where a can be lesser or greater than b.  If
// x == a or x == b, also returns true. */
extern inline coordinate_type_fp is_between(coordinate_type_fp a,
                                            coordinate_type_fp x,
                                            coordinate_type_fp b) {
  return x == a || x == b || (a-x>0) == (x-b>0);
}


// https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
static inline bool is_intersecting(const point_type_fp& p0, const point_type_fp& p1,
                                   const point_type_fp& p2, const point_type_fp& p3) {
  const coordinate_type_fp left012 = is_left(p0, p1, p2);
  const coordinate_type_fp left013 = is_left(p0, p1, p3);
  const coordinate_type_fp left230 = is_left(p2, p3, p0);
  const coordinate_type_fp left231 = is_left(p2, p3, p1);

  if (p0 != p1) {
    if (left012 == 0) {
      if (is_between(p0.x(), p2.x(), p1.x()) &&
          is_between(p0.y(), p2.y(), p1.y())) {
        return true; // p2 is on the line p0 to p1
      }
    }
    if (left013 == 0) {
      if (is_between(p0.x(), p3.x(), p1.x()) &&
          is_between(p0.y(), p3.y(), p1.y())) {
        return true; // p3 is on the line p0 to p1
      }
    }
  }
  if (p2 != p3) {
    if (left230 == 0) {
      if (is_between(p2.x(), p0.x(), p3.x()) &&
          is_between(p2.y(), p0.y(), p3.y())) {
        return true; // p0 is on the line p2 to p3
      }
    }
    if (left231 == 0) {
      if (is_between(p2.x(), p1.x(), p3.x()) &&
          is_between(p2.y(), p1.y(), p3.y())) {
        return true; // p1 is on the line p2 to p3
      }
    }
  }
  if ((left012 > 0) == (left013 > 0) ||
      (left230 > 0) == (left231 > 0)) {
    if (p1 == p2) {
      return true;
    }
    return false;
  } else {
    return true;
  }
}

template <bool on_x, bool less_than>
bool intersects(const segment_t& segment, const value_ptr<Node>& node) {
  if (node->segment) {
    return is_intersecting(segment.first(), segment.second(),
                           node->segment->first(), node->segment->second());
  }
  constexpr auto new_on_x = less_than ^ on_x;
  constexpr auto new_less_than = !less_than;
  if (intersects<new_on_x, new_less_than>(segment, node->out)) {
    return true;
  }
  coordinate_type_fp (segment_t::*corner_axis_selector)() const;
  coordinate_type_fp factor;
  if (less_than && on_x) {
    corner_axis_selector = &segment_t::min_x;
    factor = -1;
  } else if (less_than && !on_x) {
    corner_axis_selector = &segment_t::min_y;
    factor = -1;
  } else if (!less_than && on_x) {
    corner_axis_selector = &segment_t::max_x;
    factor = 1;
  } else if (!less_than && !on_x) {
    corner_axis_selector = &segment_t::max_y;
    factor = 1;
  }
  if (!(factor * (segment.*corner_axis_selector)() < factor * node->intercept)) {
    return intersects<new_on_x, new_less_than>(segment, node->in);
  }
  return false;
}

bool SegmentTree::intersects(const point_type_fp& p0, const point_type_fp& p1) const {
  if (root == nullptr) {
    return false;
  }
  return segment_tree::intersects<START_ON_X, START_LESS_THAN>(segment_t(p0, p1), root);
}

template <bool on_x, bool less_than>
void print_node(const value_ptr<Node>& node, std::string indent = "") {
  if (node->segment) {
    std::cout << indent << bg::wkt(node->segment->first()) << " "
              << bg::wkt(node->segment->second()) << std::endl;
    return;
  }
  std::cout << indent << "if all "
            << (on_x ? "x" : "y") << " is " << (!less_than ? "less than" : "greater than")
            << " " << node->intercept << " then:" << std::endl;
  constexpr auto new_on_x = less_than ^ on_x;
  constexpr auto new_less_than = !less_than;
  print_node<new_on_x, new_less_than>(node->out, indent + "  ");
  std::cout << indent << "else the above and:" << std::endl;
  print_node<new_on_x, new_less_than>(node->in, indent + "  ");
}

void SegmentTree::print() {
  print_node<START_ON_X, START_LESS_THAN>(root);
}

} //namespace path_finding

1	#include <vector>
2	using std::vector;
3
4	#include <utility>
5	using std::pair;
6
7	#include <boost/optional.hpp>
8
9	#include "bg_operators.hpp"
10
11	#include "segment_tree.hpp"
12	#include "value_ptr.hpp"
13	using smart_ptr::value_ptr;
14	using smart_ptr::make_value;
15
16	namespace segment_tree {
17
18	template <bool on_x, bool less_than>
19	value_ptr<Node> make_node(vector<segment_t>::iterator segments_begin,	709,028✔
20	vector<segment_t>::iterator segments_end) {
21	if (segments_end - segments_begin == 1) {	709,028✔
22	// We're done.
23	return make_value<Node>(*segments_begin);	354,566✔
24	}
25	// Sort the segments as specified by on_x and less_than.
26	coordinate_type_fp (segment_t::*corner_axis_selector)() const;
27	coordinate_type_fp factor;
28	if (less_than && on_x) {
29	corner_axis_selector = &segment_t::max_x;	98,749✔
30	factor = 1;	98,749✔
31	} else if (less_than && !on_x) {
32	corner_axis_selector = &segment_t::max_y;	71,866✔
33	factor = 1;	71,866✔
34	} else if (!less_than && on_x) {
35	corner_axis_selector = &segment_t::min_x;	77,228✔
36	factor = -1;	77,228✔
37	} else if (!less_than && !on_x) {
38	corner_axis_selector = &segment_t::min_y;	106,619✔
39	factor = -1;	106,619✔
40	}
41	std::sort(segments_begin, segments_end,	354,462✔
42	[&](const segment_t& s0,	69,630,264✔
43	const segment_t& s1) {
44	return factor * (s0.corner_axis_selector)() < factor (s1.*corner_axis_selector)();	34,815,132!
45	});
46	// Find the middle. It will round down. You can't add begin and
47	// end, it might overflow. Behavior is undefined.
48	auto mid = segments_begin + (segments_end - segments_begin)/2;	354,462!
49
50	const auto new_intercept = ((mid).corner_axis_selector)();	354,462!
51	constexpr auto new_on_x = less_than ^ on_x;
52	constexpr auto new_less_than = !less_than;
53	// mid will get changed below so we neeed to store the intercept.
54	return make_value<Node>(new_intercept,
55	make_node<new_on_x, new_less_than>(segments_begin, mid),
56	make_node<new_on_x, new_less_than>(mid, segments_end));	708,924!
57	}
58
59	constexpr bool START_ON_X = true;
60	constexpr bool START_LESS_THAN = true;
61
62	SegmentTree::SegmentTree(const vector<std::pair<point_type_fp, point_type_fp>>& segments_in) {	324!
63	// For each segment, find the bounding box.
64	vector<segment_t> segments;
65	segments.reserve(segments_in.size());	324!
66	for (const auto& segment : segments_in) {	354,890✔
67	segments.emplace_back(segment.first, segment.second);	354,566!
68	}
69	if (segments.size() > 0) {	324✔
70	root = make_node<START_ON_X, START_LESS_THAN>(segments.begin(), segments.end());	208!
71	}
72	}	324✔
73
74	// is_left(): tests if a point is Left\|On\|Right of an infinite line.
75	// Input: three points p0, p1, and p2
76	// Return: >0 for p2 left of the line through p0 and p1
77	// =0 for p2 on the line
78	// <0 for p2 right of the line
79	// See: Algorithm 1 "Area of Triangles and Polygons"
80	// This is p0p1 cross p0p2.
81	static inline coordinate_type_fp is_left(point_type_fp p0, point_type_fp p1, point_type_fp p2) {
82	return ((p1.x() - p0.x()) * (p2.y() - p0.y()) -	3,654,761✔
83	(p2.x() - p0.x()) * (p1.y() - p0.y()));	3,654,761✔
84	}
85
86	// Is x between a and b, where a can be lesser or greater than b. If
87	// x == a or x == b, also returns true. */
88	extern inline coordinate_type_fp is_between(coordinate_type_fp a,	35✔
89	coordinate_type_fp x,
90	coordinate_type_fp b) {
91	return x == a \|\| x == b \|\| (a-x>0) == (x-b>0);	35!
92	}
93
94
95	// https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
96	static inline bool is_intersecting(const point_type_fp& p0, const point_type_fp& p1,	3,654,761✔
97	const point_type_fp& p2, const point_type_fp& p3) {
98	const coordinate_type_fp left012 = is_left(p0, p1, p2);
99	const coordinate_type_fp left013 = is_left(p0, p1, p3);
100	const coordinate_type_fp left230 = is_left(p2, p3, p0);
101	const coordinate_type_fp left231 = is_left(p2, p3, p1);
102
103	if (p0 != p1) {	3,654,761✔
104	if (left012 == 0) {	3,637,888✔
105	if (is_between(p0.x(), p2.x(), p1.x()) &&	14✔
106	is_between(p0.y(), p2.y(), p1.y())) {	6!
107	return true; // p2 is on the line p0 to p1
108	}
109	}
110	if (left013 == 0) {	3,637,888✔
111	if (is_between(p0.x(), p3.x(), p1.x()) &&	11✔
112	is_between(p0.y(), p3.y(), p1.y())) {	4!
113	return true; // p3 is on the line p0 to p1
114	}
115	}
116	}
117	if (p2 != p3) {	3,654,761!
118	if (left230 == 0) {	3,654,761!
119	if (is_between(p2.x(), p0.x(), p3.x()) &&	×
120	is_between(p2.y(), p0.y(), p3.y())) {	×
121	return true; // p0 is on the line p2 to p3
122	}
123	}
124	if (left231 == 0) {	3,654,761!
125	if (is_between(p2.x(), p1.x(), p3.x()) &&	×
126	is_between(p2.y(), p1.y(), p3.y())) {	×
127	return true; // p1 is on the line p2 to p3
128	}
129	}
130	}
131	if ((left012 > 0) == (left013 > 0) \|\|	3,654,761✔
132	(left230 > 0) == (left231 > 0)) {	32,055✔
133	if (p1 == p2) {
134	return true;
135	}
136	return false;	3,635,476✔
137	} else {
138	return true;
139	}
140	}
141
142	template <bool on_x, bool less_than>
143	bool intersects(const segment_t& segment, const value_ptr<Node>& node) {	8,974,140✔
144	if (node->segment) {	8,974,140✔
145	return is_intersecting(segment.first(), segment.second(),	3,654,761✔
146	node->segment->first(), node->segment->second());	3,654,761✔
147	}
148	constexpr auto new_on_x = less_than ^ on_x;
149	constexpr auto new_less_than = !less_than;
150	if (intersects<new_on_x, new_less_than>(segment, node->out)) {	5,319,379✔
151	return true;
152	}
153	coordinate_type_fp (segment_t::*corner_axis_selector)() const;
154	coordinate_type_fp factor;
155	if (less_than && on_x) {
156	corner_axis_selector = &segment_t::min_x;
157	factor = -1;
158	} else if (less_than && !on_x) {
159	corner_axis_selector = &segment_t::min_y;
160	factor = -1;
161	} else if (!less_than && on_x) {
162	corner_axis_selector = &segment_t::max_x;
163	factor = 1;
164	} else if (!less_than && !on_x) {
165	corner_axis_selector = &segment_t::max_y;
166	factor = 1;
167	}
168	if (!(factor * (segment.corner_axis_selector)() < factor node->intercept)) {	5,159,300✔
169	return intersects<new_on_x, new_less_than>(segment, node->in);	3,633,396✔
170	}
171	return false;
172	}
173
174	bool SegmentTree::intersects(const point_type_fp& p0, const point_type_fp& p1) const {	21,365!
175	if (root == nullptr) {	21,365!
176	return false;
177	}
178	return segment_tree::intersects<START_ON_X, START_LESS_THAN>(segment_t(p0, p1), root);	42,730✔
179	}
180
181	template <bool on_x, bool less_than>
182	void print_node(const value_ptr<Node>& node, std::string indent = "") {	×
183	if (node->segment) {	×
184	std::cout << indent << bg::wkt(node->segment->first()) << " "	×
185	<< bg::wkt(node->segment->second()) << std::endl;	×
186	return;	×
187	}
188	std::cout << indent << "if all "
189	<< (on_x ? "x" : "y") << " is " << (!less_than ? "less than" : "greater than")
190	<< " " << node->intercept << " then:" << std::endl;	×
191	constexpr auto new_on_x = less_than ^ on_x;
192	constexpr auto new_less_than = !less_than;
193	print_node<new_on_x, new_less_than>(node->out, indent + " ");	×
194	std::cout << indent << "else the above and:" << std::endl;	×
195	print_node<new_on_x, new_less_than>(node->in, indent + " ");	×
196	}
197
198	void SegmentTree::print() {	×
199	print_node<START_ON_X, START_LESS_THAN>(root);	×
200	}	×
201
202	} //namespace path_finding

pcb2gcode / pcb2gcode / 21021097492

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