523793163

Build Type

github

Committed by GitHub

Commit Message

Merge dfaae4b02 into dd03ed1f3

Pull Request Pull Request #523: Better path finding algorithm

Run Details

4859 of 8278 branches covered (58.7%)

Branch coverage included in aggregate %.

284 of 297 new or added lines in 4 files covered. (95.62%)

18 existing lines in 2 files now uncovered.

3303 of 3552 relevant lines covered (92.99%)

198445.09 hits per line

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

51.03

/bg_helpers.cpp

#include "eulerian_paths.hpp"
#ifdef GEOS_VERSION
#include <geos/io/WKTReader.h>
#include <geos/io/WKTReader.inl>
#include <geos/io/WKTWriter.h>
#include <geos/operation/buffer/BufferOp.h>
#endif // GEOS_VERSION

#include "bg_operators.hpp"
#include "bg_helpers.hpp"

namespace bg_helpers {

// The below implementations of buffer are similar to bg::buffer but
// always convert to floating-point before doing work, if needed, and
// convert back afterward, if needed.  Also, they work if expand_by is
// 0, unlike bg::buffer.  It seems to be faster to buffer individual
// polygons and then add them together rather than to do them all at
// once, even though the results ought to be the same.  How strange!
const int points_per_circle = 32;

multi_polygon_type_fp buffer(polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  if (expand_by == 0) {
    return multi_polygon_type_fp{geometry_in};
  }
#ifdef GEOS_VERSION
  geos::io::WKTReader reader;
  std::stringstream ss;
  ss << bg::wkt(geometry_in);
  auto geos_in = reader.read(ss.str());
  std::unique_ptr<geos::geom::Geometry> geos_out(geos::operation::buffer::BufferOp::bufferOp(geos_in.get(), expand_by, points_per_circle/4));
  geos::io::WKTWriter writer;
  auto geos_wkt = writer.write(geos_out.get());
  multi_polygon_type_fp ret;
  if (strncmp(geos_wkt.c_str(), "MULTIPOLYGON", 12) == 0) {
    bg::read_wkt(geos_wkt, ret);
  } else {
    polygon_type_fp poly;
    bg::read_wkt(geos_wkt, poly);
    ret.push_back(poly);
  }
  return ret;
#else
  multi_polygon_type_fp geometry_out;
  bg::buffer(geometry_in, geometry_out,
             bg::strategy::buffer::distance_symmetric<coordinate_type_fp>(expand_by),
             bg::strategy::buffer::side_straight(),
             bg::strategy::buffer::join_round(points_per_circle),
             bg::strategy::buffer::end_round(points_per_circle),
             bg::strategy::buffer::point_circle(points_per_circle));
  return geometry_out;
#endif
}

multi_polygon_type_fp buffer_miter(polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  if (expand_by == 0) {
    return multi_polygon_type_fp{geometry_in};
  } else {
    multi_polygon_type_fp geometry_out;
    bg::buffer(geometry_in, geometry_out,
               bg::strategy::buffer::distance_symmetric<coordinate_type_fp>(expand_by),
               bg::strategy::buffer::side_straight(),
               bg::strategy::buffer::join_miter(expand_by),
               bg::strategy::buffer::end_round(points_per_circle),
               bg::strategy::buffer::point_circle(points_per_circle));
    return geometry_out;
  }
}

multi_polygon_type_fp buffer(multi_polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  if (expand_by == 0 || geometry_in.size() == 0) {
    return geometry_in;
  }
  multi_polygon_type_fp geometry_out;
  for (const auto& poly : geometry_in) {
    geometry_out = geometry_out + buffer(poly, expand_by);
  }
  return geometry_out;
}

multi_polygon_type_fp buffer_miter(multi_polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  if (expand_by == 0) {
    return geometry_in;
  }
  multi_polygon_type_fp geometry_out;
  for (const auto& poly : geometry_in) {
    geometry_out = geometry_out + buffer_miter(poly, expand_by);
  }
  return geometry_out;
}

multi_polygon_type_fp buffer(linestring_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  if (expand_by == 0) {
    return {};
  }
#ifdef GEOS_VERSION
  geos::io::WKTReader reader;
  std::stringstream ss;
  ss << bg::wkt(geometry_in);
  auto geos_in = reader.read(ss.str());
  std::unique_ptr<geos::geom::Geometry> geos_out(geos::operation::buffer::BufferOp::bufferOp(geos_in.get(), expand_by, points_per_circle/4));
  geos::io::WKTWriter writer;
  auto geos_wkt = writer.write(geos_out.get());
  multi_polygon_type_fp ret;
  if (strncmp(geos_wkt.c_str(), "MULTIPOLYGON", 12) == 0) {
    bg::read_wkt(geos_wkt, ret);
  } else {
    polygon_type_fp poly;
    bg::read_wkt(geos_wkt, poly);
    ret.push_back(poly);
  }
  return ret;
#else
  multi_polygon_type_fp geometry_out;
  bg::buffer(geometry_in, geometry_out,
             bg::strategy::buffer::distance_symmetric<coordinate_type_fp>(expand_by),
             bg::strategy::buffer::side_straight(),
             bg::strategy::buffer::join_round(points_per_circle),
             bg::strategy::buffer::end_round(points_per_circle),
             bg::strategy::buffer::point_circle(points_per_circle));
  return geometry_out;
#endif
}

multi_polygon_type_fp buffer(multi_linestring_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  if (expand_by == 0 || geometry_in.size() == 0) {
    return {};
  }
  // bg::buffer of multilinestring is broken in boost.  Converting the
  // multilinestring to non-intersecting paths seems to help.
  multi_linestring_type_fp mls = eulerian_paths::make_eulerian_paths(geometry_in, true, true);
#ifdef GEOS_VERSION
  geos::io::WKTReader reader;
  std::stringstream ss;
  ss << bg::wkt(mls);
  auto geos_in = reader.read(ss.str());
  std::unique_ptr<geos::geom::Geometry> geos_out(geos::operation::buffer::BufferOp::bufferOp(geos_in.get(), expand_by, points_per_circle/4));
  geos::io::WKTWriter writer;
  auto geos_wkt = writer.write(geos_out.get());
  multi_polygon_type_fp ret;
  if (strncmp(geos_wkt.c_str(), "MULTIPOLYGON", 12) == 0) {
    bg::read_wkt(geos_wkt, ret);
  } else {
    polygon_type_fp poly;
    bg::read_wkt(geos_wkt, poly);
    ret.push_back(poly);
  }
  return ret;
#else
  if (expand_by == 0) {
    return {};
  }
  multi_polygon_type_fp ret;
  for (const auto& ls : mls) {
    ret = ret + buffer(ls, expand_by);
  }
  return ret;
#endif
}

multi_polygon_type_fp buffer_miter(ring_type_fp const & geometry_in, coordinate_type_fp expand_by) {
  return buffer_miter(polygon_type_fp{geometry_in}, expand_by);
}

} // namespace bg_helpers

1	#include "eulerian_paths.hpp"
2	#ifdef GEOS_VERSION
3	#include <geos/io/WKTReader.h>
4	#include <geos/io/WKTReader.inl>
5	#include <geos/io/WKTWriter.h>
6	#include <geos/operation/buffer/BufferOp.h>
7	#endif // GEOS_VERSION
8
9	#include "bg_operators.hpp"
10	#include "bg_helpers.hpp"
11
12	namespace bg_helpers {
13
14	// The below implementations of buffer are similar to bg::buffer but
15	// always convert to floating-point before doing work, if needed, and
16	// convert back afterward, if needed. Also, they work if expand_by is
17	// 0, unlike bg::buffer. It seems to be faster to buffer individual
18	// polygons and then add them together rather than to do them all at
19	// once, even though the results ought to be the same. How strange!
20	const int points_per_circle = 32;
21
22	multi_polygon_type_fp buffer(polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {	3,329✔
23	if (expand_by == 0) {	3,329✔
24	return multi_polygon_type_fp{geometry_in};	1,239!
25	}
26	#ifdef GEOS_VERSION
27	geos::io::WKTReader reader;
28	std::stringstream ss;	5,832✔
29	ss << bg::wkt(geometry_in);
30	auto geos_in = reader.read(ss.str());	5,832!
31	std::unique_ptr<geos::geom::Geometry> geos_out(geos::operation::buffer::BufferOp::bufferOp(geos_in.get(), expand_by, points_per_circle/4));	2,916!
32	geos::io::WKTWriter writer;	2,916!
33	auto geos_wkt = writer.write(geos_out.get());	2,916!
34	multi_polygon_type_fp ret;
35	if (strncmp(geos_wkt.c_str(), "MULTIPOLYGON", 12) == 0) {	2,916✔
36	bg::read_wkt(geos_wkt, ret);
37	} else {
38	polygon_type_fp poly;	2,908✔
39	bg::read_wkt(geos_wkt, poly);
40	ret.push_back(poly);	2,908!
41	}
42	return ret;
43	#else
44	multi_polygon_type_fp geometry_out;
45	bg::buffer(geometry_in, geometry_out,
46	bg::strategy::buffer::distance_symmetric<coordinate_type_fp>(expand_by),
47	bg::strategy::buffer::side_straight(),
48	bg::strategy::buffer::join_round(points_per_circle),
49	bg::strategy::buffer::end_round(points_per_circle),
50	bg::strategy::buffer::point_circle(points_per_circle));
51	return geometry_out;
52	#endif
53	}
54
55	multi_polygon_type_fp buffer_miter(polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {	1,358✔
56	if (expand_by == 0) {	1,358!
UNCOV 57	return multi_polygon_type_fp{geometry_in};	×
58	} else {
59	multi_polygon_type_fp geometry_out;
60	bg::buffer(geometry_in, geometry_out,	1,358!
61	bg::strategy::buffer::distance_symmetric<coordinate_type_fp>(expand_by),	1,358✔
62	bg::strategy::buffer::side_straight(),	1,358✔
63	bg::strategy::buffer::join_miter(expand_by),	1,358✔
64	bg::strategy::buffer::end_round(points_per_circle),	1,358✔
65	bg::strategy::buffer::point_circle(points_per_circle));	1,358✔
66	return geometry_out;
67	}
68	}
69
70	multi_polygon_type_fp buffer(multi_polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {	3,086✔
71	if (expand_by == 0 \|\| geometry_in.size() == 0) {	3,086✔
72	return geometry_in;
73	}
74	multi_polygon_type_fp geometry_out;
75	for (const auto& poly : geometry_in) {	2,887✔
76	geometry_out = geometry_out + buffer(poly, expand_by);	3,272!
77	}
78	return geometry_out;
79	}
80
UNCOV 81	multi_polygon_type_fp buffer_miter(multi_polygon_type_fp const & geometry_in, coordinate_type_fp expand_by) {	×
UNCOV 82	if (expand_by == 0) {	×
83	return geometry_in;
84	}
85	multi_polygon_type_fp geometry_out;
UNCOV 86	for (const auto& poly : geometry_in) {	×
UNCOV 87	geometry_out = geometry_out + buffer_miter(poly, expand_by);	×
88	}
89	return geometry_out;
90	}
91
UNCOV 92	multi_polygon_type_fp buffer(linestring_type_fp const & geometry_in, coordinate_type_fp expand_by) {	×
UNCOV 93	if (expand_by == 0) {	×
94	return {};
95	}
96	#ifdef GEOS_VERSION
97	geos::io::WKTReader reader;
UNCOV 98	std::stringstream ss;	×
99	ss << bg::wkt(geometry_in);
UNCOV 100	auto geos_in = reader.read(ss.str());	×
UNCOV 101	std::unique_ptr<geos::geom::Geometry> geos_out(geos::operation::buffer::BufferOp::bufferOp(geos_in.get(), expand_by, points_per_circle/4));	×
UNCOV 102	geos::io::WKTWriter writer;	×
UNCOV 103	auto geos_wkt = writer.write(geos_out.get());	×
104	multi_polygon_type_fp ret;
UNCOV 105	if (strncmp(geos_wkt.c_str(), "MULTIPOLYGON", 12) == 0) {	×
106	bg::read_wkt(geos_wkt, ret);
107	} else {
UNCOV 108	polygon_type_fp poly;	×
109	bg::read_wkt(geos_wkt, poly);
UNCOV 110	ret.push_back(poly);	×
111	}
112	return ret;
113	#else
114	multi_polygon_type_fp geometry_out;
115	bg::buffer(geometry_in, geometry_out,
116	bg::strategy::buffer::distance_symmetric<coordinate_type_fp>(expand_by),
117	bg::strategy::buffer::side_straight(),
118	bg::strategy::buffer::join_round(points_per_circle),
119	bg::strategy::buffer::end_round(points_per_circle),
120	bg::strategy::buffer::point_circle(points_per_circle));
121	return geometry_out;
122	#endif
123	}
124
125	multi_polygon_type_fp buffer(multi_linestring_type_fp const & geometry_in, coordinate_type_fp expand_by) {	198✔
126	if (expand_by == 0 \|\| geometry_in.size() == 0) {	198!
127	return {};
128	}
129	// bg::buffer of multilinestring is broken in boost. Converting the
130	// multilinestring to non-intersecting paths seems to help.
131	multi_linestring_type_fp mls = eulerian_paths::make_eulerian_paths(geometry_in, true, true);	198✔
132	#ifdef GEOS_VERSION
133	geos::io::WKTReader reader;
134	std::stringstream ss;	396!
135	ss << bg::wkt(mls);
136	auto geos_in = reader.read(ss.str());	396!
137	std::unique_ptr<geos::geom::Geometry> geos_out(geos::operation::buffer::BufferOp::bufferOp(geos_in.get(), expand_by, points_per_circle/4));	198!
138	geos::io::WKTWriter writer;	198!
139	auto geos_wkt = writer.write(geos_out.get());	198!
140	multi_polygon_type_fp ret;
141	if (strncmp(geos_wkt.c_str(), "MULTIPOLYGON", 12) == 0) {	198✔
142	bg::read_wkt(geos_wkt, ret);
143	} else {
144	polygon_type_fp poly;	88✔
145	bg::read_wkt(geos_wkt, poly);
146	ret.push_back(poly);	88!
147	}
148	return ret;
149	#else
150	if (expand_by == 0) {
151	return {};
152	}
153	multi_polygon_type_fp ret;
154	for (const auto& ls : mls) {
155	ret = ret + buffer(ls, expand_by);
156	}
157	return ret;
158	#endif
159	}
160
161	multi_polygon_type_fp buffer_miter(ring_type_fp const & geometry_in, coordinate_type_fp expand_by) {	1,358✔
162	return buffer_miter(polygon_type_fp{geometry_in}, expand_by);	2,716!
163	}
164
165	} // namespace bg_helpers

pcb2gcode / pcb2gcode / 523793163

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