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 |