GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 90.4% 1196 / 3 / 1326
Functions: 95.4% 124 / 3 / 133
Branches: 69.9% 1199 / 3 / 1719

src/utilities/geometry/RoofGeometry_Details.hpp
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 "Point3d.hpp"
9 #include "../core/Logger.hpp"
10
11 #include <boost/optional.hpp>
12 #include <boost/math/constants/constants.hpp>
13
14 namespace openstudio {
15 constexpr double EPSILON = 1E-10;
16
17 class LineLinear2d // Geometry line in linear form. General form: Ax + By + C = 0;
18 {
19 public:
20 double A = 0.0;
21 double B = 0.0;
22 double C = 0.0;
23
24 56201 LineLinear2d(double a, double b, double c) : A{a}, B{b}, C{c} {}
25
26 56209 LineLinear2d(const Point3d& p1, const Point3d& p2) : A{p1.y() - p2.y()}, B{p2.x() - p1.x()}, C{p1.x() * p2.y() - p2.x() * p1.y()} {}
27
28 56206 boost::optional<Point3d> collide(const LineLinear2d& line2) const {
29 56206 double WAB = A * line2.B - line2.A * B;
30 56206 double WBC = B * line2.C - line2.B * C;
31 56206 double WCA = C * line2.A - line2.C * A;
32
33
2/2
✓ Branch 0 taken 257 times.
✓ Branch 1 taken 55949 times.
56206 if (WAB == 0) {
34 257 return boost::none;
35 }
36
37
2/2
✓ Branch 1 taken 55949 times.
✓ Branch 4 taken 55949 times.
55949 return Point3d(WBC / WAB, WCA / WAB, 0);
38 }
39
40 friend std::ostream& operator<<(std::ostream& os, const LineLinear2d& l) {
41 os << "LineLinear2d [A=" << l.A << ", B=" << l.B << ", C=" << l.C << "]";
42 return os;
43 }
44
45 private:
46 REGISTER_LOGGER("utilities.LineLinear2d");
47 };
48
49 class Ray2d
50 {
51 public:
52 Ray2d() {
53 // nop
54 }
55
56 Point3d point;
57 Vector3d vector;
58
59
1/1
✓ Branch 2 taken 15703 times.
15703 Ray2d(const Point3d& t_point, const Vector3d& t_vector) : point{t_point}, vector{t_vector} {}
60
61 41313 boost::optional<Point3d> collide(const LineLinear2d& line, double epsilon) const {
62
1/1
✓ Branch 1 taken 41313 times.
41313 LineLinear2d ll2d = getLinearForm();
63
64 // rewrite?
65
1/1
✓ Branch 1 taken 41313 times.
41313 boost::optional<Point3d> collide = ll2d.collide(line);
66
2/2
✓ Branch 1 taken 254 times.
✓ Branch 2 taken 41059 times.
41313 if (!collide) {
67 254 return boost::none;
68 }
69
70 /*
71 * Portably there is better way to do this. this is from graphical.
72 */
73
2/2
✓ Branch 1 taken 41059 times.
✓ Branch 4 taken 41059 times.
41059 Vector3d collideVector = collide.get() - point;
74
75
1/1
✓ Branch 1 taken 41059 times.
41059 double d = vector.dot(collideVector);
76
77
2/2
✓ Branch 0 taken 14251 times.
✓ Branch 1 taken 26808 times.
41059 if (d < epsilon) {
78 14251 return boost::none;
79 }
80
81 26808 return collide;
82 41313 }
83
84 56201 LineLinear2d getLinearForm() const {
85 56201 double x = point.x();
86 56201 double y = point.y();
87
88 56201 double B = -vector.x();
89 56201 double A = vector.y();
90
91 56201 double C = -1 * (A * x + B * y);
92 56201 return {A, B, C};
93 }
94
95 8577 bool isOnLeftSide(const Point3d& p, double epsilon) const {
96
1/1
✓ Branch 1 taken 8577 times.
8577 Vector3d direction = p - point;
97
1/1
✓ Branch 1 taken 8577 times.
8577 Vector3d orthRight = vector.orthogonalRight();
98
1/1
✓ Branch 1 taken 8577 times.
17154 return (orthRight.dot(direction) < epsilon);
99 8577 }
100
101 13545 bool isOnRightSide(const Point3d& p, double epsilon) const {
102
1/1
✓ Branch 1 taken 13545 times.
13545 Vector3d direction = p - point;
103
1/1
✓ Branch 1 taken 13545 times.
13545 Vector3d orthRight = vector.orthogonalRight();
104
1/1
✓ Branch 1 taken 13545 times.
27090 return (orthRight.dot(direction) > -epsilon);
105 13545 }
106
107 1163 boost::optional<Point3d> intersectRay2d(std::shared_ptr<Ray2d> other) const {
108 /*
109 * Calculate intersection points for rays. It can return more then one
110 * intersection point when rays overlaps.
111 *
112 * see http://geomalgorithms.com/a05-_intersect-1.html
113 * see http://softsurfer.com/Archive/algorithm_0102/algorithm_0102.htm
114 */
115
116
1/1
✓ Branch 1 taken 1163 times.
1163 Point3d s1p0 = point;
117
2/2
✓ Branch 1 taken 1163 times.
✓ Branch 4 taken 1163 times.
1163 Point3d s1p1 = Point3d(point) + vector;
118
119
1/1
✓ Branch 2 taken 1163 times.
1163 Point3d s2p0 = other->point;
120 // TODO: this is unread!
121 // cppcheck-suppress unreadVariable
122
2/2
✓ Branch 3 taken 1163 times.
✓ Branch 6 taken 1163 times.
1163 Point3d s2p1 = Point3d(other->point) + other->vector;
123
124
1/1
✓ Branch 1 taken 1163 times.
1163 Vector3d u = vector;
125
1/1
✓ Branch 2 taken 1163 times.
1163 Vector3d v = other->vector;
126
127
1/1
✓ Branch 1 taken 1163 times.
1163 Vector3d w = s1p0 - s2p0;
128
129
1/1
✓ Branch 1 taken 1163 times.
1163 double d = perpDot(u, v);
130
131 // test if they are parallel (includes either being a point)
132
2/2
✓ Branch 1 taken 117 times.
✓ Branch 2 taken 1046 times.
1163 if (std::abs(d) < EPSILON) { // S1 and S2 are parallel
133
134
7/8
✓ Branch 1 taken 117 times.
✓ Branch 3 taken 39 times.
✓ Branch 4 taken 78 times.
✓ Branch 6 taken 39 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 39 times.
✓ Branch 10 taken 78 times.
✓ Branch 11 taken 39 times.
117 if (perpDot(u, w) != 0 || perpDot(v, w) != 0) {
135 // they are NOT collinear
136 78 return boost::none;
137 }
138
139 // they are collinear or degenerate
140 // check if they are degenerate points
141
1/1
✓ Branch 1 taken 39 times.
39 double du = u.dot(u);
142
1/1
✓ Branch 1 taken 39 times.
39 double dv = v.dot(v);
143
144
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
39 if (du == 0 && dv == 0) {
145 // both segments are points
146 ✗ if (s1p0 != s2p0) {
147 ✗ return boost::none;
148 }
149 // they are the same point
150 ✗ return s1p0;
151 }
152
153
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
39 if (du == 0) {
154 // S1 is a single point
155 ✗ Ray2d r = Ray2d(s2p0, v);
156 ✗ if (!r.inCollinearRay(s1p0)) {
157 ✗ return boost::none;
158 }
159 ✗ return s1p0;
160 ✗ }
161
162
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
39 if (dv == 0) {
163 // S2 is a single point
164 ✗ Ray2d r = Ray2d(s1p0, u);
165 ✗ if (!r.inCollinearRay(s2p0)) {
166 ✗ return boost::none;
167 }
168 ✗ return s2p0;
169 ✗ }
170
171 //they are collinear segments - get overlap (or not)
172 double t0;
173 double t1;
174 // endpoints of S1 in eqn for S2
175
1/1
✓ Branch 1 taken 39 times.
39 Vector3d w2 = s1p1 - s2p0;
176
177
3/3
✓ Branch 1 taken 39 times.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 12 times.
39 if (v.x() != 0) {
178
2/2
✓ Branch 1 taken 27 times.
✓ Branch 4 taken 27 times.
27 t0 = w.x() / v.x();
179
2/2
✓ Branch 1 taken 27 times.
✓ Branch 4 taken 27 times.
27 t1 = w2.x() / v.x();
180 } else {
181
2/2
✓ Branch 1 taken 12 times.
✓ Branch 4 taken 12 times.
12 t0 = w.y() / v.y();
182
2/2
✓ Branch 1 taken 12 times.
✓ Branch 4 taken 12 times.
12 t1 = w2.y() / v.y();
183 }
184
185
2/2
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 6 times.
39 if (t0 > t1) {
186 // must have t0 smaller than t1
187 33 double t = t0;
188 33 t0 = t1;
189 33 t1 = t; // swap if not
190 }
191
192
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
39 if (t1 < 0) {
193 ✗ return boost::none;
194 }
195
196 // clip to min 0
197
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 37 times.
39 if (t0 < 0) {
198 2 t0 = 0;
199 }
200
201 // they overlap in a valid subsegment
202
203 // I0 = S2_P0 + t0 * v;
204 // I1 = S2_P0 + t1 * v;
205
2/2
✓ Branch 1 taken 39 times.
✓ Branch 4 taken 39 times.
39 Point3d I0 = s2p0 + t0 * v;
206 // TODO: this is unread!
207 // cppcheck-suppress unreadVariable
208
2/2
✓ Branch 1 taken 39 times.
✓ Branch 4 taken 39 times.
39 Point3d I1 = s2p0 + t1 * v;
209
210
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
39 if (t0 == t1) {
211 // intersect is a point
212 ✗ return I0;
213 }
214
215
1/1
✓ Branch 1 taken 39 times.
39 return I0; // only need first intersection point
216 39 }
217
218 // the segments are skewed and may intersect in a point
219
220 // get the intersect parameter for S1
221
1/1
✓ Branch 1 taken 1046 times.
1046 double sI = perpDot(v, w) / d;
222
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 910 times.
1046 if (sI < 0) {
223 136 return boost::none;
224 }
225
226 // get the intersect parameter for S2
227
1/1
✓ Branch 1 taken 910 times.
910 double tI = perpDot(u, w) / d;
228
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 909 times.
910 if (tI < 0) {
229 1 return boost::none;
230 }
231
232 // I0 = S1_P0 + sI * u;
233 // compute S1 intersect point
234
2/2
✓ Branch 1 taken 909 times.
✓ Branch 4 taken 909 times.
909 Point3d I0 = s1p0 + sI * u;
235
1/1
✓ Branch 1 taken 909 times.
909 return I0;
236 1163 }
237
238 /// perp dot product between two vectors
239 3275 static double perpDot(const Vector3d& p1, const Vector3d& p2) {
240 3275 return (p1.x() * p2.y() - p1.y() * p2.x());
241 }
242
243 ✗ bool inCollinearRay(const Point3d& p) const {
244 // test if p is on ray
245 ✗ Vector3d collideVector = p - point;
246
247 ✗ double d = vector.dot(collideVector);
248 ✗ if (d < 0) {
249 ✗ return false;
250 }
251 ✗ return true;
252 ✗ }
253
254 ✗ friend std::ostream& operator<<(std::ostream& os, const Ray2d& r) {
255 ✗ os << "Ray2d [A=" << r.point << ", U=" << r.vector << "]";
256 ✗ return os;
257 }
258
259 // Returns true if this ray2d is equal to other
260 bool operator==(const Ray2d& other) const {
261 if (point == other.point && vector == other.vector) {
262 return true;
263 }
264 return false;
265 }
266
267 private:
268 REGISTER_LOGGER("utilities.Ray2d");
269 };
270
271 class Edge
272 {
273 public:
274 Point3d begin;
275 Point3d end;
276 std::shared_ptr<Ray2d> bisectorPrevious;
277 std::shared_ptr<Ray2d> bisectorNext;
278 std::shared_ptr<Edge> next;
279 std::shared_ptr<Edge> previous;
280
281
1/1
✓ Branch 2 taken 8 times.
8 Edge() {
282 // nop
283 8 }
284
285
1/1
✓ Branch 2 taken 475 times.
475 Edge(const Point3d& t_begin, const Point3d& t_end) : begin{t_begin}, end{t_end} {}
286
287 91761 Vector3d normalize() const {
288
9/9
✓ Branch 1 taken 91761 times.
✓ Branch 4 taken 91761 times.
✓ Branch 7 taken 91761 times.
✓ Branch 10 taken 91761 times.
✓ Branch 13 taken 91761 times.
✓ Branch 16 taken 91761 times.
✓ Branch 19 taken 91761 times.
✓ Branch 22 taken 91761 times.
✓ Branch 25 taken 91761 times.
91761 Vector3d v = Vector3d(end.x(), end.y(), end.z()) - Vector3d(begin.x(), begin.y(), begin.z());
289
1/1
✓ Branch 1 taken 91761 times.
91761 v.normalize();
290 91761 return v;
291 ✗ }
292
293 ✗ friend std::ostream& operator<<(std::ostream& os, const Edge& e) {
294 ✗ os << "EdgeEntry [p1=" << e.begin << ", p2=" << e.end << ", bp=" << *e.bisectorPrevious << ", bn=" << *e.bisectorNext << "]";
295 ✗ return os;
296 }
297
298 // Returns true if this edge is equal to other
299 bool operator==(const Edge& other) const {
300 if (begin == other.begin && end == other.end) {
301 return true;
302 }
303 return false;
304 }
305
306 // Returns true if this edge is not equal to other
307 7 bool operator!=(const Edge& other) const {
308
5/6
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 1 time.
✓ Branch 6 taken 6 times.
✓ Branch 7 taken 1 time.
7 if (begin != other.begin || end != other.end) {
309 6 return true;
310 }
311 1 return false;
312 }
313
314 private:
315 REGISTER_LOGGER("utilities.Edge");
316 };
317
318 class Face; // forward declaration
319
320 class FaceNode
321 {
322 public:
323 Point3d point;
324 double distance = 0.0;
325 std::shared_ptr<Face> face;
326
327 FaceNode() {
328 // nop
329 }
330
331 2004 FaceNode(const Point3d& t_point, double t_distance, std::shared_ptr<Face> t_face) : point{t_point}, distance{t_distance}, face{t_face} {}
332
333 // Returns true if this vertex is equal to other
334 bool operator==(const FaceNode& other) const {
335 if (point == other.point && distance == other.distance) {
336 return true;
337 }
338 return false;
339 }
340
341 friend std::ostream& operator<<(std::ostream& os, const FaceNode& fn) {
342 os << "FaceNode [point=" << fn.point << ", distance=" << fn.distance << "]";
343 return os;
344 }
345
346 private:
347 REGISTER_LOGGER("utilities.FaceNode");
348 };
349
350 class Vertex
351 {
352 public:
353 Point3d point;
354 double distance = 0.0;
355 std::shared_ptr<Ray2d> bisector;
356 std::shared_ptr<Edge> previousEdge;
357 std::shared_ptr<Edge> nextEdge;
358 std::shared_ptr<FaceNode> leftFaceNode;
359 std::shared_ptr<FaceNode> rightFaceNode;
360 bool processed = false;
361
362 23 Vertex() {
363 // nop
364 23 }
365
366 968 Vertex(const Point3d& t_point, double t_distance, std::shared_ptr<Ray2d> t_bisector, std::shared_ptr<Edge> t_previousEdge,
367 std::shared_ptr<Edge> t_nextEdge)
368 968 : point{t_point}, distance{t_distance}, bisector{t_bisector}, previousEdge{t_previousEdge}, nextEdge{t_nextEdge} {}
369
370 20 Vertex(const std::shared_ptr<Edge> t_previousEdge, const std::shared_ptr<Edge> t_nextEdge) : previousEdge{t_previousEdge}, nextEdge{t_nextEdge} {}
371
372 1285 static std::shared_ptr<Vertex> previous(std::shared_ptr<Vertex> vertex, std::vector<std::shared_ptr<Vertex>>& vertices) {
373
1/1
✓ Branch 2 taken 1285 times.
1285 int index = getOffsetVertexIndex(vertex, vertices, -1);
374 1285 return vertices[index];
375 }
376
377 2453 static std::shared_ptr<Vertex> next(std::shared_ptr<Vertex> vertex, std::vector<std::shared_ptr<Vertex>>& vertices) {
378
1/1
✓ Branch 2 taken 2453 times.
2453 int index = getOffsetVertexIndex(vertex, vertices, 1);
379 2453 return vertices[index];
380 }
381
382 512 static std::shared_ptr<Vertex> previous(std::shared_ptr<Vertex> vertex, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
383
1/1
✓ Branch 2 taken 512 times.
512 int index = Vertex::getLavIndex(vertex, sLav);
384
1/1
✓ Branch 3 taken 512 times.
512 return Vertex::previous(vertex, sLav[index]);
385 }
386
387 435 static std::shared_ptr<Vertex> next(std::shared_ptr<Vertex> vertex, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
388
1/1
✓ Branch 2 taken 435 times.
435 int index = Vertex::getLavIndex(vertex, sLav);
389
1/1
✓ Branch 3 taken 435 times.
435 return Vertex::next(vertex, sLav[index]);
390 }
391
392 2524 static int getLavIndex(std::shared_ptr<Vertex> vertex, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
393
2/2
✓ Branch 1 taken 4605 times.
✓ Branch 2 taken 336 times.
4941 for (unsigned i = 0; i < sLav.size(); i++) {
394
3/3
✓ Branch 7 taken 4605 times.
✓ Branch 10 taken 2188 times.
✓ Branch 11 taken 2417 times.
4605 if (std::find(sLav[i].begin(), sLav[i].end(), vertex) != sLav[i].end()) {
395 2188 return i;
396 }
397 }
398 336 return -1;
399 }
400
401 1993 static void removeFromLav(std::shared_ptr<Vertex> vertex, std::vector<std::shared_ptr<Vertex>>& lav) {
402
1/1
✓ Branch 3 taken 1993 times.
1993 auto it = std::find(lav.begin(), lav.end(), vertex);
403
1/2
✓ Branch 2 taken 1993 times.
✗ Branch 3 not taken.
1993 if (it != lav.end()) {
404
1/1
✓ Branch 2 taken 1993 times.
1993 lav.erase(it);
405 }
406 1993 }
407
408 1070 static void removeFromLav(std::shared_ptr<Vertex> vertex, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
409
1/1
✓ Branch 2 taken 1070 times.
1070 int i = Vertex::getLavIndex(vertex, sLav);
410
2/2
✓ Branch 0 taken 734 times.
✓ Branch 1 taken 336 times.
1070 if (i != -1) {
411
1/1
✓ Branch 3 taken 734 times.
734 Vertex::removeFromLav(vertex, sLav[i]);
412 }
413 1070 }
414
415 ✗ friend std::ostream& operator<<(std::ostream& os, const Vertex& v) {
416 ✗ std::string processed_str = "false";
417 ✗ if (v.processed) {
418 ✗ processed_str = "true";
419 }
420
421 ✗ os << "VertexEntry [v=" << v.point << ", processed=" << processed_str << ", bisector=";
422
423 ✗ if (v.bisector) {
424 ✗ os << *v.bisector;
425 } else {
426 ✗ os << "null";
427 }
428
429 ✗ os << ", previousEdge=";
430
431 ✗ if (v.previousEdge) {
432 ✗ os << *v.previousEdge;
433 } else {
434 ✗ os << "null";
435 }
436
437 ✗ os << ", nextEdge=";
438
439 ✗ if (v.nextEdge) {
440 ✗ os << *v.nextEdge;
441 } else {
442 ✗ os << "null";
443 }
444
445 ✗ os << "]";
446 ✗ return os;
447 ✗ }
448
449 // Returns true if this vertex is equal to other
450 bool operator==(const Vertex& other) const {
451 if (point == other.point && distance == other.distance && bisector == other.bisector && previousEdge == other.previousEdge
452 && nextEdge == other.nextEdge) {
453 return true;
454 }
455 return false;
456 }
457
458 // Returns true if this vertex is not equal to other
459 bool operator!=(const Vertex& other) const {
460 if (point != other.point || distance != other.distance || bisector != other.bisector || previousEdge != other.previousEdge
461 || nextEdge != other.nextEdge) {
462 return true;
463 }
464 return false;
465 }
466
467 private:
468 − REGISTER_LOGGER("utilities.Vertex");
469
470 3738 friend int getOffsetVertexIndex(std::shared_ptr<Vertex> vertex, std::vector<std::shared_ptr<Vertex>>& vertices, int offset) {
471
1/1
✓ Branch 3 taken 3738 times.
3738 auto it = std::find(vertices.begin(), vertices.end(), vertex);
472
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 3738 times.
3738 if (it == vertices.end()) {
473 ✗ LOG_AND_THROW("Could not find vertex.");
474 }
475 3738 int vsize = vertices.size();
476 3738 auto pos = std::distance(vertices.begin(), it);
477 3738 pos += offset;
478
2/2
✓ Branch 0 taken 323 times.
✓ Branch 1 taken 3415 times.
3738 if (pos < 0) {
479 323 pos += vertices.size();
480
2/2
✓ Branch 0 taken 246 times.
✓ Branch 1 taken 3169 times.
3415 } else if (pos >= vsize) {
481 246 pos -= vertices.size();
482 }
483 3738 return static_cast<int>(pos);
484 }
485 };
486
487 class Face
488 {
489 public:
490 std::vector<std::shared_ptr<FaceNode>> nodes;
491 std::shared_ptr<Edge> edge;
492 bool closed = false;
493
494 2663 unsigned getNodeIndex(std::shared_ptr<FaceNode> node) const {
495
1/1
✓ Branch 3 taken 2663 times.
2663 auto it = std::find(nodes.begin(), nodes.end(), node);
496
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 2663 times.
2663 if (it == nodes.end()) {
497 ✗ LOG_AND_THROW("Could not find node in nodes.")
498 }
499 2663 return static_cast<unsigned>(it - nodes.begin());
500 }
501
502 988 bool isEnd(std::shared_ptr<FaceNode> vertex) const {
503
1/1
✓ Branch 2 taken 988 times.
988 unsigned nodeIndex = getNodeIndex(vertex);
504
3/4
✓ Branch 0 taken 474 times.
✓ Branch 1 taken 514 times.
✓ Branch 3 taken 474 times.
✗ Branch 4 not taken.
988 return (nodeIndex == 0 || nodeIndex == nodes.size() - 1);
505 }
506
507 1057 bool isUnconnected() const {
508
2/2
✓ Branch 1 taken 946 times.
✓ Branch 2 taken 111 times.
1057 if (edge) {
509 946 return false;
510 }
511 111 return true;
512 }
513
514 100 std::shared_ptr<FaceNode> popNode(std::shared_ptr<FaceNode> node) {
515
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 100 times.
100 if (node->face->nodes != this->nodes) {
516 ✗ LOG_AND_THROW("Node is not assigned to this list!");
517 }
518
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 100 times.
100 if (nodes.empty()) {
519 ✗ LOG_AND_THROW("List is empty, can't remove.");
520 }
521
2/3
✓ Branch 2 taken 100 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 100 times.
100 if (!isEnd(node)) {
522 ✗ LOG_AND_THROW("Can pop only from end of queue.");
523 }
524
525 100 node->face = nullptr;
526
527
1/1
✓ Branch 2 taken 100 times.
100 unsigned nodeIndex = getNodeIndex(node);
528
1/1
✓ Branch 4 taken 100 times.
100 nodes.erase(nodes.begin() + nodeIndex);
529
530
2/2
✓ Branch 1 taken 70 times.
✓ Branch 2 taken 30 times.
100 if (nodes.empty()) {
531 70 return nullptr;
532
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
30 } else if (nodeIndex > 0) {
533 30 return nodes[nodes.size() - 1];
534 } else {
535 ✗ return nodes[0];
536 }
537 }
538
539 friend std::ostream& operator<<(std::ostream& os, const Face& f) {
540 os << "Face [size=" << f.nodes.size() << ", edge=";
541
542 if (f.edge) {
543 os << *f.edge;
544 } else {
545 os << "null";
546 }
547
548 os << ", closed=" << f.closed << "]";
549
550 return os;
551 }
552
553 private:
554 − REGISTER_LOGGER("utilities.Face");
555 };
556
557 class QueueEvent
558 {
559 public:
560 enum QueueEventType
561 {
562 TYPE_EDGE = 0,
563 TYPE_SPLIT = 1,
564 TYPE_SPLIT_VERTEX = 2,
565 };
566
567 QueueEventType eventType;
568 Point3d point;
569 double distance = 0.0;
570 std::shared_ptr<Vertex> previousVertex;
571 std::shared_ptr<Vertex> nextVertex;
572 std::shared_ptr<Vertex> parent;
573 std::shared_ptr<Edge> oppositeEdge;
574
575 QueueEvent() : eventType{TYPE_EDGE} {
576 // nop
577 }
578
579 749 QueueEvent(const Point3d& t_point, double t_distance, std::shared_ptr<Vertex> t_previousVertex, std::shared_ptr<Vertex> t_nextVertex)
580 749 : eventType{TYPE_EDGE}, point{t_point}, distance{t_distance}, previousVertex{t_previousVertex}, nextVertex{t_nextVertex} {}
581
582 601 QueueEvent(const Point3d& t_point, double t_distance, std::shared_ptr<Vertex> t_parent)
583 601 : eventType{TYPE_SPLIT_VERTEX}, point{t_point}, distance{t_distance}, parent{t_parent} {}
584
585 1061 QueueEvent(const Point3d& t_point, double t_distance, std::shared_ptr<Vertex> t_parent, std::shared_ptr<Edge> t_oppositeEdge)
586 1061 : eventType{TYPE_SPLIT}, point{t_point}, distance{t_distance}, parent{t_parent}, oppositeEdge{t_oppositeEdge} {}
587
588 ✗ friend std::ostream& operator<<(std::ostream& os, const QueueEvent& e) {
589 ✗ if (e.eventType == TYPE_EDGE) {
590 ✗ os << "EdgeEvent [v=" << e.point << ", previousVertex=" << e.previousVertex->point << ", nextVertex=" << e.nextVertex->point
591 ✗ << ", distance=" << e.distance << "]";
592 ✗ } else if (e.eventType == TYPE_SPLIT) {
593 ✗ os << "SplitEvent [v=" << e.point << ", parent=" << e.parent->point << ", distance=" << e.distance << "]";
594 ✗ } else if (e.eventType == TYPE_SPLIT_VERTEX) {
595 ✗ os << "VertexSplitEvent [v=" << e.point << ", parent=" << e.parent->point << ", distance=" << e.distance << "]";
596 }
597 ✗ return os;
598 }
599
600 624035 bool operator<(const QueueEvent& other) const {
601 624035 return distance < other.distance;
602 }
603
604 // Returns true if this queue event is equal to other
605 bool operator==(const QueueEvent& other) const {
606 if (eventType == other.eventType && point == other.point && distance == other.distance && parent == other.parent
607 && oppositeEdge == other.oppositeEdge && previousVertex == other.previousVertex && nextVertex == other.nextVertex) {
608 return true;
609 }
610 return false;
611 }
612
613 1126 void addEventToGroup(std::vector<std::shared_ptr<Vertex>>& parentGroup) const {
614
4/4
✓ Branch 0 taken 853 times.
✓ Branch 1 taken 273 times.
✓ Branch 2 taken 397 times.
✓ Branch 3 taken 456 times.
1126 if (eventType == TYPE_SPLIT || eventType == TYPE_SPLIT_VERTEX) {
615 670 parentGroup.push_back(parent);
616
1/2
✓ Branch 0 taken 456 times.
✗ Branch 1 not taken.
456 } else if (eventType == TYPE_EDGE) {
617 456 parentGroup.push_back(previousVertex);
618 456 parentGroup.push_back(nextVertex);
619 }
620 1126 }
621
622 913 bool isEventInGroup(std::vector<std::shared_ptr<Vertex>>& parentGroup) {
623
4/4
✓ Branch 0 taken 755 times.
✓ Branch 1 taken 158 times.
✓ Branch 2 taken 380 times.
✓ Branch 3 taken 375 times.
913 if (eventType == TYPE_SPLIT || eventType == TYPE_SPLIT_VERTEX) {
624
1/1
✓ Branch 4 taken 538 times.
538 bool foundParent = std::find(parentGroup.begin(), parentGroup.end(), parent) != parentGroup.end();
625 538 return foundParent;
626
1/2
✓ Branch 0 taken 375 times.
✗ Branch 1 not taken.
375 } else if (eventType == TYPE_EDGE) {
627
1/1
✓ Branch 4 taken 375 times.
375 bool foundPreviousVertex = std::find(parentGroup.begin(), parentGroup.end(), previousVertex) != parentGroup.end();
628
1/1
✓ Branch 4 taken 375 times.
375 bool foundNextVertex = std::find(parentGroup.begin(), parentGroup.end(), nextVertex) != parentGroup.end();
629
4/4
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 255 times.
✓ Branch 2 taken 57 times.
✓ Branch 3 taken 63 times.
375 return (foundPreviousVertex || foundNextVertex);
630 }
631 ✗ return false;
632 }
633
634 std::shared_ptr<Edge> getOppositeEdgePrevious() const {
635 return oppositeEdge;
636 }
637
638 2642 bool isObsolete() const {
639
2/2
✓ Branch 0 taken 830 times.
✓ Branch 1 taken 1812 times.
2642 if (eventType == TYPE_EDGE) {
640
4/4
✓ Branch 1 taken 581 times.
✓ Branch 2 taken 249 times.
✓ Branch 4 taken 13 times.
✓ Branch 5 taken 568 times.
830 return (previousVertex->processed || nextVertex->processed);
641 } else {
642 1812 return parent->processed;
643 }
644 }
645
646 struct Comparer
647 {
648 624035 bool operator()(std::shared_ptr<QueueEvent> q1, std::shared_ptr<QueueEvent> q2) const {
649 624035 return *q1 < *q2;
650 }
651 };
652
653 2401 static void insert_sorted(std::vector<std::shared_ptr<QueueEvent>>& queue, std::shared_ptr<QueueEvent> item) {
654
2/2
✓ Branch 3 taken 2401 times.
✓ Branch 7 taken 2401 times.
2401 queue.insert(std::upper_bound(queue.begin(), queue.end(), item, QueueEvent::Comparer()), item);
655 2401 }
656
657 private:
658 REGISTER_LOGGER("utilities.QueueEvent");
659 };
660
661 class Chain // Chains of queue events
662 {
663 public:
664 enum ChainType
665 {
666 TYPE_EDGE = 0,
667 TYPE_SPLIT = 1,
668 TYPE_SINGLE_EDGE = 2
669 };
670
671 enum ChainMode
672 {
673 MODE_EDGE = 0,
674 MODE_SPLIT = 1,
675 MODE_CLOSED_EDGE = 2
676 };
677
678 ChainType chainType;
679 std::vector<std::shared_ptr<QueueEvent>> edgeList;
680 std::shared_ptr<QueueEvent> splitEvent;
681
682 bool closed = false;
683 bool split = false;
684
685 85 Chain() : chainType{TYPE_EDGE} {
686 // nop
687 85 }
688
689 93 Chain(std::shared_ptr<QueueEvent> t_splitEvent) : chainType{TYPE_SPLIT}, splitEvent{t_splitEvent} {}
690
691 281 Chain(std::vector<std::shared_ptr<QueueEvent>>& t_edgeList, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav)
692
2/2
✓ Branch 3 taken 281 times.
✓ Branch 6 taken 281 times.
281 : chainType{TYPE_EDGE}, edgeList{t_edgeList}, closed{(getPreviousVertex(sLav) == getNextVertex(sLav))} {}
693
694 70 Chain(std::shared_ptr<Edge> t_oppositeEdge, std::shared_ptr<Vertex> t_nextVertex, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav)
695 70 : chainType{TYPE_SINGLE_EDGE}, nextVertex{t_nextVertex}, oppositeEdge{t_oppositeEdge} {
696 /*
697 * previous vertex for opposite edge event is valid only before
698 * processing of multi split event start .We need to store vertex before
699 * processing starts.
700 */
701
1/1
✓ Branch 2 taken 70 times.
70 this->previousVertex = Vertex::previous(nextVertex, sLav);
702 70 }
703
704 731 ChainMode getChainMode() const {
705
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 251 times.
731 if (chainType == TYPE_EDGE) {
706
3/4
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 398 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 82 times.
480 if (closed && split) {
707 ✗ LOG_AND_THROW("Chain can't be closed and split");
708
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 398 times.
480 } else if (closed) {
709 82 return MODE_CLOSED_EDGE;
710
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 398 times.
398 } else if (split) {
711 ✗ return MODE_SPLIT;
712 }
713 398 return MODE_EDGE;
714
1/2
✓ Branch 0 taken 251 times.
✗ Branch 1 not taken.
251 } else if (chainType == TYPE_SPLIT) {
715 251 return MODE_SPLIT;
716 }
717 ✗ return MODE_SPLIT;
718 }
719
720 564 std::shared_ptr<Edge> getPreviousEdge() const {
721
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 564 times.
564 if (chainType == TYPE_EDGE) {
722 ✗ return edgeList[0]->previousVertex->previousEdge;
723
2/2
✓ Branch 0 taken 253 times.
✓ Branch 1 taken 311 times.
564 } else if (chainType == TYPE_SINGLE_EDGE) {
724 253 return oppositeEdge;
725 } else {
726 311 return splitEvent->parent->previousEdge;
727 }
728 }
729
730 306 std::shared_ptr<Edge> getNextEdge() const {
731
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 306 times.
306 if (chainType == TYPE_EDGE) {
732 ✗ return edgeList[edgeList.size() - 1]->nextVertex->nextEdge;
733
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 166 times.
306 } else if (chainType == TYPE_SINGLE_EDGE) {
734 140 return oppositeEdge;
735 } else {
736 166 return splitEvent->parent->nextEdge;
737 }
738 }
739
740 902 std::shared_ptr<Vertex> getPreviousVertex(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) const {
741
2/2
✓ Branch 0 taken 679 times.
✓ Branch 1 taken 223 times.
902 if (chainType == TYPE_EDGE) {
742 679 return edgeList[0]->previousVertex;
743
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 83 times.
223 } else if (chainType == TYPE_SINGLE_EDGE) {
744 140 return previousVertex;
745 } else {
746
1/1
✓ Branch 3 taken 83 times.
83 return Vertex::previous(splitEvent->parent, sLav);
747 }
748 }
749
750 902 std::shared_ptr<Vertex> getNextVertex(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) const {
751
2/2
✓ Branch 0 taken 679 times.
✓ Branch 1 taken 223 times.
902 if (chainType == TYPE_EDGE) {
752 679 return edgeList[edgeList.size() - 1]->nextVertex;
753
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 83 times.
223 } else if (chainType == TYPE_SINGLE_EDGE) {
754 140 return nextVertex;
755 } else {
756
1/1
✓ Branch 3 taken 83 times.
83 return Vertex::next(splitEvent->parent, sLav);
757 }
758 }
759
760 804 std::shared_ptr<Vertex> getCurrentVertex() const {
761 804 std::shared_ptr<Vertex> ret;
762
2/2
✓ Branch 0 taken 664 times.
✓ Branch 1 taken 140 times.
804 if (chainType == TYPE_SPLIT) {
763 664 return splitEvent->parent;
764 }
765 140 return ret;
766 804 }
767
768 93 std::shared_ptr<Edge> getOppositeEdge() const {
769
1/2
✓ Branch 0 taken 93 times.
✗ Branch 1 not taken.
93 if (chainType == TYPE_SPLIT) {
770
2/2
✓ Branch 1 taken 81 times.
✓ Branch 2 taken 12 times.
93 if (splitEvent->eventType != QueueEvent::TYPE_SPLIT_VERTEX) {
771 81 return splitEvent->oppositeEdge;
772 }
773 }
774 12 return oppositeEdge;
775 }
776
777 friend std::ostream& operator<<(std::ostream& os, const Chain& c) {
778 std::string type_s;
779 if (c.chainType == TYPE_EDGE) {
780 type_s = "Edge";
781 } else if (c.chainType == TYPE_SPLIT) {
782 type_s = "Split";
783 } else {
784 type_s = "SingleEdge";
785 }
786
787 std::string mode_s;
788 if (c.getChainMode() == MODE_EDGE) {
789 mode_s = "EDGE";
790 } else if (c.getChainMode() == MODE_SPLIT) {
791 mode_s = "SPLIT";
792 } else {
793 mode_s = "CLOSED_EDGE";
794 }
795
796 os << "Chain [type=" << type_s << ", mode=" << mode_s << ", pe=";
797
798 if (c.getPreviousEdge()) {
799 os << *c.getPreviousEdge();
800 } else {
801 os << "null";
802 }
803
804 os << ", ne=";
805
806 if (c.getNextEdge()) {
807 os << *c.getNextEdge();
808 } else {
809 os << "null";
810 }
811
812 os << ", oe=";
813
814 if (c.getOppositeEdge()) {
815 os << *c.getOppositeEdge();
816 } else {
817 os << "null";
818 }
819
820 os << ", cv=";
821
822 if (c.getCurrentVertex()) {
823 os << *c.getCurrentVertex();
824 } else {
825 os << "null";
826 }
827
828 os << "]";
829
830 return os;
831 }
832
833 // Returns true if this chain is equal to other
834 10 bool operator==(const Chain& other) const {
835
4/8
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 10 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 10 times.
✗ Branch 9 not taken.
10 if (chainType == other.chainType && splitEvent == other.splitEvent && edgeList == other.edgeList) {
836 10 return true;
837 }
838 ✗ return false;
839 }
840
841 struct Comparer
842 {
843 Point3d center;
844
845 85 Comparer(Point3d center) {
846
1/1
✓ Branch 1 taken 85 times.
85 this->center = center;
847 85 }
848
849 258 static double angle(const Point3d& p1, const Point3d& p2) {
850 258 double dx = p2.x() - p1.x();
851 258 double dy = p2.y() - p1.y();
852 258 return atan2(dy, dx);
853 }
854
855 129 bool operator()(const Chain& c1, const Chain& c2) const {
856
1/1
✓ Branch 3 taken 129 times.
129 double angle1 = angle(center, c1.getPreviousEdge()->begin);
857
1/1
✓ Branch 3 taken 129 times.
129 double angle2 = angle(center, c2.getPreviousEdge()->begin);
858 129 return (angle1 < angle2);
859 }
860 };
861
862 private:
863 − REGISTER_LOGGER("utilities.Chain");
864 std::shared_ptr<Edge> previousEdge;
865 std::shared_ptr<Edge> nextEdge;
866 std::shared_ptr<Vertex> previousVertex;
867 std::shared_ptr<Vertex> nextVertex;
868 std::shared_ptr<Vertex> currentVertex;
869 std::shared_ptr<Edge> oppositeEdge;
870 };
871
872 class LevelEvent
873 {
874 public:
875 enum LevelEventType
876 {
877 TYPE_PICK = 0,
878 TYPE_MULTI_EDGE = 1,
879 TYPE_MULTI_SPLIT = 2
880 };
881
882 LevelEventType eventType;
883 Point3d point;
884 double distance = 0.0;
885 Chain chain;
886 std::vector<Chain> chains;
887 bool obsolete = false;
888
889 LevelEvent() : eventType{TYPE_PICK} {
890 // nop
891 }
892
893 281 LevelEvent(const Point3d& t_point, double t_distance, const Chain& t_chain, bool isPickEvent)
894
1/1
✓ Branch 2 taken 281 times.
281 : point{t_point}, distance{t_distance}, chain{t_chain} {
895
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 199 times.
281 if (isPickEvent) {
896 82 this->eventType = TYPE_PICK;
897 } else {
898 199 this->eventType = TYPE_MULTI_EDGE;
899 }
900 281 }
901
902 85 LevelEvent(const Point3d& t_point, double t_distance, const std::vector<Chain>& t_chains)
903
1/1
✓ Branch 3 taken 85 times.
85 : eventType{TYPE_MULTI_SPLIT}, point{t_point}, distance{t_distance}, chains{t_chains} {}
904
905 friend std::ostream& operator<<(std::ostream& os, const LevelEvent& e) {
906 os << "IntersectEntry [v=" << e.point << ", distance=" << e.distance << "]";
907 return os;
908 }
909
910 bool operator<(const LevelEvent& other) const {
911 return distance < other.distance;
912 }
913
914 private:
915 REGISTER_LOGGER("utilities.LevelEvent");
916 };
917
918 class SplitCandidate
919 {
920 public:
921 Point3d point;
922 double distance = 0.0;
923 std::shared_ptr<Edge> oppositeEdge;
924 boost::optional<Point3d> oppositePoint;
925
926 2180 SplitCandidate(const Point3d& t_point, double t_distance, std::shared_ptr<Edge> t_oppositeEdge, boost::optional<Point3d&> t_oppositePoint)
927
1/1
✓ Branch 3 taken 2180 times.
2180 : point{t_point}, distance{t_distance}, oppositeEdge{t_oppositeEdge}, oppositePoint{t_oppositePoint} {}
928
929 // Returns true if this SplitCandidate is less than other
930 3327 bool operator<(const SplitCandidate& other) const {
931 3327 return (distance < other.distance);
932 }
933
934 // Returns true if this SplitCandidate is equal to other
935 bool operator==(const SplitCandidate& other) const {
936 return (point == other.point && distance == other.distance);
937 }
938
939 friend std::ostream& operator<<(std::ostream& os, const SplitCandidate& s) {
940 os << "SplitCandidate [point=" << s.point << ", distance=" << s.distance << "]";
941 return os;
942 }
943
944 private:
945 REGISTER_LOGGER("utilities.SplitCandidate");
946 };
947
948 41 static std::vector<std::vector<Point3d>> facesToPoint3d(const std::vector<std::shared_ptr<Face>>& faces, double roofPitchDegrees, double zcoord) {
949 41 std::vector<std::vector<Point3d>> roofsPoint3d;
950
1/1
✓ Branch 1 taken 41 times.
41 double roofSlope = tan(degToRad(roofPitchDegrees));
951
2/2
✓ Branch 5 taken 459 times.
✓ Branch 6 taken 41 times.
500 for (const std::shared_ptr<Face>& face : faces) {
952
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 459 times.
459 if (face->nodes.empty()) {
953 ✗ continue;
954 }
955 459 std::vector<Point3d> roofPoint3d;
956
2/2
✓ Branch 6 taken 2004 times.
✓ Branch 7 taken 459 times.
2463 for (const std::shared_ptr<FaceNode>& v : face->nodes) {
957
3/3
✓ Branch 3 taken 2004 times.
✓ Branch 7 taken 2004 times.
✓ Branch 10 taken 2004 times.
2004 Point3d p = Point3d(v->point.x(), v->point.y(), zcoord + v->distance * roofSlope);
958
1/1
✓ Branch 1 taken 2004 times.
2004 roofPoint3d.push_back(p);
959 2004 }
960
1/1
✓ Branch 1 taken 459 times.
459 roofsPoint3d.push_back(roofPoint3d);
961 459 }
962 41 return roofsPoint3d;
963 ✗ }
964
965 15774 static Vector3d calcVectorBisector(const Vector3d& norm1, const Vector3d& norm2) {
966
1/1
✓ Branch 1 taken 15774 times.
15774 Vector3d e1v = norm1.orthogonalLeft();
967
1/1
✓ Branch 1 taken 15774 times.
15774 Vector3d e2v = norm2.orthogonalLeft();
968
969 // 90 - 180 || 180 - 270
970
3/3
✓ Branch 1 taken 15774 times.
✓ Branch 3 taken 7541 times.
✓ Branch 4 taken 8233 times.
15774 if (norm1.dot(norm2) > 0) {
971
1/1
✓ Branch 1 taken 7541 times.
7541 e1v += e2v;
972 7541 return e1v;
973 }
974
975 // 0 - 180
976
1/1
✓ Branch 1 taken 8233 times.
8233 Vector3d ret = Vector3d(norm1);
977
1/1
✓ Branch 1 taken 8233 times.
8233 ret = ret.reverseVector();
978
1/1
✓ Branch 1 taken 8233 times.
8233 ret += norm2;
979
980
3/3
✓ Branch 1 taken 8233 times.
✓ Branch 3 taken 3984 times.
✓ Branch 4 taken 4249 times.
8233 if (e1v.dot(norm2) < 0) {
981 // 270 - 360
982
1/1
✓ Branch 1 taken 3984 times.
3984 ret = ret.reverseVector();
983 }
984
985 8233 return ret;
986 15774 }
987
988 811 static Ray2d calcBisector(const Point3d& p, std::shared_ptr<Edge> e1, std::shared_ptr<Edge> e2) {
989
990
1/1
✓ Branch 2 taken 811 times.
811 Vector3d norm1 = e1->normalize();
991
1/1
✓ Branch 2 taken 811 times.
811 Vector3d norm2 = e2->normalize();
992
1/1
✓ Branch 1 taken 811 times.
811 Vector3d bisector = calcVectorBisector(norm1, norm2);
993
1/1
✓ Branch 1 taken 811 times.
1622 return Ray2d(p, bisector);
994 811 }
995
996 1575 static void addPush(std::shared_ptr<FaceNode> node, std::shared_ptr<FaceNode> newNode) {
997 1575 std::shared_ptr<Face> face = node->face;
998
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1575 times.
1575 if (face->closed) {
999 ✗ LOG_AND_THROW("Can't add node to closed Face");
1000 }
1001
1002
1/1
✓ Branch 3 taken 1575 times.
1575 unsigned nodeIndex = face->getNodeIndex(node);
1003
2/2
✓ Branch 2 taken 831 times.
✓ Branch 3 taken 744 times.
1575 if (nodeIndex == face->nodes.size() - 1) {
1004 // if vertex is end of list, add newVertex to end
1005
1/1
✓ Branch 2 taken 831 times.
831 face->nodes.push_back(newNode);
1006
1/2
✓ Branch 0 taken 744 times.
✗ Branch 1 not taken.
744 } else if (nodeIndex == 0) {
1007 // if vertex is beginning of list, add newVertex to beginning
1008
1/1
✓ Branch 5 taken 744 times.
744 face->nodes.insert(face->nodes.begin(), newNode);
1009 } else {
1010 ✗ LOG_AND_THROW("Can't push new node. Node is inside a queue. New node can only be added at the ends of the queue.");
1011 }
1012
1013
2/2
✓ Branch 2 taken 100 times.
✓ Branch 3 taken 1475 times.
1575 if (face != newNode->face) {
1014 100 newNode->face = face;
1015 }
1016 1575 }
1017
1018 70 static void moveNodes(std::shared_ptr<FaceNode> firstNode, std::shared_ptr<FaceNode> secondNode) {
1019
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 70 times.
70 if (firstNode->face == secondNode->face) {
1020 ✗ return;
1021 }
1022 70 std::shared_ptr<FaceNode> currentQueue = firstNode;
1023 70 std::shared_ptr<FaceNode> current = secondNode;
1024 70 std::shared_ptr<FaceNode> next = nullptr;
1025
2/2
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 70 times.
170 while (current) {
1026
1/1
✓ Branch 4 taken 100 times.
100 next = current->face->popNode(current);
1027
1/1
✓ Branch 3 taken 100 times.
100 addPush(currentQueue, current);
1028 100 currentQueue = current;
1029 100 current = next;
1030 }
1031 70 }
1032
1033 514 static void connectFaces(std::shared_ptr<FaceNode> firstFaceNode, std::shared_ptr<FaceNode> secondFaceNode) {
1034 514 std::shared_ptr<Face> firstFace = firstFaceNode->face;
1035 514 std::shared_ptr<Face> secondFace = secondFaceNode->face;
1036
2/2
✓ Branch 1 taken 444 times.
✓ Branch 2 taken 70 times.
514 if (firstFace == secondFace) {
1037
7/16
✓ Branch 3 taken 444 times.
✓ Branch 5 taken 444 times.
✗ Branch 6 not taken.
✓ Branch 10 taken 444 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 444 times.
✓ Branch 14 taken 444 times.
✗ Branch 15 not taken.
✓ Branch 17 taken 444 times.
✗ Branch 18 not taken.
✗ Branch 20 not taken.
✓ Branch 21 taken 444 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
444 if (!firstFace->isEnd(firstFaceNode) || !secondFace->isEnd(secondFaceNode)) {
1038 ✗ LOG_AND_THROW("Tried to connect the same list not on end nodes.");
1039 }
1040
3/6
✓ Branch 2 taken 444 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 444 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 444 times.
444 if (firstFace->isUnconnected() || secondFace->isUnconnected()) {
1041 ✗ LOG_AND_THROW("Can't close node queue not conected with edges.");
1042 }
1043
1044 444 firstFace->closed = true;
1045 444 return;
1046 }
1047
1048
4/6
✓ Branch 2 taken 29 times.
✓ Branch 3 taken 41 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 29 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 70 times.
70 if (!firstFace->isUnconnected() && !secondFace->isUnconnected()) {
1049 ✗ LOG_AND_THROW("Can't connect two different queues if each of them is connected to an edge.");
1050 }
1051
1052
2/2
✓ Branch 2 taken 29 times.
✓ Branch 3 taken 41 times.
70 if (!firstFace->isUnconnected()) {
1053
1/1
✓ Branch 3 taken 29 times.
29 moveNodes(firstFaceNode, secondFaceNode);
1054 29 secondFace->closed = true;
1055 } else {
1056
1/1
✓ Branch 3 taken 41 times.
41 moveNodes(secondFaceNode, firstFaceNode);
1057 41 firstFace->closed = true;
1058 }
1059 958 }
1060
1061 41 static void initSlav(const std::vector<Point3d>& polygon, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav,
1062 std::vector<std::shared_ptr<Edge>>& edges, std::vector<std::shared_ptr<Face>>& faces) {
1063 41 int size = polygon.size();
1064
2/2
✓ Branch 0 taken 459 times.
✓ Branch 1 taken 41 times.
500 for (int i = 0; i < size; i++) {
1065 459 int j = (i + 1) % size;
1066
3/5
✓ Branch 1 taken 459 times.
✓ Branch 6 taken 459 times.
✓ Branch 9 taken 459 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
459 std::shared_ptr<Edge> e(new Edge(polygon[i], polygon[j]));
1067
1/1
✓ Branch 1 taken 459 times.
459 edges.push_back(e);
1068 459 }
1069
1070
2/2
✓ Branch 0 taken 459 times.
✓ Branch 1 taken 41 times.
500 for (int i = 0; i < size; i++) {
1071 459 int h = (i - 1 + size) % size;
1072 459 int j = (i + 1) % size;
1073 459 edges[i]->previous = edges[h];
1074 459 edges[i]->next = edges[j];
1075 }
1076
1077
2/2
✓ Branch 5 taken 459 times.
✓ Branch 6 taken 41 times.
500 for (const std::shared_ptr<Edge>& edge : edges) {
1078 459 std::shared_ptr<Edge> nextEdge = edge->next;
1079
1080
3/5
✓ Branch 1 taken 459 times.
✓ Branch 7 taken 459 times.
✓ Branch 10 taken 459 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
459 std::shared_ptr<Ray2d> bisector(new Ray2d(calcBisector(edge->end, edge, nextEdge)));
1081
1082 459 edge->bisectorNext = bisector;
1083
1084 459 nextEdge->bisectorPrevious = bisector;
1085 459 }
1086
1087 41 std::vector<std::shared_ptr<Vertex>> lav;
1088
1089
2/2
✓ Branch 5 taken 459 times.
✓ Branch 6 taken 41 times.
500 for (const std::shared_ptr<Edge>& edge : edges) {
1090 459 std::shared_ptr<Edge> nextEdge = edge->next;
1091
1092
3/5
✓ Branch 1 taken 459 times.
✓ Branch 9 taken 459 times.
✓ Branch 12 taken 459 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
459 std::shared_ptr<Vertex> vertex(new Vertex(edge->end, 0, edge->bisectorNext, edge, nextEdge));
1093
1094
1/1
✓ Branch 1 taken 459 times.
459 lav.push_back(vertex);
1095 459 }
1096
1/1
✓ Branch 1 taken 41 times.
41 sLav.push_back(lav);
1097
1098
2/2
✓ Branch 5 taken 459 times.
✓ Branch 6 taken 41 times.
500 for (const std::shared_ptr<Vertex>& vertex : lav) {
1099
1/1
✓ Branch 2 taken 459 times.
459 std::shared_ptr<Vertex> next = Vertex::next(vertex, lav);
1100
1101 // create face on right site of vertex
1102
2/4
✓ Branch 1 taken 459 times.
✓ Branch 5 taken 459 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
459 std::shared_ptr<Face> face(new Face());
1103 459 face->edge = vertex->nextEdge;
1104
3/5
✓ Branch 1 taken 459 times.
✓ Branch 7 taken 459 times.
✓ Branch 10 taken 459 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
459 std::shared_ptr<FaceNode> rightFaceNode(new FaceNode(vertex->point, vertex->distance, face));
1105
1/1
✓ Branch 2 taken 459 times.
459 face->nodes.push_back(rightFaceNode);
1106 459 vertex->rightFaceNode = rightFaceNode;
1107
1108 // create face on left site of next vertex
1109
3/5
✓ Branch 1 taken 459 times.
✓ Branch 7 taken 459 times.
✓ Branch 10 taken 459 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
459 std::shared_ptr<FaceNode> leftFaceNode(new FaceNode(next->point, next->distance, face));
1110
1/1
✓ Branch 3 taken 459 times.
459 addPush(rightFaceNode, leftFaceNode);
1111 459 next->leftFaceNode = leftFaceNode;
1112
1113
1/1
✓ Branch 1 taken 459 times.
459 faces.push_back(face);
1114 459 }
1115 41 }
1116
1117 26425 static bool edgeBehindBisector(std::shared_ptr<Ray2d> bisector, const LineLinear2d& edge) {
1118 /*
1119 * Simple intersection test between the bisector starting at V and the
1120 * whole line containing the currently tested line segment ei rejects
1121 * the line segments laying "behind" the vertex V
1122 */
1123
1/1
✓ Branch 2 taken 26425 times.
26425 return (!bisector->collide(edge, EPSILON));
1124 }
1125
1126 15013 static std::shared_ptr<Edge> chooseLessParallelVertexEdge(std::shared_ptr<Vertex> vertex, std::shared_ptr<Edge> edge) {
1127 15013 std::shared_ptr<Edge> edgeA = vertex->previousEdge;
1128 15013 std::shared_ptr<Edge> edgeB = vertex->nextEdge;
1129
1130 15013 std::shared_ptr<Edge> vertexEdge = edgeA;
1131
1132
3/3
✓ Branch 2 taken 15013 times.
✓ Branch 6 taken 15013 times.
✓ Branch 9 taken 15013 times.
15013 double edgeADot = std::abs(edge->normalize().dot(edgeA->normalize()));
1133
3/3
✓ Branch 2 taken 15013 times.
✓ Branch 6 taken 15013 times.
✓ Branch 9 taken 15013 times.
15013 double edgeBDot = std::abs(edge->normalize().dot(edgeB->normalize()));
1134
1135
2/2
✓ Branch 0 taken 125 times.
✓ Branch 1 taken 14888 times.
15013 if (edgeADot + edgeBDot >= 2 - EPSILON) {
1136 // both lines are parallel to given edge
1137 125 return nullptr;
1138 }
1139
1140
2/2
✓ Branch 0 taken 7545 times.
✓ Branch 1 taken 7343 times.
14888 if (edgeADot > edgeBDot) {
1141 /*
1142 * Simple check should be performed to exclude the case when one of
1143 * the line segments starting at V (vertex) is parallel to e_i
1144 * (edge) we always chose edge which is less parallel.
1145 */
1146 7545 vertexEdge = edgeB;
1147 }
1148
1149 14888 return vertexEdge;
1150 15013 }
1151
1152 // see http://en.wikipedia.org/wiki/Vector_projection
1153 2919 static Vector3d orthogonalProjection(const Vector3d& unitVector, const Vector3d& vectorToProject) {
1154
1/1
✓ Branch 1 taken 2919 times.
2919 Vector3d n = Vector3d(unitVector);
1155
1/1
✓ Branch 1 taken 2919 times.
2919 n.normalize();
1156
1157
1/1
✓ Branch 1 taken 2919 times.
2919 double px = vectorToProject.x();
1158
1/1
✓ Branch 1 taken 2919 times.
2919 double py = vectorToProject.y();
1159
1/1
✓ Branch 1 taken 2919 times.
2919 double pz = vectorToProject.z();
1160
1161
1/1
✓ Branch 1 taken 2919 times.
2919 double ax = n.x();
1162
1/1
✓ Branch 1 taken 2919 times.
2919 double ay = n.y();
1163
1/1
✓ Branch 1 taken 2919 times.
2919 double az = n.z();
1164
1165 2919 double vx = px * ax * ax + py * ax * ay + pz * ax * az;
1166 2919 double vy = px * ax * ay + py * ay * ay + pz * ay * az;
1167 2919 double vz = px * ax * az + py * ay * az + pz * az * az;
1168
1169
1/1
✓ Branch 1 taken 2919 times.
5838 return {vx, vy, vz};
1170 2919 }
1171
1172 2919 static double calcDistance(const Point3d& intersect, std::shared_ptr<Edge> currentEdge) {
1173 // TODO: Can be replaced by getDistancePointToLineSegment() ?
1174
1/1
✓ Branch 3 taken 2919 times.
2919 Vector3d edge = currentEdge->end - currentEdge->begin;
1175
1/1
✓ Branch 2 taken 2919 times.
2919 Vector3d vector = intersect - currentEdge->begin;
1176
1177
1/1
✓ Branch 1 taken 2919 times.
2919 Vector3d pointOnVector = orthogonalProjection(edge, vector);
1178
1179
9/9
✓ Branch 1 taken 2919 times.
✓ Branch 4 taken 2919 times.
✓ Branch 7 taken 2919 times.
✓ Branch 10 taken 2919 times.
✓ Branch 13 taken 2919 times.
✓ Branch 16 taken 2919 times.
✓ Branch 19 taken 2919 times.
✓ Branch 22 taken 2919 times.
✓ Branch 25 taken 2919 times.
5838 return getDistance(Point3d(vector.x(), vector.y(), vector.z()), Point3d(pointOnVector.x(), pointOnVector.y(), pointOnVector.z()));
1180 2919 }
1181
1182 15013 static boost::optional<SplitCandidate> calcCandidatePointForSplit(std::shared_ptr<Vertex> vertex, std::shared_ptr<Edge> edge) {
1183
1184
1/1
✓ Branch 3 taken 15013 times.
15013 std::shared_ptr<Edge> vertexEdge = chooseLessParallelVertexEdge(vertex, edge);
1185
2/2
✓ Branch 1 taken 125 times.
✓ Branch 2 taken 14888 times.
15013 if (!vertexEdge) {
1186 125 return boost::none;
1187 }
1188
1189
1/1
✓ Branch 2 taken 14888 times.
14888 Vector3d vertexEdgeNormNegate = vertexEdge->normalize();
1190
1/1
✓ Branch 2 taken 14888 times.
14888 Vector3d edgeNorm = edge->normalize();
1191
1/1
✓ Branch 1 taken 14888 times.
14888 Vector3d edgesBisector = calcVectorBisector(vertexEdgeNormNegate, edgeNorm);
1192
1193
1/1
✓ Branch 3 taken 14888 times.
14888 LineLinear2d llv = LineLinear2d(vertexEdge->begin, vertexEdge->end);
1194
1/1
✓ Branch 3 taken 14888 times.
14888 LineLinear2d lle = LineLinear2d(edge->begin, edge->end);
1195
1196
1/1
✓ Branch 1 taken 14888 times.
14888 boost::optional<Point3d> edgesCollide = llv.collide(lle);
1197
1198
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 14888 times.
14888 if (!edgesCollide) {
1199 /*
1200 * Check should be performed to exclude the case when one of the
1201 * line segments starting at V is parallel to ei.
1202 */
1203 ✗ return boost::none;
1204 }
1205
1206
3/3
✓ Branch 1 taken 14888 times.
✓ Branch 4 taken 14888 times.
✓ Branch 7 taken 14888 times.
14888 LineLinear2d edgesBisectorLine = Ray2d(edgesCollide.get(), edgesBisector).getLinearForm();
1207
1208 /*
1209 * Compute the coordinates of the candidate point Bi as the intersection
1210 * between the bisector at V and the axis of the angle between one of
1211 * the edges starting at V and the tested line segment ei
1212 */
1213
1/1
✓ Branch 3 taken 14888 times.
14888 boost::optional<Point3d> candidatePoint = vertex->bisector->collide(edgesBisectorLine, EPSILON);
1214
1215
2/2
✓ Branch 1 taken 3094 times.
✓ Branch 2 taken 11794 times.
14888 if (!candidatePoint) {
1216 3094 return boost::none;
1217 }
1218
1219
10/10
✓ Branch 3 taken 11794 times.
✓ Branch 6 taken 11794 times.
✓ Branch 8 taken 6397 times.
✓ Branch 9 taken 5397 times.
✓ Branch 13 taken 6397 times.
✓ Branch 16 taken 6397 times.
✓ Branch 18 taken 2180 times.
✓ Branch 19 taken 4217 times.
✓ Branch 20 taken 2180 times.
✓ Branch 21 taken 9614 times.
11794 if (edge->bisectorPrevious->isOnRightSide(candidatePoint.get(), EPSILON) && edge->bisectorNext->isOnLeftSide(candidatePoint.get(), EPSILON)) {
1220
1221
2/2
✓ Branch 2 taken 2180 times.
✓ Branch 5 taken 2180 times.
2180 double distance = calcDistance(candidatePoint.get(), edge);
1222
1223
10/10
✓ Branch 3 taken 2180 times.
✓ Branch 6 taken 2180 times.
✓ Branch 8 taken 1751 times.
✓ Branch 9 taken 429 times.
✓ Branch 13 taken 1751 times.
✓ Branch 16 taken 1751 times.
✓ Branch 18 taken 282 times.
✓ Branch 19 taken 1469 times.
✓ Branch 20 taken 711 times.
✓ Branch 21 taken 1469 times.
2180 if (edge->bisectorPrevious->isOnLeftSide(candidatePoint.get(), EPSILON) || edge->bisectorNext->isOnRightSide(candidatePoint.get(), EPSILON)) {
1224
1225
1/1
✓ Branch 2 taken 711 times.
711 Point3d oppositePoint = edge->begin;
1226
3/3
✓ Branch 3 taken 711 times.
✓ Branch 6 taken 711 times.
✓ Branch 9 taken 711 times.
711 return SplitCandidate(candidatePoint.get(), distance, nullptr, oppositePoint);
1227 711 }
1228
1229
3/3
✓ Branch 3 taken 1469 times.
✓ Branch 6 taken 1469 times.
✓ Branch 9 taken 1469 times.
1469 return SplitCandidate(candidatePoint.get(), distance, edge, boost::none);
1230 }
1231
1232 9614 return boost::none;
1233 15013 }
1234
1235 811 static std::vector<SplitCandidate> calcOppositeEdges(std::shared_ptr<Vertex> vertex, const std::vector<std::shared_ptr<Edge>>& edges) {
1236
1237 811 std::vector<SplitCandidate> ret;
1238
1239
2/2
✓ Branch 5 taken 26421 times.
✓ Branch 6 taken 811 times.
27232 for (const std::shared_ptr<Edge>& edgeEntry : edges) {
1240
1241
1/1
✓ Branch 3 taken 26421 times.
26421 LineLinear2d edge = LineLinear2d(edgeEntry->begin, edgeEntry->end);
1242
1243 // check if edge is behind bisector
1244
3/3
✓ Branch 3 taken 26421 times.
✓ Branch 6 taken 11408 times.
✓ Branch 7 taken 15013 times.
26421 if (edgeBehindBisector(vertex->bisector, edge)) {
1245 11408 continue;
1246 }
1247 // compute the coordinates of the candidate point Bi
1248
1/1
✓ Branch 3 taken 15013 times.
15013 boost::optional<SplitCandidate> candidatePoint = calcCandidatePointForSplit(vertex, edgeEntry);
1249
1250
2/2
✓ Branch 0 taken 2180 times.
✓ Branch 1 taken 12833 times.
15013 if (candidatePoint) {
1251
2/2
✓ Branch 1 taken 2180 times.
✓ Branch 4 taken 2180 times.
2180 ret.push_back(candidatePoint.get());
1252 }
1253 15013 }
1254
1255
2/2
✓ Branch 1 taken 485 times.
✓ Branch 2 taken 326 times.
811 if (ret.size() > 1) {
1256
1/1
✓ Branch 3 taken 485 times.
485 std::sort(ret.begin(), ret.end());
1257 }
1258
1259 811 return ret;
1260 ✗ }
1261
1262 811 static void computeSplitEvents(std::shared_ptr<Vertex> vertex, const std::vector<std::shared_ptr<Edge>>& edges,
1263 std::vector<std::shared_ptr<QueueEvent>>& queue, boost::optional<double> distanceSquared) {
1264
1/1
✓ Branch 2 taken 811 times.
811 Point3d source = vertex->point;
1265
1266
1/1
✓ Branch 2 taken 811 times.
811 std::vector<SplitCandidate> oppositeEdges = calcOppositeEdges(vertex, edges);
1267
1268 // check if it is vertex split event
1269
2/2
✓ Branch 5 taken 2180 times.
✓ Branch 6 taken 811 times.
2991 for (const SplitCandidate& oppositeEdge : oppositeEdges) {
1270
1271
2/2
✓ Branch 0 taken 794 times.
✓ Branch 1 taken 1386 times.
2180 if (distanceSquared) {
1272
4/4
✓ Branch 1 taken 794 times.
✓ Branch 4 taken 794 times.
✓ Branch 6 taken 518 times.
✓ Branch 7 taken 276 times.
794 if (getDistanceSquared(source, oppositeEdge.point) > distanceSquared.get() + EPSILON) {
1273 /*
1274 * Current split event distance from source of event is
1275 * greater then for edge event. Split event can be reject.
1276 * Distance from source is not the same as distance for
1277 * edge. Two events can have the same distance to edge but
1278 * they will be in different distance form its source.
1279 * Unnecessary events should be reject otherwise they cause
1280 * problems for degenerate cases.
1281 */
1282 1119 continue;
1283 }
1284 }
1285
1286 // check if it is vertex split event
1287
2/2
✓ Branch 1 taken 601 times.
✓ Branch 2 taken 1061 times.
3324 if (oppositeEdge.oppositePoint) {
1288 // some of vertex event can share the same opposite
1289 // point
1290
3/5
✓ Branch 1 taken 601 times.
✓ Branch 5 taken 601 times.
✓ Branch 8 taken 601 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
601 std::shared_ptr<QueueEvent> e1(new QueueEvent(oppositeEdge.point, oppositeEdge.distance, vertex)); // SplitEvent
1291
1/1
✓ Branch 2 taken 601 times.
601 QueueEvent::insert_sorted(queue, e1);
1292 601 continue;
1293 601 }
1294
1295
3/5
✓ Branch 1 taken 1061 times.
✓ Branch 6 taken 1061 times.
✓ Branch 9 taken 1061 times.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
1061 std::shared_ptr<QueueEvent> e2(new QueueEvent(oppositeEdge.point, oppositeEdge.distance, vertex, oppositeEdge.oppositeEdge)); // SplitVertexEvent
1296
1/1
✓ Branch 2 taken 1061 times.
1061 QueueEvent::insert_sorted(queue, e2);
1297 1061 }
1298 811 }
1299
1300 1163 static boost::optional<Point3d> computeIntersectionBisectors(std::shared_ptr<Vertex> vertexPrevious, std::shared_ptr<Vertex> vertexNext) {
1301 1163 boost::optional<Point3d> ret;
1302
1303 1163 std::shared_ptr<Ray2d> bisectorPrevious = vertexPrevious->bisector;
1304 1163 std::shared_ptr<Ray2d> bisectorNext = vertexNext->bisector;
1305
1306
1/1
✓ Branch 3 taken 1163 times.
1163 boost::optional<Point3d> thisIntersect = bisectorPrevious->intersectRay2d(bisectorNext);
1307
1308
2/2
✓ Branch 1 taken 215 times.
✓ Branch 2 taken 948 times.
1163 if (!thisIntersect) {
1309 215 return ret;
1310 }
1311
1312
10/10
✓ Branch 1 taken 948 times.
✓ Branch 5 taken 948 times.
✓ Branch 7 taken 942 times.
✓ Branch 8 taken 6 times.
✓ Branch 10 taken 942 times.
✓ Branch 14 taken 942 times.
✓ Branch 16 taken 16 times.
✓ Branch 17 taken 926 times.
✓ Branch 18 taken 22 times.
✓ Branch 19 taken 926 times.
948 if (vertexPrevious->point == thisIntersect.get() || vertexNext->point == thisIntersect.get()) {
1313 // skip the same points
1314 22 return ret;
1315 }
1316
1317
2/2
✓ Branch 1 taken 926 times.
✓ Branch 4 taken 926 times.
926 ret = thisIntersect.get();
1318 926 return ret;
1319 1163 }
1320
1321 739 static std::shared_ptr<QueueEvent> createEdgeEvent(const Point3d& point, std::shared_ptr<Vertex> previousVertex, std::shared_ptr<Vertex> nextVertex) {
1322
3/5
✓ Branch 6 taken 739 times.
✓ Branch 9 taken 739 times.
✓ Branch 12 taken 739 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
739 std::shared_ptr<QueueEvent> e(new QueueEvent(point, calcDistance(point, previousVertex->nextEdge), previousVertex, nextVertex)); // EdgeEvent
1323 739 return e;
1324 }
1325
1326 459 static void computeEdgeEvents(std::shared_ptr<Vertex> previousVertex, std::shared_ptr<Vertex> nextVertex,
1327 std::vector<std::shared_ptr<QueueEvent>>& queue) {
1328
1/1
✓ Branch 3 taken 459 times.
459 boost::optional<Point3d> point = computeIntersectionBisectors(previousVertex, nextVertex);
1329
2/2
✓ Branch 0 taken 314 times.
✓ Branch 1 taken 145 times.
459 if (point) {
1330
2/2
✓ Branch 3 taken 314 times.
✓ Branch 6 taken 314 times.
314 std::shared_ptr<QueueEvent> e(createEdgeEvent(point.get(), previousVertex, nextVertex));
1331
1/1
✓ Branch 2 taken 314 times.
314 QueueEvent::insert_sorted(queue, e);
1332 314 }
1333 459 }
1334
1335 41 static void initEvents(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav, std::vector<std::shared_ptr<QueueEvent>>& queue,
1336 const std::vector<std::shared_ptr<Edge>>& edges) {
1337
2/2
✓ Branch 5 taken 41 times.
✓ Branch 6 taken 41 times.
82 for (const std::vector<std::shared_ptr<Vertex>>& lav : sLav) {
1338
2/2
✓ Branch 4 taken 459 times.
✓ Branch 5 taken 41 times.
500 for (const std::shared_ptr<Vertex>& vertex : lav) {
1339
1/1
✓ Branch 3 taken 459 times.
459 computeSplitEvents(vertex, edges, queue, boost::none);
1340 }
1341 }
1342
1343
2/2
✓ Branch 5 taken 41 times.
✓ Branch 6 taken 41 times.
82 for (std::vector<std::shared_ptr<Vertex>>& lav : sLav) {
1344
2/2
✓ Branch 5 taken 459 times.
✓ Branch 6 taken 41 times.
500 for (const std::shared_ptr<Vertex>& vertex : lav) {
1345
1/1
✓ Branch 2 taken 459 times.
459 std::shared_ptr<Vertex> next = Vertex::next(vertex, lav);
1346
1/1
✓ Branch 3 taken 459 times.
459 computeEdgeEvents(vertex, next, queue);
1347 459 }
1348 }
1349 41 }
1350
1351 // Calculate area of polygon outline. For clockwise area will be less than
1352 // zero, for counter-clockwise polygon area will be greater than zero.
1353 41 static double area(const std::vector<Point3d>& polygon) {
1354 41 int n = polygon.size();
1355 41 double a = 0.0;
1356
2/2
✓ Branch 0 taken 459 times.
✓ Branch 1 taken 41 times.
500 for (int p = n - 1, q = 0; q < n; p = q++) {
1357
1/1
✓ Branch 2 taken 459 times.
459 Point3d pp = polygon[p];
1358
1/1
✓ Branch 2 taken 459 times.
459 Point3d pq = polygon[q];
1359
4/4
✓ Branch 1 taken 459 times.
✓ Branch 4 taken 459 times.
✓ Branch 7 taken 459 times.
✓ Branch 10 taken 459 times.
459 a += pp.x() * pq.y() - pq.x() * pp.y();
1360 459 }
1361 41 return a * 0.5;
1362 }
1363
1364 // Check if polygon is clockwise.
1365 41 static bool isClockwisePolygon(const std::vector<Point3d>& polygon) {
1366 41 return (area(polygon) < 0);
1367 }
1368
1369 // Updates points ordered as counter clockwise.
1370 41 static void makeCounterClockwise(std::vector<Point3d>& polygon) {
1371
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 27 times.
41 if (isClockwisePolygon(polygon)) {
1372
1/1
✓ Branch 1 taken 14 times.
14 polygon = reverse(polygon);
1373 }
1374 41 }
1375
1376 47 static void setZcoordsToZero(std::vector<Point3d>& polygon) {
1377
2/2
✓ Branch 4 taken 491 times.
✓ Branch 5 taken 47 times.
538 for (Point3d& p : polygon) {
1378
3/3
✓ Branch 1 taken 491 times.
✓ Branch 4 taken 491 times.
✓ Branch 7 taken 491 times.
491 p += Vector3d(0, 0, -p.z());
1379 }
1380 47 }
1381
1382 50 static double initPolygon(std::vector<Point3d>& polygon) {
1383
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 49 times.
50 if (polygon.size() < 3) {
1384
13/13
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✓ Branch 7 taken 1 time.
✓ Branch 10 taken 1 time.
✓ Branch 13 taken 1 time.
✓ Branch 19 taken 1 time.
✓ Branch 22 taken 1 time.
✓ Branch 25 taken 1 time.
✓ Branch 28 taken 1 time.
✓ Branch 31 taken 1 time.
✓ Branch 34 taken 1 time.
✓ Branch 38 taken 1 time.
✓ Branch 41 taken 1 time.
1 LOG_AND_THROW("Polygon must have at least 3 points.");
1385
2/2
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 48 times.
49 } else if (polygon[0] == polygon[polygon.size() - 1]) {
1386
13/13
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✓ Branch 7 taken 1 time.
✓ Branch 10 taken 1 time.
✓ Branch 13 taken 1 time.
✓ Branch 19 taken 1 time.
✓ Branch 22 taken 1 time.
✓ Branch 25 taken 1 time.
✓ Branch 28 taken 1 time.
✓ Branch 31 taken 1 time.
✓ Branch 34 taken 1 time.
✓ Branch 38 taken 1 time.
✓ Branch 41 taken 1 time.
1 LOG_AND_THROW("Polygon can't start and end with the same point.");
1387 }
1388
1389
2/2
✓ Branch 1 taken 445 times.
✓ Branch 2 taken 47 times.
492 for (unsigned i = 1; i < polygon.size(); i++) {
1390
2/2
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 444 times.
445 if (polygon[i].z() != polygon[0].z()) {
1391
13/13
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✓ Branch 7 taken 1 time.
✓ Branch 10 taken 1 time.
✓ Branch 13 taken 1 time.
✓ Branch 19 taken 1 time.
✓ Branch 22 taken 1 time.
✓ Branch 25 taken 1 time.
✓ Branch 28 taken 1 time.
✓ Branch 31 taken 1 time.
✓ Branch 34 taken 1 time.
✓ Branch 38 taken 1 time.
✓ Branch 41 taken 1 time.
1 LOG_AND_THROW("All polygon z coordinates must be the same.");
1392 }
1393 }
1394
1395 47 double zcoord = polygon[0].z();
1396 47 setZcoordsToZero(polygon);
1397
1398 47 return zcoord;
1399 }
1400
1401 362 static int assertMaxNumberOfIterations(int count) {
1402 362 count++;
1403
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 362 times.
362 if (count > 10000) {
1404 ✗ LOG_AND_THROW("Maximum number of iterations reached. Bug?");
1405 }
1406 362 return count;
1407 }
1408
1409 362 static std::vector<std::shared_ptr<QueueEvent>> loadLevelEvents(std::vector<std::shared_ptr<QueueEvent>>& queue) {
1410 /*
1411 * Loads all non obsolete events which are on one level.
1412 */
1413
1414 362 std::vector<std::shared_ptr<QueueEvent>> level;
1415
1416 362 std::shared_ptr<QueueEvent> levelStart = nullptr;
1417
2/2
✓ Branch 1 taken 1476 times.
✓ Branch 2 taken 36 times.
1512 while (!queue.empty()) {
1418 1476 levelStart = queue[0];
1419
1/1
✓ Branch 3 taken 1476 times.
1476 queue.erase(queue.begin());
1420 // skip all obsolete events in level
1421
2/2
✓ Branch 2 taken 326 times.
✓ Branch 3 taken 1150 times.
1476 if (!levelStart->isObsolete()) {
1422 326 break;
1423 }
1424 }
1425
1426
5/6
✓ Branch 1 taken 362 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 36 times.
✓ Branch 6 taken 326 times.
✓ Branch 7 taken 36 times.
✓ Branch 8 taken 326 times.
362 if (!levelStart || levelStart->isObsolete()) {
1427 // all events obsolete
1428 36 return level;
1429 }
1430
1431 326 double levelStartHeight = levelStart->distance;
1432
1433
1/1
✓ Branch 1 taken 326 times.
326 level.push_back(levelStart);
1434
1435 326 std::shared_ptr<QueueEvent> event = nullptr;
1436
1437
2/2
✓ Branch 1 taken 1125 times.
✓ Branch 2 taken 5 times.
1456 while (!queue.empty()) {
1438 1125 event = queue[0];
1439
2/2
✓ Branch 1 taken 321 times.
✓ Branch 2 taken 804 times.
1125 if (event->distance - levelStartHeight >= EPSILON) {
1440 321 break;
1441 }
1442
1/1
✓ Branch 3 taken 804 times.
804 queue.erase(queue.begin());
1443
2/2
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 796 times.
804 if (!event->isObsolete()) {
1444
1/1
✓ Branch 1 taken 796 times.
796 level.push_back(event);
1445 }
1446 }
1447
1448 326 return level;
1449 362 }
1450
1451 283 static std::vector<std::shared_ptr<QueueEvent>> createEdgeChain(std::vector<std::shared_ptr<QueueEvent>>& edgeCluster) {
1452 283 std::vector<std::shared_ptr<QueueEvent>> edgeList;
1453
1454
1/1
✓ Branch 2 taken 283 times.
283 edgeList.push_back(edgeCluster[0]);
1455
1/1
✓ Branch 3 taken 283 times.
283 edgeCluster.erase(edgeCluster.begin());
1456
1457 // find all successors of edge event
1458 // find all predecessors of edge event
1459
1460 do {
1461 461 std::shared_ptr<Vertex> beginVertex = edgeList[0]->previousVertex;
1462 461 std::shared_ptr<Vertex> endVertex = edgeList[edgeList.size() - 1]->nextVertex;
1463
1464 461 bool do_continue = false;
1465
2/2
✓ Branch 1 taken 180 times.
✓ Branch 2 taken 283 times.
463 for (unsigned i = 0; i < edgeCluster.size(); i++) {
1466
2/2
✓ Branch 3 taken 131 times.
✓ Branch 4 taken 49 times.
180 if (edgeCluster[i]->previousVertex == endVertex) {
1467 // edge should be added as last in chain
1468
1/1
✓ Branch 2 taken 131 times.
131 edgeList.push_back(edgeCluster[i]);
1469
1/1
✓ Branch 4 taken 131 times.
131 edgeCluster.erase(edgeCluster.begin() + i);
1470 131 do_continue = true;
1471 131 break;
1472
2/2
✓ Branch 3 taken 47 times.
✓ Branch 4 taken 2 times.
49 } else if (edgeCluster[i]->nextVertex == beginVertex) {
1473 // edge should be added as first in chain
1474
1/1
✓ Branch 4 taken 47 times.
47 edgeList.insert(edgeList.begin(), edgeCluster[i]);
1475
1/1
✓ Branch 4 taken 47 times.
47 edgeCluster.erase(edgeCluster.begin() + i);
1476 47 do_continue = true;
1477 47 break;
1478 }
1479 }
1480
1481
2/2
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 283 times.
461 if (do_continue) {
1482 178 continue;
1483 }
1484
1485 283 break;
1486
1487
4/4
✓ Branch 1 taken 178 times.
✓ Branch 2 taken 283 times.
✓ Branch 4 taken 178 times.
✓ Branch 5 taken 283 times.
922 } while (true);
1488
1489 283 return edgeList;
1490 ✗ }
1491
1492 537 static bool isInEdgeChain(std::shared_ptr<QueueEvent> split, const Chain& chain) {
1493
1/2
✓ Branch 5 taken 628 times.
✗ Branch 6 not taken.
628 for (const std::shared_ptr<QueueEvent>& edgeEvent : chain.edgeList) {
1494
6/6
✓ Branch 3 taken 399 times.
✓ Branch 4 taken 229 times.
✓ Branch 8 taken 308 times.
✓ Branch 9 taken 91 times.
✓ Branch 10 taken 537 times.
✓ Branch 11 taken 91 times.
628 if (edgeEvent->previousVertex == split->parent || edgeEvent->nextVertex == split->parent) {
1495 537 return true;
1496 }
1497 }
1498
1499 ✗ return false;
1500 }
1501
1502 366 static std::vector<Chain> createChains(const std::vector<std::shared_ptr<QueueEvent>>& cluster,
1503 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1504 /*
1505 * Create chains of events from cluster. Cluster is set of events which meet
1506 * in the same result point. Try to connect all events which share the same
1507 * vertex into chain. Events in a chain are sorted. If events don't share a
1508 * vertex, returned chains contains only one event.
1509 */
1510
1511 366 std::vector<std::shared_ptr<QueueEvent>> edgeCluster;
1512 366 std::vector<std::shared_ptr<QueueEvent>> splitCluster;
1513 366 std::vector<std::shared_ptr<Vertex>> vertexEventsParents;
1514
1515
2/2
✓ Branch 5 taken 1126 times.
✓ Branch 6 taken 366 times.
1492 for (const std::shared_ptr<QueueEvent>& event : cluster) {
1516
2/2
✓ Branch 1 taken 456 times.
✓ Branch 2 taken 670 times.
1126 if (event->eventType == QueueEvent::TYPE_EDGE) {
1517
1/1
✓ Branch 1 taken 456 times.
456 edgeCluster.push_back(event);
1518 } else {
1519
2/2
✓ Branch 1 taken 397 times.
✓ Branch 2 taken 273 times.
670 if (event->eventType == QueueEvent::TYPE_SPLIT_VERTEX) {
1520 /*
1521 * It will be processed in the next loop to find unique split
1522 * events for one parent.
1523 */
1524 397 continue;
1525
1/2
✓ Branch 1 taken 273 times.
✗ Branch 2 not taken.
273 } else if (event->eventType == QueueEvent::TYPE_SPLIT) {
1526
1/1
✓ Branch 2 taken 273 times.
273 vertexEventsParents.push_back(event->parent);
1527
1/1
✓ Branch 1 taken 273 times.
273 splitCluster.push_back(event);
1528 }
1529 }
1530 }
1531
1532
2/2
✓ Branch 5 taken 1126 times.
✓ Branch 6 taken 366 times.
1492 for (const std::shared_ptr<QueueEvent>& event : cluster) {
1533
2/2
✓ Branch 1 taken 397 times.
✓ Branch 2 taken 729 times.
1126 if (event->eventType == QueueEvent::TYPE_SPLIT_VERTEX) {
1534
1/1
✓ Branch 5 taken 397 times.
397 bool found = std::find(vertexEventsParents.begin(), vertexEventsParents.end(), event->parent) != vertexEventsParents.end();
1535
2/2
✓ Branch 0 taken 357 times.
✓ Branch 1 taken 40 times.
397 if (!found) {
1536 /*
1537 * Multiple vertex events can be created for one parent.
1538 * It is caused by two edges that share one vertex and new
1539 * event will be added for both of them. When processing we
1540 * always need to group them into one per vertex. Always prefer
1541 * split events over vertex events.
1542 */
1543
1/1
✓ Branch 2 taken 357 times.
357 vertexEventsParents.push_back(event->parent);
1544
1/1
✓ Branch 1 taken 357 times.
357 splitCluster.push_back(event);
1545 }
1546 }
1547 }
1548
1549 366 std::vector<Chain> edgeChains;
1550
1551
2/2
✓ Branch 1 taken 281 times.
✓ Branch 2 taken 366 times.
647 while (!edgeCluster.empty()) {
1552 /*
1553 * We need to find all connected edge events, and create chains from
1554 * them. Two events are assumed to be connected if next parent of one
1555 * event is equal to previous parent of second event.
1556 */
1557
1/1
✓ Branch 1 taken 281 times.
281 std::vector<std::shared_ptr<QueueEvent>> edgeList = createEdgeChain(edgeCluster);
1558
1/1
✓ Branch 1 taken 281 times.
281 Chain edgeChain = Chain(edgeList, sLav);
1559
1/1
✓ Branch 1 taken 281 times.
281 edgeChains.push_back(edgeChain); // EdgeChain
1560 281 }
1561
1562 366 std::vector<Chain> chains;
1563
2/2
✓ Branch 5 taken 281 times.
✓ Branch 6 taken 366 times.
647 for (const Chain& edgeChain : edgeChains) {
1564
1/1
✓ Branch 1 taken 281 times.
281 chains.push_back(edgeChain);
1565 }
1566
1567
2/2
✓ Branch 1 taken 630 times.
✓ Branch 2 taken 366 times.
996 while (!splitCluster.empty()) {
1568 630 std::shared_ptr<QueueEvent> split = splitCluster[0];
1569
1/1
✓ Branch 3 taken 630 times.
630 splitCluster.erase(splitCluster.begin());
1570
1571 630 bool inEdgeChain = false;
1572
2/2
✓ Branch 5 taken 537 times.
✓ Branch 6 taken 93 times.
630 for (const Chain& chain : edgeChains) {
1573 // check if chain is split type
1574
1/2
✓ Branch 3 taken 537 times.
✗ Branch 4 not taken.
537 if (isInEdgeChain(split, chain)) {
1575 // if we have edge chain it can't share split event
1576 537 inEdgeChain = true;
1577 537 break;
1578 }
1579 }
1580
1581
2/2
✓ Branch 0 taken 537 times.
✓ Branch 1 taken 93 times.
630 if (inEdgeChain) {
1582 537 continue;
1583 }
1584
1585 /*
1586 * split event is not part of any edge chain, it should be added as
1587 * new single element chain;
1588 */
1589
1/1
✓ Branch 3 taken 93 times.
93 chains.push_back(Chain(split)); // SplitChain
1590 630 }
1591
1592 /*
1593 * Return list of chains with type. Possible types are edge chain,
1594 * closed edge chain, split chain. Closed edge chain will produce pick
1595 * event. Always it can exist only one closed edge chain for point
1596 * cluster.
1597 */
1598
1599 732 return chains;
1600 366 }
1601
1602 366 static LevelEvent createLevelEvent(const Point3d& eventCenter, double distance, const std::vector<std::shared_ptr<QueueEvent>>& eventCluster,
1603 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1604
1605
1/1
✓ Branch 1 taken 366 times.
366 std::vector<Chain> chains = createChains(eventCluster, sLav);
1606
1607
2/2
✓ Branch 1 taken 360 times.
✓ Branch 2 taken 6 times.
366 if (chains.size() == 1) {
1608
3/3
✓ Branch 2 taken 360 times.
✓ Branch 4 taken 82 times.
✓ Branch 5 taken 278 times.
360 if (chains[0].getChainMode() == Chain::MODE_CLOSED_EDGE) {
1609
1/1
✓ Branch 2 taken 82 times.
82 return LevelEvent(eventCenter, distance, chains[0], true); // PickEvent
1610
3/3
✓ Branch 2 taken 278 times.
✓ Branch 4 taken 199 times.
✓ Branch 5 taken 79 times.
278 } else if (chains[0].getChainMode() == Chain::MODE_EDGE) {
1611
1/1
✓ Branch 2 taken 199 times.
199 return LevelEvent(eventCenter, distance, chains[0], false); // MultiEdgeEvent
1612
2/3
✓ Branch 2 taken 79 times.
✓ Branch 4 taken 79 times.
✗ Branch 5 not taken.
79 } else if (chains[0].getChainMode() == Chain::MODE_SPLIT) {
1613
1/1
✓ Branch 1 taken 79 times.
79 return LevelEvent(eventCenter, distance, chains); // MultiSplitEvent
1614 }
1615 }
1616
1617
2/2
✓ Branch 5 taken 14 times.
✓ Branch 6 taken 6 times.
20 for (const Chain& chain : chains) {
1618
2/3
✓ Branch 1 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 14 times.
14 if (chain.getChainMode() == Chain::MODE_CLOSED_EDGE) {
1619 ✗ LOG_AND_THROW("found closed chain of events for single point, but found more then one chain");
1620 }
1621 }
1622
1623
1/1
✓ Branch 1 taken 6 times.
6 return LevelEvent(eventCenter, distance, chains); // MultiSplitEvent
1624 366 }
1625
1626 363 static std::vector<LevelEvent> groupLevelEvents(std::vector<std::shared_ptr<QueueEvent>>& levelEvents,
1627 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1628 363 std::vector<LevelEvent> ret;
1629 363 std::vector<std::shared_ptr<Vertex>> parentGroup;
1630
1631
2/2
✓ Branch 1 taken 366 times.
✓ Branch 2 taken 363 times.
729 while (!levelEvents.empty()) {
1632 366 parentGroup.clear();
1633
1634
1/1
✓ Branch 3 taken 366 times.
366 Point3d eventCenter = levelEvents[0]->point;
1635 366 double distance = levelEvents[0]->distance;
1636
1637
1/1
✓ Branch 3 taken 366 times.
366 levelEvents[0]->addEventToGroup(parentGroup);
1638
1639 366 std::vector<std::shared_ptr<QueueEvent>> cluster;
1640
1/1
✓ Branch 2 taken 366 times.
366 cluster.push_back(levelEvents[0]);
1641
1642
1/1
✓ Branch 3 taken 366 times.
366 levelEvents.erase(levelEvents.begin());
1643
1644
2/2
✓ Branch 1 taken 913 times.
✓ Branch 2 taken 366 times.
1279 for (unsigned j = 0; j < levelEvents.size(); j++) {
1645
1646
3/3
✓ Branch 3 taken 913 times.
✓ Branch 5 taken 646 times.
✓ Branch 6 taken 267 times.
913 if (levelEvents[j]->isEventInGroup(parentGroup)) {
1647 /* Because of numerical errors, split event and edge event
1648 * can appear in slight different points. Epsilon can be
1649 * applied to level but event point can move rapidly even for
1650 * little changes in level. If two events for the same level
1651 * share the same parent, they should be merge together.
1652 */
1653
1/1
✓ Branch 2 taken 646 times.
646 cluster.push_back(levelEvents[j]);
1654
1/1
✓ Branch 3 taken 646 times.
646 levelEvents[j]->addEventToGroup(parentGroup);
1655
1/1
✓ Branch 4 taken 646 times.
646 levelEvents.erase(levelEvents.begin() + j);
1656 646 j--;
1657
3/3
✓ Branch 3 taken 267 times.
✓ Branch 5 taken 114 times.
✓ Branch 6 taken 153 times.
267 } else if (getDistance(eventCenter, levelEvents[j]->point) < EPSILON) {
1658 // group all events when the result points are near each other
1659
1/1
✓ Branch 2 taken 114 times.
114 cluster.push_back(levelEvents[j]);
1660
1/1
✓ Branch 3 taken 114 times.
114 levelEvents[j]->addEventToGroup(parentGroup);
1661
1/1
✓ Branch 4 taken 114 times.
114 levelEvents.erase(levelEvents.begin() + j);
1662 114 j--;
1663 }
1664 }
1665
1666 // More than one event can share the same result point, we need to
1667 // create new level event.
1668
2/2
✓ Branch 1 taken 366 times.
✓ Branch 4 taken 366 times.
366 ret.push_back(createLevelEvent(eventCenter, distance, cluster, sLav));
1669 366 }
1670
1671 726 return ret;
1672 363 }
1673
1674 362 static std::vector<LevelEvent> loadAndGroupLevelEvents(std::vector<std::shared_ptr<QueueEvent>>& queue,
1675 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1676
1/1
✓ Branch 1 taken 362 times.
362 std::vector<std::shared_ptr<QueueEvent>> levelEvents = loadLevelEvents(queue);
1677
1/1
✓ Branch 1 taken 362 times.
724 return groupLevelEvents(levelEvents, sLav);
1678 362 }
1679
1680 143 static std::shared_ptr<Vertex> getEdgeInLav(std::vector<std::shared_ptr<Vertex>>& lav, std::shared_ptr<Edge> oppositeEdge) {
1681
2/2
✓ Branch 6 taken 839 times.
✓ Branch 7 taken 70 times.
909 for (std::shared_ptr<Vertex> vertex : lav) {
1682
5/6
✓ Branch 2 taken 839 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 73 times.
✓ Branch 7 taken 766 times.
✓ Branch 8 taken 73 times.
✓ Branch 9 taken 766 times.
839 if (vertex->previousEdge && oppositeEdge == vertex->previousEdge) {
1683 73 return vertex;
1684 } else {
1685
1/1
✓ Branch 2 taken 766 times.
766 std::shared_ptr<Vertex> previous = Vertex::previous(vertex, lav);
1686
3/6
✓ Branch 2 taken 766 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 766 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 766 times.
766 if (previous->nextEdge && oppositeEdge == previous->nextEdge) {
1687 ✗ return vertex;
1688 }
1689 766 }
1690 839 }
1691 70 return nullptr;
1692 }
1693
1694 /// Test if point is inside polygon
1695 2 static bool isInsidePolygon(const Point3d& point, const std::vector<Point3d>& points) {
1696 /*
1697 * see http://en.wikipedia.org/wiki/Point_in_polygon
1698 * see http://en.wikipedia.org/wiki/Even-odd_rule
1699 * see http://paulbourke.net/geometry/insidepoly/
1700 */
1701
1702 2 int numpoints = points.size();
1703
1704
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
2 if (numpoints < 3) {
1705 ✗ return false;
1706 }
1707
1708 2 int it = 0;
1709
1710
1/1
✓ Branch 2 taken 2 times.
2 Point3d first = points[it];
1711
1712 2 bool oddNodes = false;
1713
1714
1/1
✓ Branch 1 taken 2 times.
2 Point3d node1;
1715
1/1
✓ Branch 1 taken 2 times.
2 Point3d node2;
1716
1717
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 2 times.
15 for (int i = 0; i < numpoints; i++) {
1718
1/1
✓ Branch 2 taken 13 times.
13 node1 = points[it];
1719 13 it++;
1720
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 11 times.
13 if (i == numpoints - 1) {
1721
1/1
✓ Branch 1 taken 2 times.
2 node2 = first;
1722 } else {
1723
1/1
✓ Branch 2 taken 11 times.
11 node2 = points[it];
1724 }
1725
1726
1/1
✓ Branch 1 taken 13 times.
13 const double y = point.y();
1727
14/14
✓ Branch 1 taken 13 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 7 times.
✓ Branch 6 taken 6 times.
✓ Branch 8 taken 5 times.
✓ Branch 9 taken 1 time.
✓ Branch 11 taken 12 times.
✓ Branch 13 taken 6 times.
✓ Branch 14 taken 6 times.
✓ Branch 16 taken 6 times.
✓ Branch 18 taken 1 time.
✓ Branch 19 taken 5 times.
✓ Branch 20 taken 2 times.
✓ Branch 21 taken 11 times.
13 if ((node1.y() < y && node2.y() >= y) || (node2.y() < y && node1.y() >= y)) {
1728
1/1
✓ Branch 1 taken 2 times.
2 const double x = point.x();
1729
8/8
✓ Branch 1 taken 2 times.
✓ Branch 4 taken 2 times.
✓ Branch 7 taken 2 times.
✓ Branch 10 taken 2 times.
✓ Branch 13 taken 2 times.
✓ Branch 16 taken 2 times.
✓ Branch 18 taken 1 time.
✓ Branch 19 taken 1 time.
2 if (node1.x() + (y - node1.y()) / (node2.y() - node1.y()) * (node2.x() - node1.x()) < x) {
1730 1 oddNodes = !oddNodes;
1731 }
1732 }
1733 }
1734
1735 2 return oddNodes;
1736 2 }
1737
1738 92 static int chooseOppositeEdgeLavIndex(const std::vector<std::shared_ptr<Vertex>>& edgeLavs, std::shared_ptr<Edge> oppositeEdge, const Point3d& center,
1739 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1740
2/2
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 72 times.
92 if (edgeLavs.empty()) {
1741 20 return -1;
1742
2/2
✓ Branch 1 taken 67 times.
✓ Branch 2 taken 5 times.
72 } else if (edgeLavs.size() == 1) {
1743 67 return 0;
1744 }
1745
1746 5 const Point3d& edgeStart = oppositeEdge->begin;
1747
1/1
✓ Branch 2 taken 5 times.
5 Vector3d edgeNorm = oppositeEdge->normalize();
1748
1/1
✓ Branch 1 taken 5 times.
5 Vector3d centerVector = center - edgeStart;
1749
1/1
✓ Branch 1 taken 5 times.
5 double centerDot = edgeNorm.dot(centerVector);
1750
1751
2/2
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 1 time.
8 for (unsigned i = 0; i < edgeLavs.size(); i++) {
1752 7 std::shared_ptr<Vertex> end = edgeLavs[i];
1753
1/1
✓ Branch 2 taken 7 times.
7 std::shared_ptr<Vertex> begin = Vertex::previous(end, sLav);
1754
1/1
✓ Branch 2 taken 7 times.
7 Vector3d beginVector = begin->point - edgeStart;
1755
1/1
✓ Branch 2 taken 7 times.
7 Vector3d endVector = end->point - edgeStart;
1756
1757
1/1
✓ Branch 1 taken 7 times.
7 double beginDot = edgeNorm.dot(beginVector);
1758
1/1
✓ Branch 1 taken 7 times.
7 double endDot = edgeNorm.dot(endVector);
1759
1760 /*
1761 * Make projection of center, begin and end into edge. Begin and end
1762 * are vertices chosen by opposite edge (then point to opposite edge).
1763 * Chose lav only when center is between begin and end. Only one lav
1764 * should meet criteria.
1765 */
1766
1767
8/8
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 4 times.
✓ Branch 5 taken 1 time.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 2 times.
7 if ((beginDot < centerDot && centerDot < endDot) || (beginDot > centerDot && centerDot > endDot)) {
1768 4 return i;
1769 }
1770 19 }
1771
1772 // Additional check if center is inside lav
1773
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
2 for (unsigned i = 0; i < edgeLavs.size(); i++) {
1774 2 std::shared_ptr<Vertex> end = edgeLavs[i];
1775
1/1
✓ Branch 2 taken 2 times.
2 int index = Vertex::getLavIndex(end, sLav);
1776 2 unsigned size = sLav[index].size();
1777 2 std::vector<Point3d> points;
1778 2 std::shared_ptr<Vertex> next = end;
1779
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 2 times.
15 for (unsigned j = 0; j < size; j++) {
1780
1/1
✓ Branch 2 taken 13 times.
13 points.push_back(next->point);
1781
1/1
✓ Branch 3 taken 13 times.
13 next = Vertex::next(next, sLav[index]);
1782 }
1783
3/3
✓ Branch 1 taken 2 times.
✓ Branch 3 taken 1 time.
✓ Branch 4 taken 1 time.
2 if (isInsidePolygon(center, points)) {
1784 1 return i;
1785 }
1786 4 }
1787
1788 ✗ LOG_AND_THROW("could not find lav for opposite edge, it could be correct but need some test data to check.")
1789 5 }
1790
1791 90 static std::shared_ptr<Vertex> findOppositeEdgeLav(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav, std::shared_ptr<Edge> oppositeEdge,
1792 const Point3d& center) {
1793 90 std::vector<std::shared_ptr<Vertex>> edgeLavs;
1794
2/2
✓ Branch 5 taken 143 times.
✓ Branch 6 taken 90 times.
233 for (std::vector<std::shared_ptr<Vertex>>& lav : sLav) {
1795
1/1
✓ Branch 2 taken 143 times.
143 std::shared_ptr<Vertex> vertexInLav = getEdgeInLav(lav, oppositeEdge);
1796
2/2
✓ Branch 1 taken 73 times.
✓ Branch 2 taken 70 times.
143 if (vertexInLav) {
1797
1/1
✓ Branch 1 taken 73 times.
73 edgeLavs.push_back(vertexInLav);
1798 }
1799 143 }
1800
1/1
✓ Branch 2 taken 90 times.
90 int lavIndex = chooseOppositeEdgeLavIndex(edgeLavs, oppositeEdge, center, sLav);
1801
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 20 times.
90 if (lavIndex > -1) {
1802 70 return edgeLavs[lavIndex];
1803 }
1804 20 return nullptr;
1805 90 }
1806
1807 85 static void createOppositeEdgeChains(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav, std::vector<Chain>& chains, Point3d& center) {
1808 /*
1809 * Add chain created from opposite edge, this chain have to be
1810 * calculated during processing event because lav could change during
1811 * processing another events on the same level
1812 */
1813 85 std::vector<std::shared_ptr<Edge>> oppositeEdges;
1814
1815 85 std::vector<Chain> oppositeEdgeChains;
1816 85 std::vector<Chain> chainsForRemoval;
1817
1818
2/2
✓ Branch 5 taken 93 times.
✓ Branch 6 taken 85 times.
178 for (const Chain& chain : chains) {
1819 // add opposite edges as chain parts
1820
1/2
✓ Branch 0 taken 93 times.
✗ Branch 1 not taken.
93 if (chain.chainType == Chain::TYPE_SPLIT) {
1821 93 std::shared_ptr<Edge> oppositeEdge = chain.getOppositeEdge();
1822
1823 93 bool hasOppositeEdge = false;
1824
2/2
✓ Branch 1 taken 81 times.
✓ Branch 2 taken 12 times.
93 if (oppositeEdge) {
1825
1/1
✓ Branch 4 taken 81 times.
81 hasOppositeEdge = std::find(oppositeEdges.begin(), oppositeEdges.end(), oppositeEdge) != oppositeEdges.end();
1826 }
1827
6/6
✓ Branch 1 taken 81 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 80 times.
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 80 times.
✓ Branch 6 taken 13 times.
93 if (oppositeEdge && !hasOppositeEdge) {
1828 // find lav vertex for opposite edge
1829
1830
1/1
✓ Branch 1 taken 80 times.
80 Point3d c = Point3d(center);
1831
1/1
✓ Branch 2 taken 80 times.
80 std::shared_ptr<Vertex> nextVertex = findOppositeEdgeLav(sLav, oppositeEdge, c);
1832
2/2
✓ Branch 1 taken 70 times.
✓ Branch 2 taken 10 times.
80 if (nextVertex) {
1833
2/2
✓ Branch 3 taken 70 times.
✓ Branch 6 taken 70 times.
70 oppositeEdgeChains.push_back(Chain(oppositeEdge, nextVertex, sLav)); // SingleEdgeChain
1834 } else {
1835
1/1
✓ Branch 2 taken 10 times.
10 findOppositeEdgeLav(sLav, oppositeEdge, center);
1836
1/1
✓ Branch 1 taken 10 times.
10 chainsForRemoval.push_back(chain);
1837 }
1838
1/1
✓ Branch 1 taken 80 times.
80 oppositeEdges.push_back(oppositeEdge);
1839 80 }
1840
1841
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
93 } else if (chain.chainType == Chain::TYPE_EDGE) {
1842 ✗ if (chain.getChainMode() == Chain::MODE_SPLIT) {
1843 ✗ std::shared_ptr<Edge> oppositeEdge = chain.getOppositeEdge();
1844 ✗ if (oppositeEdge) {
1845 // never happen?
1846 // find lav vertex for opposite edge
1847 ✗ oppositeEdges.push_back(oppositeEdge);
1848 }
1849 ✗ }
1850 }
1851 }
1852
1853 /*
1854 * if opposite edge can't be found in active lavs then split chain with
1855 * that edge should be removed
1856 */
1857
2/2
✓ Branch 4 taken 10 times.
✓ Branch 5 taken 85 times.
95 for (Chain& chain : chainsForRemoval) {
1858
1/1
✓ Branch 3 taken 10 times.
10 auto it = std::find(chains.begin(), chains.end(), chain);
1859
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
10 if (it == chains.end()) {
1860 ✗ LOG_AND_THROW("Could not find chain for removal.");
1861 }
1862
1/1
✓ Branch 2 taken 10 times.
10 chains.erase(it);
1863 }
1864
1865
2/2
✓ Branch 5 taken 70 times.
✓ Branch 6 taken 85 times.
155 for (const Chain& chain : oppositeEdgeChains) {
1866
1/1
✓ Branch 1 taken 70 times.
70 chains.push_back(chain);
1867 }
1868 85 }
1869
1870 153 static std::shared_ptr<Vertex> createMultiSplitVertex(std::shared_ptr<Edge> nextEdge, std::shared_ptr<Edge> previousEdge, const Point3d& center,
1871 double distance) {
1872
3/5
✓ Branch 1 taken 153 times.
✓ Branch 6 taken 153 times.
✓ Branch 9 taken 153 times.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
153 std::shared_ptr<Ray2d> bisector(new Ray2d(calcBisector(center, previousEdge, nextEdge)));
1873
1874 // edges are mirrored for event
1875
3/5
✓ Branch 1 taken 153 times.
✓ Branch 7 taken 153 times.
✓ Branch 10 taken 153 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
153 std::shared_ptr<Vertex> vertex(new Vertex(center, distance, bisector, previousEdge, nextEdge));
1876 306 return vertex;
1877 153 }
1878
1879 153 static void correctBisectorDirection(std::shared_ptr<Ray2d> bisector, std::shared_ptr<Vertex> beginNextVertex,
1880 std::shared_ptr<Vertex> endPreviousVertex, std::shared_ptr<Edge> beginEdge, std::shared_ptr<Edge> endEdge) {
1881 /*
1882 * New bisector for vertex is created using connected edges. For
1883 * parallel edges numerical error may appear and direction of created
1884 * bisector is wrong. For parallel edges direction of edge need to be
1885 * corrected using location of vertex.
1886 */
1887
1888 153 std::shared_ptr<Edge> beginEdge2 = beginNextVertex->previousEdge;
1889 153 std::shared_ptr<Edge> endEdge2 = endPreviousVertex->nextEdge;
1890
1891
3/6
✓ Branch 1 taken 153 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 153 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 153 times.
153 if (beginEdge != beginEdge2 || endEdge != endEdge2) {
1892 ✗ LOG_AND_THROW("Unexpected situation");
1893 }
1894
1895 /*
1896 * Check if edges are parallel and in opposite direction to each other.
1897 */
1898
5/5
✓ Branch 2 taken 153 times.
✓ Branch 6 taken 153 times.
✓ Branch 9 taken 153 times.
✓ Branch 13 taken 75 times.
✓ Branch 14 taken 78 times.
153 if (beginEdge->normalize().dot(endEdge->normalize()) < -0.97) {
1899
1/1
✓ Branch 2 taken 75 times.
75 Point3d epvp = endPreviousVertex->point;
1900
1/1
✓ Branch 2 taken 75 times.
75 Point3d bp = bisector->point;
1901
1/1
✓ Branch 2 taken 75 times.
75 Point3d bnvp = beginNextVertex->point;
1902
9/9
✓ Branch 1 taken 75 times.
✓ Branch 4 taken 75 times.
✓ Branch 7 taken 75 times.
✓ Branch 10 taken 75 times.
✓ Branch 13 taken 75 times.
✓ Branch 16 taken 75 times.
✓ Branch 19 taken 75 times.
✓ Branch 22 taken 75 times.
✓ Branch 25 taken 75 times.
75 Vector3d n1 = Vector3d(bp.x(), bp.y(), bp.z()) - Vector3d(epvp.x(), epvp.y(), epvp.z());
1903
9/9
✓ Branch 1 taken 75 times.
✓ Branch 4 taken 75 times.
✓ Branch 7 taken 75 times.
✓ Branch 10 taken 75 times.
✓ Branch 13 taken 75 times.
✓ Branch 16 taken 75 times.
✓ Branch 19 taken 75 times.
✓ Branch 22 taken 75 times.
✓ Branch 25 taken 75 times.
75 Vector3d n2 = Vector3d(bnvp.x(), bnvp.y(), bnvp.z()) - Vector3d(bp.x(), bp.y(), bp.z());
1904
1/1
✓ Branch 1 taken 75 times.
75 n1.normalize();
1905
1/1
✓ Branch 1 taken 75 times.
75 n2.normalize();
1906
1/1
✓ Branch 1 taken 75 times.
75 Vector3d bisectorPrediction = calcVectorBisector(n1, n2);
1907
1908
3/3
✓ Branch 2 taken 75 times.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 69 times.
75 if (bisector->vector.dot(bisectorPrediction) < 0) {
1909 /*
1910 * Bisector is calculated in opposite direction to edges and
1911 * center.
1912 */
1913
1/1
✓ Branch 2 taken 6 times.
6 bisector->vector = bisector->vector.reverseVector();
1914 }
1915 75 }
1916 153 }
1917
1918 153 static bool areSameLav(const std::vector<std::shared_ptr<Vertex>>& lav1, const std::vector<std::shared_ptr<Vertex>>& lav2) {
1919
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 153 times.
153 if (lav1.size() != lav2.size()) {
1920 ✗ return false;
1921 }
1922
2/2
✓ Branch 1 taken 2126 times.
✓ Branch 2 taken 153 times.
2279 for (unsigned i = 0; i < lav1.size(); i++) {
1923
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 2126 times.
2126 if (lav1[i] != lav2[i]) {
1924 ✗ return false;
1925 }
1926 }
1927 153 return true;
1928 }
1929
1930 /// Add all vertex from "merged" lav into "base" lav. Vertex are added before
1931 /// base vertex. Merged vertex order is reversed.
1932 ✗ static void mergeBeforeBaseVertex(std::shared_ptr<Vertex> base, std::vector<std::shared_ptr<Vertex>>& baseList, std::shared_ptr<Vertex> merged,
1933 std::vector<std::shared_ptr<Vertex>>& mergedList) {
1934 ✗ int size = mergedList.size();
1935
1936 ✗ for (int i = 0; i < size; i++) {
1937 ✗ std::shared_ptr<Vertex> nextMerged = Vertex::next(merged, mergedList);
1938 ✗ auto it = std::find(baseList.begin(), baseList.end(), base);
1939 ✗ baseList.insert(it, nextMerged);
1940 ✗ }
1941
1942 ✗ mergedList.erase(mergedList.begin(), mergedList.end());
1943 ✗ }
1944
1945 352 static boost::optional<double> computeCloserEdgeEvent(std::shared_ptr<Vertex> vertex, std::vector<std::shared_ptr<QueueEvent>>& queue,
1946 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1947 /*
1948 * Calculate two new edge events for given vertex. Events are generated
1949 * using current, previous and next vertex in current lav. When two edge
1950 * events are generated distance from source is check. To queue is added
1951 * only closer event or both if they have the same distance.
1952 */
1953
1954
1/1
✓ Branch 2 taken 352 times.
352 std::shared_ptr<Vertex> nextVertex = Vertex::next(vertex, sLav);
1955
1/1
✓ Branch 2 taken 352 times.
352 std::shared_ptr<Vertex> previousVertex = Vertex::previous(vertex, sLav);
1956
1957 /*
1958 * We need to chose closer edge event. When two evens appear in epsilon
1959 * we take both. They will create single MultiEdgeEvent.
1960 */
1961
1962
1/1
✓ Branch 3 taken 352 times.
352 boost::optional<Point3d> point1 = computeIntersectionBisectors(vertex, nextVertex);
1963
1/1
✓ Branch 3 taken 352 times.
352 boost::optional<Point3d> point2 = computeIntersectionBisectors(previousVertex, vertex);
1964
1965
6/6
✓ Branch 1 taken 51 times.
✓ Branch 2 taken 301 times.
✓ Branch 4 taken 32 times.
✓ Branch 5 taken 19 times.
✓ Branch 6 taken 32 times.
✓ Branch 7 taken 320 times.
352 if (!point1 && !point2) {
1966 32 return boost::none;
1967 }
1968
1969 320 double distance1 = std::numeric_limits<double>::max();
1970 320 double distance2 = std::numeric_limits<double>::max();
1971
1972
2/2
✓ Branch 0 taken 301 times.
✓ Branch 1 taken 19 times.
320 if (point1) {
1973
2/2
✓ Branch 1 taken 301 times.
✓ Branch 5 taken 301 times.
301 distance1 = getDistanceSquared(vertex->point, point1.get());
1974 }
1975
2/2
✓ Branch 0 taken 311 times.
✓ Branch 1 taken 9 times.
320 if (point2) {
1976
2/2
✓ Branch 1 taken 311 times.
✓ Branch 5 taken 311 times.
311 distance2 = getDistanceSquared(vertex->point, point2.get());
1977 }
1978
1979
2/2
✓ Branch 0 taken 199 times.
✓ Branch 1 taken 121 times.
320 if (distance1 - EPSILON < distance2) {
1980
2/2
✓ Branch 3 taken 199 times.
✓ Branch 6 taken 199 times.
199 std::shared_ptr<QueueEvent> e(createEdgeEvent(point1.get(), vertex, nextVertex));
1981
1/1
✓ Branch 2 taken 199 times.
199 QueueEvent::insert_sorted(queue, e);
1982 199 }
1983
2/2
✓ Branch 0 taken 226 times.
✓ Branch 1 taken 94 times.
320 if (distance2 - EPSILON < distance1) {
1984
2/2
✓ Branch 3 taken 226 times.
✓ Branch 6 taken 226 times.
226 std::shared_ptr<QueueEvent> e(createEdgeEvent(point2.get(), previousVertex, vertex));
1985
1/1
✓ Branch 2 taken 226 times.
226 QueueEvent::insert_sorted(queue, e);
1986 226 }
1987
1988
2/2
✓ Branch 0 taken 135 times.
✓ Branch 1 taken 185 times.
320 if (distance1 < distance2) {
1989
1/1
✓ Branch 1 taken 135 times.
135 return distance1;
1990 }
1991
1/1
✓ Branch 1 taken 185 times.
185 return distance2;
1992 352 }
1993
1994 352 static void computeEvents(std::shared_ptr<Vertex> vertex, std::vector<std::shared_ptr<QueueEvent>>& queue,
1995 const std::vector<std::shared_ptr<Edge>>& edges, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
1996
1/1
✓ Branch 2 taken 352 times.
352 boost::optional<double> distanceSquared = computeCloserEdgeEvent(vertex, queue, sLav);
1997
1/1
✓ Branch 2 taken 352 times.
352 computeSplitEvents(vertex, edges, queue, distanceSquared);
1998 352 }
1999
2000 70 static std::shared_ptr<Vertex> createOppositeEdgeVertex(std::shared_ptr<Vertex> newVertex) {
2001 /*
2002 * When opposite edge is processed we need to create copy of vertex to
2003 * use in opposite face. When opposite edge chain occur vertex is shared
2004 * by additional output face.
2005 */
2006
2007 std::shared_ptr<Vertex> vertex(
2008
3/5
✓ Branch 1 taken 70 times.
✓ Branch 12 taken 70 times.
✓ Branch 15 taken 70 times.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
70 new Vertex(newVertex->point, newVertex->distance, newVertex->bisector, newVertex->previousEdge, newVertex->nextEdge));
2009
2010
2/4
✓ Branch 1 taken 70 times.
✓ Branch 5 taken 70 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
70 std::shared_ptr<Face> oppFace(new Face());
2011
2012 // create new empty node queue
2013
3/5
✓ Branch 1 taken 70 times.
✓ Branch 7 taken 70 times.
✓ Branch 10 taken 70 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
70 std::shared_ptr<FaceNode> fn(new FaceNode(vertex->point, vertex->distance, oppFace));
2014 70 vertex->leftFaceNode = fn;
2015 70 vertex->rightFaceNode = fn;
2016
2017 // add one node for queue to present opposite side of edge split event
2018
1/1
✓ Branch 2 taken 70 times.
70 oppFace->nodes.push_back(fn);
2019
2020 140 return vertex;
2021 70 }
2022
2023 282 static void addFaceLeft(std::shared_ptr<Vertex> newVertex, std::shared_ptr<Vertex> va, std::vector<std::shared_ptr<Face>>& /*faces*/) {
2024 282 std::shared_ptr<Face> face = va->leftFaceNode->face;
2025
3/5
✓ Branch 1 taken 282 times.
✓ Branch 7 taken 282 times.
✓ Branch 10 taken 282 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
282 std::shared_ptr<FaceNode> fn(new FaceNode(newVertex->point, newVertex->distance, face));
2026
1/1
✓ Branch 4 taken 282 times.
282 addPush(va->leftFaceNode, fn);
2027 282 newVertex->leftFaceNode = fn;
2028 282 }
2029
2030 282 static void addFaceRight(std::shared_ptr<Vertex> newVertex, std::shared_ptr<Vertex> vb, std::vector<std::shared_ptr<Face>>& /*faces*/) {
2031 282 std::shared_ptr<Face> face = vb->rightFaceNode->face;
2032
3/5
✓ Branch 1 taken 282 times.
✓ Branch 7 taken 282 times.
✓ Branch 10 taken 282 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
282 std::shared_ptr<FaceNode> fn(new FaceNode(newVertex->point, newVertex->distance, face));
2033
1/1
✓ Branch 4 taken 282 times.
282 addPush(vb->rightFaceNode, fn);
2034 282 newVertex->rightFaceNode = fn;
2035 282 }
2036
2037 153 static std::shared_ptr<FaceNode> addSplitFaces(std::shared_ptr<FaceNode> lastFaceNode, const Chain& chainBegin, const Chain& chainEnd,
2038 std::shared_ptr<Vertex> newVertex, std::vector<std::shared_ptr<Face>>& faces,
2039 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
2040
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 83 times.
153 if (chainBegin.chainType == Chain::TYPE_SINGLE_EDGE) {
2041 /*
2042 * When chain is generated by opposite edge we need to share face
2043 * between two chains. Number of that chains shares is always odd.
2044 */
2045 // TODO: Unread variable!
2046 // cppcheck-suppress unreadVariable
2047
1/1
✓ Branch 1 taken 70 times.
70 std::shared_ptr<Vertex> beginVertex = chainBegin.getNextVertex(sLav);
2048
2049 // right face
2050
2/2
✓ Branch 1 taken 43 times.
✓ Branch 2 taken 27 times.
70 if (lastFaceNode) {
2051 // face queue exist simply assign it to new node
2052 43 newVertex->rightFaceNode = lastFaceNode;
2053 43 lastFaceNode = nullptr;
2054 } else {
2055 /*
2056 * Vertex generated by opposite edge share three faces, but
2057 * vertex can store only left and right face. So we need to
2058 * create vertex clone to store additional back face.
2059 */
2060
1/1
✓ Branch 2 taken 27 times.
27 beginVertex = createOppositeEdgeVertex(newVertex);
2061
2062 /* same face in two vertex, original and in opposite edge clone */
2063 27 newVertex->rightFaceNode = beginVertex->rightFaceNode;
2064 27 lastFaceNode = beginVertex->leftFaceNode;
2065 }
2066
2067 70 } else {
2068 83 std::shared_ptr<Vertex> beginVertex = chainBegin.getCurrentVertex();
2069
2070 // right face
2071
1/1
✓ Branch 3 taken 83 times.
83 addFaceRight(newVertex, beginVertex, faces);
2072 83 }
2073
2074
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 83 times.
153 if (chainEnd.chainType == Chain::TYPE_SINGLE_EDGE) {
2075 // TODO: Unread variable!
2076 // cppcheck-suppress unreadVariable
2077
1/1
✓ Branch 1 taken 70 times.
70 std::shared_ptr<Vertex> endVertex = chainEnd.getPreviousVertex(sLav);
2078
2079 // left face
2080
2/2
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 43 times.
70 if (lastFaceNode) {
2081 // face queue exist simply assign it to new node
2082 27 newVertex->leftFaceNode = lastFaceNode;
2083 27 lastFaceNode = nullptr;
2084 } else {
2085 /*
2086 * Vertex generated by opposite edge share three faces, but
2087 * vertex can store only left and right face. So we need to
2088 * create vertex clone to store additional back face.
2089 */
2090
1/1
✓ Branch 2 taken 43 times.
43 endVertex = createOppositeEdgeVertex(newVertex);
2091
2092 /* same face in two vertex, original and in opposite edge clone */
2093 43 newVertex->leftFaceNode = endVertex->leftFaceNode;
2094 43 lastFaceNode = endVertex->leftFaceNode;
2095 }
2096
2097 70 } else {
2098 83 std::shared_ptr<Vertex> endVertex = chainEnd.getCurrentVertex();
2099
2100 // left face
2101
1/1
✓ Branch 3 taken 83 times.
83 addFaceLeft(newVertex, endVertex, faces);
2102 83 }
2103
2104 153 return lastFaceNode;
2105 }
2106
2107 // Returns cut portion of lav from startVertex to endVertex, including both
2108 155 static std::vector<std::shared_ptr<Vertex>> cutLavPart(std::vector<std::shared_ptr<Vertex>>& lav, std::shared_ptr<Vertex> startVertex,
2109 std::shared_ptr<Vertex> endVertex) {
2110 155 std::vector<std::shared_ptr<Vertex>> ret;
2111
2112 155 std::shared_ptr<Vertex> current = startVertex;
2113
1/1
✓ Branch 1 taken 155 times.
155 ret.push_back(current);
2114
2115
2/2
✓ Branch 1 taken 141 times.
✓ Branch 2 taken 14 times.
155 if (startVertex == endVertex) {
2116 14 return ret;
2117 }
2118
2119 while (true) {
2120
1/1
✓ Branch 2 taken 1056 times.
1056 current = Vertex::next(current, lav);
2121
1/1
✓ Branch 1 taken 1056 times.
1056 ret.push_back(current);
2122
2/2
✓ Branch 1 taken 141 times.
✓ Branch 2 taken 915 times.
1056 if (current == endVertex) {
2123 141 break;
2124 }
2125
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 915 times.
915 if (ret.size() > lav.size()) {
2126 ✗ LOG_AND_THROW("End vertex not found in start vertex lav.");
2127 }
2128 915 }
2129
2130
2/2
✓ Branch 4 taken 1197 times.
✓ Branch 5 taken 141 times.
1338 for (const std::shared_ptr<Vertex>& v : ret) {
2131
1/1
✓ Branch 2 taken 1197 times.
1197 Vertex::removeFromLav(v, lav);
2132 }
2133
2134 141 return ret;
2135 155 }
2136
2137 85 static void multiSplitEvent(LevelEvent& event, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav,
2138 std::vector<std::shared_ptr<QueueEvent>>& queue, const std::vector<std::shared_ptr<Edge>>& edges,
2139 std::vector<std::shared_ptr<Face>>& faces) {
2140
2141
1/1
✓ Branch 1 taken 85 times.
85 createOppositeEdgeChains(sLav, event.chains, event.point);
2142
2143 // sort list of chains clock wise
2144
3/3
✓ Branch 1 taken 85 times.
✓ Branch 4 taken 85 times.
✓ Branch 9 taken 85 times.
85 std::sort(event.chains.begin(), event.chains.end(), Chain::Comparer(event.point));
2145
2146 // face vertex for split event is shared between two chains
2147 85 std::shared_ptr<FaceNode> lastFaceNode;
2148
2149 // connect all edges into new bisectors and lavs
2150 85 int edgeListSize = event.chains.size();
2151
2/2
✓ Branch 0 taken 153 times.
✓ Branch 1 taken 85 times.
238 for (int i = 0; i < edgeListSize; i++) {
2152 153 Chain& chainBegin = event.chains[i];
2153 153 Chain& chainEnd = event.chains[(i + 1) % edgeListSize];
2154
2155
1/1
✓ Branch 1 taken 153 times.
153 Point3d p = Point3d(event.point);
2156
1/1
✓ Branch 3 taken 153 times.
153 std::shared_ptr<Vertex> newVertex(createMultiSplitVertex(chainBegin.getNextEdge(), chainEnd.getPreviousEdge(), p, event.distance));
2157
2158 // Split and merge lavs...
2159
1/1
✓ Branch 1 taken 153 times.
153 std::shared_ptr<Vertex> beginNextVertex = chainBegin.getNextVertex(sLav);
2160
1/1
✓ Branch 1 taken 153 times.
153 std::shared_ptr<Vertex> endPreviousVertex = chainEnd.getPreviousVertex(sLav);
2161
2162
1/1
✓ Branch 7 taken 153 times.
153 correctBisectorDirection(newVertex->bisector, beginNextVertex, endPreviousVertex, chainBegin.getNextEdge(), chainEnd.getPreviousEdge());
2163
2164
1/1
✓ Branch 2 taken 153 times.
153 std::vector<std::shared_ptr<Vertex>>& beginNextVertexLav = sLav[Vertex::getLavIndex(beginNextVertex, sLav)];
2165
1/1
✓ Branch 2 taken 153 times.
153 std::vector<std::shared_ptr<Vertex>>& endPreviousVertexLav = sLav[Vertex::getLavIndex(endPreviousVertex, sLav)];
2166
2167
1/2
✓ Branch 1 taken 153 times.
✗ Branch 2 not taken.
153 if (areSameLav(beginNextVertexLav, endPreviousVertexLav)) {
2168 /*
2169 * if vertices are in same lav we need to cut part of lav in the
2170 * middle of vertex and create new lav from that points
2171 */
2172
2173
1/1
✓ Branch 3 taken 153 times.
153 std::vector<std::shared_ptr<Vertex>> lavPart = cutLavPart(beginNextVertexLav, beginNextVertex, endPreviousVertex);
2174
2175 153 std::vector<std::shared_ptr<Vertex>> lav;
2176
1/1
✓ Branch 1 taken 153 times.
153 lav.push_back(newVertex);
2177
2/2
✓ Branch 5 taken 1208 times.
✓ Branch 6 taken 153 times.
1361 for (const std::shared_ptr<Vertex>& vertex : lavPart) {
2178
1/1
✓ Branch 1 taken 1208 times.
1208 lav.push_back(vertex);
2179 }
2180
1/1
✓ Branch 1 taken 153 times.
153 sLav.push_back(lav);
2181
2182 153 } else {
2183 /*
2184 * if vertices are in different lavs we need to merge them into
2185 * one.
2186 */
2187 ✗ mergeBeforeBaseVertex(beginNextVertex, beginNextVertexLav, endPreviousVertex, endPreviousVertexLav);
2188
2189 ✗ int lavIndex = Vertex::getLavIndex(endPreviousVertex, sLav);
2190 ✗ if (lavIndex == -1) {
2191 ✗ LOG_AND_THROW("Could not find vertex in sLav.")
2192 }
2193 ✗ auto it = std::find(sLav[lavIndex].begin(), sLav[lavIndex].end(), endPreviousVertex);
2194 ✗ sLav[lavIndex].insert(it + 1, newVertex);
2195 }
2196
2197
1/1
✓ Branch 2 taken 153 times.
153 computeEvents(newVertex, queue, edges, sLav);
2198
2199
1/1
✓ Branch 3 taken 153 times.
153 lastFaceNode = addSplitFaces(lastFaceNode, chainBegin, chainEnd, newVertex, faces, sLav);
2200 153 }
2201
2202 // remove all centers of events from lav
2203 85 edgeListSize = event.chains.size();
2204
2/2
✓ Branch 0 taken 153 times.
✓ Branch 1 taken 85 times.
238 for (int i = 0; i < edgeListSize; i++) {
2205 153 const Chain& chainBegin = event.chains[i];
2206 153 const Chain& chainEnd = event.chains[(i + 1) % edgeListSize];
2207
2208
2/2
✓ Branch 3 taken 83 times.
✓ Branch 4 taken 70 times.
153 if (chainBegin.getCurrentVertex()) {
2209 83 chainBegin.getCurrentVertex()->processed = true;
2210
1/1
✓ Branch 2 taken 83 times.
83 Vertex::removeFromLav(chainBegin.getCurrentVertex(), sLav);
2211 }
2212
2/2
✓ Branch 3 taken 83 times.
✓ Branch 4 taken 70 times.
153 if (chainEnd.getCurrentVertex()) {
2213 83 chainEnd.getCurrentVertex()->processed = true;
2214
1/1
✓ Branch 2 taken 83 times.
83 Vertex::removeFromLav(chainEnd.getCurrentVertex(), sLav);
2215 }
2216 }
2217 85 }
2218
2219 452 static void addFaceBack(std::shared_ptr<Vertex> newVertex, std::shared_ptr<Vertex> va, std::shared_ptr<Vertex> vb,
2220 std::vector<std::shared_ptr<Face>>& /*faces*/) {
2221 452 std::shared_ptr<Face> face = va->rightFaceNode->face;
2222
3/5
✓ Branch 1 taken 452 times.
✓ Branch 7 taken 452 times.
✓ Branch 10 taken 452 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
452 std::shared_ptr<FaceNode> fn(new FaceNode(newVertex->point, newVertex->distance, face));
2223
1/1
✓ Branch 4 taken 452 times.
452 addPush(va->rightFaceNode, fn);
2224
1/1
✓ Branch 4 taken 452 times.
452 connectFaces(fn, vb->leftFaceNode);
2225 452 }
2226
2227 280 static void addMultiBackFaces(const std::vector<std::shared_ptr<QueueEvent>>& edgeList, std::shared_ptr<Vertex> edgeVertex,
2228 std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav, std::vector<std::shared_ptr<QueueEvent>>& /*queue*/,
2229 std::vector<std::shared_ptr<Face>>& faces) {
2230
2/2
✓ Branch 4 taken 452 times.
✓ Branch 5 taken 280 times.
732 for (const std::shared_ptr<QueueEvent>& edgeEvent : edgeList) {
2231
2232 452 edgeEvent->previousVertex->processed = true;
2233
1/1
✓ Branch 3 taken 452 times.
452 Vertex::removeFromLav(edgeEvent->previousVertex, sLav);
2234
2235 452 edgeEvent->nextVertex->processed = true;
2236
1/1
✓ Branch 3 taken 452 times.
452 Vertex::removeFromLav(edgeEvent->nextVertex, sLav);
2237
2238
1/1
✓ Branch 6 taken 452 times.
452 addFaceBack(edgeVertex, edgeEvent->previousVertex, edgeEvent->nextVertex, faces);
2239 }
2240 280 }
2241
2242 81 static void pickEvent(const LevelEvent& event, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav,
2243 std::vector<std::shared_ptr<QueueEvent>>& queue, std::vector<std::shared_ptr<Edge>>& /*edges*/,
2244 std::vector<std::shared_ptr<Face>>& faces) {
2245 // lav will be removed so it is final vertex.
2246
3/5
✓ Branch 1 taken 81 times.
✓ Branch 7 taken 81 times.
✓ Branch 10 taken 81 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
81 std::shared_ptr<Vertex> pickVertex(new Vertex(event.point, event.distance, nullptr, nullptr, nullptr));
2247 81 pickVertex->processed = true;
2248
2249
1/1
✓ Branch 2 taken 81 times.
81 addMultiBackFaces(event.chain.edgeList, pickVertex, sLav, queue, faces);
2250 81 }
2251
2252 199 static void multiEdgeEvent(LevelEvent& event, std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav,
2253 std::vector<std::shared_ptr<QueueEvent>>& queue, const std::vector<std::shared_ptr<Edge>>& edges,
2254 std::vector<std::shared_ptr<Face>>& faces) {
2255
2256
1/1
✓ Branch 1 taken 199 times.
199 std::shared_ptr<Vertex> prevVertex = event.chain.getPreviousVertex(sLav);
2257
1/1
✓ Branch 1 taken 199 times.
199 std::shared_ptr<Vertex> nextVertex = event.chain.getNextVertex(sLav);
2258
2259 199 prevVertex->processed = true;
2260 199 nextVertex->processed = true;
2261
2262
3/5
✓ Branch 1 taken 199 times.
✓ Branch 8 taken 199 times.
✓ Branch 11 taken 199 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
199 std::shared_ptr<Ray2d> bisector(new Ray2d(calcBisector(event.point, prevVertex->previousEdge, nextVertex->nextEdge)));
2263
1/1
✓ Branch 1 taken 199 times.
199 Point3d p = Point3d(event.point);
2264
3/5
✓ Branch 1 taken 199 times.
✓ Branch 9 taken 199 times.
✓ Branch 12 taken 199 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
199 std::shared_ptr<Vertex> edgeVertex(new Vertex(p, event.distance, bisector, prevVertex->previousEdge, nextVertex->nextEdge));
2265
2266 // left face
2267
2/2
✓ Branch 1 taken 199 times.
✓ Branch 5 taken 199 times.
199 addFaceLeft(edgeVertex, event.chain.getPreviousVertex(sLav), faces);
2268
2269 // right face
2270
2/2
✓ Branch 1 taken 199 times.
✓ Branch 5 taken 199 times.
199 addFaceRight(edgeVertex, event.chain.getNextVertex(sLav), faces);
2271
2272
1/1
✓ Branch 2 taken 199 times.
199 int lavIndex = Vertex::getLavIndex(prevVertex, sLav);
2273
1/1
✓ Branch 5 taken 199 times.
199 auto it = std::find(sLav[lavIndex].begin(), sLav[lavIndex].end(), prevVertex);
2274 199 auto pos = std::distance(sLav[lavIndex].begin(), it);
2275
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 162 times.
199 if (pos == 0) {
2276
1/1
✓ Branch 2 taken 37 times.
37 sLav[lavIndex].push_back(edgeVertex);
2277 } else {
2278
1/1
✓ Branch 3 taken 162 times.
162 sLav[lavIndex].insert(it, edgeVertex);
2279 }
2280
2281 // back faces
2282
1/1
✓ Branch 2 taken 199 times.
199 addMultiBackFaces(event.chain.edgeList, edgeVertex, sLav, queue, faces);
2283
2284
1/1
✓ Branch 2 taken 199 times.
199 computeEvents(edgeVertex, queue, edges, sLav);
2285 199 }
2286
2287 362 static void processTwoNodeLavs(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav, std::vector<std::shared_ptr<QueueEvent>>& /*queue*/,
2288 std::vector<std::shared_ptr<Face>>& /*faces*/) {
2289
2/2
✓ Branch 5 taken 771 times.
✓ Branch 6 taken 362 times.
1133 for (std::vector<std::shared_ptr<Vertex>>& lav : sLav) {
2290
2/2
✓ Branch 1 taken 31 times.
✓ Branch 2 taken 740 times.
771 if (lav.size() == 2) {
2291 31 std::shared_ptr<Vertex> first = lav[0];
2292
1/1
✓ Branch 2 taken 31 times.
31 std::shared_ptr<Vertex> last = Vertex::next(first, lav);
2293
2294
1/1
✓ Branch 5 taken 31 times.
31 connectFaces(first->leftFaceNode, last->rightFaceNode);
2295
1/1
✓ Branch 5 taken 31 times.
31 connectFaces(first->rightFaceNode, last->leftFaceNode);
2296
2297 31 first->processed = true;
2298 31 last->processed = true;
2299
2300
1/1
✓ Branch 2 taken 31 times.
31 Vertex::removeFromLav(first, lav);
2301
1/1
✓ Branch 2 taken 31 times.
31 Vertex::removeFromLav(last, lav);
2302 31 }
2303 }
2304 362 }
2305
2306 362 static void removeEventsUnderHeight(std::vector<std::shared_ptr<QueueEvent>>& queue, double levelHeight) {
2307
2/2
✓ Branch 1 taken 442 times.
✓ Branch 2 taken 41 times.
483 while (!queue.empty()) {
2308
2/2
✓ Branch 2 taken 321 times.
✓ Branch 3 taken 121 times.
442 if (queue[0]->distance > levelHeight + EPSILON) {
2309 321 break;
2310 }
2311
1/1
✓ Branch 3 taken 121 times.
121 queue.erase(queue.begin());
2312 }
2313 362 }
2314
2315 362 static void removeEmptyLav(std::vector<std::vector<std::shared_ptr<Vertex>>>& sLav) {
2316
2/2
✓ Branch 1 taken 771 times.
✓ Branch 2 taken 362 times.
1133 for (unsigned i = 0; i < sLav.size(); i++) {
2317
2/2
✓ Branch 2 taken 176 times.
✓ Branch 3 taken 595 times.
771 if (sLav[i].empty()) {
2318
1/1
✓ Branch 4 taken 176 times.
176 sLav.erase(sLav.begin() + i);
2319 176 i--;
2320 }
2321 }
2322 362 }
2323
2324 44 [[maybe_unused]] static std::vector<std::vector<Point3d>> doStraightSkeleton(std::vector<Point3d>& polygon, double roofPitchDegrees) {
2325
2326 /* Straight skeleton algorithm implementation. Based on highly modified Petr
2327 * Felkel and Stepan Obdrzalek algorithm.
2328 * Translated from https://github.com/kendzi/kendzi-math
2329 */
2330
2331 44 std::vector<std::shared_ptr<QueueEvent>> queue;
2332 44 std::vector<std::shared_ptr<Face>> faces;
2333 44 std::vector<std::shared_ptr<Edge>> edges;
2334 44 std::vector<std::vector<std::shared_ptr<Vertex>>> sLav;
2335
2336
1/1
✓ Branch 1 taken 41 times.
44 double zcoord = initPolygon(polygon);
2337
1/1
✓ Branch 1 taken 41 times.
41 makeCounterClockwise(polygon);
2338
1/1
✓ Branch 1 taken 41 times.
41 initSlav(polygon, sLav, edges, faces);
2339
1/1
✓ Branch 1 taken 41 times.
41 initEvents(sLav, queue, edges);
2340
2341 41 int count = 0;
2342
2343
2/2
✓ Branch 1 taken 362 times.
✓ Branch 2 taken 41 times.
403 while (!queue.empty()) {
2344 // start processing skeleton level
2345
1/1
✓ Branch 1 taken 362 times.
362 count = assertMaxNumberOfIterations(count);
2346
2347
1/1
✓ Branch 3 taken 362 times.
362 std::sort(queue.begin(), queue.end(), QueueEvent::Comparer());
2348
2349 362 double levelHeight = queue[0]->distance;
2350
2351
1/1
✓ Branch 1 taken 362 times.
362 std::vector<LevelEvent> levelEvents = loadAndGroupLevelEvents(queue, sLav);
2352
2353
2/2
✓ Branch 5 taken 365 times.
✓ Branch 6 taken 362 times.
727 for (LevelEvent& event : levelEvents) {
2354
2355
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 365 times.
365 if (event.obsolete) {
2356 /*
2357 * Event is outdated some of parent vertex was processed
2358 * before
2359 */
2360 ✗ continue;
2361 }
2362
2363
2/2
✓ Branch 0 taken 85 times.
✓ Branch 1 taken 280 times.
365 if (event.eventType == LevelEvent::TYPE_MULTI_SPLIT) {
2364
1/1
✓ Branch 1 taken 85 times.
85 multiSplitEvent(event, sLav, queue, edges, faces);
2365 85 continue;
2366
2/2
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 199 times.
280 } else if (event.eventType == LevelEvent::TYPE_PICK) {
2367
1/1
✓ Branch 1 taken 81 times.
81 pickEvent(event, sLav, queue, edges, faces);
2368 81 continue;
2369
1/2
✓ Branch 0 taken 199 times.
✗ Branch 1 not taken.
199 } else if (event.eventType == LevelEvent::TYPE_MULTI_EDGE) {
2370
1/1
✓ Branch 1 taken 199 times.
199 multiEdgeEvent(event, sLav, queue, edges, faces);
2371 199 continue;
2372 } else {
2373 ✗ LOG_AND_THROW("Unexpected event type");
2374 }
2375 }
2376
2377
1/1
✓ Branch 1 taken 362 times.
362 processTwoNodeLavs(sLav, queue, faces);
2378
1/1
✓ Branch 1 taken 362 times.
362 removeEventsUnderHeight(queue, levelHeight);
2379
1/1
✓ Branch 1 taken 362 times.
362 removeEmptyLav(sLav);
2380 362 }
2381
2382
1/1
✓ Branch 1 taken 41 times.
82 return facesToPoint3d(faces, roofPitchDegrees, zcoord);
2383 53 }
2384
2385 18 static std::vector<Point3d> getGableTopAndBottomVertices(const std::vector<Point3d>& surface) {
2386 18 std::vector<Point3d> ret;
2387
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 12 times.
18 if (surface.size() != 3) {
2388 // gable must have 3 vertices
2389 6 return ret;
2390 }
2391
10/14
✓ Branch 2 taken 12 times.
✓ Branch 6 taken 12 times.
✓ Branch 8 taken 12 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 12 times.
✓ Branch 16 taken 12 times.
✓ Branch 18 taken 12 times.
✗ Branch 19 not taken.
✓ Branch 22 taken 12 times.
✓ Branch 26 taken 12 times.
✓ Branch 28 taken 12 times.
✗ Branch 29 not taken.
✓ Branch 30 taken 12 times.
✗ Branch 31 not taken.
12 if (surface[0].z() > surface[1].z() && surface[0].z() > surface[2].z() && surface[1].z() == surface[2].z()) {
2392
1/1
✓ Branch 2 taken 12 times.
12 ret.push_back(surface[0]); // top
2393
1/1
✓ Branch 2 taken 12 times.
12 ret.push_back(surface[1]); // bottom
2394
1/1
✓ Branch 2 taken 12 times.
12 ret.push_back(surface[2]); // bottom
2395 ✗ } else if (surface[1].z() > surface[0].z() && surface[1].z() > surface[2].z() && surface[0].z() == surface[2].z()) {
2396 ✗ ret.push_back(surface[1]); // top
2397 ✗ ret.push_back(surface[0]); // bottom
2398 ✗ ret.push_back(surface[2]); // bottom
2399 ✗ } else if (surface[2].z() > surface[0].z() && surface[2].z() > surface[1].z() && surface[0].z() == surface[1].z()) {
2400 ✗ ret.push_back(surface[2]); // top
2401 ✗ ret.push_back(surface[0]); // bottom
2402 ✗ ret.push_back(surface[1]); // bottom
2403 }
2404 12 return ret;
2405 ✗ }
2406
2407 7 static int getOppositeGableIndex(const std::vector<std::vector<Point3d>>& surfaces, const std::vector<unsigned>& connectedSurfaces,
2408 unsigned gableIndexNum) {
2409 // Obtain opposite gable index relative to gableIndexNum
2410
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 1 time.
7 if (connectedSurfaces.size() < 4) {
2411 // There must be at least 4 connected surfaces (including gableIndexNum) for
2412 // there to be an opposite gable.
2413 6 return -1;
2414 }
2415
1/1
✓ Branch 2 taken 1 time.
1 std::vector<Point3d> baseVertices = getGableTopAndBottomVertices(surfaces[gableIndexNum]);
2416
1/1
✓ Branch 3 taken 1 time.
1 Edge base1 = Edge(baseVertices[0], baseVertices[1]);
2417
1/1
✓ Branch 3 taken 1 time.
1 Edge base2 = Edge(baseVertices[0], baseVertices[2]);
2418
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
3 for (unsigned i = 0; i < connectedSurfaces.size(); i++) {
2419
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 2 times.
3 if (connectedSurfaces[i] == gableIndexNum) {
2420 1 continue;
2421 }
2422
1/1
✓ Branch 3 taken 2 times.
2 std::vector<Point3d> tryVertices = getGableTopAndBottomVertices(surfaces[connectedSurfaces[i]]);
2423
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
2 if (tryVertices.empty()) {
2424 ✗ continue;
2425 }
2426
1/1
✓ Branch 3 taken 2 times.
2 Edge try1 = Edge(tryVertices[0], tryVertices[1]);
2427
1/1
✓ Branch 3 taken 2 times.
2 Edge try2 = Edge(tryVertices[0], tryVertices[2]);
2428
11/14
✓ Branch 1 taken 2 times.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✓ Branch 13 taken 1 time.
✓ Branch 14 taken 1 time.
✓ Branch 16 taken 1 time.
✓ Branch 18 taken 1 time.
✗ Branch 19 not taken.
✓ Branch 20 taken 1 time.
✓ Branch 21 taken 1 time.
2 if (base1 != try1 && base1 != try2 && base2 != try1 && base2 != try2) {
2429 1 return i;
2430 }
2431 4 }
2432 ✗ return -1;
2433 1 }
2434
2435 3 static void applyGableLogicTriangles(std::vector<std::vector<Point3d>>& surfaces) {
2436 // For any roof surface that has 3 vertices, convert from an angled
2437 // surface to a gable surface.
2438
2439 3 std::set<int> processedSurfaces;
2440
2441
2/2
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 3 times.
23 for (unsigned i = 0; i < surfaces.size(); i++) {
2442
3/3
✓ Branch 4 taken 20 times.
✓ Branch 7 taken 7 times.
✓ Branch 8 taken 13 times.
20 if (std::find(processedSurfaces.begin(), processedSurfaces.end(), i) != processedSurfaces.end()) {
2443 13 continue; // already processed
2444 }
2445
2446 13 std::vector<Point3d>& gable = surfaces[i];
2447
1/1
✓ Branch 1 taken 13 times.
13 std::vector<Point3d> gableVertices = getGableTopAndBottomVertices(gable);
2448
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 7 times.
13 if (gableVertices.empty()) {
2449 6 continue;
2450 }
2451
2452
1/1
✓ Branch 1 taken 7 times.
7 processedSurfaces.insert(i);
2453
1/1
✓ Branch 2 taken 7 times.
7 Point3d gableTop = gableVertices[0];
2454
2455 7 std::vector<unsigned> connectedSurfaces;
2456
2/2
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 7 times.
67 for (unsigned j = 0; j < surfaces.size(); j++) {
2457
2/2
✓ Branch 6 taken 216 times.
✓ Branch 7 taken 60 times.
276 for (const Point3d& vertex : surfaces[j]) {
2458
3/3
✓ Branch 1 taken 216 times.
✓ Branch 3 taken 194 times.
✓ Branch 4 taken 22 times.
216 if (vertex != gableTop) {
2459 194 continue;
2460 }
2461
1/1
✓ Branch 1 taken 22 times.
22 connectedSurfaces.push_back(j);
2462
1/1
✓ Branch 1 taken 22 times.
22 processedSurfaces.insert(j); // will be processed below
2463 }
2464 }
2465
2466
1/1
✓ Branch 1 taken 7 times.
7 int oppositeGableIndex = getOppositeGableIndex(surfaces, connectedSurfaces, i);
2467
2468
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 6 times.
7 if (oppositeGableIndex != -1) {
2469 // Two gables opposite each other meet, we'll need to create a (arbitrary) ridge line.
2470
2471 /* ___________ ___________
2472 * |\ /| | | |
2473 * | \ / | | | |
2474 * | \ / | | | |
2475 * | / \ | => | | |
2476 * | / \ | | | |
2477 * |/_________\| |_____|_____|
2478 */
2479
2480 // Shift gable top vertex for opposite surfaces
2481 1 std::vector<Point3d> newVertices;
2482
2483
1/1
✓ Branch 2 taken 1 time.
2 std::vector<unsigned> gableSurfaceIndices = {i, connectedSurfaces[oppositeGableIndex]};
2484
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1 time.
3 for (unsigned j = 0; j < gableSurfaceIndices.size(); j++) {
2485 2 std::vector<Point3d>& surface = surfaces[gableSurfaceIndices[j]];
2486
2/2
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 2 times.
8 for (Point3d& vertex : surface) {
2487
3/3
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 2 times.
6 if (vertex != gableTop) {
2488 4 continue;
2489 }
2490
1/1
✓ Branch 1 taken 2 times.
2 std::vector<Point3d> surfVertices = getGableTopAndBottomVertices(surface);
2491 Point3d newVertex =
2492
6/6
✓ Branch 2 taken 2 times.
✓ Branch 6 taken 2 times.
✓ Branch 10 taken 2 times.
✓ Branch 14 taken 2 times.
✓ Branch 18 taken 2 times.
✓ Branch 21 taken 2 times.
2 Point3d((surfVertices[1].x() + surfVertices[2].x()) / 2.0, (surfVertices[1].y() + surfVertices[2].y()) / 2.0, surfVertices[0].z());
2493
1/1
✓ Branch 1 taken 2 times.
2 newVertices.push_back(newVertex);
2494
1/1
✓ Branch 1 taken 2 times.
2 vertex = newVertex;
2495 2 }
2496 }
2497
2498 // Split gable top vertex (create ridge) for other surfaces
2499
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 time.
5 for (unsigned j = 0; j < connectedSurfaces.size(); j++) {
2500
3/3
✓ Branch 5 taken 4 times.
✓ Branch 8 taken 2 times.
✓ Branch 9 taken 2 times.
4 if (std::find(gableSurfaceIndices.begin(), gableSurfaceIndices.end(), connectedSurfaces[j]) != gableSurfaceIndices.end()) {
2501 2 continue; // already processed these surfaces
2502 }
2503 2 std::vector<Point3d>& surface = surfaces[connectedSurfaces[j]];
2504 2 std::vector<Point3d> trySurface1;
2505 2 std::vector<Point3d> trySurface2;
2506 2 std::vector<Edge> tryEdges1;
2507 2 std::vector<Edge> tryEdges2;
2508
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 2 times.
8 for (unsigned k = 0; k < surface.size(); k++) {
2509
1/1
✓ Branch 2 taken 6 times.
6 Point3d vertex = surface[k];
2510
3/3
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 2 times.
6 if (vertex != gableTop) {
2511
1/1
✓ Branch 1 taken 4 times.
4 trySurface1.push_back(vertex);
2512
1/1
✓ Branch 1 taken 4 times.
4 trySurface2.push_back(vertex);
2513 4 continue;
2514 }
2515 2 int prevk = k - 1 + surface.size();
2516 2 int nextk = k + 1;
2517
1/1
✓ Branch 3 taken 2 times.
2 Point3d previousVertex = surface[prevk % surface.size()];
2518
1/1
✓ Branch 3 taken 2 times.
2 Point3d nextVertex = surface[nextk % surface.size()];
2519
2520
1/1
✓ Branch 2 taken 2 times.
2 trySurface1.push_back(newVertices[0]);
2521
1/1
✓ Branch 2 taken 2 times.
2 trySurface1.push_back(newVertices[1]);
2522
2/2
✓ Branch 2 taken 2 times.
✓ Branch 5 taken 2 times.
2 tryEdges1.push_back(Edge(newVertices[0], previousVertex));
2523
2/2
✓ Branch 2 taken 2 times.
✓ Branch 5 taken 2 times.
2 tryEdges1.push_back(Edge(newVertices[1], nextVertex));
2524
2525
1/1
✓ Branch 2 taken 2 times.
2 trySurface2.push_back(newVertices[1]);
2526
1/1
✓ Branch 2 taken 2 times.
2 trySurface2.push_back(newVertices[0]);
2527
2/2
✓ Branch 2 taken 2 times.
✓ Branch 5 taken 2 times.
2 tryEdges2.push_back(Edge(newVertices[1], previousVertex));
2528
2/2
✓ Branch 2 taken 2 times.
✓ Branch 5 taken 2 times.
2 tryEdges2.push_back(Edge(newVertices[0], nextVertex));
2529 6 }
2530
2531 // Correct surface will have no edge intersections
2532
1/1
✓ Branch 3 taken 2 times.
2 LineLinear2d l1a = LineLinear2d(tryEdges1[0].begin, tryEdges1[0].end);
2533
1/1
✓ Branch 3 taken 2 times.
2 LineLinear2d l1b = LineLinear2d(tryEdges1[1].begin, tryEdges1[1].end);
2534
1/1
✓ Branch 3 taken 2 times.
2 LineLinear2d l2a = LineLinear2d(tryEdges2[0].begin, tryEdges2[0].end);
2535
1/1
✓ Branch 3 taken 2 times.
2 LineLinear2d l2b = LineLinear2d(tryEdges2[1].begin, tryEdges2[1].end);
2536
2537
10/16
✓ Branch 1 taken 2 times.
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 1 time.
✓ Branch 7 taken 1 time.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
✓ Branch 12 taken 1 time.
✓ Branch 13 taken 1 time.
✓ Branch 15 taken 2 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 1 time.
✓ Branch 19 taken 1 time.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
4 if (l1a.collide(l1b) && !l2a.collide(l2b)) {
2538
1/1
✓ Branch 1 taken 1 time.
1 surface = trySurface2; // trySurface1 has self intersection
2539
7/16
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
✓ Branch 12 taken 1 time.
✗ Branch 13 not taken.
✓ Branch 15 taken 1 time.
✗ Branch 16 not taken.
✓ Branch 18 taken 1 time.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
2 } else if (l2a.collide(l2b) && !l1a.collide(l1b)) {
2540
1/1
✓ Branch 1 taken 1 time.
1 surface = trySurface1; // trySurface2 has self intersection
2541 } else {
2542 ✗ LOG_AND_THROW("Could not create gable ridge.");
2543 }
2544 2 }
2545
2546 1 } else {
2547
2548 // Shift gable top vertex for all connected surfaces.
2549
2550 /* ___________ ___________
2551 * |\ /| | | |
2552 * | \ / | | | |
2553 * | \ / | | | |
2554 * | | | | | |
2555 * | | | => | | |
2556 * | / \ | | | |
2557 * | / \ | | | |
2558 * |/_________\| |_____|_____|
2559 */
2560
2561 Point3d newVertex =
2562
6/6
✓ Branch 2 taken 6 times.
✓ Branch 6 taken 6 times.
✓ Branch 10 taken 6 times.
✓ Branch 14 taken 6 times.
✓ Branch 18 taken 6 times.
✓ Branch 21 taken 6 times.
6 Point3d((gableVertices[1].x() + gableVertices[2].x()) / 2.0, (gableVertices[1].y() + gableVertices[2].y()) / 2.0, gableVertices[0].z());
2563
2/2
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 6 times.
24 for (unsigned j = 0; j < connectedSurfaces.size(); j++) {
2564 18 std::vector<Point3d>& surface = surfaces[connectedSurfaces[j]];
2565
2/2
✓ Branch 5 taken 66 times.
✓ Branch 6 taken 18 times.
84 for (Point3d& vertex : surface) {
2566
3/3
✓ Branch 1 taken 66 times.
✓ Branch 3 taken 48 times.
✓ Branch 4 taken 18 times.
66 if (vertex != gableTop) {
2567 48 continue;
2568 }
2569
1/1
✓ Branch 1 taken 18 times.
18 vertex = newVertex;
2570 }
2571 }
2572 6 }
2573 13 }
2574 3 }
2575
2576 3 static void applyGableLogicRidgeTwoAnglesForward(const std::vector<std::vector<Point3d>>& surfaces) {
2577 // TODO
2578
2579 /* ___________ ___________
2580 * | | | | | |
2581 * | | | | | |
2582 * | | | | | |
2583 * | | | | | |
2584 * | / \ | => | | |
2585 * | / \ | | | |
2586 * | / | | | | |
2587 * | / /| | | | |
2588 * |/_____/ | | |_____|_____|
2589 * | | | | | |
2590 * |__|__| |__|__|
2591 */
2592 3 }
2593
2594 3 static void applyGableLogicRidgeTwoAnglesInside(const std::vector<std::vector<Point3d>>& surfaces) {
2595 // TODO
2596
2597 /* ___________ ___________
2598 * | | | | | |
2599 * | | | | | |
2600 * | | | | | |
2601 * | | | | | |
2602 * | / \ | => | | |
2603 * | / \ | | | |
2604 * | / \ | | | |
2605 * | / /|\ \ | | | |
2606 * |/___/ | \_\| |_____|_____|
2607 * | | | | | |
2608 * |_|_| |_|_|
2609 */
2610 3 }
2611
2612 3 static void applyGableLogicRidgeTwoAnglesBackward(const std::vector<std::vector<Point3d>>& surfaces) {
2613 // TODO
2614
2615 /* _______________________ _______________________
2616 * | /| | |
2617 * | / | | |
2618 * | / | | |
2619 * | / | | |
2620 * |------------------- | |-----------------------|
2621 * | \ | => | |
2622 * | \ | | |
2623 * | | | | |
2624 * | /| | | /|\ |
2625 * |__________________/ | | |__________________/ | \|
2626 * | | | | | |
2627 * | | | | | |
2628 * |__|__| |__|__|
2629 */
2630 3 }
2631
2632 3 static void applyGableLogicTwoRidgesTwoOppositeAngles(const std::vector<std::vector<Point3d>>& surfaces) {
2633 // TODO
2634
2635 /* _______________________ _______________________
2636 * | /| | |
2637 * | / | | |
2638 * | / | | |
2639 * | / | | |
2640 * |------------------- | |-----------------------|
2641 * | /| | => | /|\ |
2642 * | / | | | / | \ |
2643 * | / | | | / | \ |
2644 * | / | | | / | \|
2645 * |______________/ | | |_____________/ | |
2646 * | | | | | |
2647 * | | | | | |
2648 * |____|___| |____|____|
2649 */
2650 3 }
2651
2652 3 [[maybe_unused]] static void applyGables(std::vector<std::vector<Point3d>>& surfaces) {
2653 // Convert hip roof to gable roof
2654
2655 // Simple logic
2656 3 applyGableLogicTriangles(surfaces);
2657
2658 // Complex logic
2659 3 applyGableLogicRidgeTwoAnglesForward(surfaces);
2660 3 applyGableLogicRidgeTwoAnglesInside(surfaces);
2661 3 applyGableLogicRidgeTwoAnglesBackward(surfaces);
2662 3 applyGableLogicTwoRidgesTwoOppositeAngles(surfaces);
2663 3 }
2664
2665 struct Point3dComparer // needed to use std::map<Point3d, foo>
2666 {
2667 518 bool operator()(Point3d p1, Point3d p2) const {
2668
2/2
✓ Branch 2 taken 111 times.
✓ Branch 3 taken 407 times.
518 if (p1.x() < p2.x()) {
2669 111 return true;
2670
2/2
✓ Branch 2 taken 348 times.
✓ Branch 3 taken 59 times.
407 } else if (p1.x() == p2.x()) {
2671 348 return (p1.y() < p2.y());
2672 }
2673 59 return false;
2674 }
2675 };
2676
2677 6 static std::vector<Point3d> getShedLine(const std::vector<Point3d>& polygon, double directionDegrees) {
2678
1/1
✓ Branch 1 taken 6 times.
6 boost::optional<Point3d> centroid = getCentroid(polygon);
2679
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
6 if (!centroid) {
2680 ✗ LOG_AND_THROW("Could not obtain centroid for polygon.");
2681 }
2682
2683 // Get max distance of any polygon vertex from centroid
2684 6 double maxDistance = 0.0;
2685
2/2
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 6 times.
38 for (const Point3d& vertex : polygon) {
2686
2/2
✓ Branch 1 taken 32 times.
✓ Branch 4 taken 32 times.
32 double distance = getDistance(vertex, centroid.get());
2687
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 26 times.
32 if (distance > maxDistance) {
2688 6 maxDistance = distance;
2689 }
2690 }
2691 6 maxDistance *= 2.0; // add buffer
2692
2693 6 double angleStandard = 90 - directionDegrees;
2694
2695 // Construct line segment through centroid perpendicular to directionDegrees
2696
1/1
✓ Branch 1 taken 6 times.
6 double angleRad1 = degToRad(angleStandard - 90.0);
2697
1/1
✓ Branch 1 taken 6 times.
6 double angleRad2 = degToRad(angleStandard + 90.0);
2698
5/5
✓ 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.
6 Point3d start = Point3d(centroid.get().x() + maxDistance * cos(angleRad1), centroid.get().y() + maxDistance * sin(angleRad1), 0.0);
2699
5/5
✓ 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.
6 Point3d end = Point3d(centroid.get().x() + maxDistance * cos(angleRad2), centroid.get().y() + maxDistance * sin(angleRad2), 0.0);
2700
2701 // Shift line segment in opposite direction of directionDegrees
2702
4/4
✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
✓ Branch 7 taken 6 times.
✓ Branch 10 taken 6 times.
6 double angle = atan2(end.x() - start.x(), end.y() - start.y());
2703 6 double dx = -maxDistance * cos(angle);
2704 6 double dy = maxDistance * sin(angle);
2705
2/2
✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
6 start += Vector3d(dx, dy, 0.0);
2706
2/2
✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
6 end += Vector3d(dx, dy, 0.0);
2707
2708
3/5
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 6 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
24 std::vector<Point3d> line = {start, end};
2709 12 return line;
2710 12 }
2711
2712 6 [[maybe_unused]] static std::vector<std::vector<Point3d>> doShedRoof(std::vector<Point3d>& polygon, double roofPitchDegrees,
2713 double directionDegrees) {
2714 6 std::vector<std::vector<Point3d>> surfaces;
2715
2716
1/1
✓ Branch 1 taken 6 times.
6 double zcoord = initPolygon(polygon);
2717
2718 // Define arbitrary line outside of the polygon based on directionDegrees. The
2719 // closest point to the line defines the start (height = 0) of the shed roof.
2720
1/1
✓ Branch 1 taken 6 times.
6 std::vector<Point3d> line = getShedLine(polygon, directionDegrees);
2721
2722 // Calculate distance from each polygon vertex to the line.
2723 6 std::map<Point3d, double, Point3dComparer> distances;
2724 6 double minDistance = std::numeric_limits<double>::max();
2725
2/2
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 6 times.
38 for (const Point3d& vertex : polygon) {
2726
2/2
✓ Branch 1 taken 32 times.
✓ Branch 4 taken 32 times.
32 distances[vertex] = getDistancePointToLineSegment(vertex, line);
2727
3/3
✓ Branch 1 taken 32 times.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 20 times.
32 if (distances[vertex] < minDistance) {
2728
1/1
✓ Branch 1 taken 12 times.
12 minDistance = distances[vertex];
2729 }
2730 }
2731
2732 // Reduce all vertex distances by minimum vertex distance. Combined with
2733 // roofPitchDegrees, this defines the height of the shed roof vertex.
2734
1/1
✓ Branch 1 taken 6 times.
6 double roofSlope = tan(degToRad(roofPitchDegrees));
2735
2/2
✓ Branch 4 taken 32 times.
✓ Branch 5 taken 6 times.
38 for (const auto& element : distances) {
2736
1/1
✓ Branch 1 taken 32 times.
32 distances[element.first] = element.second - minDistance;
2737 }
2738
2/2
✓ Branch 4 taken 32 times.
✓ Branch 5 taken 6 times.
38 for (Point3d& vertex : polygon) {
2739
3/3
✓ Branch 1 taken 32 times.
✓ Branch 4 taken 32 times.
✓ Branch 7 taken 32 times.
32 vertex += Vector3d(0.0, 0.0, zcoord + distances[vertex] * roofSlope);
2740 }
2741
2742 // Construct vertical walls for each polygon edge up to the shed roof.
2743
2/2
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 6 times.
38 for (unsigned i = 0; i < polygon.size(); i++) {
2744
1/1
✓ Branch 2 taken 32 times.
32 Point3d vertex = polygon[i];
2745
1/1
✓ Branch 3 taken 32 times.
32 Point3d nextVertex = polygon[(i + 1) % polygon.size()];
2746
3/5
✓ Branch 1 taken 32 times.
✓ Branch 3 taken 64 times.
✓ Branch 4 taken 32 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
128 std::vector<Point3d> wall = {vertex, nextVertex};
2747
3/3
✓ Branch 1 taken 32 times.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 13 times.
32 if (nextVertex.z() - zcoord > EPSILON) {
2748
3/3
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 19 times.
✓ Branch 7 taken 19 times.
19 Point3d nextVertexFloor = Point3d(nextVertex.x(), nextVertex.y(), zcoord);
2749
1/1
✓ Branch 1 taken 19 times.
19 wall.push_back(nextVertexFloor);
2750 19 }
2751
3/3
✓ Branch 1 taken 32 times.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 13 times.
32 if (vertex.z() - zcoord > EPSILON) {
2752
3/3
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 19 times.
✓ Branch 7 taken 19 times.
19 Point3d vertexFloor = Point3d(vertex.x(), vertex.y(), zcoord);
2753
1/1
✓ Branch 1 taken 19 times.
19 wall.push_back(vertexFloor);
2754 19 }
2755
2/2
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 6 times.
32 if (wall.size() > 2) {
2756
1/1
✓ Branch 1 taken 26 times.
26 surfaces.push_back(wall);
2757 }
2758 32 }
2759
2/2
✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
6 surfaces.push_back(reverse(polygon));
2760
2761 12 return surfaces;
2762 38 }
2763 } // namespace openstudio
2764