GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 75.3% 678 / 0 / 900
Functions: 81.5% 44 / 0 / 54
Branches: 66.2% 714 / 0 / 1078

src/utilities/geometry/Intersection.cpp
Line Branch Exec Source
1 /***********************************************************************************************************************
2 * OpenStudio(R), Copyright (c) Alliance for Energy Innovation, LLC.
3 * See also https://openstudio.net/license
4 ***********************************************************************************************************************/
5
6 #include "Geometry.hpp"
7 #include "Vector3d.hpp"
8 #include "Intersection.hpp"
9 #include "../data/Matrix.hpp"
10 #include "../core/Assert.hpp"
11 #include "../core/ContainersMove.hpp"
12 #include "../core/Logger.hpp"
13
14 #undef BOOST_UBLAS_TYPE_CHECK
15 #if defined(_MSC_VER)
16 # pragma warning(push)
17 # pragma warning(disable : 4244)
18 #endif
19 #include <boost/geometry.hpp>
20 #include <boost/geometry/geometry.hpp>
21 #include <boost/geometry/geometries/point_xy.hpp>
22 #include <boost/geometry/geometries/polygon.hpp>
23 #include <boost/geometry/geometries/ring.hpp>
24 #include <boost/geometry/geometries/multi_polygon.hpp>
25 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
26 #include <boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp>
27 #include <boost/geometry/strategies/cartesian/point_in_poly_crossings_multiply.hpp>
28 #include <boost/geometry/algorithms/within.hpp>
29 #include <boost/geometry/algorithms/simplify.hpp>
30 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
31 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
32 #if defined(_MSC_VER)
33 # pragma warning(pop)
34 #endif
35
36 #include <algorithm>
37 #include <cmath>
38 #include <iterator>
39
40 using coordinate_type = double;
41 using BoostPoint = boost::geometry::model::d2::point_xy<double>;
42 using BoostPolygon = boost::geometry::model::polygon<BoostPoint>;
43 using BoostRing = boost::geometry::model::ring<BoostPoint>;
44 using BoostMultiPolygon = boost::geometry::model::multi_polygon<BoostPolygon>;
45
46 #include <polypartition/polypartition.h>
47
48 namespace openstudio {
49
50 // Private implementation functions
51
52 // Boost 1.73.0 has this bit in has_self_intersections.hpp:
53 //
54 // For backward compatibility
55 // template <typename Geometry>
56 // inline bool has_self_intersections(Geometry const& geometry, bool throw_on_self_intersection = true) {
57 // typedef typename geometry::point_type<Geometry>::type point_type;
58 // typedef typename geometry::rescale_policy_type<point_type>::type rescale_policy_type;
59
60 // typename strategy::intersection::services::default_strategy<typename cs_tag<Geometry>::type>::type strategy;
61
62 // rescale_policy_type robust_policy = geometry::get_rescale_policy<rescale_policy_type>(geometry, strategy);
63
64 // return has_self_intersections(geometry, strategy, robust_policy, throw_on_self_intersection);
65 // }
66
67 // For backward compatibility
68 template <typename Geometry>
69 94634 inline bool has_self_intersections(Geometry const& geometry, bool throw_on_self_intersection = true) {
70 using point_type = typename boost::geometry::point_type<Geometry>::type;
71 using rescale_policy_type = typename boost::geometry::rescale_policy_type<point_type>::type;
72
73 typename boost::geometry::strategies::relate::services::default_strategy<Geometry, Geometry>::type const strategy;
74
75 // typename boost::geometry::strategy::intersection::services::default_strategy<typename boost::geometry::cs_tag<Geometry>::type>::type strategy;
76
77
2/2
bool openstudio::has_self_intersections<boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> >(boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> const&, bool):
✓ Branch 1 taken 14272 times.
bool openstudio::has_self_intersections<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >(boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> const&, bool):
✓ Branch 1 taken 80362 times.
94634 auto robust_policy = boost::geometry::get_rescale_policy<rescale_policy_type>(geometry, strategy);
78
79
2/2
bool openstudio::has_self_intersections<boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> >(boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> const&, bool):
✓ Branch 1 taken 14264 times.
bool openstudio::has_self_intersections<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >(boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> const&, bool):
✓ Branch 1 taken 80362 times.
189260 return boost::geometry::detail::overlay::has_self_intersections(geometry, strategy, robust_policy, throw_on_self_intersection);
80 }
81
82 // Some operators for Boost data types that are useful for extra logging
83 ✗ std::ostream& operator<<(std::ostream& os, const BoostRing& boostRing) {
84 ✗ os << "[";
85 ✗ for (unsigned int i = 0; i < boostRing.size(); i++) {
86 ✗ os << "{";
87 ✗ os << R"("X":)" << boostRing[i].x() << ",";
88 ✗ os << R"("Y":)" << boostRing[i].y() << ",";
89 ✗ os << R"("Z":0.0},)";
90 }
91 ✗ os << "],";
92 ✗ return os;
93 }
94
95 ✗ std::ostream& operator<<(std::ostream& os, const std::vector<BoostRing>& boostRings) {
96 ✗ os << "[";
97 ✗ for (const auto& ring : boostRings) {
98 ✗ os << ring;
99 }
100 ✗ os << "]";
101 ✗ return os;
102 }
103
104 ✗ std::ostream& operator<<(std::ostream& os, const BoostPolygon& boostPolygon) {
105 ✗ os << "{";
106 ✗ os << R"("Color":"Black",)";
107 ✗ os << R"("OuterPath":)" << boostPolygon.outer();
108 ✗ os << R"("InnerPaths":)" << boostPolygon.inners();
109 ✗ os << "},";
110 ✗ return os;
111 }
112
113 ✗ std::ostream& operator<<(std::ostream& os, const std::vector<BoostPolygon>& boostPolygons) {
114 ✗ os << "[";
115 ✗ for (const auto& poly : boostPolygons) {
116 ✗ os << poly;
117 }
118 ✗ os << "]";
119 ✗ return os;
120 }
121
122 ✗ std::ostream& operator<<(std::ostream& os, const BoostMultiPolygon& boostPolygons) {
123 ✗ os << "[";
124 ✗ for (const auto& poly : boostPolygons) {
125 ✗ os << poly;
126 }
127 ✗ os << "]";
128 ✗ return os;
129 }
130
131 // Scale factor for parameters when converting between openstudio and boost data formats to improve the numerical accuracy of the boolean operations.
132 // Idea came from this comment in the boostorg/geometry repo: https://github.com/boostorg/geometry/issues/1034#issuecomment-1284180101
133 // where the author indicates that scaling the values by 10 improved the result and talks about rounding to an integer grid,
134 // so by increasing the range of values we pass to boost we should be improving the resolution of the integer rounding
135 static constexpr double scaleBy = 1000.0;
136
137 // Cleans a polygon by shrinking and expanding. Can return multiple polygons
138 41055 std::vector<BoostPolygon> removeSpikesEx(const BoostPolygon& polygon) {
139
140 //const double buffer_distance = 1.0;
141 //const int points_per_circle = 36;
142 41055 constexpr bool extraLogging = false;
143 // The amount to shrink and expand the polygons by
144 41055 constexpr double offsetBy = 0.01;
145 41055 constexpr double tol = offsetBy;
146 // Sets the limit to how far miters are extended for sharp corners
147 41055 constexpr double mitreLimit = 100;
148 41055 const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> expand(offsetBy * scaleBy);
149 41055 const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> shrink(-offsetBy * scaleBy);
150
1/1
✓ Branch 1 taken 41055 times.
41055 const boost::geometry::strategy::buffer::join_miter join_strategy(mitreLimit * scaleBy);
151 const boost::geometry::strategy::buffer::end_flat end_strategy;
152 const boost::geometry::strategy::buffer::side_straight side_strategy;
153 41055 const boost::geometry::strategy::buffer::point_circle point_strategy;
154
155 41055 BoostMultiPolygon resultExpand;
156 41055 BoostMultiPolygon resultShrink;
157 41055 BoostMultiPolygon result;
158
159 // Used for extra logging
160 41055 BoostMultiPolygon shrinkExpand;
161 // cppcheck-suppress knownConditionTrueFalse
162 if constexpr (extraLogging) {
163 shrinkExpand.push_back(polygon);
164 }
165
166 // Shrink the polygon
167
1/1
✓ Branch 1 taken 41055 times.
41055 boost::geometry::buffer(polygon, resultShrink, shrink, side_strategy, join_strategy, end_strategy, point_strategy);
168 // cppcheck-suppress knownConditionTrueFalse
169 if constexpr (extraLogging) {
170 shrinkExpand.push_back(resultShrink[0]);
171 }
172
173 // Inflate the polygon
174
1/1
✓ Branch 1 taken 41055 times.
41055 boost::geometry::buffer(resultShrink, resultExpand, expand, side_strategy, join_strategy, end_strategy, point_strategy);
175 // cppcheck-suppress knownConditionTrueFalse
176 if constexpr (extraLogging) {
177 shrinkExpand.push_back(resultExpand[0]);
178 }
179
180 // Very small tolerance to remove artifacts from the inflate
181 41055 constexpr double tol1 = 0.001;
182
1/1
✓ Branch 1 taken 41055 times.
41055 boost::geometry::simplify(resultExpand, result, tol1 * scaleBy);
183 // cppcheck-suppress knownConditionTrueFalse
184 if constexpr (extraLogging) {
185 shrinkExpand.push_back(result[0]);
186 LOG_FREE(Debug, "Shrink/Expand", shrinkExpand);
187 }
188
189 41055 std::vector<BoostPolygon> solution;
190
2/2
✓ Branch 1 taken 519 times.
✓ Branch 2 taken 40536 times.
41055 if (result.empty()) {
191 // There's no result because the polygon was completely removed so return nothing
192 519 return solution;
193
6/6
✓ Branch 1 taken 40523 times.
✓ Branch 2 taken 13 times.
✓ Branch 8 taken 37712 times.
✓ Branch 9 taken 2811 times.
✓ Branch 10 taken 37712 times.
✓ Branch 11 taken 2824 times.
40536 } else if (result.size() == 1 && result[0].outer().size() == polygon.outer().size()) {
194 // Number of vertices didn't change so no spikes were removed
195
1/1
✓ Branch 1 taken 37712 times.
37712 solution.push_back(polygon);
196 37712 return solution;
197 } else {
198
2/2
✓ Branch 5 taken 2837 times.
✓ Branch 6 taken 2824 times.
5661 for (auto& boostPolygon : result) {
199
200 // The returned points are adjusted to the input polygon (which defines the canonical set)
201
2/2
✓ Branch 6 taken 18636 times.
✓ Branch 7 taken 2837 times.
21473 for (auto& cleanedRing : boostPolygon.outer()) {
202
3/3
✓ Branch 1 taken 18636 times.
✓ Branch 4 taken 18636 times.
✓ Branch 7 taken 18636 times.
18636 const Point3d point3d(cleanedRing.x(), cleanedRing.y(), 0.0);
203
204 // Outer ring of the original polygon
205
2/2
✓ Branch 6 taken 94083 times.
✓ Branch 7 taken 78 times.
94161 for (const auto& oriRing : polygon.outer()) {
206
3/3
✓ Branch 1 taken 94083 times.
✓ Branch 4 taken 94083 times.
✓ Branch 7 taken 94083 times.
94083 const Point3d p1(oriRing.x(), oriRing.y(), 0);
207 // Two points are within tolerance set the result to the original input point
208
3/3
✓ Branch 1 taken 94083 times.
✓ Branch 3 taken 18558 times.
✓ Branch 4 taken 75525 times.
94083 if (getDistance(point3d, p1) <= tol * scaleBy) {
209
2/2
✓ Branch 1 taken 18558 times.
✓ Branch 4 taken 18558 times.
18558 cleanedRing.x(oriRing.x());
210
2/2
✓ Branch 1 taken 18558 times.
✓ Branch 4 taken 18558 times.
18558 cleanedRing.y(oriRing.y());
211 18558 break;
212 }
213 94083 }
214 18636 }
215
216
1/1
✓ Branch 1 taken 2837 times.
2837 solution.push_back(boostPolygon);
217 }
218 2824 return solution;
219 }
220 41055 }
221
222 440 BoostPolygon removeSpikes(const BoostPolygon& polygon) {
223 440 BoostPolygon temp(polygon);
224
1/1
✓ Branch 1 taken 440 times.
440 boost::geometry::remove_spikes(temp);
225 440 return temp;
226 ✗ }
227
228 37926 std::vector<BoostPolygon> removeSpikes(const std::vector<BoostPolygon>& polygons) {
229 37926 std::vector<BoostPolygon> result;
230
2/2
✓ Branch 4 taken 41055 times.
✓ Branch 5 taken 37926 times.
78981 for (const BoostPolygon& polygon : polygons) {
231
2/2
✓ Branch 1 taken 41055 times.
✓ Branch 4 taken 41055 times.
41055 openstudio::detail::concat_helper(result, removeSpikesEx(polygon));
232 }
233 37926 return result;
234 ✗ }
235
236 872 std::vector<BoostPolygon> removeHoles(const BoostPolygon& boostPolygon) {
237 872 std::vector<BoostPolygon> result;
238
239 // convert to vector of TPPLPoly
240 872 std::list<TPPLPoly> polys;
241
242
1/1
✓ Branch 2 taken 872 times.
872 BoostRing outer = boostPolygon.outer();
243
1/1
✓ Branch 1 taken 872 times.
872 TPPLPoly outerPoly; // must be counter-clockwise
244
1/1
✓ Branch 2 taken 872 times.
872 outerPoly.Init(outer.size() - 1);
245 872 outerPoly.SetHole(false);
246 //std::cout << "outer :";
247 // Note - no scaling conversion here as this accepts boost data and returns boost data
248
2/2
✓ Branch 1 taken 5149 times.
✓ Branch 2 taken 872 times.
6021 for (size_t i = 0; i < outer.size() - 1; ++i) {
249
1/1
✓ Branch 2 taken 5149 times.
5149 outerPoly[i].x = outer[i].x();
250
1/1
✓ Branch 2 taken 5149 times.
5149 outerPoly[i].y = outer[i].y();
251 //std::cout << "(" << outer[i].x() << ", " << outer[i].y() << ") ";
252 }
253 //std::cout << '\n';
254
1/1
✓ Branch 1 taken 872 times.
872 outerPoly.SetOrientation(TPPL_CCW);
255
1/1
✓ Branch 1 taken 872 times.
872 polys.push_back(outerPoly);
256
257 872 const std::vector<BoostRing>& inners = boostPolygon.inners();
258
2/2
✓ Branch 5 taken 603 times.
✓ Branch 6 taken 872 times.
1475 for (const BoostRing& inner : inners) {
259
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 603 times.
603 if (inner.size() < 3) {
260 ✗ continue;
261 }
262
1/1
✓ Branch 1 taken 603 times.
603 TPPLPoly innerPoly; // must be clockwise
263
1/1
✓ Branch 2 taken 603 times.
603 innerPoly.Init(inner.size() - 1);
264 603 innerPoly.SetHole(true);
265 //std::cout << "inner :";
266 // Note - no scaling conversion here as this accepts boost data and returns boost data
267
2/2
✓ Branch 1 taken 2448 times.
✓ Branch 2 taken 603 times.
3051 for (unsigned i = 0; i < inner.size() - 1; ++i) {
268
1/1
✓ Branch 2 taken 2448 times.
2448 innerPoly[i].x = inner[i].x();
269
1/1
✓ Branch 2 taken 2448 times.
2448 innerPoly[i].y = inner[i].y();
270 //std::cout << "(" << inner[i].x() << ", " << inner[i].y() << ") ";
271 }
272 //std::cout << '\n';
273
1/1
✓ Branch 1 taken 603 times.
603 innerPoly.SetOrientation(TPPL_CW);
274
1/1
✓ Branch 1 taken 603 times.
603 polys.push_back(innerPoly);
275 603 }
276
277 // do partitioning
278 TPPLPartition pp;
279 872 std::list<TPPLPoly> resultPolys;
280
1/1
✓ Branch 1 taken 872 times.
872 const int test = pp.ConvexPartition_HM(&polys, &resultPolys);
281
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 872 times.
872 if (test == 0) {
282 ✗ LOG_FREE(Error, "utilities.geometry.removeHoles", "Failed to partition polygon");
283 ✗ return result;
284 }
285
286 // convert back to BoostPolygon
287 872 std::list<TPPLPoly>::iterator it;
288 872 std::list<TPPLPoly>::iterator itend;
289
2/2
✓ Branch 4 taken 4036 times.
✓ Branch 5 taken 872 times.
4908 for (it = resultPolys.begin(), itend = resultPolys.end(); it != itend; ++it) {
290
1/1
✓ Branch 1 taken 4036 times.
4036 BoostPolygon newBoostPolygon;
291 //std::cout << "result :";
292
2/2
✓ Branch 2 taken 15131 times.
✓ Branch 3 taken 4036 times.
19167 for (long i = 0; i < it->GetNumPoints(); ++i) {
293 15131 const TPPLPoint& point = it->GetPoint(i);
294
2/2
✓ Branch 1 taken 15131 times.
✓ Branch 4 taken 15131 times.
15131 boost::geometry::append(newBoostPolygon, boost::make_tuple(point.x, point.y));
295 //std::cout << "(" << point.x << ", " << point.y << ") ";
296 }
297 4036 const TPPLPoint& point = it->GetPoint(0);
298
2/2
✓ Branch 1 taken 4036 times.
✓ Branch 4 taken 4036 times.
4036 boost::geometry::append(newBoostPolygon, boost::make_tuple(point.x, point.y));
299 //std::cout << "(" << point.x << ", " << point.y << ") ";
300 //std::cout << '\n';
301
302
1/1
✓ Branch 1 taken 4036 times.
4036 boost::geometry::correct(newBoostPolygon);
303
1/1
✓ Branch 1 taken 4036 times.
4036 result.push_back(newBoostPolygon);
304 4036 }
305
306 872 return result;
307 872 }
308
309 22596 std::vector<BoostPolygon> removeHoles(const std::vector<BoostPolygon>& polygons) {
310 22596 std::vector<BoostPolygon> result;
311
2/2
✓ Branch 5 taken 11202 times.
✓ Branch 6 taken 22596 times.
33798 for (const BoostPolygon& polygon : polygons) {
312
2/2
✓ Branch 2 taken 10767 times.
✓ Branch 3 taken 435 times.
11202 if (polygon.inners().empty()) {
313 // DLM: might also want to partition if this polygon is self intersecting?
314
1/1
✓ Branch 1 taken 10767 times.
10767 result.push_back(polygon);
315 } else {
316
1/1
✓ Branch 1 taken 435 times.
435 std::vector<BoostPolygon> temp = removeHoles(polygon);
317
1/1
✓ Branch 5 taken 435 times.
435 result.insert(result.end(), temp.begin(), temp.end());
318 435 }
319 }
320 22596 return result;
321 ✗ }
322
323 // convert a Point3d to a BoostPoint
324 502171 boost::tuple<double, double> boostPointFromPoint3d(const Point3d& point3d, std::vector<Point3d>& allPoints, double tol) {
325
2/4
✓ Branch 1 taken 502171 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 502171 times.
✗ Branch 7 not taken.
502171 OS_ASSERT(std::abs(point3d.z()) <= tol);
326
327 // simple method
328 //return boost::make_tuple(point3d.x(), point3d.y());
329
330 // detailed method, try to combine points within tolerance
331
1/1
✓ Branch 1 taken 502171 times.
502171 const Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol);
332
333
3/3
✓ Branch 1 taken 502171 times.
✓ Branch 4 taken 502171 times.
✓ Branch 7 taken 502171 times.
1004342 return boost::make_tuple(resultPoint.x() * scaleBy, resultPoint.y() * scaleBy);
334 502171 }
335
336 // convert vertices to a boost polygon, all vertices must lie on z = 0 plane
337 6823 boost::optional<BoostPolygon> boostPolygonFromVertices(const std::vector<Point3d>& vertices, std::vector<Point3d>& allPoints, double tol) {
338
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 6820 times.
6823 if (vertices.size() < 3) {
339 3 return boost::none;
340 }
341
342
1/1
✓ Branch 1 taken 6820 times.
6820 BoostPolygon polygon;
343
2/2
✓ Branch 4 taken 31679 times.
✓ Branch 5 taken 6820 times.
38499 for (const Point3d& vertex : vertices) {
344
345 // should all have zero z coordinate now
346
1/1
✓ Branch 1 taken 31679 times.
31679 const double z = vertex.z();
347
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 31679 times.
31679 if (std::abs(z) > tol) {
348 ✗ LOG_FREE(Error, "utilities.geometry.boostPolygonFromVertices", "All points must be on z = 0 plane");
349 ✗ return boost::none;
350 }
351
352 // use helper method which combines close points
353
2/2
✓ Branch 1 taken 31679 times.
✓ Branch 4 taken 31679 times.
31679 boost::geometry::append(polygon, boostPointFromPoint3d(vertex, allPoints, tol));
354 }
355
356 // close polygon, use helper method which combines close points
357
2/2
✓ Branch 2 taken 6820 times.
✓ Branch 5 taken 6820 times.
6820 boost::geometry::append(polygon, boostPointFromPoint3d(vertices[0], allPoints, tol));
358
359 //boost::geometry::correct(polygon);
360
361
2/2
✓ Branch 1 taken 6820 times.
✓ Branch 4 taken 6820 times.
6820 boost::optional<double> testArea = boost::geometry::area(polygon);
362
6/7
✓ Branch 1 taken 6820 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6820 times.
✓ Branch 6 taken 81 times.
✓ Branch 7 taken 6739 times.
✓ Branch 8 taken 81 times.
✓ Branch 9 taken 6739 times.
6820 if (!testArea || (*testArea < 0)) {
363 // DLM: we could offer to reverse these vertices here but that might not be the best idea
364 81 return boost::none;
365 }
366
367
1/1
✓ Branch 1 taken 6739 times.
6739 return polygon;
368 6820 }
369
370 1053 boost::optional<BoostPolygon> nonIntersectingBoostPolygonFromVertices(const std::vector<Point3d>& polygon, std::vector<Point3d>& allPoints,
371 double tol) {
372
1/1
✓ Branch 1 taken 1053 times.
1053 boost::optional<BoostPolygon> result = boostPolygonFromVertices(polygon, allPoints, tol);
373
2/2
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 1025 times.
1053 if (!result) {
374 28 return boost::none;
375 }
376 // check if polygon overlaps itself
377 try {
378
2/2
✓ Branch 1 taken 1025 times.
✓ Branch 4 taken 1023 times.
1025 has_self_intersections(*result);
379
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
2 } catch (const boost::geometry::overlay_invalid_input_exception&) {
380 //LOG_FREE(Error, "utilities.geometry.nonIntersectingBoostPolygonFromVertices", "Self intersecting polygon");
381 2 return boost::none;
382 2 }
383 1023 return result;
384 1053 }
385
386 // convert vertices to a boost ring, all vertices must lie on z = 0 plane
387 80505 boost::optional<BoostRing> boostRingFromVertices(const std::vector<Point3d>& vertices, std::vector<Point3d>& allPoints, double tol) {
388
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 80505 times.
80505 if (vertices.size() < 3) {
389 ✗ return boost::none;
390 }
391
392 80505 BoostRing ring;
393
2/2
✓ Branch 4 taken 347803 times.
✓ Branch 5 taken 80479 times.
428282 for (const Point3d& vertex : vertices) {
394
395 // should all have zero z coordinate now
396
1/1
✓ Branch 1 taken 347803 times.
347803 const double z = vertex.z();
397
2/2
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 347777 times.
347803 if (std::abs(z) > tol) {
398
5/5
✓ Branch 1 taken 26 times.
✓ Branch 4 taken 26 times.
✓ Branch 7 taken 26 times.
✓ Branch 10 taken 26 times.
✓ Branch 13 taken 26 times.
78 LOG_FREE(Error, "utilities.geometry.boostRingFromVertices", "All points must be on z = 0 plane");
399 26 return boost::none;
400 }
401
402 // use helper method which combines close points
403
2/2
✓ Branch 1 taken 347777 times.
✓ Branch 4 taken 347777 times.
347777 boost::geometry::append(ring, boostPointFromPoint3d(vertex, allPoints, tol));
404 }
405
406 // close polygon, use helper method which combines close points
407
2/2
✓ Branch 2 taken 80479 times.
✓ Branch 5 taken 80479 times.
80479 boost::geometry::append(ring, boostPointFromPoint3d(vertices[0], allPoints, tol));
408
409 //boost::geometry::correct(ring);
410
411
2/2
✓ Branch 1 taken 80479 times.
✓ Branch 4 taken 80479 times.
80479 boost::optional<double> testArea = boost::geometry::area(ring);
412
6/7
✓ Branch 1 taken 80479 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80479 times.
✓ Branch 6 taken 117 times.
✓ Branch 7 taken 80362 times.
✓ Branch 8 taken 117 times.
✓ Branch 9 taken 80362 times.
80479 if (!testArea || (*testArea < 0)) {
413 // DLM: we could offer to reverse these vertices here but that might not be the best idea
414 117 return boost::none;
415 }
416
417
1/1
✓ Branch 1 taken 80362 times.
80362 return ring;
418 80505 }
419
420 80505 boost::optional<BoostRing> nonIntersectingBoostRingFromVertices(const std::vector<Point3d>& polygon, std::vector<Point3d>& allPoints, double tol) {
421
1/1
✓ Branch 1 taken 80505 times.
80505 boost::optional<BoostRing> result = boostRingFromVertices(polygon, allPoints, tol);
422
2/2
✓ Branch 1 taken 143 times.
✓ Branch 2 taken 80362 times.
80505 if (!result) {
423 143 return boost::none;
424 }
425 // check if polygon overlaps itself
426 try {
427
2/2
✓ Branch 1 taken 80362 times.
✓ Branch 4 taken 80362 times.
80362 has_self_intersections(*result);
428 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
429 //LOG_FREE(Error, "utilities.geometry.nonIntersectingBoostRingFromVertices", "Self intersecting polygon");
430 ✗ return boost::none;
431 ✗ }
432 80362 return result;
433 80505 }
434
435 // convert a boost polygon to vertices
436 16944 std::vector<Point3d> verticesFromBoostPolygon(const BoostPolygon& polygon, std::vector<Point3d>& allPoints, double tol,
437 bool removeCollinear = false) {
438 16944 std::vector<Point3d> result;
439
1/1
✓ Branch 2 taken 16944 times.
16944 BoostRing outer = polygon.outer();
440
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 16944 times.
16944 if (outer.empty()) {
441 ✗ return result;
442 }
443
444 // add point for each vertex except final vertex
445
2/2
✓ Branch 1 taken 79334 times.
✓ Branch 2 taken 16944 times.
96278 for (unsigned i = 0; i < outer.size() - 1; ++i) {
446
3/3
✓ Branch 2 taken 79334 times.
✓ Branch 6 taken 79334 times.
✓ Branch 9 taken 79334 times.
79334 const Point3d point3d(outer[i].x() / scaleBy, outer[i].y() / scaleBy, 0.0);
447
448 // try to combine points within tolerance
449
1/1
✓ Branch 1 taken 79334 times.
79334 Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol);
450
451 // don't keep repeated vertices
452
7/7
✓ Branch 0 taken 62390 times.
✓ Branch 1 taken 16944 times.
✓ Branch 4 taken 62390 times.
✓ Branch 6 taken 58 times.
✓ Branch 7 taken 62332 times.
✓ Branch 8 taken 58 times.
✓ Branch 9 taken 79276 times.
79334 if ((i > 0) && (result.back() == resultPoint)) {
453 58 continue;
454 }
455
1/1
✓ Branch 2 taken 79276 times.
79276 result.emplace_back(std::move(resultPoint));
456 79392 }
457
458
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 16944 times.
16944 if (!polygon.inners().empty()) {
459 ✗ LOG_FREE(Warn, "utilities.geometry.verticesFromBoostPolygon",
460 "Converting polygon with " << polygon.inners().size() << " inner loops to OpenStudio vertices, inner loops ignored");
461 }
462
463
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 16876 times.
16944 if (removeCollinear) {
464
1/1
✓ Branch 1 taken 68 times.
68 result = removeCollinearLegacy(result);
465 }
466
467 // don't keep repeated vertices
468
3/3
✓ Branch 3 taken 16944 times.
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 16933 times.
16944 if (result.front() == result.back()) {
469 11 result.pop_back();
470 }
471
472
2/2
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 16924 times.
16944 if (result.size() < 3) {
473 20 return {};
474 }
475
476 16924 return result;
477 16944 }
478
479 // convert a boost ring to vertices
480 ✗ std::vector<Point3d> verticesFromBoostRing(const BoostRing& ring, std::vector<Point3d>& allPoints, double tol) {
481 ✗ std::vector<Point3d> result;
482
483 // add point for each vertex except final vertex
484 ✗ for (unsigned i = 0; i < ring.size() - 1; ++i) {
485 ✗ const Point3d point3d(ring[i].x(), ring[i].y(), 0.0);
486
487 // try to combine points within tolerance
488 ✗ Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol);
489
490 // don't keep repeated vertices
491 ✗ if ((i > 0) && (result.back() == resultPoint)) {
492 ✗ continue;
493 }
494 ✗ result.emplace_back(std::move(resultPoint));
495 ✗ }
496
497 ✗ result = removeCollinearLegacy(result);
498
499 // don't keep repeated vertices
500 ✗ if (result.front() == result.back()) {
501 ✗ result.pop_back();
502 }
503
504 ✗ if (result.size() < 3) {
505 ✗ return {};
506 }
507
508 ✗ return result;
509 ✗ }
510
511 // struct used to sort polygons in descending order by area
512 struct BoostPolygonAreaGreater
513 {
514 1 bool operator()(const BoostPolygon& left, const BoostPolygon& right) const {
515
2/2
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
1 boost::optional<double> leftA = boost::geometry::area(left);
516
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
1 if (!leftA) {
517 ✗ leftA = 0;
518 }
519
2/2
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
1 boost::optional<double> rightA = boost::geometry::area(right);
520
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
1 if (!rightA) {
521 ✗ rightA = 0;
522 }
523
2/2
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
2 return (*leftA > *rightA);
524 }
525 };
526
527 // Public functions
528
529 7532 IntersectionResult::IntersectionResult(std::vector<Point3d> polygon1, std::vector<Point3d> polygon2, std::vector<std::vector<Point3d>> newPolygons1,
530 7532 std::vector<std::vector<Point3d>> newPolygons2)
531 7532 : m_polygon1(std::move(polygon1)),
532 7532 m_polygon2(std::move(polygon2)),
533 7532 m_newPolygons1(std::move(newPolygons1)),
534 7532 m_newPolygons2(std::move(newPolygons2)) {}
535
536 7530 std::vector<Point3d> IntersectionResult::polygon1() const {
537 7530 return m_polygon1;
538 }
539
540 7027 std::vector<Point3d> IntersectionResult::polygon2() const {
541 7027 return m_polygon2;
542 }
543
544 7037 std::vector<std::vector<Point3d>> IntersectionResult::newPolygons1() const {
545 7037 return m_newPolygons1;
546 }
547
548 7029 std::vector<std::vector<Point3d>> IntersectionResult::newPolygons2() const {
549 7029 return m_newPolygons2;
550 }
551
552 7203 double IntersectionResult::area1() const {
553 7203 double result = 0;
554 7203 boost::optional<double> d;
555
1/1
✓ Branch 1 taken 7203 times.
7203 d = getArea(m_polygon1);
556
1/2
✓ Branch 0 taken 7203 times.
✗ Branch 1 not taken.
7203 if (d) {
557
1/1
✓ Branch 1 taken 7203 times.
7203 result += *d;
558 } else {
559 ✗ LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon1");
560 }
561
562
2/2
✓ Branch 5 taken 1939 times.
✓ Branch 6 taken 7203 times.
9142 for (const auto& polygon : m_newPolygons1) {
563
1/1
✓ Branch 1 taken 1939 times.
1939 d = getArea(polygon);
564
1/2
✓ Branch 0 taken 1939 times.
✗ Branch 1 not taken.
1939 if (d) {
565
1/1
✓ Branch 1 taken 1939 times.
1939 result += *d;
566 } else {
567 ✗ LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon in polygons1");
568 }
569 }
570
571 7203 return result;
572 }
573
574 7221 double IntersectionResult::area2() const {
575 7221 double result = 0;
576 7221 boost::optional<double> d;
577
1/1
✓ Branch 1 taken 7221 times.
7221 d = getArea(m_polygon2);
578
1/2
✓ Branch 0 taken 7221 times.
✗ Branch 1 not taken.
7221 if (d) {
579
1/1
✓ Branch 1 taken 7221 times.
7221 result += *d;
580 } else {
581 ✗ LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon2");
582 }
583
584
2/2
✓ Branch 5 taken 1450 times.
✓ Branch 6 taken 7221 times.
8671 for (const auto& polygon : m_newPolygons2) {
585
1/1
✓ Branch 1 taken 1450 times.
1450 d = getArea(polygon);
586
1/2
✓ Branch 0 taken 1450 times.
✗ Branch 1 not taken.
1450 if (d) {
587
1/1
✓ Branch 1 taken 1450 times.
1450 result += *d;
588 } else {
589 ✗ LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon in polygons2");
590 }
591 }
592
593 7221 return result;
594 }
595
596 6 std::vector<Point3d> removeSpikes(const std::vector<Point3d>& polygon, double tol) {
597 // convert vertices to boost rings
598 6 std::vector<Point3d> allPoints;
599
600
1/1
✓ Branch 1 taken 6 times.
6 boost::optional<BoostPolygon> boostPolygon = boostPolygonFromVertices(polygon, allPoints, tol);
601
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 3 times.
6 if (!boostPolygon) {
602 3 return {};
603 }
604
605
2/2
✓ Branch 1 taken 3 times.
✓ Branch 4 taken 3 times.
3 const BoostPolygon boostResult = removeSpikes(*boostPolygon);
606
607
1/1
✓ Branch 1 taken 3 times.
3 std::vector<Point3d> result = verticesFromBoostPolygon(boostResult, allPoints, tol);
608
609 3 return result;
610 6 }
611
612 // cppcheck-suppress constParameterReference
613 20 bool polygonInPolygon(std::vector<Point3d>& points, const std::vector<Point3d>& polygon, double tol) {
614
615 // convert vertices to boost rings
616 20 std::vector<Point3d> allPoints;
617
618
1/1
✓ Branch 1 taken 20 times.
20 boost::optional<BoostRing> boostPolygon = nonIntersectingBoostRingFromVertices(polygon, allPoints, tol);
619
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
20 if (!boostPolygon) {
620 ✗ return false;
621 }
622
623
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
20 if (points.empty()) {
624 ✗ return false;
625 }
626
627
2/2
✓ Branch 5 taken 80 times.
✓ Branch 6 taken 20 times.
100 for (const Point3d& point : points) {
628
2/3
✓ Branch 1 taken 80 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 80 times.
80 if (std::abs(point.z()) > tol) {
629 ✗ return false;
630 }
631 }
632
633
2/2
✓ Branch 5 taken 78 times.
✓ Branch 6 taken 19 times.
97 for (const Point3d& point : points) {
634
1/1
✓ Branch 1 taken 78 times.
78 boost::tuple<double, double> p = boostPointFromPoint3d(point, allPoints, tol);
635
3/3
✓ Branch 1 taken 78 times.
✓ Branch 4 taken 78 times.
✓ Branch 7 taken 78 times.
78 const BoostPoint boostPoint(p.get<0>(), p.get<1>());
636
2/2
✓ Branch 1 taken 78 times.
✓ Branch 4 taken 78 times.
78 const double distance = boost::geometry::distance(boostPoint, *boostPolygon);
637
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 77 times.
78 if (distance >= 0.0001) {
638 1 return false;
639 }
640 }
641 19 return true;
642 20 }
643
644 94 bool pointInPolygon(const Point3d& point, const std::vector<Point3d>& polygon, double tol) {
645 // convert vertices to boost rings
646 94 std::vector<Point3d> allPoints;
647
648
1/1
✓ Branch 1 taken 94 times.
94 boost::optional<BoostRing> boostPolygon = nonIntersectingBoostRingFromVertices(polygon, allPoints, tol);
649
2/2
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 38 times.
94 if (!boostPolygon) {
650 56 return false;
651 }
652
653
3/3
✓ Branch 1 taken 38 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 36 times.
38 if (std::abs(point.z()) > tol) {
654 2 return false;
655 }
656
657
1/1
✓ Branch 1 taken 36 times.
36 boost::tuple<double, double> p = boostPointFromPoint3d(point, allPoints, tol);
658
3/3
✓ Branch 1 taken 36 times.
✓ Branch 4 taken 36 times.
✓ Branch 7 taken 36 times.
36 const BoostPoint boostPoint(p.get<0>(), p.get<1>());
659
660 //boost::geometry::strategy::within::winding<BoostPoint> strategy;
661 //boost::geometry::strategy::within::franklin<BoostPoint> strategy;
662 //boost::geometry::strategy::within::crossings_multiply<BoostPoint> strategy;
663 //bool result = boost::geometry::within(boostPoint, *boostPolygon, strategy);
664
665 //bool result = boost::geometry::intersects(boostPoint, *boostPolygon);
666
667 //bool result = boost::geometry::overlaps(boostPoint, *boostPolygon);
668
669
2/2
✓ Branch 1 taken 36 times.
✓ Branch 4 taken 36 times.
36 const double distance = boost::geometry::distance(boostPoint, *boostPolygon);
670 36 const bool result = (distance <= 0.0001);
671
672 36 return result;
673 94 }
674
675 13465 boost::optional<std::vector<Point3d>> join(const std::vector<Point3d>& polygon1, const std::vector<Point3d>& polygon2, double tol) {
676 // convert vertices to boost rings
677 13465 std::vector<Point3d> allPoints;
678
679
1/1
✓ Branch 1 taken 13465 times.
13465 boost::optional<BoostRing> boostPolygon1 = nonIntersectingBoostRingFromVertices(polygon1, allPoints, tol);
680
2/2
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 13441 times.
13465 if (!boostPolygon1) {
681 24 return boost::none;
682 }
683
684
1/1
✓ Branch 1 taken 13441 times.
13441 boost::optional<BoostRing> boostPolygon2 = nonIntersectingBoostRingFromVertices(polygon2, allPoints, tol);
685
2/2
✓ Branch 1 taken 31 times.
✓ Branch 2 taken 13410 times.
13441 if (!boostPolygon2) {
686 31 return boost::none;
687 }
688
689 // union the points in face coordinates,
690 13410 std::vector<BoostPolygon> unionResult;
691 try {
692
3/3
✓ Branch 1 taken 13410 times.
✓ Branch 4 taken 13410 times.
✓ Branch 7 taken 13410 times.
13410 boost::geometry::union_(*boostPolygon1, *boostPolygon2, unionResult);
693 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
694 ✗ LOG_FREE(Error, "utilities.geometry.join", "overlay_invalid_input_exception");
695 ✗ return boost::none;
696 ✗ }
697
698
1/1
✓ Branch 1 taken 13410 times.
13410 unionResult = removeSpikes(unionResult);
699
700 // should not be any holes, check for that below
701
702 // check that union is ok
703
5/6
✓ Branch 1 taken 13410 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12900 times.
✓ Branch 5 taken 510 times.
✓ Branch 6 taken 12900 times.
✓ Branch 7 taken 510 times.
13410 if (unionResult.empty() or (unionResult.size() > 1)) {
704 12900 return boost::none;
705
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 510 times.
510 } else if (!unionResult[0].inners().empty()) {
706 // check for holes
707 ✗ LOG_FREE(Error, "utilities.geometry.join", "Union has inner loops");
708 ✗ return boost::none;
709 };
710
711
1/1
✓ Branch 2 taken 510 times.
510 std::vector<Point3d> unionVertices = verticesFromBoostPolygon(unionResult[0], allPoints, tol);
712
2/2
✓ Branch 2 taken 510 times.
✓ Branch 5 taken 510 times.
510 boost::optional<double> testArea = boost::geometry::area(unionResult[0]);
713
3/6
✓ Branch 1 taken 510 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 510 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 510 times.
510 if (!testArea || unionVertices.empty()) {
714 ✗ LOG_FREE(Info, "utilities.geometry.join", "Cannot compute area of union");
715 ✗ return boost::none;
716
2/3
✓ Branch 1 taken 510 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 510 times.
510 } else if (*testArea < tol * tol) {
717 ✗ LOG_FREE(Info, "utilities.geometry.join", "Union has very small area of " << *testArea << " m^2");
718 ✗ return boost::none;
719 }
720
721 try {
722
1/1
✓ Branch 2 taken 510 times.
510 has_self_intersections(unionResult[0]);
723 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
724 ✗ LOG_FREE(Error, "utilities.geometry.join", "Union is self intersecting");
725 ✗ return boost::none;
726 ✗ }
727
728
1/1
✓ Branch 1 taken 510 times.
510 unionVertices = reorderULC(unionVertices);
729
1/1
✓ Branch 1 taken 510 times.
510 unionVertices = removeCollinearLegacy(unionVertices);
730
731
1/1
✓ Branch 1 taken 510 times.
510 return unionVertices;
732 13465 }
733
734 26050 std::vector<std::vector<Point3d>> joinAll(const std::vector<std::vector<Point3d>>& polygons, double tol) {
735 26050 std::vector<std::vector<Point3d>> result;
736
737 26050 const size_t N = polygons.size();
738
2/2
✓ Branch 0 taken 25652 times.
✓ Branch 1 taken 398 times.
26050 if (N <= 1) {
739
1/1
✓ Branch 1 taken 25652 times.
25652 return polygons;
740 }
741
742
1/1
✓ Branch 1 taken 398 times.
398 std::vector<double> polygonAreas(N, 0.0);
743
2/2
✓ Branch 0 taken 2081 times.
✓ Branch 1 taken 398 times.
2479 for (unsigned i = 0; i < N; ++i) {
744
1/1
✓ Branch 2 taken 2081 times.
2081 auto area = getArea(polygons[i]);
745
1/2
✓ Branch 0 taken 2081 times.
✗ Branch 1 not taken.
2081 if (area) {
746
1/1
✓ Branch 1 taken 2081 times.
2081 polygonAreas[i] = *area;
747 }
748 }
749
750 // compute adjacency matrix
751
1/1
✓ Branch 1 taken 398 times.
398 Matrix A(N, N, 0.0);
752
2/2
✓ Branch 0 taken 2081 times.
✓ Branch 1 taken 398 times.
2479 for (unsigned i = 0; i < N; ++i) {
753
1/1
✓ Branch 1 taken 2081 times.
2081 A(i, i) = 1.0;
754
2/2
✓ Branch 0 taken 13302 times.
✓ Branch 1 taken 2081 times.
15383 for (unsigned j = i + 1; j < N; ++j) {
755
3/3
✓ Branch 3 taken 13302 times.
✓ Branch 6 taken 385 times.
✓ Branch 7 taken 12917 times.
26604 if (join(polygons[i], polygons[j], tol)) {
756
1/1
✓ Branch 1 taken 385 times.
385 A(i, j) = 1.0;
757
1/1
✓ Branch 1 taken 385 times.
385 A(j, i) = 1.0;
758 }
759 }
760 }
761
762
1/1
✓ Branch 1 taken 398 times.
398 const std::vector<std::vector<unsigned>> connectedComponents = findConnectedComponents(A);
763
2/2
✓ Branch 5 taken 1964 times.
✓ Branch 6 taken 398 times.
2362 for (const std::vector<unsigned>& component : connectedComponents) {
764
1/1
✓ Branch 1 taken 1964 times.
1964 std::vector<unsigned> orderedComponent(component);
765 // #4831 - Use a stable_sort to produce consistent results between Windows and Unix in case you have polygons with the same area
766
1/1
✓ Branch 3 taken 1964 times.
1964 std::stable_sort(orderedComponent.begin(), orderedComponent.end(),
767 434 [&polygonAreas](int ia, int ib) { return polygonAreas[ia] > polygonAreas[ib]; });
768
769 1964 std::vector<Point3d> points;
770 1964 std::set<unsigned> joinedComponents;
771
772 // try to join at most component.size() times
773
1/2
✓ Branch 1 taken 1970 times.
✗ Branch 2 not taken.
1970 for (unsigned n = 0; n < component.size(); ++n) {
774
775 // loop over polygons to join in order
776
2/2
✓ Branch 5 taken 2152 times.
✓ Branch 6 taken 1970 times.
4122 for (const unsigned i : orderedComponent) {
777
2/2
✓ Branch 1 taken 1964 times.
✓ Branch 2 taken 188 times.
2152 if (points.empty()) {
778
1/1
✓ Branch 2 taken 1964 times.
1964 points = polygons[i];
779
1/1
✓ Branch 1 taken 1964 times.
1964 joinedComponents.insert(i);
780 } else {
781 // if not already joined
782
3/3
✓ Branch 2 taken 188 times.
✓ Branch 5 taken 137 times.
✓ Branch 6 taken 51 times.
188 if (joinedComponents.find(i) == joinedComponents.end()) {
783
1/1
✓ Branch 2 taken 137 times.
137 boost::optional<std::vector<Point3d>> joined = join(points, polygons[i], tol);
784
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 20 times.
137 if (joined) {
785
2/2
✓ Branch 1 taken 117 times.
✓ Branch 4 taken 117 times.
117 points = *joined;
786
1/1
✓ Branch 1 taken 117 times.
117 joinedComponents.insert(i);
787 }
788 137 }
789 }
790 }
791
792 // if all polygons have been joined then we are done
793
2/2
✓ Branch 2 taken 1964 times.
✓ Branch 3 taken 6 times.
1970 if (joinedComponents.size() == component.size()) {
794 1964 break;
795 }
796 }
797
798
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 1964 times.
1964 if (joinedComponents.size() != component.size()) {
799 ✗ LOG_FREE(Error, "utilities.geometry.joinAll", "Could not join all connected components");
800 }
801
1/1
✓ Branch 1 taken 1964 times.
1964 result.push_back(points);
802 1964 }
803
804 398 return result;
805 26050 }
806
807 26751 boost::optional<IntersectionResult> intersect(const std::vector<Point3d>& polygon1, const std::vector<Point3d>& polygon2, double tol) {
808
809 26751 constexpr bool extraLogging = false;
810 //std::cout << "Initial polygon1 area " << getArea(polygon1).get() << '\n';
811 //std::cout << "Initial polygon2 area " << getArea(polygon2).get() << '\n';
812
813 // convert vertices to boost rings
814 26751 std::vector<Point3d> allPoints;
815
816
1/1
✓ Branch 1 taken 26751 times.
26751 boost::optional<BoostRing> boostPolygon1 = nonIntersectingBoostRingFromVertices(polygon1, allPoints, tol);
817
2/2
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 26734 times.
26751 if (!boostPolygon1) {
818 17 return boost::none;
819 }
820
821
1/1
✓ Branch 1 taken 26734 times.
26734 boost::optional<BoostRing> boostPolygon2 = nonIntersectingBoostRingFromVertices(polygon2, allPoints, tol);
822
2/2
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 26719 times.
26734 if (!boostPolygon2) {
823 15 return boost::none;
824 }
825
826 26719 BoostMultiPolygon polys;
827 if constexpr (extraLogging) {
828 boost::optional<BoostPolygon> poly1 = boostPolygonFromVertices(polygon1, allPoints, tol);
829 if (poly1.has_value()) {
830 polys.push_back(*poly1);
831 }
832 boost::optional<BoostPolygon> poly2 = boostPolygonFromVertices(polygon2, allPoints, tol);
833 if (poly2.has_value()) {
834 polys.push_back(*poly2);
835 }
836 }
837
838 // intersect the points in face coordinates,
839 26719 std::vector<BoostPolygon> intersectionResult;
840 try {
841
3/3
✓ Branch 1 taken 26719 times.
✓ Branch 4 taken 26719 times.
✓ Branch 7 taken 26719 times.
26719 boost::geometry::intersection(*boostPolygon1, *boostPolygon2, intersectionResult);
842 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
843 ✗ LOG_FREE(Error, "utilities.geometry.intersect", "overlay_invalid_input_exception");
844 ✗ return boost::none;
845 ✗ }
846
847 if constexpr (extraLogging) {
848 polys.push_back(intersectionResult[0]);
849 }
850
851 // check if intersection is empty
852
2/2
✓ Branch 1 taken 19110 times.
✓ Branch 2 taken 7609 times.
26719 if (intersectionResult.empty()) {
853 //LOG_FREE(Info, "utilities.geometry.intersect", "Intersection is empty");
854 19110 return boost::none;
855 }
856
857
1/1
✓ Branch 1 taken 7609 times.
7609 intersectionResult = removeSpikes(intersectionResult);
858
2/2
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 7532 times.
7609 if (intersectionResult.empty()) {
859 77 return boost::none;
860 }
861 if constexpr (extraLogging) {
862 polys.push_back(intersectionResult[0]);
863 LOG_FREE(Debug, "intersection result", polys);
864 }
865
1/1
✓ Branch 1 taken 7532 times.
7532 intersectionResult = removeHoles(intersectionResult);
866
867 // check for multiple intersections
868
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 7531 times.
7532 if (intersectionResult.size() > 1) {
869
7/7
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✓ Branch 8 taken 1 time.
✓ Branch 11 taken 1 time.
✓ Branch 14 taken 1 time.
✓ Branch 17 taken 1 time.
✓ Branch 20 taken 1 time.
3 LOG_FREE(Info, "utilities.geometry.intersect", "Intersection has " << intersectionResult.size() << " elements");
870
1/1
✓ Branch 3 taken 1 time.
1 std::sort(intersectionResult.begin(), intersectionResult.end(), BoostPolygonAreaGreater());
871 }
872
873 // check that largest intersection is ok
874
1/1
✓ Branch 2 taken 7532 times.
7532 std::vector<Point3d> intersectionVertices = verticesFromBoostPolygon(intersectionResult[0], allPoints, tol, false);
875
2/2
✓ Branch 2 taken 7532 times.
✓ Branch 5 taken 7532 times.
7532 boost::optional<double> testArea = boost::geometry::area(intersectionResult[0]);
876
3/6
✓ Branch 1 taken 7532 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 7532 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 7532 times.
7532 if (!testArea || intersectionVertices.empty()) {
877 ✗ LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of largest intersection");
878 ✗ return boost::none;
879
2/3
✓ Branch 1 taken 7532 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 7532 times.
7532 } else if (*testArea < tol * tol) {
880 ✗ LOG_FREE(Info, "utilities.geometry.intersect", "Largest intersection has very small area of " << *testArea << " m^2");
881 ✗ return boost::none;
882 }
883 try {
884
1/1
✓ Branch 2 taken 7532 times.
7532 has_self_intersections(intersectionResult[0]);
885 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
886 ✗ LOG_FREE(Error, "utilities.geometry.intersect", "Largest intersection is self intersecting");
887 ✗ return boost::none;
888 ✗ }
889
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 7532 times.
7532 if (!intersectionResult[0].inners().empty()) {
890 ✗ LOG_FREE(Error, "utilities.geometry.intersect", "Largest intersection has inner loops");
891 ✗ return boost::none;
892 };
893
894 7532 std::vector<std::vector<Point3d>> newPolygons1;
895
1/1
✓ Branch 2 taken 7532 times.
7532 newPolygons1.reserve(intersectionResult.size() - 1);
896
897 // create new polygon for each **remaining** intersection (all but the largest one)
898
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 7532 times.
7533 for (unsigned i = 1; i < intersectionResult.size(); ++i) {
899
900
1/1
✓ Branch 2 taken 1 time.
1 std::vector<Point3d> newPolygon = verticesFromBoostPolygon(intersectionResult[i], allPoints, tol, false);
901
902
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
1 testArea = boost::geometry::area(intersectionResult[i]);
903
3/6
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 time.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 time.
1 if (!testArea || newPolygon.empty()) {
904 ✗ LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of intersection, result will not include this polygon, " << newPolygon);
905 ✗ continue;
906
2/3
✓ Branch 1 taken 1 time.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 time.
1 } else if (*testArea < tol * tol) {
907 ✗ LOG_FREE(Info, "utilities.geometry.intersect",
908 "Intersection has very small area of " << *testArea << " m^2, result will not include this polygon, " << newPolygon);
909 ✗ continue;
910 ✗ }
911 try {
912
1/1
✓ Branch 2 taken 1 time.
1 has_self_intersections(intersectionResult[i]);
913 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
914 ✗ LOG_FREE(Error, "utilities.geometry.intersect", "Intersection is self intersecting, result will not include this polygon, " << newPolygon);
915 ✗ continue;
916 ✗ }
917
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 1 time.
1 if (!intersectionResult[i].inners().empty()) {
918 ✗ LOG_FREE(Error, "utilities.geometry.intersect", "Intersection has inner loops, result will not include this polygon, " << newPolygon);
919 ✗ continue;
920 ✗ };
921
922
1/1
✓ Branch 2 taken 1 time.
1 newPolygons1.push_back(std::move(newPolygon));
923 1 }
924
925
1/1
✓ Branch 1 taken 7532 times.
7532 std::vector<std::vector<Point3d>> newPolygons2 = newPolygons1;
926
927 // polygon1 minus polygon2
928 7532 std::vector<BoostPolygon> differenceResult1;
929
3/3
✓ Branch 1 taken 7532 times.
✓ Branch 4 taken 7532 times.
✓ Branch 7 taken 7532 times.
7532 boost::geometry::difference(*boostPolygon1, *boostPolygon2, differenceResult1);
930
1/1
✓ Branch 1 taken 7532 times.
7532 differenceResult1 = removeSpikes(differenceResult1);
931
1/1
✓ Branch 1 taken 7532 times.
7532 differenceResult1 = removeHoles(differenceResult1);
932
933
1/1
✓ Branch 3 taken 7532 times.
7532 newPolygons1.reserve(newPolygons1.size() + differenceResult1.size());
934
935 // create new polygon for each difference
936
2/2
✓ Branch 5 taken 1948 times.
✓ Branch 6 taken 7532 times.
9480 for (auto& pp : differenceResult1) {
937
1/1
✓ Branch 1 taken 1948 times.
1948 std::vector<Point3d> newPolygon1 = verticesFromBoostPolygon(pp, allPoints, tol, false);
938
939
2/2
✓ Branch 1 taken 1948 times.
✓ Branch 4 taken 1948 times.
1948 testArea = boost::geometry::area(pp);
940
3/6
✓ Branch 1 taken 1948 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1948 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1948 times.
1948 if (!testArea || newPolygon1.empty()) {
941 ✗ LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of face difference, result will not include this polygon, " << newPolygon1);
942 ✗ continue;
943
2/3
✓ Branch 1 taken 1948 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1948 times.
1948 } else if (*testArea < tol * tol) {
944 ✗ LOG_FREE(Info, "utilities.geometry.intersect",
945 "Face difference has very small area of " << *testArea << " m^2, result will not include this polygon, " << newPolygon1);
946 ✗ continue;
947 ✗ }
948 try {
949
1/1
✓ Branch 1 taken 1942 times.
1948 has_self_intersections(pp);
950
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
6 } catch (const boost::geometry::overlay_invalid_input_exception&) {
951
6/6
✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
✓ Branch 7 taken 6 times.
✓ Branch 10 taken 6 times.
✓ Branch 13 taken 6 times.
✓ Branch 16 taken 6 times.
18 LOG_FREE(Error, "utilities.geometry.intersect", "Face difference is self intersecting, result will not include this polygon, " << newPolygon1);
952 6 continue;
953 6 }
954
955
1/1
✓ Branch 2 taken 1942 times.
1942 newPolygons1.push_back(std::move(newPolygon1));
956 1948 }
957
958 // polygon2 minus polygon1
959 7532 std::vector<BoostPolygon> differenceResult2;
960
3/3
✓ Branch 1 taken 7532 times.
✓ Branch 4 taken 7532 times.
✓ Branch 7 taken 7532 times.
7532 boost::geometry::difference(*boostPolygon2, *boostPolygon1, differenceResult2);
961
1/1
✓ Branch 1 taken 7532 times.
7532 differenceResult2 = removeSpikes(differenceResult2);
962
1/1
✓ Branch 1 taken 7532 times.
7532 differenceResult2 = removeHoles(differenceResult2);
963
964
1/1
✓ Branch 3 taken 7532 times.
7532 newPolygons2.reserve(newPolygons2.size() + differenceResult2.size());
965
966 // create new polygon for each difference
967
2/2
✓ Branch 5 taken 3276 times.
✓ Branch 6 taken 7532 times.
10808 for (auto& pp : differenceResult2) {
968
1/1
✓ Branch 1 taken 3276 times.
3276 std::vector<Point3d> newPolygon2 = verticesFromBoostPolygon(pp, allPoints, tol, false);
969
970
2/2
✓ Branch 1 taken 3276 times.
✓ Branch 4 taken 3276 times.
3276 testArea = boost::geometry::area(pp);
971
5/6
✓ Branch 1 taken 3276 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✓ Branch 5 taken 3256 times.
✓ Branch 6 taken 20 times.
✓ Branch 7 taken 3256 times.
3276 if (!testArea || newPolygon2.empty()) {
972
6/6
✓ Branch 1 taken 20 times.
✓ Branch 4 taken 20 times.
✓ Branch 7 taken 20 times.
✓ Branch 10 taken 20 times.
✓ Branch 13 taken 20 times.
✓ Branch 16 taken 20 times.
60 LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of face difference, result will not include this polygon, " << newPolygon2);
973 20 continue;
974
2/3
✓ Branch 1 taken 3256 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 3256 times.
3276 } else if (*testArea < tol * tol) {
975 ✗ LOG_FREE(Info, "utilities.geometry.intersect",
976 "Face difference has very small area of " << *testArea << " m^2, result will not include this polygon, " << newPolygon2);
977 ✗ continue;
978 ✗ }
979 try {
980
1/1
✓ Branch 1 taken 3256 times.
3256 has_self_intersections(pp);
981 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
982 ✗ LOG_FREE(Error, "utilities.geometry.intersect", "Face difference is self intersecting, result will not include this polygon, " << newPolygon2);
983 ✗ continue;
984 ✗ }
985
986
1/1
✓ Branch 2 taken 3256 times.
3256 newPolygons2.push_back(std::move(newPolygon2));
987 3276 }
988
989 // intersections are the same
990
1/1
✓ Branch 1 taken 7532 times.
7532 std::vector<Point3d> resultPolygon1 = intersectionVertices;
991
1/1
✓ Branch 9 taken 7532 times.
7532 IntersectionResult result(std::move(resultPolygon1), std::move(intersectionVertices), std::move(newPolygons1), std::move(newPolygons2));
992
993 //std::cout << "Result area1 " << result.area1() << '\n';
994 //std::cout << "Result area2 " << result.area2() << '\n';
995
996
1/1
✓ Branch 1 taken 7532 times.
7532 return result;
997 26751 }
998
999 423 std::vector<std::vector<Point3d>> subtract(const std::vector<Point3d>& polygon, const std::vector<std::vector<Point3d>>& holes, double tol) {
1000 423 std::vector<std::vector<Point3d>> result;
1001
1002 // convert vertices to boost rings
1003 423 std::vector<Point3d> allPoints;
1004
1005
1/1
✓ Branch 1 taken 423 times.
423 boost::optional<BoostPolygon> initialBoostPolygon = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol);
1006
2/2
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 412 times.
423 if (!initialBoostPolygon) {
1007 11 return result;
1008 }
1009
1010 412 std::vector<BoostPolygon> boostPolygons;
1011
2/2
✓ Branch 1 taken 412 times.
✓ Branch 4 taken 412 times.
412 boostPolygons.push_back(*initialBoostPolygon);
1012
1013
2/2
✓ Branch 5 taken 573 times.
✓ Branch 6 taken 410 times.
983 for (const auto& hole : holes) {
1014
1/1
✓ Branch 1 taken 573 times.
573 boost::optional<BoostPolygon> boostHole = nonIntersectingBoostPolygonFromVertices(hole, allPoints, tol);
1015
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 571 times.
573 if (!boostHole) {
1016 2 return result;
1017 }
1018
1019 571 std::vector<BoostPolygon> newBoostPolygons;
1020
1021
2/2
✓ Branch 5 taken 573 times.
✓ Branch 6 taken 571 times.
1144 for (const BoostPolygon& boostPolygon : boostPolygons) {
1022 573 std::vector<BoostPolygon> diffResult;
1023
2/2
✓ Branch 1 taken 573 times.
✓ Branch 4 taken 573 times.
573 boost::geometry::difference(boostPolygon, *boostHole, diffResult);
1024
1/1
✓ Branch 3 taken 573 times.
573 newBoostPolygons.reserve(newBoostPolygons.size() + diffResult.size());
1025
3/3
✓ Branch 2 taken 573 times.
✓ Branch 6 taken 573 times.
✓ Branch 11 taken 573 times.
573 newBoostPolygons.insert(newBoostPolygons.end(), std::make_move_iterator(diffResult.begin()), std::make_move_iterator(diffResult.end()));
1026 573 }
1027 571 boostPolygons = std::move(newBoostPolygons);
1028 573 }
1029
1030 // Remove the holes and spikes and convert back to our data types
1031
2/2
✓ Branch 5 taken 437 times.
✓ Branch 6 taken 410 times.
847 for (const BoostPolygon& boostPolygon : boostPolygons) {
1032
1/1
✓ Branch 1 taken 437 times.
437 const BoostPolygon removedSpikes = removeSpikes(boostPolygon);
1033
1/1
✓ Branch 1 taken 437 times.
437 const std::vector<BoostPolygon>& removedHoles = removeHoles(removedSpikes);
1034
1/1
✓ Branch 3 taken 437 times.
437 result.reserve(result.size() + removedHoles.size());
1035
2/2
✓ Branch 4 taken 2046 times.
✓ Branch 5 taken 437 times.
2483 for (const BoostPolygon& removedHole : removedHoles) {
1036
2/2
✓ Branch 1 taken 2046 times.
✓ Branch 4 taken 2046 times.
2046 result.push_back(verticesFromBoostPolygon(removedHole, allPoints, tol));
1037 }
1038 437 }
1039
1040 410 return result;
1041 423 }
1042
1043 5 bool selfIntersects(const std::vector<Point3d>& polygon, double tol) {
1044 // convert vertices to boost rings
1045 5 std::vector<Point3d> allPoints;
1046
1047
1/1
✓ Branch 1 taken 5 times.
5 const boost::optional<BoostPolygon> bp = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol);
1048 // if bp has a value, we're able to get a non intersecting polygon, so does not self intersect
1049 10 return !bp.has_value();
1050 5 }
1051
1052 ✗ bool intersects(const std::vector<Point3d>& polygon1, const std::vector<Point3d>& polygon2, double tol) {
1053 // convert vertices to boost rings
1054 ✗ std::vector<Point3d> allPoints;
1055
1056 ✗ boost::optional<BoostPolygon> bp1 = boostPolygonFromVertices(polygon1, allPoints, tol);
1057 ✗ boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol);
1058
1059 ✗ if (bp1 && bp2) {
1060 ✗ return boost::geometry::intersects(*bp1, *bp2);
1061 }
1062
1063 ✗ return false;
1064 ✗ }
1065
1066 1432 bool within(const Point3d& point1, const std::vector<Point3d>& polygon2, double tol) {
1067
3/5
✓ Branch 1 taken 1432 times.
✓ Branch 3 taken 1432 times.
✓ Branch 4 taken 1432 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
4296 const std::vector<Point3d> geometry1 = {point1};
1068
1/1
✓ Branch 1 taken 1432 times.
2864 return within(geometry1, polygon2, tol);
1069 2864 }
1070
1071 4163 bool within(const std::vector<Point3d>& geometry1, const std::vector<Point3d>& polygon2, double tol) {
1072 // convert vertices to boost rings
1073 4163 std::vector<Point3d> allPoints;
1074
1075
2/2
✓ Branch 1 taken 1432 times.
✓ Branch 2 taken 2731 times.
4163 if (geometry1.size() == 1) {
1076
3/3
✓ Branch 2 taken 1432 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 1430 times.
1432 if (geometry1[0].z() > tol) {
1077 2 return false;
1078 }
1079
1080
1/1
✓ Branch 2 taken 1430 times.
1430 boost::tuple<double, double> p = boostPointFromPoint3d(geometry1[0], allPoints, tol);
1081
3/3
✓ Branch 1 taken 1430 times.
✓ Branch 4 taken 1430 times.
✓ Branch 7 taken 1430 times.
1430 const BoostPoint boostPoint(p.get<0>(), p.get<1>());
1082
1083
1/1
✓ Branch 1 taken 1430 times.
1430 boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol);
1084
1085
2/2
✓ Branch 0 taken 1377 times.
✓ Branch 1 taken 53 times.
1430 if (bp2) {
1086
2/2
✓ Branch 1 taken 1377 times.
✓ Branch 4 taken 1377 times.
1377 return boost::geometry::within(boostPoint, *bp2);
1087 }
1088
1089 53 return false;
1090 1430 }
1091
1092 /*
1093 // DLM: this is the better implementation, requires boost 1.57
1094 boost::optional<BoostPolygon> bp1 = boostPolygonFromVertices(geometry1, allPoints, tol);
1095 boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol);
1096 if (bp1 && bp2){
1097 return boost::geometry::within(*bp1, *bp2);
1098 }
1099 */
1100
1101 // DLM: temp code
1102
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2731 times.
2731 if (geometry1.size() < 3) {
1103 ✗ return false;
1104 }
1105
1/1
✓ Branch 1 taken 2731 times.
2731 boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol);
1106
1/2
✓ Branch 0 taken 2731 times.
✗ Branch 1 not taken.
2731 if (bp2) {
1107
2/2
✓ Branch 5 taken 10254 times.
✓ Branch 6 taken 2382 times.
12636 for (const Point3d& point : geometry1) {
1108
1/1
✓ Branch 1 taken 10254 times.
10254 boost::tuple<double, double> p = boostPointFromPoint3d(point, allPoints, tol);
1109
3/3
✓ Branch 1 taken 10254 times.
✓ Branch 4 taken 10254 times.
✓ Branch 7 taken 10254 times.
10254 const BoostPoint boostPoint(p.get<0>(), p.get<1>());
1110
1111
4/4
✓ Branch 1 taken 10254 times.
✓ Branch 4 taken 10254 times.
✓ Branch 6 taken 349 times.
✓ Branch 7 taken 9905 times.
10254 if (!boost::geometry::within(boostPoint, *bp2)) {
1112 349 return false;
1113 }
1114 }
1115 } else {
1116 ✗ return false;
1117 }
1118
1119 2382 return true;
1120 4163 }
1121
1122 2615 boost::optional<double> getLinearAlpha(const Point3d& point0, const Point3d& point1, const Point3d& test) {
1123 // test = point0 + a*(point1 - point0)
1124
1/1
✓ Branch 1 taken 2615 times.
2615 Vector3d diff1 = point1 - point0;
1125
1/1
✓ Branch 1 taken 2615 times.
2615 const Vector3d diffTest = test - point0;
1126
1127
1/1
✓ Branch 1 taken 2615 times.
2615 const double length = diff1.length();
1128
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2615 times.
2615 if (length < 0.001) {
1129 ✗ return boost::none;
1130 }
1131
1132 2615 double a = 0.0;
1133
4/4
✓ Branch 1 taken 2615 times.
✓ Branch 5 taken 2615 times.
✓ Branch 8 taken 1222 times.
✓ Branch 9 taken 1393 times.
2615 if (std::abs(diff1.x()) > std::abs(diff1.y())) {
1134
3/4
✓ Branch 1 taken 1222 times.
✓ Branch 5 taken 1222 times.
✓ Branch 8 taken 1222 times.
✗ Branch 9 not taken.
1222 if (std::abs(diff1.x()) > std::abs(diff1.z())) {
1135
2/2
✓ Branch 1 taken 1222 times.
✓ Branch 4 taken 1222 times.
1222 a = diffTest.x() / diff1.x();
1136 } else {
1137 ✗ a = diffTest.z() / diff1.z();
1138 }
1139 } else {
1140
3/4
✓ Branch 1 taken 1393 times.
✓ Branch 5 taken 1393 times.
✓ Branch 8 taken 1393 times.
✗ Branch 9 not taken.
1393 if (std::abs(diff1.y()) > std::abs(diff1.z())) {
1141
2/2
✓ Branch 1 taken 1393 times.
✓ Branch 4 taken 1393 times.
1393 a = diffTest.y() / diff1.y();
1142 } else {
1143 ✗ a = diffTest.z() / diff1.z();
1144 }
1145 }
1146
1147
1/1
✓ Branch 1 taken 2615 times.
2615 diff1.setLength(a * length);
1148
1/1
✓ Branch 1 taken 2615 times.
2615 const Point3d test2 = point0 + diff1;
1149
1/1
✓ Branch 1 taken 2615 times.
2615 const double d = getDistance(test, test2);
1150
2/2
✓ Branch 0 taken 783 times.
✓ Branch 1 taken 1832 times.
2615 if (d < 0.001) {
1151
4/4
✓ Branch 0 taken 779 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 702 times.
✓ Branch 3 taken 77 times.
783 if (a > 0 && a < 1) {
1152
1/1
✓ Branch 1 taken 702 times.
702 return a;
1153 }
1154 }
1155
1156 1913 return boost::none;
1157 2615 }
1158
1159 1605 std::vector<Point3d> simplify(const std::vector<Point3d>& vertices, bool removeCollinear, double tol) {
1160 1605 std::vector<Point3d> allPoints;
1161
1162 1605 bool reversed = false;
1163
1/1
✓ Branch 1 taken 1605 times.
1605 boost::optional<Vector3d> outwardNormal = getOutwardNormal(vertices);
1164
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1603 times.
1605 if (!outwardNormal) {
1165 2 return {};
1166
4/4
✓ Branch 1 taken 1603 times.
✓ Branch 4 taken 1603 times.
✓ Branch 6 taken 992 times.
✓ Branch 7 taken 611 times.
1603 } else if (outwardNormal->z() > 0) {
1167 992 reversed = true;
1168 }
1169
1170 1603 boost::optional<BoostPolygon> bp;
1171
2/2
✓ Branch 0 taken 992 times.
✓ Branch 1 taken 611 times.
1603 if (reversed) {
1172
3/3
✓ Branch 1 taken 992 times.
✓ Branch 4 taken 992 times.
✓ Branch 7 taken 992 times.
992 bp = boostPolygonFromVertices(reorderULC(reverse(vertices)), allPoints, tol);
1173 } else {
1174
2/2
✓ Branch 1 taken 611 times.
✓ Branch 4 taken 611 times.
611 bp = boostPolygonFromVertices(reorderULC(vertices), allPoints, tol);
1175 }
1176
1177
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1603 times.
1603 if (!bp) {
1178 ✗ return {};
1179 }
1180
1181
2/2
✓ Branch 1 taken 1603 times.
✓ Branch 4 taken 1603 times.
1603 boost::geometry::remove_spikes(*bp);
1182
1183
1/1
✓ Branch 1 taken 1603 times.
1603 BoostPolygon out;
1184
1185 // this uses the Douglas-Peucker algorithm with a max difference of 0 so no non-collinear points will be removed
1186 // if we want to allow this algorithm to be called with a non-zero value I suggest naming it "approximate" or something
1187
2/2
✓ Branch 0 taken 1535 times.
✓ Branch 1 taken 68 times.
1603 if (!removeCollinear) {
1188
2/2
✓ Branch 1 taken 1535 times.
✓ Branch 4 taken 1535 times.
1535 boost::geometry::simplify(*bp, out, 0.0);
1189 } else {
1190
2/2
✓ Branch 1 taken 68 times.
✓ Branch 4 taken 68 times.
68 boost::geometry::simplify(*bp, out, tol); // points within tol would already be merged
1191 }
1192
1193
1/1
✓ Branch 1 taken 1603 times.
1603 std::vector<Point3d> tmp = verticesFromBoostPolygon(out, allPoints, tol, removeCollinear);
1194
1195
2/2
✓ Branch 0 taken 992 times.
✓ Branch 1 taken 611 times.
1603 if (reversed) {
1196
2/2
✓ Branch 1 taken 992 times.
✓ Branch 4 taken 992 times.
992 tmp = reorderULC(reverse(tmp));
1197 } else {
1198
1/1
✓ Branch 1 taken 611 times.
611 tmp = reorderULC(tmp);
1199 }
1200
1201
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 1535 times.
1603 if (removeCollinear) {
1202 // collinear points already removed
1203 68 return tmp;
1204 }
1205
1206
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1535 times.
1535 if (tmp.empty()) {
1207 ✗ return tmp;
1208 }
1209
1210 // we want to add back in all the unique points, have to put them in the right place
1211 1535 std::set<size_t> pointsToAdd;
1212
2/2
✓ Branch 1 taken 10352 times.
✓ Branch 2 taken 1535 times.
11887 for (size_t i = 0; i < allPoints.size(); ++i) {
1213 10352 bool found = false;
1214
2/2
✓ Branch 5 taken 79062 times.
✓ Branch 6 taken 10352 times.
89414 for (const auto& tmpPoint : tmp) {
1215
3/3
✓ Branch 2 taken 79062 times.
✓ Branch 4 taken 9648 times.
✓ Branch 5 taken 69414 times.
79062 if (getDistance(tmpPoint, allPoints[i]) < tol) {
1216 9648 found = true;
1217 }
1218 }
1219
2/2
✓ Branch 0 taken 704 times.
✓ Branch 1 taken 9648 times.
10352 if (!found) {
1220
1/1
✓ Branch 1 taken 704 times.
704 pointsToAdd.insert(i);
1221 }
1222 }
1223
1224 1535 std::vector<Point3d> result;
1225
1/1
✓ Branch 2 taken 1535 times.
1535 result.push_back(tmp[0]);
1226
2/2
✓ Branch 1 taken 8113 times.
✓ Branch 2 taken 1535 times.
9648 for (size_t i = 1; i < tmp.size(); ++i) {
1227 // see which remaining points fit in this segment, double is index in allPoints, alpha along line
1228 8113 std::vector<std::pair<size_t, double>> pointsInSegment;
1229
2/2
✓ Branch 5 taken 2487 times.
✓ Branch 6 taken 8113 times.
10600 for (const size_t j : pointsToAdd) {
1230
1/1
✓ Branch 4 taken 2487 times.
2487 boost::optional<double> alpha = getLinearAlpha(tmp[i - 1], tmp[i], allPoints[j]);
1231
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 1911 times.
2487 if (alpha) {
1232
2/2
✓ Branch 1 taken 576 times.
✓ Branch 4 taken 576 times.
576 pointsInSegment.emplace_back(j, *alpha);
1233 }
1234 }
1235
1236
1/1
✓ Branch 3 taken 8113 times.
8113 std::sort(pointsInSegment.begin(), pointsInSegment.end(),
1237 218 [](std::pair<size_t, double> a, std::pair<size_t, double> b) { return a.second < b.second; });
1238
1239
2/2
✓ Branch 5 taken 576 times.
✓ Branch 6 taken 8113 times.
8689 for (const auto& pointInSegment : pointsInSegment) {
1240
1/1
✓ Branch 2 taken 576 times.
576 result.push_back(allPoints[pointInSegment.first]);
1241
1/1
✓ Branch 1 taken 576 times.
576 pointsToAdd.erase(pointInSegment.first);
1242 }
1243
1244 // push the next point in simplified polygon
1245
1/1
✓ Branch 2 taken 8113 times.
8113 result.push_back(tmp[i]);
1246 8113 }
1247
1248 // now check between last point and first point
1249 1535 std::vector<std::pair<size_t, double>> pointsInSegment;
1250
2/2
✓ Branch 5 taken 128 times.
✓ Branch 6 taken 1535 times.
1663 for (const size_t j : pointsToAdd) {
1251
1/1
✓ Branch 5 taken 128 times.
128 boost::optional<double> alpha = getLinearAlpha(tmp[tmp.size() - 1], tmp[0], allPoints[j]);
1252
2/2
✓ Branch 0 taken 126 times.
✓ Branch 1 taken 2 times.
128 if (alpha) {
1253
2/2
✓ Branch 1 taken 126 times.
✓ Branch 4 taken 126 times.
126 pointsInSegment.emplace_back(j, *alpha);
1254 }
1255 }
1256
1257
1/1
✓ Branch 3 taken 1535 times.
1535 std::sort(pointsInSegment.begin(), pointsInSegment.end(),
1258 48 [](std::pair<size_t, double> a, std::pair<size_t, double> b) { return a.second < b.second; });
1259
1260
2/2
✓ Branch 5 taken 126 times.
✓ Branch 6 taken 1535 times.
1661 for (const auto& pointInSegment : pointsInSegment) {
1261
1/1
✓ Branch 2 taken 126 times.
126 result.push_back(allPoints[pointInSegment.first]);
1262
1/1
✓ Branch 1 taken 126 times.
126 pointsToAdd.erase(pointInSegment.first);
1263 }
1264
1265
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1533 times.
1535 if (!pointsToAdd.empty()) {
1266
6/6
✓ Branch 1 taken 2 times.
✓ Branch 5 taken 2 times.
✓ Branch 8 taken 2 times.
✓ Branch 11 taken 2 times.
✓ Branch 14 taken 2 times.
✓ Branch 17 taken 2 times.
6 LOG_FREE(Warn, "utilities.geometry.simplify", pointsToAdd.size() << " unique vertices were not added back to the polygon");
1267 }
1268
1269 1535 return result;
1270 1605 }
1271
1272 /// Converts a Polygon to a BoostPolygon
1273 3686 boost::optional<BoostPolygon> BoostPolygonFromPolygon(const Polygon3d& polygon, Point3dVector& allPoints, double tol) {
1274
1/1
✓ Branch 1 taken 3686 times.
3686 BoostPolygon boostPolygon;
1275
1276
3/3
✓ Branch 1 taken 3686 times.
✓ Branch 7 taken 19932 times.
✓ Branch 8 taken 3686 times.
23618 for (const Point3d& vertex : polygon.getOuterPath()) {
1277
1278 // should all have zero z coordinate now
1279 //double z = vertex.z();
1280 //if (std::abs(z) > tol) {
1281 // LOG_FREE(Error, "utilities.geometry.boostPolygonFromVertices", "All points must be on z = 0 plane");
1282 // return boost::none;
1283 //}
1284
2/2
✓ Branch 1 taken 19932 times.
✓ Branch 4 taken 19932 times.
19932 boost::geometry::append(boostPolygon, boostPointFromPoint3d(vertex, allPoints, tol));
1285 3686 }
1286
1287
1/1
✓ Branch 1 taken 3686 times.
3686 const Point3dVector& path = polygon.getOuterPath();
1288 3686 const Point3d& first = path.front();
1289
2/2
✓ Branch 1 taken 3686 times.
✓ Branch 4 taken 3686 times.
3686 boost::geometry::append(boostPolygon, boostPointFromPoint3d(first, allPoints, tol));
1290
1291
1/1
✓ Branch 1 taken 3686 times.
7372 return boostPolygon;
1292 3686 }
1293
1294 499 Polygon3d PolygonFromBoostPolygon(const BoostPolygon& boostPolygon, Point3dVector& allPoints, double tol) {
1295 499 Polygon3d p;
1296
1/1
✓ Branch 2 taken 499 times.
499 BoostRing outer = boostPolygon.outer();
1297
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 499 times.
499 if (outer.empty()) {
1298 ✗ return p;
1299 }
1300
1301 499 Point3dVector points;
1302
2/2
✓ Branch 1 taken 4977 times.
✓ Branch 2 taken 499 times.
5476 for (unsigned i = 0; i < outer.size() - 1; ++i) {
1303
3/3
✓ Branch 2 taken 4977 times.
✓ Branch 6 taken 4977 times.
✓ Branch 9 taken 4977 times.
4977 const Point3d point3d(outer[i].x() / scaleBy, outer[i].y() / scaleBy, 0.0);
1304
1/1
✓ Branch 1 taken 4977 times.
4977 Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol);
1305 // don't keep repeated vertices
1306
5/7
✓ Branch 0 taken 4478 times.
✓ Branch 1 taken 499 times.
✓ Branch 4 taken 4478 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 4478 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 4977 times.
4977 if ((i > 0) && (points.back() == resultPoint)) {
1307 ✗ continue;
1308 }
1309
1/1
✓ Branch 2 taken 4977 times.
4977 points.emplace_back(std::move(resultPoint));
1310 4977 }
1311
1312
1/1
✓ Branch 1 taken 499 times.
499 points = removeCollinearLegacy(points);
1313
2/2
✓ Branch 5 taken 4977 times.
✓ Branch 6 taken 499 times.
5476 for (const auto& point : points) {
1314
1/1
✓ Branch 1 taken 4977 times.
4977 p.addPoint(point);
1315 }
1316
1317
2/2
✓ Branch 6 taken 19 times.
✓ Branch 7 taken 499 times.
518 for (const auto& inner : boostPolygon.inners()) {
1318 19 Point3dVector hole;
1319
2/2
✓ Branch 1 taken 76 times.
✓ Branch 2 taken 19 times.
95 for (unsigned i = 0; i < inner.size() - 1; ++i) {
1320
3/3
✓ Branch 2 taken 76 times.
✓ Branch 6 taken 76 times.
✓ Branch 9 taken 76 times.
76 Point3d point3d(inner[i].x() / scaleBy, inner[i].y() / scaleBy, 0.0);
1321
1/1
✓ Branch 1 taken 76 times.
76 const Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol);
1322 // don't keep repeated vertices
1323
5/7
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 57 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 57 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 76 times.
76 if ((i > 0) && (hole.back() == resultPoint)) {
1324 ✗ continue;
1325 }
1326
1/1
✓ Branch 2 taken 76 times.
76 hole.emplace_back(std::move(resultPoint));
1327 76 }
1328
1/1
✓ Branch 1 taken 19 times.
19 p.addHole(hole);
1329 19 }
1330
1331 499 return p;
1332 499 }
1333
1334 // Non class member stuff
1335 1843 boost::optional<Polygon3d> join(const Polygon3d& polygon1, const Polygon3d& polygon2) {
1336 1843 Point3dVector allPoints;
1337
1338 1843 constexpr double tol = 0.01;
1339
1340 // Convert polygons to boost polygon (not ring obvs)
1341
1/1
✓ Branch 1 taken 1843 times.
1843 boost::optional<BoostPolygon> boostPolygon1 = BoostPolygonFromPolygon(polygon1, allPoints, tol);
1342
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1843 times.
1843 if (!boostPolygon1) {
1343 ✗ return boost::none;
1344 }
1345
1346
1/1
✓ Branch 1 taken 1843 times.
1843 boost::optional<BoostPolygon> boostPolygon2 = BoostPolygonFromPolygon(polygon2, allPoints, tol);
1347
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1843 times.
1843 if (!boostPolygon2) {
1348 ✗ return boost::none;
1349 }
1350
1351 1843 std::vector<BoostPolygon> unionResult;
1352 try {
1353
3/3
✓ Branch 1 taken 1843 times.
✓ Branch 4 taken 1843 times.
✓ Branch 7 taken 1843 times.
1843 boost::geometry::union_(*boostPolygon1, *boostPolygon2, unionResult);
1354 ✗ } catch (const boost::geometry::overlay_invalid_input_exception&) {
1355 ✗ LOG_FREE(Error, "utilities.geometry.join", "overlay_invalid_input_exception");
1356 ✗ return boost::none;
1357 ✗ }
1358
1359 // Smooth the result
1360
1/1
✓ Branch 1 taken 1843 times.
1843 unionResult = removeSpikes(unionResult);
1361
1362 // Check the result - we do not have to bail for holes but we bail for > 1 poly
1363
6/6
✓ Branch 1 taken 1768 times.
✓ Branch 2 taken 75 times.
✓ Branch 4 taken 1269 times.
✓ Branch 5 taken 499 times.
✓ Branch 6 taken 1344 times.
✓ Branch 7 taken 499 times.
1843 if (unionResult.empty() or (unionResult.size() > 1)) {
1364 1344 return boost::none;
1365 }
1366
1367 // Convert back to polygon
1368
1/1
✓ Branch 2 taken 499 times.
499 Polygon3d p = PolygonFromBoostPolygon(unionResult.front(), allPoints, tol);
1369
1/1
✓ Branch 1 taken 499 times.
499 return p;
1370 1843 }
1371
1372 13 std::vector<Polygon3d> joinAllPolygons(const std::vector<std::vector<Point3d>>& polygons, double tol) {
1373 13 std::vector<Polygon3d> inputPolygons;
1374
1375 // Create Polygon3d from point3dvectors
1376
2/2
✓ Branch 5 taken 189 times.
✓ Branch 6 taken 13 times.
202 for (const auto& polygon : polygons) {
1377 189 Polygon3d inputPolygon;
1378
2/2
✓ Branch 5 taken 883 times.
✓ Branch 6 taken 189 times.
1072 for (const auto& point : polygon) {
1379
1/1
✓ Branch 1 taken 883 times.
883 inputPolygon.addPoint(point);
1380 }
1381
1/1
✓ Branch 1 taken 189 times.
189 inputPolygons.push_back(inputPolygon);
1382 189 }
1383
1384
1/1
✓ Branch 1 taken 13 times.
26 return joinAll(inputPolygons, tol);
1385 13 }
1386
1387 15 std::vector<Polygon3d> joinAll(const std::vector<Polygon3d>& polygons, double /*tol*/) {
1388
1389 15 std::vector<Polygon3d> result;
1390
1391 15 const size_t N = polygons.size();
1392
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
15 if (N <= 1) {
1393 ✗ return polygons;
1394 }
1395
1396
1/1
✓ Branch 1 taken 15 times.
15 std::vector<double> polygonAreas(N, 0.0);
1397
2/2
✓ Branch 0 taken 197 times.
✓ Branch 1 taken 15 times.
212 for (unsigned i = 0; i < N; ++i) {
1398
2/2
✓ Branch 2 taken 197 times.
✓ Branch 5 taken 197 times.
197 auto area = getArea(polygons[i].getOuterPath());
1399
1/2
✓ Branch 0 taken 197 times.
✗ Branch 1 not taken.
197 if (area) {
1400
1/1
✓ Branch 1 taken 197 times.
197 polygonAreas[i] = *area;
1401 }
1402 }
1403
1404 // compute adjacency matrix
1405
1/1
✓ Branch 1 taken 15 times.
15 Matrix A(N, N, 0.0);
1406
2/2
✓ Branch 0 taken 197 times.
✓ Branch 1 taken 15 times.
212 for (unsigned i = 0; i < N; ++i) {
1407
1/1
✓ Branch 1 taken 197 times.
197 A(i, i) = 1.0;
1408
2/2
✓ Branch 0 taken 1571 times.
✓ Branch 1 taken 197 times.
1768 for (unsigned j = i + 1; j < N; ++j) {
1409
3/3
✓ Branch 3 taken 1571 times.
✓ Branch 6 taken 320 times.
✓ Branch 7 taken 1251 times.
3142 if (join(polygons[i], polygons[j] /*,tol*/)) {
1410
1/1
✓ Branch 1 taken 320 times.
320 A(i, j) = 1.0;
1411
1/1
✓ Branch 1 taken 320 times.
320 A(j, i) = 1.0;
1412 }
1413 }
1414 }
1415
1416
1/1
✓ Branch 1 taken 15 times.
15 const std::vector<std::vector<unsigned>> connectedComponents = findConnectedComponents(A);
1417
2/2
✓ Branch 5 taken 15 times.
✓ Branch 6 taken 15 times.
30 for (const std::vector<unsigned>& component : connectedComponents) {
1418
1419
1/1
✓ Branch 1 taken 15 times.
15 std::vector<unsigned> orderedComponent(component);
1420 // #4831 - Use a stable_sort to produce consistent results between Windows and Unix in case you have polygons with the same area
1421
1/1
✓ Branch 3 taken 15 times.
15 std::stable_sort(orderedComponent.begin(), orderedComponent.end(),
1422 644 [&polygonAreas](int ia, int ib) { return polygonAreas[ia] > polygonAreas[ib]; });
1423
1424 15 Polygon3d polygon;
1425 15 std::set<unsigned> joinedComponents;
1426 // try to join at most component.size() times
1427
2/2
✓ Branch 1 taken 44 times.
✓ Branch 2 taken 3 times.
47 for (unsigned n = 0; n < component.size(); ++n) {
1428
1429 // loop over polygons to join in order
1430
2/2
✓ Branch 5 taken 522 times.
✓ Branch 6 taken 44 times.
566 for (const unsigned i : orderedComponent) {
1431
3/3
✓ Branch 1 taken 522 times.
✓ Branch 5 taken 15 times.
✓ Branch 6 taken 507 times.
522 if (polygon.getOuterPath().empty()) {
1432
1/1
✓ Branch 2 taken 15 times.
15 polygon = polygons[i];
1433
1/1
✓ Branch 1 taken 15 times.
15 joinedComponents.insert(i);
1434 } else {
1435 // if not already joined
1436
3/3
✓ Branch 2 taken 507 times.
✓ Branch 5 taken 269 times.
✓ Branch 6 taken 238 times.
507 if (joinedComponents.find(i) == joinedComponents.end()) {
1437
1/1
✓ Branch 2 taken 269 times.
269 boost::optional<Polygon3d> joined = join(polygon, polygons[i] /*, tol*/);
1438
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 93 times.
269 if (joined) {
1439
2/2
✓ Branch 1 taken 176 times.
✓ Branch 4 taken 176 times.
176 polygon = *joined;
1440
1/1
✓ Branch 1 taken 176 times.
176 joinedComponents.insert(i);
1441 }
1442 269 }
1443 }
1444 }
1445
1446 // if all polygons have been joined then we are done
1447
2/2
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 32 times.
44 if (joinedComponents.size() == component.size()) {
1448 12 break;
1449 }
1450 }
1451
1452
2/2
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 12 times.
15 if (joinedComponents.size() != component.size()) {
1453
5/5
✓ Branch 1 taken 3 times.
✓ Branch 4 taken 3 times.
✓ Branch 7 taken 3 times.
✓ Branch 10 taken 3 times.
✓ Branch 13 taken 3 times.
9 LOG_FREE(Error, "utilities.geometry.joinAll", "Could not join all connected components");
1454 }
1455
1/1
✓ Branch 1 taken 15 times.
15 result.push_back(polygon);
1456 15 }
1457
1458 15 return result;
1459 15 }
1460
1461 ✗ std::vector<Polygon3d> bufferAll(const std::vector<Polygon3d>& polygons, double tol) {
1462 ✗ BoostMultiPolygon source;
1463 ✗ std::vector<Point3d> allPoints;
1464
1465 ✗ for (const Polygon3d& polygon : polygons) {
1466 ✗ boost::optional<BoostPolygon> boostPolygon = BoostPolygonFromPolygon(polygon, allPoints, tol);
1467 ✗ source.push_back(*boostPolygon);
1468 ✗ }
1469
1470 ✗ const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> expand(tol * scaleBy);
1471 ✗ const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> shrink(-tol * scaleBy);
1472 ✗ const boost::geometry::strategy::buffer::join_miter join_strategy;
1473 const boost::geometry::strategy::buffer::end_flat end_strategy;
1474 const boost::geometry::strategy::buffer::side_straight side_strategy;
1475 ✗ const boost::geometry::strategy::buffer::point_circle point_strategy;
1476
1477 ✗ BoostMultiPolygon resultExpand;
1478 ✗ BoostMultiPolygon resultShrink;
1479 ✗ boost::geometry::buffer(source, resultExpand, expand, side_strategy, join_strategy, end_strategy, point_strategy);
1480 ✗ boost::geometry::buffer(resultExpand, resultShrink, shrink, side_strategy, join_strategy, end_strategy, point_strategy);
1481
1482 ✗ std::vector<Polygon3d> result;
1483 ✗ result.reserve(resultShrink.size());
1484 ✗ for (const auto& boostPolygon : resultShrink) {
1485 ✗ BoostPolygon simplified;
1486 ✗ boost::geometry::simplify(boostPolygon, simplified, tol);
1487 ✗ result.push_back(PolygonFromBoostPolygon(simplified, allPoints, tol));
1488 ✗ }
1489
1490 ✗ return result;
1491 ✗ }
1492
1493 31 boost::optional<std::vector<Point3d>> buffer(const std::vector<Point3d>& polygon1, double amount, double tol) {
1494 31 std::vector<Point3d> allPoints;
1495
1/1
✓ Branch 1 taken 31 times.
31 boost::optional<BoostPolygon> boostPolygon1 = nonIntersectingBoostPolygonFromVertices(polygon1, allPoints, tol);
1496
1497
2/2
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 16 times.
31 if (!boostPolygon1) {
1498 15 return boost::none;
1499 }
1500
1501 16 constexpr double miterLimit = 15;
1502 //const double buffer_distance = 1.0;
1503 //const int points_per_circle = 36;
1504 16 const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> distance_strategy(amount * scaleBy);
1505
1/1
✓ Branch 1 taken 16 times.
16 const boost::geometry::strategy::buffer::join_miter join_strategy(miterLimit * scaleBy);
1506 const boost::geometry::strategy::buffer::end_flat end_strategy;
1507 const boost::geometry::strategy::buffer::side_straight side_strategy;
1508 16 const boost::geometry::strategy::buffer::point_circle point_strategy;
1509
1510 16 BoostMultiPolygon polygons;
1511
2/2
✓ Branch 1 taken 16 times.
✓ Branch 4 taken 16 times.
16 polygons.push_back(*boostPolygon1);
1512
1513 16 BoostMultiPolygon buffered;
1514 16 BoostMultiPolygon result;
1515
1516
1/1
✓ Branch 1 taken 16 times.
16 boost::geometry::buffer(polygons, buffered, distance_strategy, side_strategy, join_strategy, end_strategy, point_strategy);
1517
1/1
✓ Branch 1 taken 16 times.
16 boost::geometry::simplify(buffered, result, 0.0005);
1518
1519
1/1
✓ Branch 2 taken 16 times.
16 std::vector<Point3d> vertices = verticesFromBoostPolygon(result[0], allPoints, tol);
1520
1/1
✓ Branch 1 taken 16 times.
16 return vertices;
1521 31 }
1522
1523 8 boost::optional<std::vector<std::vector<Point3d>>> buffer(const std::vector<std::vector<Point3d>>& polygons, double amount, double tol) {
1524 8 std::vector<Point3d> allPoints;
1525
1526 8 BoostMultiPolygon boostPolygons;
1527
1/1
✓ Branch 2 taken 8 times.
8 boostPolygons.reserve(polygons.size());
1528
2/2
✓ Branch 5 taken 21 times.
✓ Branch 6 taken 8 times.
29 for (const auto& polygon : polygons) {
1529
1/1
✓ Branch 1 taken 21 times.
21 boost::optional<BoostPolygon> boostPolygon = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol);
1530
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 21 times.
21 if (!boostPolygon) {
1531 ✗ return boost::none;
1532 }
1533
2/2
✓ Branch 1 taken 21 times.
✓ Branch 4 taken 21 times.
21 boostPolygons.push_back(boostPolygon.get());
1534 21 }
1535
1536 8 constexpr double miterLimit = 15;
1537 8 const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> distance_strategy(amount * scaleBy);
1538
1/1
✓ Branch 1 taken 8 times.
8 const boost::geometry::strategy::buffer::join_miter join_strategy(miterLimit * scaleBy);
1539 const boost::geometry::strategy::buffer::end_flat end_strategy;
1540 const boost::geometry::strategy::buffer::side_straight side_strategy;
1541 8 const boost::geometry::strategy::buffer::point_circle point_strategy;
1542
1543 8 BoostMultiPolygon offset;
1544 8 BoostMultiPolygon result;
1545
1/1
✓ Branch 1 taken 8 times.
8 boost::geometry::buffer(boostPolygons, offset, distance_strategy, side_strategy, join_strategy, end_strategy, point_strategy);
1546
1/1
✓ Branch 1 taken 8 times.
8 boost::geometry::simplify(offset, result, 0.0005);
1547
1548 8 std::vector<Point3dVector> results;
1549
1/1
✓ Branch 2 taken 8 times.
8 results.reserve(result.size());
1550
2/2
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 8 times.
17 for (const auto& boostPolygon : result) {
1551
2/2
✓ Branch 1 taken 9 times.
✓ Branch 4 taken 9 times.
9 results.push_back(verticesFromBoostPolygon(boostPolygon, allPoints, tol));
1552 }
1553
1/1
✓ Branch 1 taken 8 times.
8 return results;
1554 8 }
1555
1556 // buffers the polygons to increase reliability of joining
1557 ✗ std::vector<std::vector<Point3d>> joinAllWithBuffer(const std::vector<std::vector<Point3d>>& polygons, double offset, double tol) {
1558 ✗ std::vector<std::vector<Point3d>> result;
1559
1560 ✗ const size_t N = polygons.size();
1561 ✗ if (N <= 1) {
1562 ✗ return polygons;
1563 }
1564
1565 ✗ std::vector<double> polygonAreas(N, 0.0);
1566 ✗ for (unsigned i = 0; i < N; ++i) {
1567 ✗ auto area = getArea(polygons[i]);
1568 ✗ if (area) {
1569 ✗ polygonAreas[i] = *area;
1570 }
1571 }
1572
1573 ✗ std::vector<std::vector<Point3d>> modifiedPolygons;
1574
1575 ✗ for (unsigned i = 0; i < N; i++) {
1576 ✗ modifiedPolygons.push_back(*buffer(polygons[i], offset, tol));
1577 }
1578
1579 // compute adjacency matrix
1580 ✗ Matrix A(N, N, 0.0);
1581 ✗ for (unsigned i = 0; i < N; ++i) {
1582 ✗ A(i, i) = 1.0;
1583 ✗ for (unsigned j = i + 1; j < N; ++j) {
1584 ✗ if (join(modifiedPolygons[i], modifiedPolygons[j], tol)) {
1585 ✗ A(i, j) = 1.0;
1586 ✗ A(j, i) = 1.0;
1587 }
1588 }
1589 }
1590
1591 ✗ const std::vector<std::vector<unsigned>> connectedComponents = findConnectedComponents(A);
1592 ✗ for (const std::vector<unsigned>& component : connectedComponents) {
1593 ✗ std::vector<unsigned> orderedComponent(component);
1594 ✗ std::sort(orderedComponent.begin(), orderedComponent.end(), [&polygonAreas](int ia, int ib) { return polygonAreas[ia] > polygonAreas[ib]; });
1595
1596 ✗ std::vector<Point3d> points;
1597 ✗ std::set<unsigned> joinedComponents;
1598
1599 // try to join at most component.size() times
1600 ✗ for (unsigned n = 0; n < component.size(); ++n) {
1601
1602 // loop over polygons to join in order
1603 ✗ for (const unsigned i : orderedComponent) {
1604 ✗ if (points.empty()) {
1605 ✗ points = modifiedPolygons[i];
1606 ✗ joinedComponents.insert(i);
1607 } else {
1608 // if not already joined
1609 ✗ if (joinedComponents.find(i) == joinedComponents.end()) {
1610 ✗ boost::optional<std::vector<Point3d>> joined = join(points, modifiedPolygons[i], tol);
1611 ✗ if (joined) {
1612 ✗ points = *joined;
1613 ✗ joinedComponents.insert(i);
1614 }
1615 ✗ }
1616 }
1617 }
1618
1619 // if all polygons have been joined then we are done
1620 ✗ if (joinedComponents.size() == component.size()) {
1621 ✗ break;
1622 }
1623 }
1624
1625 ✗ if (joinedComponents.size() != component.size()) {
1626 ✗ LOG_FREE(Error, "utilities.geometry.joinAll", "Could not join all connected components");
1627 }
1628 ✗ points = simplify(points, true, tol);
1629 ✗ result.push_back(points);
1630 ✗ }
1631
1632 ✗ return result;
1633 ✗ }
1634 } // namespace openstudio
1635