1 //Copyright (c) 2018 Ultimaker B.V. 2 //CuraEngine is released under the terms of the AGPLv3 or higher. 3 4 #ifndef UTILS_POLYGON_H 5 #define UTILS_POLYGON_H 6 7 #include <vector> 8 #include <assert.h> 9 #include <float.h> 10 #include <clipper.hpp> 11 12 #include <algorithm> // std::reverse, fill_n array 13 #include <cmath> // fabs 14 #include <limits> // int64_t.min 15 #include <list> 16 17 #include <initializer_list> 18 19 #include "IntPoint.h" 20 #include "../settings/types/AngleDegrees.h" //For angles between vertices. 21 22 #define CHECK_POLY_ACCESS 23 #ifdef CHECK_POLY_ACCESS 24 #define POLY_ASSERT(e) assert(e) 25 #else 26 #define POLY_ASSERT(e) do {} while(0) 27 #endif 28 29 namespace cura { 30 31 32 class PartsView; 33 class Polygons; 34 class Polygon; 35 class PolygonRef; 36 37 class ListPolyIt; 38 39 typedef std::list<Point> ListPolygon; //!< A polygon represented by a linked list instead of a vector 40 typedef std::vector<ListPolygon> ListPolygons; //!< Polygons represented by a vector of linked lists instead of a vector of vectors 41 42 const static int clipper_init = (0); 43 #define NO_INDEX (std::numeric_limits<unsigned int>::max()) 44 45 class ConstPolygonPointer; 46 47 /*! 48 * Outer polygons should be counter-clockwise, 49 * inner hole polygons should be clockwise. 50 * (When negative X is to the left and negative Y is downward.) 51 */ 52 class ConstPolygonRef 53 { 54 friend class Polygons; 55 friend class Polygon; 56 friend class PolygonRef; 57 friend class ConstPolygonPointer; 58 protected: 59 ClipperLib::Path* path; 60 public: ConstPolygonRef(const ClipperLib::Path & polygon)61 ConstPolygonRef(const ClipperLib::Path& polygon) 62 : path(const_cast<ClipperLib::Path*>(&polygon)) 63 {} 64 ~ConstPolygonRef()65 virtual ~ConstPolygonRef() 66 { 67 } 68 69 bool operator==(ConstPolygonRef& other) const =delete; // polygon comparison is expensive and probably not what you want when you use the equality operator 70 71 ConstPolygonRef& operator=(const ConstPolygonRef& other) =delete; // Cannot assign to a const object 72 73 /*! 74 * Gets the number of vertices in this polygon. 75 * \return The number of vertices in this polygon. 76 */ 77 size_t size() const; 78 79 /*! 80 * Returns whether there are any vertices in this polygon. 81 * \return ``true`` if the polygon has no vertices at all, or ``false`` if 82 * it does have vertices. 83 */ 84 bool empty() const; 85 86 const Point& operator[] (unsigned int index) const 87 { 88 POLY_ASSERT(index < size()); 89 return (*path)[index]; 90 } 91 92 const ClipperLib::Path& operator*() const 93 { 94 return *path; 95 } 96 begin()97 ClipperLib::Path::const_iterator begin() const 98 { 99 return path->begin(); 100 } 101 end()102 ClipperLib::Path::const_iterator end() const 103 { 104 return path->end(); 105 } 106 back()107 ClipperLib::Path::const_reference back() const 108 { 109 return path->back(); 110 } 111 data()112 const void* data() const 113 { 114 return path->data(); 115 } 116 117 118 /*! 119 * On Y-axis positive upward displays, Orientation will return true if the polygon's orientation is counter-clockwise. 120 * 121 * from http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Functions/Orientation.htm 122 */ orientation()123 bool orientation() const 124 { 125 return ClipperLib::Orientation(*path); 126 } 127 128 Polygons offset(int distance, ClipperLib::JoinType joinType = ClipperLib::jtMiter, double miter_limit = 1.2) const; 129 polygonLength()130 int64_t polygonLength() const 131 { 132 int64_t length = 0; 133 Point p0 = (*path)[path->size()-1]; 134 for(unsigned int n=0; n<path->size(); n++) 135 { 136 Point p1 = (*path)[n]; 137 length += vSize(p0 - p1); 138 p0 = p1; 139 } 140 return length; 141 } 142 143 bool shorterThan(const coord_t check_length) const; 144 min()145 Point min() const 146 { 147 Point ret = Point(POINT_MAX, POINT_MAX); 148 for(Point p : *path) 149 { 150 ret.X = std::min(ret.X, p.X); 151 ret.Y = std::min(ret.Y, p.Y); 152 } 153 return ret; 154 } 155 max()156 Point max() const 157 { 158 Point ret = Point(POINT_MIN, POINT_MIN); 159 for(Point p : *path) 160 { 161 ret.X = std::max(ret.X, p.X); 162 ret.Y = std::max(ret.Y, p.Y); 163 } 164 return ret; 165 } 166 area()167 double area() const 168 { 169 return ClipperLib::Area(*path); 170 } 171 centerOfMass()172 Point centerOfMass() const 173 { 174 double x = 0, y = 0; 175 Point p0 = (*path)[path->size()-1]; 176 for(unsigned int n=0; n<path->size(); n++) 177 { 178 Point p1 = (*path)[n]; 179 double second_factor = (p0.X * p1.Y) - (p1.X * p0.Y); 180 181 x += double(p0.X + p1.X) * second_factor; 182 y += double(p0.Y + p1.Y) * second_factor; 183 p0 = p1; 184 } 185 186 double area = Area(*path); 187 188 x = x / 6 / area; 189 y = y / 6 / area; 190 191 return Point(x, y); 192 } 193 closestPointTo(Point p)194 Point closestPointTo(Point p) const 195 { 196 Point ret = p; 197 float bestDist = FLT_MAX; 198 for(unsigned int n=0; n<path->size(); n++) 199 { 200 float dist = vSize2f(p - (*path)[n]); 201 if (dist < bestDist) 202 { 203 ret = (*path)[n]; 204 bestDist = dist; 205 } 206 } 207 return ret; 208 } 209 210 /*! 211 * Check if we are inside the polygon. We do this by tracing from the point towards the positive X direction, 212 * every line we cross increments the crossings counter. If we have an even number of crossings then we are not inside the polygon. 213 * Care needs to be taken, if p.Y exactly matches a vertex to the right of p, then we need to count 1 intersect if the 214 * outline passes vertically past; and 0 (or 2) intersections if that point on the outline is a 'top' or 'bottom' vertex. 215 * The easiest way to do this is to break out two cases for increasing and decreasing Y ( from p0 to p1 ). 216 * A segment is tested if pa.Y <= p.Y < pb.Y, where pa and pb are the points (from p0,p1) with smallest & largest Y. 217 * When both have the same Y, no intersections are counted but there is a special test to see if the point falls 218 * exactly on the line. 219 * 220 * Returns false if outside, true if inside; if the point lies exactly on the border, will return 'border_result'. 221 * 222 * \deprecated This function is no longer used, since the Clipper function is used by the function PolygonRef::inside(.) 223 * 224 * \param p The point for which to check if it is inside this polygon 225 * \param border_result What to return when the point is exactly on the border 226 * \return Whether the point \p p is inside this polygon (or \p border_result when it is on the border) 227 */ 228 bool _inside(Point p, bool border_result = false) const; 229 230 /*! 231 * Clipper function. 232 * Returns false if outside, true if inside; if the point lies exactly on the border, will return 'border_result'. 233 * 234 * http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Functions/PointInPolygon.htm 235 */ 236 bool inside(Point p, bool border_result = false) const 237 { 238 int res = ClipperLib::PointInPolygon(p, *path); 239 if (res == -1) 240 { 241 return border_result; 242 } 243 return res == 1; 244 } 245 246 /*! 247 * Smooth out small perpendicular segments and store the result in \p result. 248 * Smoothing is performed by removing the inner most vertex of a line segment smaller than \p remove_length 249 * which has an angle with the next and previous line segment smaller than roughly 150* 250 * 251 * Note that in its current implementation this function doesn't remove line segments with an angle smaller than 30* 252 * Such would be the case for an N shape. 253 * 254 * \param remove_length The length of the largest segment removed 255 * \param result (output) The result polygon, assumed to be empty 256 */ 257 void smooth(int remove_length, PolygonRef result) const; 258 259 /*! 260 * Smooth out sharp inner corners, by taking a shortcut which bypasses the corner 261 * 262 * \param angle The maximum angle of inner corners to be smoothed out 263 * \param shortcut_length The desired length of the shortcut line segment introduced (shorter shortcuts may be unavoidable) 264 * \param result The resulting polygon 265 */ 266 void smooth_outward(const AngleDegrees angle, int shortcut_length, PolygonRef result) const; 267 268 /*! 269 * Smooth out the polygon and store the result in \p result. 270 * Smoothing is performed by removing vertices for which both connected line segments are smaller than \p remove_length 271 * 272 * \param remove_length The length of the largest segment removed 273 * \param result (output) The result polygon, assumed to be empty 274 */ 275 void smooth2(int remove_length, PolygonRef result) const; 276 277 /*! 278 * Compute the morphological intersection between this polygon and another. 279 * 280 * Note that the result may consist of multiple polygons, if you have bad 281 * luck. 282 * 283 * \param other The polygon with which to intersect this polygon. 284 */ 285 Polygons intersection(const ConstPolygonRef& other) const; 286 287 288 private: 289 /*! 290 * Smooth out a simple corner consisting of two linesegments. 291 * 292 * Auxiliary function for \ref smooth_outward 293 * 294 * \param p0 The point before the corner 295 * \param p1 The corner 296 * \param p2 The point after the corner 297 * \param p0_it Iterator to the point before the corner 298 * \param p1_it Iterator to the corner 299 * \param p2_it Iterator to the point after the corner 300 * \param v10 Vector from \p p1 to \p p0 301 * \param v12 Vector from \p p1 to \p p2 302 * \param v02 Vector from \p p0 to \p p2 303 * \param shortcut_length The desired length ofthe shortcutting line 304 * \param cos_angle The cosine on the angle in L 012 305 */ 306 static void smooth_corner_simple(const Point p0, const Point p1, const Point p2, const ListPolyIt p0_it, const ListPolyIt p1_it, const ListPolyIt p2_it, const Point v10, const Point v12, const Point v02, const int64_t shortcut_length, float cos_angle); 307 308 /*! 309 * Smooth out a complex corner where the shortcut bypasses more than two line segments 310 * 311 * Auxiliary function for \ref smooth_outward 312 * 313 * \warning This function might try to remove the whole polygon 314 * Error code -1 means the whole polygon should be removed (which means it is a hole polygon) 315 * 316 * \param p1 The corner point 317 * \param[in,out] p0_it Iterator to the last point checked before \p p1 to consider cutting off 318 * \param[in,out] p2_it Iterator to the last point checked after \p p1 to consider cutting off 319 * \param shortcut_length The desired length ofthe shortcutting line 320 * \return Whether this whole polygon whould be removed by the smoothing 321 */ 322 static bool smooth_corner_complex(const Point p1, ListPolyIt& p0_it, ListPolyIt& p2_it, const int64_t shortcut_length); 323 324 /*! 325 * Try to take a step away from the corner point in order to take a bigger shortcut. 326 * 327 * Try to take the shortcut from a place as far away from the corner as the place we are taking the shortcut to. 328 * 329 * Auxiliary function for \ref smooth_outward 330 * 331 * \param[in] p1 The corner point 332 * \param[in] shortcut_length2 The square of the desired length ofthe shortcutting line 333 * \param[in,out] p0_it Iterator to the previously checked point somewhere beyond \p p1. Updated for the next iteration. 334 * \param[in,out] p2_it Iterator to the previously checked point somewhere before \p p1. Updated for the next iteration. 335 * \param[in,out] forward_is_blocked Whether trying another step forward is blocked by the smoothing outward condition. Updated for the next iteration. 336 * \param[in,out] backward_is_blocked Whether trying another step backward is blocked by the smoothing outward condition. Updated for the next iteration. 337 * \param[in,out] forward_is_too_far Whether trying another step forward is blocked by the shortcut length condition. Updated for the next iteration. 338 * \param[in,out] backward_is_too_far Whether trying another step backward is blocked by the shortcut length condition. Updated for the next iteration. 339 */ 340 static void smooth_outward_step(const Point p1, const int64_t shortcut_length2, ListPolyIt& p0_it, ListPolyIt& p2_it, bool& forward_is_blocked, bool& backward_is_blocked, bool& forward_is_too_far, bool& backward_is_too_far); 341 }; 342 343 344 class PolygonPointer; 345 346 class PolygonRef : public ConstPolygonRef 347 { 348 friend class PolygonPointer; 349 public: PolygonRef(ClipperLib::Path & polygon)350 PolygonRef(ClipperLib::Path& polygon) 351 : ConstPolygonRef(polygon) 352 {} 353 PolygonRef(const PolygonRef & other)354 PolygonRef(const PolygonRef& other) 355 : ConstPolygonRef(*other.path) 356 {} 357 ~PolygonRef()358 virtual ~PolygonRef() 359 { 360 } 361 reserve(size_t min_size)362 void reserve(size_t min_size) 363 { 364 path->reserve(min_size); 365 } 366 367 PolygonRef& operator=(const ConstPolygonRef& other) =delete; // polygon assignment is expensive and probably not what you want when you use the assignment operator 368 369 PolygonRef& operator=(ConstPolygonRef& other) =delete; // polygon assignment is expensive and probably not what you want when you use the assignment operator 370 // { path = other.path; return *this; } 371 372 PolygonRef& operator=(PolygonRef&& other) 373 { 374 *path = std::move(*other.path); 375 return *this; 376 } 377 378 Point& operator[] (unsigned int index) 379 { 380 POLY_ASSERT(index < size()); 381 return (*path)[index]; 382 } 383 begin()384 ClipperLib::Path::iterator begin() 385 { 386 return path->begin(); 387 } 388 end()389 ClipperLib::Path::iterator end() 390 { 391 return path->end(); 392 } 393 back()394 ClipperLib::Path::reference back() 395 { 396 return path->back(); 397 } 398 data()399 void* data() 400 { 401 return path->data(); 402 } 403 add(const Point p)404 void add(const Point p) 405 { 406 path->push_back(p); 407 } 408 409 ClipperLib::Path& operator*() 410 { 411 return *path; 412 } 413 414 template <typename... Args> emplace_back(Args &&...args)415 void emplace_back(Args&&... args) 416 { 417 path->emplace_back(args...); 418 } 419 remove(unsigned int index)420 void remove(unsigned int index) 421 { 422 POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max())); 423 path->erase(path->begin() + index); 424 } 425 clear()426 void clear() 427 { 428 path->clear(); 429 } 430 reverse()431 void reverse() 432 { 433 ClipperLib::ReversePath(*path); 434 } 435 436 /*! 437 * Translate the whole polygon in some direction. 438 * 439 * \param translation The direction in which to move the polygon 440 */ translate(Point translation)441 void translate(Point translation) 442 { 443 for (Point& p : *this) 444 { 445 p += translation; 446 } 447 } 448 449 /*! 450 * Removes consecutive line segments with same orientation and changes this polygon. 451 * 452 * Removes verts which are connected to line segments which are both too small. 453 * Removes verts which detour from a direct line from the previous and next vert by a too small amount. 454 * 455 * Criteria: 456 * 1. Never remove a vertex if either of the connceted segments is larger than \p smallest_line_segment 457 * 2. Never remove a vertex if the distance between that vertex and the final resulting polygon would be higher than \p allowed_error_distance 458 * 3. Simplify uses a heuristic and doesn't neccesarily remove all removable vertices under the above criteria. 459 * 4. But simplify may never violate these criteria. 460 * 5. Unless the segments or the distance is smaller than the rounding error of 5 micron 461 * 462 * \param smallest_line_segment_squared maximal squared length of removed line segments 463 * \param allowed_error_distance_squared The square of the distance of the middle point to the line segment of the consecutive and previous point for which the middle point is removed 464 */ 465 void simplify(const coord_t smallest_line_segment_squared = 100, const coord_t allowed_error_distance_squared = 25); 466 pop_back()467 void pop_back() 468 { 469 path->pop_back(); 470 } 471 472 /*! 473 * Apply a matrix to each vertex in this polygon 474 */ 475 void applyMatrix(const PointMatrix& matrix); 476 void applyMatrix(const Point3Matrix& matrix); 477 }; 478 479 class ConstPolygonPointer 480 { 481 protected: 482 const ClipperLib::Path* path; 483 public: ConstPolygonPointer()484 ConstPolygonPointer() 485 : path(nullptr) 486 {} ConstPolygonPointer(const ConstPolygonRef * ref)487 ConstPolygonPointer(const ConstPolygonRef* ref) 488 : path(ref->path) 489 {} ConstPolygonPointer(const ConstPolygonRef & ref)490 ConstPolygonPointer(const ConstPolygonRef& ref) 491 : path(ref.path) 492 {} 493 494 ConstPolygonRef operator*() const 495 { 496 assert(path); 497 return ConstPolygonRef(*path); 498 } 499 const ClipperLib::Path* operator->() const 500 { 501 assert(path); 502 return path; 503 } 504 505 operator bool() const 506 { 507 return path; 508 } 509 510 bool operator==(const ConstPolygonPointer& rhs) 511 { 512 return path == rhs.path; 513 } 514 }; 515 516 class PolygonPointer 517 { 518 protected: 519 ClipperLib::Path* path; 520 public: PolygonPointer()521 PolygonPointer() 522 : path(nullptr) 523 {} PolygonPointer(PolygonRef * ref)524 PolygonPointer(PolygonRef* ref) 525 : path(ref->path) 526 {} 527 PolygonPointer(PolygonRef & ref)528 PolygonPointer(PolygonRef& ref) 529 : path(ref.path) 530 {} 531 532 PolygonRef operator*() 533 { 534 assert(path); 535 return PolygonRef(*path); 536 } 537 ClipperLib::Path* operator->() 538 { 539 assert(path); 540 return path; 541 } 542 543 operator bool() const 544 { 545 return path; 546 } 547 }; 548 549 class Polygon : public PolygonRef 550 { 551 ClipperLib::Path poly; 552 public: Polygon()553 Polygon() 554 : PolygonRef(poly) 555 { 556 } 557 Polygon(const ConstPolygonRef & other)558 Polygon(const ConstPolygonRef& other) 559 : PolygonRef(poly) 560 , poly(*other.path) 561 { 562 } 563 Polygon(const Polygon & other)564 Polygon(const Polygon& other) 565 : PolygonRef(poly) 566 , poly(*other.path) 567 { 568 } 569 Polygon(Polygon && moved)570 Polygon(Polygon&& moved) 571 : PolygonRef(poly) 572 , poly(std::move(moved.poly)) 573 { 574 } 575 ~Polygon()576 virtual ~Polygon() 577 { 578 } 579 580 Polygon& operator=(const ConstPolygonRef& other) = delete; // copying a single polygon is generally not what you want 581 // { 582 // path = other.path; 583 // poly = *other.path; 584 // return *this; 585 // } 586 587 Polygon& operator=(Polygon&& other) //!< move assignment 588 { 589 poly = std::move(other.poly); 590 return *this; 591 } 592 }; 593 594 class PolygonsPart; 595 596 class Polygons 597 { 598 friend class Polygon; 599 friend class PolygonRef; 600 friend class ConstPolygonRef; 601 protected: 602 ClipperLib::Paths paths; 603 public: size()604 unsigned int size() const 605 { 606 return paths.size(); 607 } 608 609 /*! 610 * Convenience function to check if the polygon has no points. 611 * 612 * \return `true` if the polygon has no points, or `false` if it does. 613 */ 614 bool empty() const; 615 616 unsigned int pointCount() const; //!< Return the amount of points in all polygons 617 618 PolygonRef operator[] (unsigned int index) 619 { 620 POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max())); 621 return paths[index]; 622 } 623 ConstPolygonRef operator[] (unsigned int index) const 624 { 625 POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max())); 626 return paths[index]; 627 } begin()628 ClipperLib::Paths::iterator begin() 629 { 630 return paths.begin(); 631 } begin()632 ClipperLib::Paths::const_iterator begin() const 633 { 634 return paths.begin(); 635 } end()636 ClipperLib::Paths::iterator end() 637 { 638 return paths.end(); 639 } end()640 ClipperLib::Paths::const_iterator end() const 641 { 642 return paths.end(); 643 } 644 /*! 645 * Remove a polygon from the list and move the last polygon to its place 646 * 647 * \warning changes the order of the polygons! 648 */ remove(unsigned int index)649 void remove(unsigned int index) 650 { 651 POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max())); 652 if (index < paths.size() - 1) 653 { 654 paths[index] = std::move(paths.back()); 655 } 656 paths.resize(paths.size() - 1); 657 } 658 /*! 659 * Remove a range of polygons 660 */ erase(ClipperLib::Paths::iterator start,ClipperLib::Paths::iterator end)661 void erase(ClipperLib::Paths::iterator start, ClipperLib::Paths::iterator end) 662 { 663 paths.erase(start, end); 664 } clear()665 void clear() 666 { 667 paths.clear(); 668 } add(ConstPolygonRef & poly)669 void add(ConstPolygonRef& poly) 670 { 671 paths.push_back(*poly.path); 672 } add(const ConstPolygonRef & poly)673 void add(const ConstPolygonRef& poly) 674 { 675 paths.push_back(*poly.path); 676 } add(Polygon && other_poly)677 void add(Polygon&& other_poly) 678 { 679 paths.emplace_back(std::move(*other_poly)); 680 } add(const Polygons & other)681 void add(const Polygons& other) 682 { 683 std::copy(other.paths.begin(), other.paths.end(), std::back_inserter(paths)); 684 } 685 /*! 686 * Add a 'polygon' consisting of two points 687 */ addLine(const Point from,const Point to)688 void addLine(const Point from, const Point to) 689 { 690 paths.emplace_back(ClipperLib::Path{from, to}); 691 } 692 693 template<typename... Args> emplace_back(Args...args)694 void emplace_back(Args... args) 695 { 696 paths.emplace_back(args...); 697 } 698 newPoly()699 PolygonRef newPoly() 700 { 701 paths.emplace_back(); 702 return PolygonRef(paths.back()); 703 } back()704 PolygonRef back() 705 { 706 return PolygonRef(paths.back()); 707 } back()708 ConstPolygonRef back() const 709 { 710 return ConstPolygonRef(paths.back()); 711 } 712 Polygons()713 Polygons() {} 714 Polygons(const Polygons & other)715 Polygons(const Polygons& other) { paths = other.paths; } Polygons(Polygons && other)716 Polygons(Polygons&& other) { paths = std::move(other.paths); } 717 Polygons& operator=(const Polygons& other) { paths = other.paths; return *this; } 718 Polygons& operator=(Polygons&& other) { paths = std::move(other.paths); return *this; } 719 720 bool operator==(const Polygons& other) const =delete; 721 722 /*! 723 * Convert ClipperLib::PolyTree to a Polygons object, 724 * which uses ClipperLib::Paths instead of ClipperLib::PolyTree 725 */ 726 static Polygons toPolygons(ClipperLib::PolyTree& poly_tree); 727 difference(const Polygons & other)728 Polygons difference(const Polygons& other) const 729 { 730 Polygons ret; 731 ClipperLib::Clipper clipper(clipper_init); 732 clipper.AddPaths(paths, ClipperLib::ptSubject, true); 733 clipper.AddPaths(other.paths, ClipperLib::ptClip, true); 734 clipper.Execute(ClipperLib::ctDifference, ret.paths); 735 return ret; 736 } unionPolygons(const Polygons & other)737 Polygons unionPolygons(const Polygons& other) const 738 { 739 Polygons ret; 740 ClipperLib::Clipper clipper(clipper_init); 741 clipper.AddPaths(paths, ClipperLib::ptSubject, true); 742 clipper.AddPaths(other.paths, ClipperLib::ptSubject, true); 743 clipper.Execute(ClipperLib::ctUnion, ret.paths, ClipperLib::pftNonZero, ClipperLib::pftNonZero); 744 return ret; 745 } 746 /*! 747 * Union all polygons with each other (When polygons.add(polygon) has been called for overlapping polygons) 748 */ unionPolygons()749 Polygons unionPolygons() const 750 { 751 return unionPolygons(Polygons()); 752 } intersection(const Polygons & other)753 Polygons intersection(const Polygons& other) const 754 { 755 Polygons ret; 756 ClipperLib::Clipper clipper(clipper_init); 757 clipper.AddPaths(paths, ClipperLib::ptSubject, true); 758 clipper.AddPaths(other.paths, ClipperLib::ptClip, true); 759 clipper.Execute(ClipperLib::ctIntersection, ret.paths); 760 return ret; 761 } 762 763 /*! 764 * Intersect polylines with this area Polygons object. 765 */ 766 Polygons intersectionPolyLines(const Polygons& polylines) const; 767 768 /*! 769 * Clips input line segments by this Polygons. 770 * \param other Input line segments to be cropped 771 * \param segment_tree the resulting interior line segments 772 */ lineSegmentIntersection(const Polygons & other,ClipperLib::PolyTree & segment_tree)773 void lineSegmentIntersection(const Polygons& other, ClipperLib::PolyTree& segment_tree) const 774 { 775 ClipperLib::Clipper clipper(clipper_init); 776 clipper.AddPaths(paths, ClipperLib::ptClip, true); 777 clipper.AddPaths(other.paths, ClipperLib::ptSubject, false); 778 clipper.Execute(ClipperLib::ctIntersection, segment_tree); 779 } xorPolygons(const Polygons & other)780 Polygons xorPolygons(const Polygons& other) const 781 { 782 Polygons ret; 783 ClipperLib::Clipper clipper(clipper_init); 784 clipper.AddPaths(paths, ClipperLib::ptSubject, true); 785 clipper.AddPaths(other.paths, ClipperLib::ptClip, true); 786 clipper.Execute(ClipperLib::ctXor, ret.paths); 787 return ret; 788 } 789 790 Polygons offset(int distance, ClipperLib::JoinType joinType = ClipperLib::jtMiter, double miter_limit = 1.2) const; 791 792 Polygons offsetPolyLine(int distance, ClipperLib::JoinType joinType = ClipperLib::jtMiter) const 793 { 794 Polygons ret; 795 double miterLimit = 1.2; 796 ClipperLib::ClipperOffset clipper(miterLimit, 10.0); 797 clipper.AddPaths(paths, joinType, ClipperLib::etOpenSquare); 798 clipper.MiterLimit = miterLimit; 799 clipper.Execute(ret.paths, distance); 800 return ret; 801 } 802 803 /*! 804 * Check if we are inside the polygon. 805 * 806 * We do this by counting the number of polygons inside which this point lies. 807 * An odd number is inside, while an even number is outside. 808 * 809 * Returns false if outside, true if inside; if the point lies exactly on the border, will return \p border_result. 810 * 811 * \param p The point for which to check if it is inside this polygon 812 * \param border_result What to return when the point is exactly on the border 813 * \return Whether the point \p p is inside this polygon (or \p border_result when it is on the border) 814 */ 815 bool inside(Point p, bool border_result = false) const; 816 817 /*! 818 * Check if we are inside the polygon. We do this by tracing from the point towards the positive X direction, 819 * every line we cross increments the crossings counter. If we have an even number of crossings then we are not inside the polygon. 820 * Care needs to be taken, if p.Y exactly matches a vertex to the right of p, then we need to count 1 intersect if the 821 * outline passes vertically past; and 0 (or 2) intersections if that point on the outline is a 'top' or 'bottom' vertex. 822 * The easiest way to do this is to break out two cases for increasing and decreasing Y ( from p0 to p1 ). 823 * A segment is tested if pa.Y <= p.Y < pb.Y, where pa and pb are the points (from p0,p1) with smallest & largest Y. 824 * When both have the same Y, no intersections are counted but there is a special test to see if the point falls 825 * exactly on the line. 826 * 827 * Returns false if outside, true if inside; if the point lies exactly on the border, will return \p border_result. 828 * 829 * \deprecated This function is old and no longer used. instead use \ref Polygons::inside 830 * 831 * \param p The point for which to check if it is inside this polygon 832 * \param border_result What to return when the point is exactly on the border 833 * \return Whether the point \p p is inside this polygon (or \p border_result when it is on the border) 834 */ 835 bool insideOld(Point p, bool border_result = false) const; 836 837 /*! 838 * Find the polygon inside which point \p p resides. 839 * 840 * We do this by tracing from the point towards the positive X direction, 841 * every line we cross increments the crossings counter. If we have an even number of crossings then we are not inside the polygon. 842 * We then find the polygon with an uneven number of crossings which is closest to \p p. 843 * 844 * If \p border_result, we return the first polygon which is exactly on \p p. 845 * 846 * \param p The point for which to check in which polygon it is. 847 * \param border_result Whether a point exactly on a polygon counts as inside 848 * \return The index of the polygon inside which the point \p p resides 849 */ 850 unsigned int findInside(Point p, bool border_result = false); 851 852 /*! 853 * Approximates the convex hull of the polygons. 854 * \p extra_outset Extra offset outward 855 * \return the convex hull (approximately) 856 * 857 */ 858 Polygons approxConvexHull(int extra_outset = 0); 859 860 /*! 861 * Compute the area enclosed within the polygons (minus holes) 862 * 863 * \return The area in square micron 864 */ 865 double area() const; 866 867 /*! 868 * Smooth out small perpendicular segments 869 * Smoothing is performed by removing the inner most vertex of a line segment smaller than \p remove_length 870 * which has an angle with the next and previous line segment smaller than roughly 150* 871 * 872 * Note that in its current implementation this function doesn't remove line segments with an angle smaller than 30* 873 * Such would be the case for an N shape. 874 * 875 * \param remove_length The length of the largest segment removed 876 * \return The smoothed polygon 877 */ 878 Polygons smooth(int remove_length) const; 879 880 /*! 881 * Smooth out sharp inner corners, by taking a shortcut which bypasses the corner 882 * 883 * \param angle The maximum angle of inner corners to be smoothed out 884 * \param shortcut_length The desired length of the shortcut line segment introduced (shorter shortcuts may be unavoidable) 885 * \return The resulting polygons 886 */ 887 Polygons smooth_outward(const AngleDegrees angle, int shortcut_length); 888 889 Polygons smooth2(int remove_length, int min_area) const; //!< removes points connected to small lines 890 891 /*! 892 * Removes vertices of the polygons to make sure that they are not too high 893 * resolution. 894 * 895 * This removes points which are connected to line segments that are shorter 896 * than the `smallest_line_segment`, unless that would introduce a deviation 897 * in the contour of more than `allowed_error_distance`. 898 * 899 * Criteria: 900 * 1. Never remove a vertex if either of the connceted segments is larger than \p smallest_line_segment 901 * 2. Never remove a vertex if the distance between that vertex and the final resulting polygon would be higher than \p allowed_error_distance 902 * 3. Simplify uses a heuristic and doesn't neccesarily remove all removable vertices under the above criteria. 903 * 4. But simplify may never violate these criteria. 904 * 5. Unless the segments or the distance is smaller than the rounding error of 5 micron 905 * 906 * Vertices which introduce an error of less than 5 microns are removed 907 * anyway, even if the segments are longer than the smallest line segment. 908 * This makes sure that (practically) colinear line segments are joined into 909 * a single line segment. 910 * \param smallest_line_segment Maximal length of removed line segments. 911 * \param allowed_error_distance If removing a vertex introduces a deviation 912 * from the original path that is more than this distance, the vertex may 913 * not be removed. 914 */ 915 void simplify(const coord_t smallest_line_segment = 10, const coord_t allowed_error_distance = 5) 916 { 917 const coord_t allowed_error_distance_squared = allowed_error_distance * allowed_error_distance; 918 const coord_t smallest_line_segment_squared = smallest_line_segment * smallest_line_segment; 919 Polygons& thiss = *this; 920 for (size_t p = 0; p < size(); p++) 921 { 922 thiss[p].simplify(smallest_line_segment_squared, allowed_error_distance_squared); 923 if (thiss[p].size() < 3) 924 { 925 remove(p); 926 p--; 927 } 928 } 929 } 930 931 /*! 932 * Remove all but the polygons on the very outside. 933 * Exclude holes and parts within holes. 934 * \return the resulting polygons. 935 */ 936 Polygons getOutsidePolygons() const; 937 938 /*! 939 * Exclude holes which have no parts inside of them. 940 * \return the resulting polygons. 941 */ 942 Polygons removeEmptyHoles() const; 943 944 /*! 945 * Return hole polygons which have no parts inside of them. 946 * \return the resulting polygons. 947 */ 948 Polygons getEmptyHoles() const; 949 950 /*! 951 * Split up the polygons into groups according to the even-odd rule. 952 * Each PolygonsPart in the result has an outline as first polygon, whereas the rest are holes. 953 */ 954 std::vector<PolygonsPart> splitIntoParts(bool unionAll = false) const; 955 956 /*! 957 * Utility method for creating the tube (or 'donut') of a shape. 958 * \param inner_offset Offset relative to the original shape-outline towards the inside of the shape. Sort-of like a negative normal offset, except it's the offset part that's kept, not the shape. 959 * \param outer_offset Offset relative to the original shape-outline towards the outside of the shape. Comparable to normal offset. 960 * \return The resulting polygons. 961 */ 962 Polygons tubeShape(const coord_t inner_offset, const coord_t outer_offset) const; 963 964 private: 965 /*! 966 * recursive part of \ref Polygons::removeEmptyHoles and \ref Polygons::getEmptyHoles 967 * \param node The node of the polygons part to process 968 * \param remove_holes Whether to remove empty holes or everything but the empty holes 969 * \param ret Where to store polygons which are not empty holes 970 */ 971 void removeEmptyHoles_processPolyTreeNode(const ClipperLib::PolyNode& node, const bool remove_holes, Polygons& ret) const; 972 void splitIntoParts_processPolyTreeNode(ClipperLib::PolyNode* node, std::vector<PolygonsPart>& ret) const; 973 974 /*! 975 * Convert a node from a ClipperLib::PolyTree and add it to a Polygons object, 976 * which uses ClipperLib::Paths instead of ClipperLib::PolyTree 977 */ 978 void addPolyTreeNodeRecursive(const ClipperLib::PolyNode& node); 979 public: 980 /*! 981 * Split up the polygons into groups according to the even-odd rule. 982 * Each vector in the result has the index to an outline as first index, whereas the rest are indices to holes. 983 * 984 * \warning Note that this function reorders the polygons! 985 */ 986 PartsView splitIntoPartsView(bool unionAll = false); 987 private: 988 void splitIntoPartsView_processPolyTreeNode(PartsView& partsView, Polygons& reordered, ClipperLib::PolyNode* node) const; 989 public: 990 /*! 991 * Removes polygons with area smaller than \p min_area_size (note that min_area_size is in mm^2, not in micron^2). 992 * Unless \p remove_holes is true, holes are not removed even if their area is below \p min_area_size. 993 * However, holes that are contained within outlines whose area is below the threshold are removed though. 994 */ 995 void removeSmallAreas(const double min_area_size, const bool remove_holes = false); 996 997 /*! 998 * Removes overlapping consecutive line segments which don't delimit a positive area. 999 */ removeDegenerateVerts()1000 void removeDegenerateVerts() 1001 { 1002 Polygons& thiss = *this; 1003 for (unsigned int poly_idx = 0; poly_idx < size(); poly_idx++) 1004 { 1005 PolygonRef poly = thiss[poly_idx]; 1006 Polygon result; 1007 1008 auto isDegenerate = [](Point& last, Point& now, Point& next) 1009 { 1010 Point last_line = now - last; 1011 Point next_line = next - now; 1012 return dot(last_line, next_line) == -1 * vSize(last_line) * vSize(next_line); 1013 }; 1014 bool isChanged = false; 1015 for (unsigned int idx = 0; idx < poly.size(); idx++) 1016 { 1017 Point& last = (result.size() == 0) ? poly.back() : result.back(); 1018 if (idx+1 == poly.size() && result.size() == 0) { break; } 1019 Point& next = (idx+1 == poly.size())? result[0] : poly[idx+1]; 1020 if ( isDegenerate(last, poly[idx], next) ) 1021 { // lines are in the opposite direction 1022 // don't add vert to the result 1023 isChanged = true; 1024 while (result.size() > 1 && isDegenerate(result[result.size()-2], result.back(), next) ) 1025 { 1026 result.pop_back(); 1027 } 1028 } 1029 else 1030 { 1031 result.add(poly[idx]); 1032 } 1033 } 1034 1035 if (isChanged) 1036 { 1037 if (result.size() > 2) 1038 { 1039 *poly = *result; 1040 } 1041 else 1042 { 1043 thiss.remove(poly_idx); 1044 poly_idx--; // effectively the next iteration has the same poly_idx (referring to a new poly which is not yet processed) 1045 } 1046 } 1047 } 1048 } 1049 /*! 1050 * Removes the same polygons from this set (and also empty polygons). 1051 * Polygons are considered the same if all points lie within [same_distance] of their counterparts. 1052 */ 1053 Polygons remove(const Polygons& to_be_removed, int same_distance = 0) const 1054 { 1055 Polygons result; 1056 for (unsigned int poly_keep_idx = 0; poly_keep_idx < size(); poly_keep_idx++) 1057 { 1058 ConstPolygonRef poly_keep = (*this)[poly_keep_idx]; 1059 bool should_be_removed = false; 1060 if (poly_keep.size() > 0) 1061 // for (int hole_poly_idx = 0; hole_poly_idx < to_be_removed.size(); hole_poly_idx++) 1062 for (ConstPolygonRef poly_rem : to_be_removed) 1063 { 1064 // PolygonRef poly_rem = to_be_removed[hole_poly_idx]; 1065 if (poly_rem.size() != poly_keep.size() || poly_rem.size() == 0) continue; 1066 1067 // find closest point, supposing this point aligns the two shapes in the best way 1068 int closest_point_idx = 0; 1069 int smallestDist2 = -1; 1070 for (unsigned int point_rem_idx = 0; point_rem_idx < poly_rem.size(); point_rem_idx++) 1071 { 1072 int dist2 = vSize2(poly_rem[point_rem_idx] - poly_keep[0]); 1073 if (dist2 < smallestDist2 || smallestDist2 < 0) 1074 { 1075 smallestDist2 = dist2; 1076 closest_point_idx = point_rem_idx; 1077 } 1078 } 1079 bool poly_rem_is_poly_keep = true; 1080 // compare the two polygons on all points 1081 if (smallestDist2 > same_distance * same_distance) 1082 continue; 1083 for (unsigned int point_idx = 0; point_idx < poly_rem.size(); point_idx++) 1084 { 1085 int dist2 = vSize2(poly_rem[(closest_point_idx + point_idx) % poly_rem.size()] - poly_keep[point_idx]); 1086 if (dist2 > same_distance * same_distance) 1087 { 1088 poly_rem_is_poly_keep = false; 1089 break; 1090 } 1091 } 1092 if (poly_rem_is_poly_keep) 1093 { 1094 should_be_removed = true; 1095 break; 1096 } 1097 } 1098 if (!should_be_removed) 1099 result.add(poly_keep); 1100 1101 } 1102 return result; 1103 } 1104 processEvenOdd()1105 Polygons processEvenOdd() const 1106 { 1107 Polygons ret; 1108 ClipperLib::Clipper clipper(clipper_init); 1109 clipper.AddPaths(paths, ClipperLib::ptSubject, true); 1110 clipper.Execute(ClipperLib::ctUnion, ret.paths); 1111 return ret; 1112 } 1113 polygonLength()1114 coord_t polygonLength() const 1115 { 1116 coord_t length = 0; 1117 for(unsigned int i=0; i<paths.size(); i++) 1118 { 1119 Point p0 = paths[i][paths[i].size()-1]; 1120 for(unsigned int n=0; n<paths[i].size(); n++) 1121 { 1122 Point p1 = paths[i][n]; 1123 length += vSize(p0 - p1); 1124 p0 = p1; 1125 } 1126 } 1127 return length; 1128 } 1129 1130 coord_t polyLineLength() const; 1131 min()1132 Point min() const 1133 { 1134 Point ret = Point(POINT_MAX, POINT_MAX); 1135 for(const ClipperLib::Path& polygon : paths) 1136 { 1137 for(Point p : polygon) 1138 { 1139 ret.X = std::min(ret.X, p.X); 1140 ret.Y = std::min(ret.Y, p.Y); 1141 } 1142 } 1143 return ret; 1144 } 1145 max()1146 Point max() const 1147 { 1148 Point ret = Point(POINT_MIN, POINT_MIN); 1149 for(const ClipperLib::Path& polygon : paths) 1150 { 1151 for(Point p : polygon) 1152 { 1153 ret.X = std::max(ret.X, p.X); 1154 ret.Y = std::max(ret.Y, p.Y); 1155 } 1156 } 1157 return ret; 1158 } 1159 applyMatrix(const PointMatrix & matrix)1160 void applyMatrix(const PointMatrix& matrix) 1161 { 1162 for(unsigned int i=0; i<paths.size(); i++) 1163 { 1164 for(unsigned int j=0; j<paths[i].size(); j++) 1165 { 1166 paths[i][j] = matrix.apply(paths[i][j]); 1167 } 1168 } 1169 } 1170 }; 1171 1172 /*! 1173 * A single area with holes. The first polygon is the outline, while the rest are holes within this outline. 1174 * 1175 * This class has little more functionality than Polygons, but serves to show that a specific instance is ordered such that the first Polygon is the outline and the rest are holes. 1176 */ 1177 class PolygonsPart : public Polygons 1178 { 1179 public: outerPolygon()1180 PolygonRef outerPolygon() 1181 { 1182 return paths[0]; 1183 } outerPolygon()1184 ConstPolygonRef outerPolygon() const 1185 { 1186 return paths[0]; 1187 } 1188 1189 /*! 1190 * Tests whether the given point is inside this polygon part. 1191 * \param p The point to test whether it is inside. 1192 * \param border_result If the point is exactly on the border, this will be 1193 * returned instead. 1194 */ 1195 bool inside(Point p, bool border_result = false) const; 1196 }; 1197 1198 /*! 1199 * Extension of vector<vector<unsigned int>> which is similar to a vector of PolygonParts, except the base of the container is indices to polygons into the original Polygons, instead of the polygons themselves 1200 */ 1201 class PartsView : public std::vector<std::vector<unsigned int>> 1202 { 1203 public: 1204 Polygons& polygons; PartsView(Polygons & polygons)1205 PartsView(Polygons& polygons) : polygons(polygons) { } 1206 /*! 1207 * Get the index of the PolygonsPart of which the polygon with index \p poly_idx is part. 1208 * 1209 * \param poly_idx The index of the polygon in \p polygons 1210 * \param boundary_poly_idx Optional output parameter: The index of the boundary polygon of the part in \p polygons 1211 * \return The PolygonsPart containing the polygon with index \p poly_idx 1212 */ 1213 unsigned int getPartContaining(unsigned int poly_idx, unsigned int* boundary_poly_idx = nullptr) const; 1214 /*! 1215 * Assemble the PolygonsPart of which the polygon with index \p poly_idx is part. 1216 * 1217 * \param poly_idx The index of the polygon in \p polygons 1218 * \param boundary_poly_idx Optional output parameter: The index of the boundary polygon of the part in \p polygons 1219 * \return The PolygonsPart containing the polygon with index \p poly_idx 1220 */ 1221 PolygonsPart assemblePartContaining(unsigned int poly_idx, unsigned int* boundary_poly_idx = nullptr) const; 1222 /*! 1223 * Assemble the PolygonsPart of which the polygon with index \p poly_idx is part. 1224 * 1225 * \param part_idx The index of the part 1226 * \return The PolygonsPart with index \p poly_idx 1227 */ 1228 PolygonsPart assemblePart(unsigned int part_idx) const; 1229 }; 1230 1231 }//namespace cura 1232 1233 #endif//UTILS_POLYGON_H 1234