diff options
Diffstat (limited to 'thirdparty/clipper2/include')
8 files changed, 485 insertions, 238 deletions
diff --git a/thirdparty/clipper2/include/clipper2/clipper.core.h b/thirdparty/clipper2/include/clipper2/clipper.core.h index 0de7c3720e..0f69bf2d9f 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.core.h +++ b/thirdparty/clipper2/include/clipper2/clipper.core.h @@ -1,8 +1,8 @@ /******************************************************************************* * Author : Angus Johnson * -* Date : 24 November 2023 * +* Date : 12 May 2024 * * Website : http://www.angusj.com * -* Copyright : Angus Johnson 2010-2023 * +* Copyright : Angus Johnson 2010-2024 * * Purpose : Core Clipper Library structures and functions * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ @@ -19,6 +19,7 @@ #include <algorithm> #include <climits> #include <numeric> +#include <optional> #include "clipper2/clipper.version.h" #define CLIPPER2_THROW(exception) std::abort() @@ -51,19 +52,19 @@ namespace Clipper2Lib // error codes (2^n) const int precision_error_i = 1; // non-fatal - const int scale_error_i = 2; // non-fatal - const int non_pair_error_i = 4; // non-fatal - const int undefined_error_i = 32; // fatal + const int scale_error_i = 2; // non-fatal + const int non_pair_error_i = 4; // non-fatal + const int undefined_error_i = 32; // fatal const int range_error_i = 64; #ifndef PI static const double PI = 3.141592653589793238; #endif -#ifdef CLIPPER2_MAX_PRECISION - const int MAX_DECIMAL_PRECISION = CLIPPER2_MAX_PRECISION; +#ifdef CLIPPER2_MAX_DECIMAL_PRECISION + const int CLIPPER2_MAX_DEC_PRECISION = CLIPPER2_MAX_DECIMAL_PRECISION; #else - const int MAX_DECIMAL_PRECISION = 8; // see Discussions #564 + const int CLIPPER2_MAX_DEC_PRECISION = 8; // see Discussions #564 #endif static const int64_t MAX_COORD = INT64_MAX >> 2; @@ -74,7 +75,7 @@ namespace Clipper2Lib static const double MAX_DBL = (std::numeric_limits<double>::max)(); - static void DoError(int error_code) + static void DoError([[maybe_unused]] int error_code) { #if (defined(__cpp_exceptions) && __cpp_exceptions) || (defined(__EXCEPTIONS) && __EXCEPTIONS) switch (error_code) @@ -95,6 +96,13 @@ namespace Clipper2Lib #endif } + // can we call std::round on T? (default false) (#824) + template <typename T, typename = void> + struct is_round_invocable : std::false_type {}; + + template <typename T> + struct is_round_invocable<T, std::void_t<decltype(std::round(std::declval<T>()))>> : std::true_type {}; + //By far the most widely used filling rules for polygons are EvenOdd //and NonZero, sometimes called Alternate and Winding respectively. @@ -113,8 +121,8 @@ namespace Clipper2Lib template <typename T2> inline void Init(const T2 x_ = 0, const T2 y_ = 0, const int64_t z_ = 0) { - if constexpr (std::numeric_limits<T>::is_integer && - !std::numeric_limits<T2>::is_integer) + if constexpr (std::is_integral_v<T> && + is_round_invocable<T2>::value && !std::is_integral_v<T2>) { x = static_cast<T>(std::round(x_)); y = static_cast<T>(std::round(y_)); @@ -143,6 +151,12 @@ namespace Clipper2Lib Init(p.x, p.y, p.z); } + template <typename T2> + explicit Point(const Point<T2>& p, int64_t z_) + { + Init(p.x, p.y, z_); + } + Point operator * (const double scale) const { return Point(x * scale, y * scale, z); @@ -161,8 +175,8 @@ namespace Clipper2Lib template <typename T2> inline void Init(const T2 x_ = 0, const T2 y_ = 0) { - if constexpr (std::numeric_limits<T>::is_integer && - !std::numeric_limits<T2>::is_integer) + if constexpr (std::is_integral_v<T> && + is_round_invocable<T2>::value && !std::is_integral_v<T2>) { x = static_cast<T>(std::round(x_)); y = static_cast<T>(std::round(y_)); @@ -244,6 +258,14 @@ namespace Clipper2Lib (std::numeric_limits<double>::max)(), (std::numeric_limits<double>::max)()); + template<typename T> + static inline Point<T> MidPoint(const Point<T>& p1, const Point<T>& p2) + { + Point<T> result; + result.x = (p1.x + p2.x) / 2; + result.y = (p1.y + p2.y) / 2; + return result; + } // Rect ------------------------------------------------------------------------ @@ -275,10 +297,19 @@ namespace Clipper2Lib else { left = top = (std::numeric_limits<T>::max)(); - right = bottom = (std::numeric_limits<T>::lowest)(); + right = bottom = std::numeric_limits<T>::lowest(); } } + static Rect<T> InvalidRect() + { + return { + (std::numeric_limits<T>::max)(), + (std::numeric_limits<T>::max)(), + std::numeric_limits<T>::lowest(), + std::numeric_limits<T>::lowest() }; + } + bool IsValid() const { return left != (std::numeric_limits<T>::max)(); } T Width() const { return right - left; } @@ -329,7 +360,7 @@ namespace Clipper2Lib }; bool operator==(const Rect<T>& other) const { - return left == other.left && right == other.right && + return left == other.left && right == other.right && top == other.top && bottom == other.bottom; } @@ -344,8 +375,8 @@ namespace Clipper2Lib { Rect<T1> result; - if constexpr (std::numeric_limits<T1>::is_integer && - !std::numeric_limits<T2>::is_integer) + if constexpr (std::is_integral_v<T1> && + is_round_invocable<T2>::value && !std::is_integral_v<T2>) { result.left = static_cast<T1>(std::round(rect.left * scale)); result.top = static_cast<T1>(std::round(rect.top * scale)); @@ -354,32 +385,24 @@ namespace Clipper2Lib } else { - result.left = rect.left * scale; - result.top = rect.top * scale; - result.right = rect.right * scale; - result.bottom = rect.bottom * scale; + result.left = static_cast<T1>(rect.left * scale); + result.top = static_cast<T1>(rect.top * scale); + result.right = static_cast<T1>(rect.right * scale); + result.bottom = static_cast<T1>(rect.bottom * scale); } return result; } - static const Rect64 InvalidRect64 = Rect64( - (std::numeric_limits<int64_t>::max)(), - (std::numeric_limits<int64_t>::max)(), - (std::numeric_limits<int64_t>::lowest)(), - (std::numeric_limits<int64_t>::lowest)()); - static const RectD InvalidRectD = RectD( - (std::numeric_limits<double>::max)(), - (std::numeric_limits<double>::max)(), - (std::numeric_limits<double>::lowest)(), - (std::numeric_limits<double>::lowest)()); + static const Rect64 InvalidRect64 = Rect64::InvalidRect(); + static const RectD InvalidRectD = RectD::InvalidRect(); template <typename T> Rect<T> GetBounds(const Path<T>& path) { - auto xmin = (std::numeric_limits<T>::max)(); - auto ymin = (std::numeric_limits<T>::max)(); - auto xmax = std::numeric_limits<T>::lowest(); - auto ymax = std::numeric_limits<T>::lowest(); + T xmin = (std::numeric_limits<T>::max)(); + T ymin = (std::numeric_limits<T>::max)(); + T xmax = std::numeric_limits<T>::lowest(); + T ymax = std::numeric_limits<T>::lowest(); for (const auto& p : path) { if (p.x < xmin) xmin = p.x; @@ -393,17 +416,52 @@ namespace Clipper2Lib template <typename T> Rect<T> GetBounds(const Paths<T>& paths) { - auto xmin = (std::numeric_limits<T>::max)(); - auto ymin = (std::numeric_limits<T>::max)(); - auto xmax = std::numeric_limits<T>::lowest(); - auto ymax = std::numeric_limits<T>::lowest(); + T xmin = (std::numeric_limits<T>::max)(); + T ymin = (std::numeric_limits<T>::max)(); + T xmax = std::numeric_limits<T>::lowest(); + T ymax = std::numeric_limits<T>::lowest(); for (const Path<T>& path : paths) for (const Point<T>& p : path) { - if (p.x < xmin) xmin = p.x; - if (p.x > xmax) xmax = p.x; - if (p.y < ymin) ymin = p.y; - if (p.y > ymax) ymax = p.y; + if (p.x < xmin) xmin = p.x; + if (p.x > xmax) xmax = p.x; + if (p.y < ymin) ymin = p.y; + if (p.y > ymax) ymax = p.y; + } + return Rect<T>(xmin, ymin, xmax, ymax); + } + + template <typename T, typename T2> + Rect<T> GetBounds(const Path<T2>& path) + { + T xmin = (std::numeric_limits<T>::max)(); + T ymin = (std::numeric_limits<T>::max)(); + T xmax = std::numeric_limits<T>::lowest(); + T ymax = std::numeric_limits<T>::lowest(); + for (const auto& p : path) + { + if (p.x < xmin) xmin = static_cast<T>(p.x); + if (p.x > xmax) xmax = static_cast<T>(p.x); + if (p.y < ymin) ymin = static_cast<T>(p.y); + if (p.y > ymax) ymax = static_cast<T>(p.y); + } + return Rect<T>(xmin, ymin, xmax, ymax); + } + + template <typename T, typename T2> + Rect<T> GetBounds(const Paths<T2>& paths) + { + T xmin = (std::numeric_limits<T>::max)(); + T ymin = (std::numeric_limits<T>::max)(); + T xmax = std::numeric_limits<T>::lowest(); + T ymax = std::numeric_limits<T>::lowest(); + for (const Path<T2>& path : paths) + for (const Point<T2>& p : path) + { + if (p.x < xmin) xmin = static_cast<T>(p.x); + if (p.x > xmax) xmax = static_cast<T>(p.x); + if (p.y < ymin) ymin = static_cast<T>(p.y); + if (p.y > ymax) ymax = static_cast<T>(p.y); } return Rect<T>(xmin, ymin, xmax, ymax); } @@ -431,7 +489,7 @@ namespace Clipper2Lib template <typename T1, typename T2> - inline Path<T1> ScalePath(const Path<T2>& path, + inline Path<T1> ScalePath(const Path<T2>& path, double scale_x, double scale_y, int& error_code) { Path<T1> result; @@ -447,11 +505,11 @@ namespace Clipper2Lib result.reserve(path.size()); #ifdef USINGZ std::transform(path.begin(), path.end(), back_inserter(result), - [scale_x, scale_y](const auto& pt) + [scale_x, scale_y](const auto& pt) { return Point<T1>(pt.x * scale_x, pt.y * scale_y, pt.z); }); #else std::transform(path.begin(), path.end(), back_inserter(result), - [scale_x, scale_y](const auto& pt) + [scale_x, scale_y](const auto& pt) { return Point<T1>(pt.x * scale_x, pt.y * scale_y); }); #endif return result; @@ -465,20 +523,19 @@ namespace Clipper2Lib } template <typename T1, typename T2> - inline Paths<T1> ScalePaths(const Paths<T2>& paths, + inline Paths<T1> ScalePaths(const Paths<T2>& paths, double scale_x, double scale_y, int& error_code) { Paths<T1> result; - if constexpr (std::numeric_limits<T1>::is_integer && - !std::numeric_limits<T2>::is_integer) + if constexpr (std::is_integral_v<T1>) { - RectD r = GetBounds(paths); + RectD r = GetBounds<double, T2>(paths); if ((r.left * scale_x) < min_coord || (r.right * scale_x) > max_coord || (r.top * scale_y) < min_coord || (r.bottom * scale_y) > max_coord) - { + { error_code |= range_error_i; DoError(range_error_i); return result; // empty path @@ -493,7 +550,7 @@ namespace Clipper2Lib } template <typename T1, typename T2> - inline Paths<T1> ScalePaths(const Paths<T2>& paths, + inline Paths<T1> ScalePaths(const Paths<T2>& paths, double scale, int& error_code) { return ScalePaths<T1, T2>(paths, scale, scale, error_code); @@ -590,20 +647,94 @@ namespace Clipper2Lib // Miscellaneous ------------------------------------------------------------ - inline void CheckPrecision(int& precision, int& error_code) + inline void CheckPrecisionRange(int& precision, int& error_code) { - if (precision >= -MAX_DECIMAL_PRECISION && precision <= MAX_DECIMAL_PRECISION) return; + if (precision >= -CLIPPER2_MAX_DEC_PRECISION && + precision <= CLIPPER2_MAX_DEC_PRECISION) return; error_code |= precision_error_i; // non-fatal error - DoError(precision_error_i); // does nothing unless exceptions enabled - precision = precision > 0 ? MAX_DECIMAL_PRECISION : -MAX_DECIMAL_PRECISION; + DoError(precision_error_i); // does nothing when exceptions are disabled + precision = precision > 0 ? CLIPPER2_MAX_DEC_PRECISION : -CLIPPER2_MAX_DEC_PRECISION; } - inline void CheckPrecision(int& precision) + inline void CheckPrecisionRange(int& precision) { int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); + } + + inline int TriSign(int64_t x) // returns 0, 1 or -1 + { + return (x > 0) - (x < 0); + } + + struct MultiplyUInt64Result + { + const uint64_t result = 0; + const uint64_t carry = 0; + + bool operator==(const MultiplyUInt64Result& other) const + { + return result == other.result && carry == other.carry; + }; + }; + + inline MultiplyUInt64Result Multiply(uint64_t a, uint64_t b) // #834, #835 + { + const auto lo = [](uint64_t x) { return x & 0xFFFFFFFF; }; + const auto hi = [](uint64_t x) { return x >> 32; }; + + const uint64_t x1 = lo(a) * lo(b); + const uint64_t x2 = hi(a) * lo(b) + hi(x1); + const uint64_t x3 = lo(a) * hi(b) + lo(x2); + const uint64_t result = lo(x3) << 32 | lo(x1); + const uint64_t carry = hi(a) * hi(b) + hi(x2) + hi(x3); + + return { result, carry }; + } + + // returns true if (and only if) a * b == c * d + inline bool ProductsAreEqual(int64_t a, int64_t b, int64_t c, int64_t d) + { +// -- GODOT start -- +// #if (defined(__clang__) || defined(__GNUC__)) && UINTPTR_MAX >= UINT64_MAX +// const auto ab = static_cast<__int128_t>(a) * static_cast<__int128_t>(b); +// const auto cd = static_cast<__int128_t>(c) * static_cast<__int128_t>(d); +// return ab == cd; +// #else +// -- GODOT end -- + // nb: unsigned values needed for calculating overflow carry + const auto abs_a = static_cast<uint64_t>(std::abs(a)); + const auto abs_b = static_cast<uint64_t>(std::abs(b)); + const auto abs_c = static_cast<uint64_t>(std::abs(c)); + const auto abs_d = static_cast<uint64_t>(std::abs(d)); + + const auto abs_ab = Multiply(abs_a, abs_b); + const auto abs_cd = Multiply(abs_c, abs_d); + + // nb: it's important to differentiate 0 values here from other values + const auto sign_ab = TriSign(a) * TriSign(b); + const auto sign_cd = TriSign(c) * TriSign(d); + + return abs_ab == abs_cd && sign_ab == sign_cd; +// -- GODOT start -- +// #endif +// -- GODOT end -- + } + + template <typename T> + inline bool IsCollinear(const Point<T>& pt1, + const Point<T>& sharedPt, const Point<T>& pt2) // #777 + { + const auto a = sharedPt.x - pt1.x; + const auto b = pt2.y - sharedPt.y; + const auto c = sharedPt.y - pt1.y; + const auto d = pt2.x - sharedPt.x; + // When checking for collinearity with very large coordinate values + // then ProductsAreEqual is more accurate than using CrossProduct. + return ProductsAreEqual(a, b, c, d); } + template <typename T> inline double CrossProduct(const Point<T>& pt1, const Point<T>& pt2, const Point<T>& pt3) { return (static_cast<double>(pt2.x - pt1.x) * static_cast<double>(pt3.y - @@ -635,15 +766,17 @@ namespace Clipper2Lib } template <typename T> - inline double DistanceFromLineSqrd(const Point<T>& pt, const Point<T>& ln1, const Point<T>& ln2) + inline double PerpendicDistFromLineSqrd(const Point<T>& pt, + const Point<T>& line1, const Point<T>& line2) { //perpendicular distance of point (x³,y³) = (Ax³ + By³ + C)/Sqrt(A² + B²) //see http://en.wikipedia.org/wiki/Perpendicular_distance - double A = static_cast<double>(ln1.y - ln2.y); - double B = static_cast<double>(ln2.x - ln1.x); - double C = A * ln1.x + B * ln1.y; - C = A * pt.x + B * pt.y - C; - return (C * C) / (A * A + B * B); + double a = static_cast<double>(pt.x - line1.x); + double b = static_cast<double>(pt.y - line1.y); + double c = static_cast<double>(line2.x - line1.x); + double d = static_cast<double>(line2.y - line1.y); + if (c == 0 && d == 0) return 0; + return Sqr(a * d - c * b) / (c * c + d * d); } template <typename T> @@ -663,7 +796,7 @@ namespace Clipper2Lib } if (cnt & 1) a += static_cast<double>(it2->y + it1->y) * (it2->x - it1->x); - return a * 0.5; + return (a * 0.5); } template <typename T> @@ -681,16 +814,73 @@ namespace Clipper2Lib template <typename T> inline bool IsPositive(const Path<T>& poly) { - // A curve has positive orientation [and area] if a region 'R' + // A curve has positive orientation [and area] if a region 'R' // is on the left when traveling around the outside of 'R'. //https://mathworld.wolfram.com/CurveOrientation.html //nb: This statement is premised on using Cartesian coordinates return Area<T>(poly) >= 0; } - - inline bool GetIntersectPoint(const Point64& ln1a, const Point64& ln1b, - const Point64& ln2a, const Point64& ln2b, Point64& ip) - { + +#if CLIPPER2_HI_PRECISION + // caution: this will compromise performance + // https://github.com/AngusJohnson/Clipper2/issues/317#issuecomment-1314023253 + // See also CPP/BenchMark/GetIntersectPtBenchmark.cpp + #define CC_MIN(x,y) ((x)>(y)?(y):(x)) + #define CC_MAX(x,y) ((x)<(y)?(y):(x)) + template<typename T> + inline bool GetSegmentIntersectPt(const Point<T>& ln1a, const Point<T>& ln1b, + const Point<T>& ln2a, const Point<T>& ln2b, Point<T>& ip) + { + double ln1dy = static_cast<double>(ln1b.y - ln1a.y); + double ln1dx = static_cast<double>(ln1a.x - ln1b.x); + double ln2dy = static_cast<double>(ln2b.y - ln2a.y); + double ln2dx = static_cast<double>(ln2a.x - ln2b.x); + double det = (ln2dy * ln1dx) - (ln1dy * ln2dx); + if (det == 0.0) return false; + T bb0minx = CC_MIN(ln1a.x, ln1b.x); + T bb0miny = CC_MIN(ln1a.y, ln1b.y); + T bb0maxx = CC_MAX(ln1a.x, ln1b.x); + T bb0maxy = CC_MAX(ln1a.y, ln1b.y); + T bb1minx = CC_MIN(ln2a.x, ln2b.x); + T bb1miny = CC_MIN(ln2a.y, ln2b.y); + T bb1maxx = CC_MAX(ln2a.x, ln2b.x); + T bb1maxy = CC_MAX(ln2a.y, ln2b.y); + + if constexpr (std::is_integral_v<T>) + { + int64_t originx = (CC_MIN(bb0maxx, bb1maxx) + CC_MAX(bb0minx, bb1minx)) >> 1; + int64_t originy = (CC_MIN(bb0maxy, bb1maxy) + CC_MAX(bb0miny, bb1miny)) >> 1; + double ln0c = (ln1dy * static_cast<double>(ln1a.x - originx)) + + (ln1dx * static_cast<double>(ln1a.y - originy)); + double ln1c = (ln2dy * static_cast<double>(ln2a.x - originx)) + + (ln2dx * static_cast<double>(ln2a.y - originy)); + double hitx = ((ln1dx * ln1c) - (ln2dx * ln0c)) / det; + double hity = ((ln2dy * ln0c) - (ln1dy * ln1c)) / det; + + ip.x = originx + (T)nearbyint(hitx); + ip.y = originy + (T)nearbyint(hity); + } + else + { + double originx = (CC_MIN(bb0maxx, bb1maxx) + CC_MAX(bb0minx, bb1minx)) / 2.0; + double originy = (CC_MIN(bb0maxy, bb1maxy) + CC_MAX(bb0miny, bb1miny)) / 2.0; + double ln0c = (ln1dy * static_cast<double>(ln1a.x - originx)) + + (ln1dx * static_cast<double>(ln1a.y - originy)); + double ln1c = (ln2dy * static_cast<double>(ln2a.x - originx)) + + (ln2dx * static_cast<double>(ln2a.y - originy)); + double hitx = ((ln1dx * ln1c) - (ln2dx * ln0c)) / det; + double hity = ((ln2dy * ln0c) - (ln1dy * ln1c)) / det; + + ip.x = originx + static_cast<T>(hitx); + ip.y = originy + static_cast<T>(hity); + } + return true; +} +#else + template<typename T> + inline bool GetSegmentIntersectPt(const Point<T>& ln1a, const Point<T>& ln1b, + const Point<T>& ln2a, const Point<T>& ln2b, Point<T>& ip) + { // https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection double dx1 = static_cast<double>(ln1b.x - ln1a.x); double dy1 = static_cast<double>(ln1b.y - ln1a.y); @@ -700,15 +890,44 @@ namespace Clipper2Lib double det = dy1 * dx2 - dy2 * dx1; if (det == 0.0) return false; double t = ((ln1a.x - ln2a.x) * dy2 - (ln1a.y - ln2a.y) * dx2) / det; - if (t <= 0.0) ip = ln1a; // ?? check further (see also #568) - else if (t >= 1.0) ip = ln1b; // ?? check further + if (t <= 0.0) ip = ln1a; + else if (t >= 1.0) ip = ln1b; else { - ip.x = static_cast<int64_t>(ln1a.x + t * dx1); - ip.y = static_cast<int64_t>(ln1a.y + t * dy1); - } + ip.x = static_cast<T>(ln1a.x + t * dx1); + ip.y = static_cast<T>(ln1a.y + t * dy1); + } return true; } +#endif + + template<typename T> + inline Point<T> TranslatePoint(const Point<T>& pt, double dx, double dy) + { +#ifdef USINGZ + return Point<T>(pt.x + dx, pt.y + dy, pt.z); +#else + return Point<T>(pt.x + dx, pt.y + dy); +#endif + } + + + template<typename T> + inline Point<T> ReflectPoint(const Point<T>& pt, const Point<T>& pivot) + { +#ifdef USINGZ + return Point<T>(pivot.x + (pivot.x - pt.x), pivot.y + (pivot.y - pt.y), pt.z); +#else + return Point<T>(pivot.x + (pivot.x - pt.x), pivot.y + (pivot.y - pt.y)); +#endif + } + + template<typename T> + inline int GetSign(const T& val) + { + if (!val) return 0; + return (val > 0) ? 1 : -1; + } inline bool SegmentsIntersect(const Point64& seg1a, const Point64& seg1b, const Point64& seg2a, const Point64& seg2b, bool inclusive = false) @@ -724,10 +943,10 @@ namespace Clipper2Lib return (res1 || res2 || res3 || res4); // ensures not collinear } else { - return (CrossProduct(seg1a, seg2a, seg2b) * - CrossProduct(seg1b, seg2a, seg2b) < 0) && - (CrossProduct(seg2a, seg1a, seg1b) * - CrossProduct(seg2b, seg1a, seg1b) < 0); + return (GetSign(CrossProduct(seg1a, seg2a, seg2b)) * + GetSign(CrossProduct(seg1b, seg2a, seg2b)) < 0) && + (GetSign(CrossProduct(seg2a, seg1a, seg1b)) * + GetSign(CrossProduct(seg2b, seg1a, seg1b)) < 0); } } @@ -743,7 +962,7 @@ namespace Clipper2Lib static_cast<double>(offPt.y - seg1.y) * dy) / (Sqr(dx) + Sqr(dy)); if (q < 0) q = 0; else if (q > 1) q = 1; - if constexpr (std::numeric_limits<T>::is_integer) + if constexpr (std::is_integral_v<T>) return Point<T>( seg1.x + static_cast<T>(nearbyint(q * dx)), seg1.y + static_cast<T>(nearbyint(q * dy))); @@ -770,7 +989,7 @@ namespace Clipper2Lib return PointInPolygonResult::IsOutside; bool is_above = first->y < pt.y, starting_above = is_above; - curr = first +1; + curr = first +1; while (true) { if (curr == cend) @@ -779,7 +998,7 @@ namespace Clipper2Lib cend = first; curr = cbegin; } - + if (is_above) { while (curr != cend && curr->y < pt.y) ++curr; @@ -791,14 +1010,14 @@ namespace Clipper2Lib if (curr == cend) continue; } - if (curr == cbegin) + if (curr == cbegin) prev = polygon.cend() - 1; //nb: NOT cend (since might equal first) - else + else prev = curr - 1; if (curr->y == pt.y) { - if (curr->x == pt.x || + if (curr->x == pt.x || (curr->y == prev->y && ((pt.x < prev->x) != (pt.x < curr->x)))) return PointInPolygonResult::IsOn; @@ -822,7 +1041,7 @@ namespace Clipper2Lib is_above = !is_above; ++curr; } - + if (is_above != starting_above) { cend = polygon.cend(); diff --git a/thirdparty/clipper2/include/clipper2/clipper.engine.h b/thirdparty/clipper2/include/clipper2/clipper.engine.h index 13c7f069aa..f6108832cd 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.engine.h +++ b/thirdparty/clipper2/include/clipper2/clipper.engine.h @@ -1,8 +1,8 @@ /******************************************************************************* * Author : Angus Johnson * -* Date : 22 November 2023 * +* Date : 5 July 2024 * * Website : http://www.angusj.com * -* Copyright : Angus Johnson 2010-2023 * +* Copyright : Angus Johnson 2010-2024 * * Purpose : This is the main polygon clipping module * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ @@ -33,7 +33,7 @@ namespace Clipper2Lib { //Note: all clipping operations except for Difference are commutative. enum class ClipType { None, Intersection, Union, Difference, Xor }; - + enum class PathType { Subject, Clip }; enum class JoinWith { None, Left, Right }; @@ -41,7 +41,7 @@ namespace Clipper2Lib { None = 0, OpenStart = 1, OpenEnd = 2, LocalMax = 4, LocalMin = 8 }; - constexpr enum VertexFlags operator &(enum VertexFlags a, enum VertexFlags b) + constexpr enum VertexFlags operator &(enum VertexFlags a, enum VertexFlags b) { return (enum VertexFlags)(uint32_t(a) & uint32_t(b)); } @@ -95,7 +95,7 @@ namespace Clipper2Lib { Path64 path; bool is_open = false; - ~OutRec() { + ~OutRec() { if (splits) delete splits; // nb: don't delete the split pointers // as these are owned by ClipperBase's outrec_list_ @@ -106,7 +106,7 @@ namespace Clipper2Lib { //Important: UP and DOWN here are premised on Y-axis positive down //displays, which is the orientation used in Clipper's development. /////////////////////////////////////////////////////////////////// - + struct Active { Point64 bot; Point64 top; @@ -230,7 +230,7 @@ namespace Clipper2Lib { inline bool PopHorz(Active *&e); inline OutPt* StartOpenPath(Active &e, const Point64& pt); inline void UpdateEdgeIntoAEL(Active *e); - OutPt* IntersectEdges(Active &e1, Active &e2, const Point64& pt); + void IntersectEdges(Active &e1, Active &e2, const Point64& pt); inline void DeleteFromAEL(Active &e); inline void AdjustCurrXAndCopyToSEL(const int64_t top_y); void DoIntersections(const int64_t top_y); @@ -240,7 +240,7 @@ namespace Clipper2Lib { void SwapPositionsInAEL(Active& edge1, Active& edge2); OutRec* NewOutRec(); OutPt* AddOutPt(const Active &e, const Point64& pt); - OutPt* AddLocalMinPoly(Active &e1, Active &e2, + OutPt* AddLocalMinPoly(Active &e1, Active &e2, const Point64& pt, bool is_new = false); OutPt* AddLocalMaxPoly(Active &e1, Active &e2, const Point64& pt); void DoHorizontal(Active &horz); @@ -251,13 +251,13 @@ namespace Clipper2Lib { void JoinOutrecPaths(Active &e1, Active &e2); void FixSelfIntersects(OutRec* outrec); void DoSplitOp(OutRec* outRec, OutPt* splitOp); - + inline void AddTrialHorzJoin(OutPt* op); void ConvertHorzSegsToJoins(); void ProcessHorzJoins(); void Split(Active& e, const Point64& pt); - inline void CheckJoinLeft(Active& e, + inline void CheckJoinLeft(Active& e, const Point64& pt, bool check_curr_x = false); inline void CheckJoinRight(Active& e, const Point64& pt, bool check_curr_x = false); @@ -326,12 +326,12 @@ namespace Clipper2Lib { const PolyPath* Parent() const { return parent_; } - bool IsHole() const + bool IsHole() const { unsigned lvl = Level(); //Even levels except level 0 return lvl && !(lvl & 1); - } + } }; typedef typename std::vector<std::unique_ptr<PolyPath64>> PolyPath64List; @@ -343,15 +343,16 @@ namespace Clipper2Lib { Path64 polygon_; public: explicit PolyPath64(PolyPath64* parent = nullptr) : PolyPath(parent) {} + explicit PolyPath64(PolyPath64* parent, const Path64& path) : PolyPath(parent) { polygon_ = path; } ~PolyPath64() { childs_.resize(0); } PolyPath64* operator [] (size_t index) const - { + { return childs_[index].get(); //std::unique_ptr - } + } PolyPath64* Child(size_t index) const { @@ -363,10 +364,7 @@ namespace Clipper2Lib { PolyPath64* AddChild(const Path64& path) override { - auto p = std::make_unique<PolyPath64>(this); - auto* result = childs_.emplace_back(std::move(p)).get(); - result->polygon_ = path; - return result; + return childs_.emplace_back(std::make_unique<PolyPath64>(this, path)).get(); } void Clear() override @@ -401,12 +399,25 @@ namespace Clipper2Lib { scale_ = parent ? parent->scale_ : 1.0; } + explicit PolyPathD(PolyPathD* parent, const Path64& path) : PolyPath(parent) + { + scale_ = parent ? parent->scale_ : 1.0; + int error_code = 0; + polygon_ = ScalePath<double, int64_t>(path, scale_, error_code); + } + + explicit PolyPathD(PolyPathD* parent, const PathD& path) : PolyPath(parent) + { + scale_ = parent ? parent->scale_ : 1.0; + polygon_ = path; + } + ~PolyPathD() { childs_.resize(0); } PolyPathD* operator [] (size_t index) const - { + { return childs_[index].get(); } @@ -420,22 +431,15 @@ namespace Clipper2Lib { void SetScale(double value) { scale_ = value; } double Scale() const { return scale_; } - + PolyPathD* AddChild(const Path64& path) override { - int error_code = 0; - auto p = std::make_unique<PolyPathD>(this); - PolyPathD* result = childs_.emplace_back(std::move(p)).get(); - result->polygon_ = ScalePath<double, int64_t>(path, scale_, error_code); - return result; + return childs_.emplace_back(std::make_unique<PolyPathD>(this, path)).get(); } PolyPathD* AddChild(const PathD& path) { - auto p = std::make_unique<PolyPathD>(this); - PolyPathD* result = childs_.emplace_back(std::move(p)).get(); - result->polygon_ = path; - return result; + return childs_.emplace_back(std::make_unique<PolyPathD>(this, path)).get(); } void Clear() override @@ -488,7 +492,7 @@ namespace Clipper2Lib { return Execute(clip_type, fill_rule, closed_paths, dummy); } - bool Execute(ClipType clip_type, FillRule fill_rule, + bool Execute(ClipType clip_type, FillRule fill_rule, Paths64& closed_paths, Paths64& open_paths) { closed_paths.clear(); @@ -530,7 +534,7 @@ namespace Clipper2Lib { public: explicit ClipperD(int precision = 2) : ClipperBase() { - CheckPrecision(precision, error_code_); + CheckPrecisionRange(precision, error_code_); // to optimize scaling / descaling precision // set the scale to a power of double's radix (2) (#25) scale_ = std::pow(std::numeric_limits<double>::radix, @@ -560,12 +564,12 @@ namespace Clipper2Lib { void CheckCallback() { if(zCallbackD_) - // if the user defined float point callback has been assigned + // if the user defined float point callback has been assigned // then assign the proxy callback function - ClipperBase::zCallback_ = + ClipperBase::zCallback_ = std::bind(&ClipperD::ZCB, this, std::placeholders::_1, std::placeholders::_2, std::placeholders::_3, - std::placeholders::_4, std::placeholders::_5); + std::placeholders::_4, std::placeholders::_5); else ClipperBase::zCallback_ = nullptr; } @@ -632,6 +636,6 @@ namespace Clipper2Lib { }; -} // namespace +} // namespace #endif // CLIPPER_ENGINE_H diff --git a/thirdparty/clipper2/include/clipper2/clipper.export.h b/thirdparty/clipper2/include/clipper2/clipper.export.h index d7286132a4..53a445368e 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.export.h +++ b/thirdparty/clipper2/include/clipper2/clipper.export.h @@ -1,14 +1,14 @@ /******************************************************************************* * Author : Angus Johnson * -* Date : 26 November 2023 * +* Date : 14 May 2024 * * Website : http://www.angusj.com * -* Copyright : Angus Johnson 2010-2023 * +* Copyright : Angus Johnson 2010-2024 * * Purpose : This module exports the Clipper2 Library (ie DLL/so) * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ -/* +/* Boolean clipping: cliptype: None=0, Intersection=1, Union=2, Difference=3, Xor=4 fillrule: EvenOdd=0, NonZero=1, Positive=2, Negative=3 @@ -19,12 +19,12 @@ The path structures used extensively in other parts of this library are all based on std::vector classes. Since C++ classes can't be accessed by other -languages, these paths must be converted into simple C data structures that -can be understood by just about any programming language. And these C style -path structures are simple arrays of int64_t (CPath64) and double (CPathD). +languages, these paths are converted into very simple array data structures +(of either int64_t for CPath64 or double for CPathD) that can be parsed by +just about any programming language. CPath64 and CPathD: -These are arrays of consecutive x and y path coordinates preceeded by +These are arrays of consecutive x and y path coordinates preceeded by a pair of values containing the path's length (N) and a 0 value. __________________________________ |counter|coord1|coord2|...|coordN| @@ -34,23 +34,24 @@ __________________________________ CPaths64 and CPathsD: These are also arrays containing any number of consecutive CPath64 or CPathD structures. But preceeding these consecutive paths, there is pair of -values that contain the total length of the array (A) structure and -the number (C) of CPath64 or CPathD it contains. +values that contain the total length of the array structure (A) and the +number of CPath64 or CPathD it contains (C). The space these structures will +occupy in memory = A * sizeof(int64_t) or A * sizeof(double) respectively. _______________________________ |counter|path1|path2|...|pathC| |A , C | | _______________________________ CPolytree64 and CPolytreeD: -These are also arrays consisting of CPolyPath structures that represent +These are also arrays consisting of CPolyPath structures that represent individual paths in a tree structure. However, the very first (ie top) -CPolyPath is just the tree container that won't have a path. And because +CPolyPath is just the tree container that doesn't have a path. And because of that, its structure will be very slightly different from the remaining CPolyPath. This difference will be discussed below. CPolyPath64 and CPolyPathD: -These are simple arrays consisting of a series of path coordinates followed -by any number of child (ie nested) CPolyPath. Preceeding these are two values +These are simple arrays consisting of a series of path coordinates followed +by any number of child (ie nested) CPolyPath. Preceeding these are two values indicating the length of the path (N) and the number of child CPolyPath (C). ____________________________________________________________ |counter|coord1|coord2|...|coordN| child1|child2|...|childC| @@ -58,19 +59,20 @@ ____________________________________________________________ ____________________________________________________________ As mentioned above, the very first CPolyPath structure is just a container -that owns (both directly and indirectly) every other CPolyPath in the tree. +that owns (both directly and indirectly) every other CPolyPath in the tree. Since this first CPolyPath has no path, instead of a path length, its very -first value will contain the total length of the CPolytree array structure. - -All theses exported structures (CPaths64, CPathsD, CPolyTree64 & CPolyTreeD) -are arrays of type int64_t or double. And the first value in these arrays -will always contain the length of that array. - -These array structures are allocated in heap memory which will eventually -need to be released. But since applications dynamically linking to these -functions may use different memory managers, the only safe way to free up -this memory is to use the exported DisposeArray64 and DisposeArrayD -functions below. +first value will contain the total length of the CPolytree array (not its +total bytes length). + +Again, all theses exported structures (CPaths64, CPathsD, CPolyTree64 & +CPolyTreeD) are arrays of either type int64_t or double, and the first +value in these arrays will always be the length of that array. + +These array structures are allocated in heap memory which will eventually +need to be released. However, since applications dynamically linking to +these functions may use different memory managers, the only safe way to +free up this memory is to use the exported DisposeArray64 and +DisposeArrayD functions (see below). */ @@ -128,7 +130,7 @@ inline Rect<T> CRectToRect(const CRect<T>& rect) #ifdef _WIN32 #define EXTERN_DLL_EXPORT extern "C" __declspec(dllexport) #else - #define EXTERN_DLL_EXPORT extern "C" + #define EXTERN_DLL_EXPORT extern "C" #endif @@ -173,8 +175,8 @@ EXTERN_DLL_EXPORT int BooleanOp_PolyTreeD(uint8_t cliptype, bool preserve_collinear = true, bool reverse_solution = false); EXTERN_DLL_EXPORT CPaths64 InflatePaths64(const CPaths64 paths, - double delta, uint8_t jointype, uint8_t endtype, - double miter_limit = 2.0, double arc_tolerance = 0.0, + double delta, uint8_t jointype, uint8_t endtype, + double miter_limit = 2.0, double arc_tolerance = 0.0, bool reverse_solution = false); EXTERN_DLL_EXPORT CPathsD InflatePathsD(const CPathsD paths, double delta, uint8_t jointype, uint8_t endtype, @@ -219,10 +221,10 @@ static size_t GetPolyPath64ArrayLen(const PolyPath64& pp) return result; } -static void GetPolytreeCountAndCStorageSize(const PolyTree64& tree, +static void GetPolytreeCountAndCStorageSize(const PolyTree64& tree, size_t& cnt, size_t& array_len) { - cnt = tree.Count(); // nb: top level count only + cnt = tree.Count(); // nb: top level count only array_len = GetPolyPath64ArrayLen(tree); } @@ -272,16 +274,33 @@ CPathsD CreateCPathsDFromPaths64(const Paths64& paths, double scale) } template <typename T> +static Path<T> ConvertCPath(T* path) +{ + Path<T> result; + if (!path) return result; + T* v = path; + size_t cnt = static_cast<size_t>(*v); + v += 2; // skip 0 value + result.reserve(cnt); + for (size_t j = 0; j < cnt; ++j) + { + T x = *v++, y = *v++; + result.push_back(Point<T>(x, y)); + } + return result; +} + +template <typename T> static Paths<T> ConvertCPaths(T* paths) { Paths<T> result; if (!paths) return result; T* v = paths; ++v; - size_t cnt = *v++; + size_t cnt = static_cast<size_t>(*v++); result.reserve(cnt); for (size_t i = 0; i < cnt; ++i) { - size_t cnt2 = *v; + size_t cnt2 = static_cast<size_t>(*v); v += 2; Path<T> path; path.reserve(cnt2); @@ -300,17 +319,17 @@ static Paths64 ConvertCPathsDToPaths64(const CPathsD paths, double scale) { Paths64 result; if (!paths) return result; - double* v = paths; + double* v = paths; ++v; // skip the first value (0) - int64_t cnt = (int64_t)*v++; + size_t cnt = static_cast<size_t>(*v++); result.reserve(cnt); - for (int i = 0; i < cnt; ++i) + for (size_t i = 0; i < cnt; ++i) { - int64_t cnt2 = (int64_t)*v; + size_t cnt2 = static_cast<size_t>(*v); v += 2; Path64 path; path.reserve(cnt2); - for (int j = 0; j < cnt2; ++j) + for (size_t j = 0; j < cnt2; ++j) { double x = *v++ * scale; double y = *v++ * scale; @@ -362,7 +381,7 @@ EXTERN_DLL_EXPORT const char* Version() return CLIPPER2_VERSION; } -EXTERN_DLL_EXPORT int BooleanOp64(uint8_t cliptype, +EXTERN_DLL_EXPORT int BooleanOp64(uint8_t cliptype, uint8_t fillrule, const CPaths64 subjects, const CPaths64 subjects_open, const CPaths64 clips, CPaths64& solution, CPaths64& solution_open, @@ -370,7 +389,7 @@ EXTERN_DLL_EXPORT int BooleanOp64(uint8_t cliptype, { if (cliptype > static_cast<uint8_t>(ClipType::Xor)) return -4; if (fillrule > static_cast<uint8_t>(FillRule::Negative)) return -3; - + Paths64 sub, sub_open, clp, sol, sol_open; sub = ConvertCPaths(subjects); sub_open = ConvertCPaths(subjects_open); @@ -382,7 +401,7 @@ EXTERN_DLL_EXPORT int BooleanOp64(uint8_t cliptype, if (sub.size() > 0) clipper.AddSubject(sub); if (sub_open.size() > 0) clipper.AddOpenSubject(sub_open); if (clp.size() > 0) clipper.AddClip(clp); - if (!clipper.Execute(ClipType(cliptype), FillRule(fillrule), sol, sol_open)) + if (!clipper.Execute(ClipType(cliptype), FillRule(fillrule), sol, sol_open)) return -1; // clipping bug - should never happen :) solution = CreateCPaths(sol); solution_open = CreateCPaths(sol_open); @@ -455,7 +474,7 @@ EXTERN_DLL_EXPORT int BooleanOp_PolyTreeD(uint8_t cliptype, if (precision < -8 || precision > 8) return -5; if (cliptype > static_cast<uint8_t>(ClipType::Xor)) return -4; if (fillrule > static_cast<uint8_t>(FillRule::Negative)) return -3; - + double scale = std::pow(10, precision); int err = 0; @@ -485,10 +504,10 @@ EXTERN_DLL_EXPORT CPaths64 InflatePaths64(const CPaths64 paths, { Paths64 pp; pp = ConvertCPaths(paths); - ClipperOffset clip_offset( miter_limit, + ClipperOffset clip_offset( miter_limit, arc_tolerance, reverse_solution); clip_offset.AddPaths(pp, JoinType(jointype), EndType(endtype)); - Paths64 result; + Paths64 result; clip_offset.Execute(delta, result); return CreateCPaths(result); } @@ -560,6 +579,22 @@ EXTERN_DLL_EXPORT CPathsD RectClipLinesD(const CRectD& rect, return CreateCPathsDFromPaths64(result, 1 / scale); } +EXTERN_DLL_EXPORT CPaths64 MinkowskiSum64(const CPath64& cpattern, const CPath64& cpath, bool is_closed) +{ + Path64 path = ConvertCPath(cpath); + Path64 pattern = ConvertCPath(cpattern); + Paths64 solution = MinkowskiSum(pattern, path, is_closed); + return CreateCPaths(solution); +} + +EXTERN_DLL_EXPORT CPaths64 MinkowskiDiff64(const CPath64& cpattern, const CPath64& cpath, bool is_closed) +{ + Path64 path = ConvertCPath(cpath); + Path64 pattern = ConvertCPath(cpattern); + Paths64 solution = MinkowskiDiff(pattern, path, is_closed); + return CreateCPaths(solution); +} + } // end Clipper2Lib namespace - + #endif // CLIPPER2_EXPORT_H diff --git a/thirdparty/clipper2/include/clipper2/clipper.h b/thirdparty/clipper2/include/clipper2/clipper.h index 0f516b60e8..a2fe5c3cc2 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.h +++ b/thirdparty/clipper2/include/clipper2/clipper.h @@ -1,8 +1,8 @@ /******************************************************************************* * Author : Angus Johnson * -* Date : 18 November 2023 * +* Date : 27 April 2024 * * Website : http://www.angusj.com * -* Copyright : Angus Johnson 2010-2023 * +* Copyright : Angus Johnson 2010-2024 * * Purpose : This module provides a simple interface to the Clipper Library * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ @@ -24,7 +24,7 @@ namespace Clipper2Lib { inline Paths64 BooleanOp(ClipType cliptype, FillRule fillrule, const Paths64& subjects, const Paths64& clips) - { + { Paths64 result; Clipper64 clipper; clipper.AddSubject(subjects); @@ -47,7 +47,7 @@ namespace Clipper2Lib { const PathsD& subjects, const PathsD& clips, int precision = 2) { int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); PathsD result; if (error_code) return result; ClipperD clipper(precision); @@ -58,12 +58,12 @@ namespace Clipper2Lib { } inline void BooleanOp(ClipType cliptype, FillRule fillrule, - const PathsD& subjects, const PathsD& clips, + const PathsD& subjects, const PathsD& clips, PolyTreeD& polytree, int precision = 2) { polytree.Clear(); int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); if (error_code) return; ClipperD clipper(precision); clipper.AddSubject(subjects); @@ -75,7 +75,7 @@ namespace Clipper2Lib { { return BooleanOp(ClipType::Intersection, fillrule, subjects, clips); } - + inline PathsD Intersect(const PathsD& subjects, const PathsD& clips, FillRule fillrule, int decimal_prec = 2) { return BooleanOp(ClipType::Intersection, fillrule, subjects, clips, decimal_prec); @@ -104,7 +104,7 @@ namespace Clipper2Lib { { PathsD result; int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); if (error_code) return result; ClipperD clipper(precision); clipper.AddSubject(subjects); @@ -145,11 +145,11 @@ namespace Clipper2Lib { } inline PathsD InflatePaths(const PathsD& paths, double delta, - JoinType jt, EndType et, double miter_limit = 2.0, + JoinType jt, EndType et, double miter_limit = 2.0, int precision = 2, double arc_tolerance = 0.0) { int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); if (!delta) return paths; if (error_code) return PathsD(); const double scale = std::pow(10, precision); @@ -219,13 +219,13 @@ namespace Clipper2Lib { { if (rect.IsEmpty() || paths.empty()) return PathsD(); int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); if (error_code) return PathsD(); const double scale = std::pow(10, precision); Rect64 r = ScaleRect<int64_t, double>(rect, scale); RectClip64 rc(r); Paths64 pp = ScalePaths<int64_t, double>(paths, scale, error_code); - if (error_code) return PathsD(); // ie: error_code result is lost + if (error_code) return PathsD(); // ie: error_code result is lost return ScalePaths<double, int64_t>( rc.Execute(pp), 1 / scale, error_code); } @@ -251,7 +251,7 @@ namespace Clipper2Lib { { if (rect.IsEmpty() || lines.empty()) return PathsD(); int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); if (error_code) return PathsD(); const double scale = std::pow(10, precision); Rect64 r = ScaleRect<int64_t, double>(rect, scale); @@ -290,8 +290,8 @@ namespace Clipper2Lib { { // return false if this child isn't fully contained by its parent - // checking for a single vertex outside is a bit too crude since - // it doesn't account for rounding errors. It's better to check + // checking for a single vertex outside is a bit too crude since + // it doesn't account for rounding errors. It's better to check // for consecutive vertices found outside the parent's polygon. int outsideCnt = 0; @@ -311,7 +311,7 @@ namespace Clipper2Lib { return true; } - static void OutlinePolyPath(std::ostream& os, + static void OutlinePolyPath(std::ostream& os, size_t idx, bool isHole, size_t count, const std::string& preamble) { std::string plural = (count == 1) ? "." : "s."; @@ -342,19 +342,19 @@ namespace Clipper2Lib { } template<typename T, typename U> - inline constexpr void MakePathGeneric(const T an_array, + inline constexpr void MakePathGeneric(const T an_array, size_t array_size, std::vector<U>& result) { result.reserve(array_size / 2); for (size_t i = 0; i < array_size; i +=2) #ifdef USINGZ - result.push_back( U{ an_array[i], an_array[i +1], 0} ); + result.push_back( U{ an_array[i], an_array[i + 1], 0} ); #else result.push_back( U{ an_array[i], an_array[i + 1]} ); #endif } - } // end details namespace + } // end details namespace inline std::ostream& operator<< (std::ostream& os, const PolyTree64& pp) { @@ -398,7 +398,7 @@ namespace Clipper2Lib { inline bool CheckPolytreeFullyContainsChildren(const PolyTree64& polytree) { for (const auto& child : polytree) - if (child->Count() > 0 && + if (child->Count() > 0 && !details::PolyPath64ContainsChildren(*child)) return false; return true; @@ -471,7 +471,7 @@ namespace Clipper2Lib { std::size_t size = N / 3; Path64 result(size); for (size_t i = 0; i < size; ++i) - result[i] = Point64(list[i * 3], + result[i] = Point64(list[i * 3], list[i * 3 + 1], list[i * 3 + 2]); return result; } @@ -489,7 +489,7 @@ namespace Clipper2Lib { list[i * 3 + 1], list[i * 3 + 2]); else for (size_t i = 0; i < size; ++i) - result[i] = PointD(list[i * 3], list[i * 3 + 1], + result[i] = PointD(list[i * 3], list[i * 3 + 1], static_cast<int64_t>(list[i * 3 + 2])); return result; } @@ -510,9 +510,9 @@ namespace Clipper2Lib { if (!is_open_path) { - while (srcIt != stop && !CrossProduct(*stop, *srcIt, *(srcIt + 1))) + while (srcIt != stop && IsCollinear(*stop, *srcIt, *(srcIt + 1))) ++srcIt; - while (srcIt != stop && !CrossProduct(*(stop - 1), *stop, *srcIt)) + while (srcIt != stop && IsCollinear(*(stop - 1), *stop, *srcIt)) --stop; if (srcIt == stop) return Path64(); } @@ -521,7 +521,7 @@ namespace Clipper2Lib { dst.push_back(*prevIt); for (; srcIt != stop; ++srcIt) { - if (CrossProduct(*prevIt, *srcIt, *(srcIt + 1))) + if (!IsCollinear(*prevIt, *srcIt, *(srcIt + 1))) { prevIt = srcIt; dst.push_back(*prevIt); @@ -530,12 +530,12 @@ namespace Clipper2Lib { if (is_open_path) dst.push_back(*srcIt); - else if (CrossProduct(*prevIt, *stop, dst[0])) + else if (!IsCollinear(*prevIt, *stop, dst[0])) dst.push_back(*stop); else { while (dst.size() > 2 && - !CrossProduct(dst[dst.size() - 1], dst[dst.size() - 2], dst[0])) + IsCollinear(dst[dst.size() - 1], dst[dst.size() - 2], dst[0])) dst.pop_back(); if (dst.size() < 3) return Path64(); } @@ -545,7 +545,7 @@ namespace Clipper2Lib { inline PathD TrimCollinear(const PathD& path, int precision, bool is_open_path = false) { int error_code = 0; - CheckPrecision(precision, error_code); + CheckPrecisionRange(precision, error_code); if (error_code) return PathD(); const double scale = std::pow(10, precision); Path64 p = ScalePath<int64_t, double>(path, scale, error_code); @@ -580,23 +580,23 @@ namespace Clipper2Lib { double cp = std::abs(CrossProduct(pt1, pt2, pt3)); return (cp * cp) / (DistanceSqr(pt1, pt2) * DistanceSqr(pt2, pt3)) < sin_sqrd_min_angle_rads; } - + template <typename T> - inline Path<T> Ellipse(const Rect<T>& rect, int steps = 0) + inline Path<T> Ellipse(const Rect<T>& rect, size_t steps = 0) { - return Ellipse(rect.MidPoint(), - static_cast<double>(rect.Width()) *0.5, + return Ellipse(rect.MidPoint(), + static_cast<double>(rect.Width()) *0.5, static_cast<double>(rect.Height()) * 0.5, steps); } template <typename T> inline Path<T> Ellipse(const Point<T>& center, - double radiusX, double radiusY = 0, int steps = 0) + double radiusX, double radiusY = 0, size_t steps = 0) { if (radiusX <= 0) return Path<T>(); if (radiusY <= 0) radiusY = radiusX; if (steps <= 2) - steps = static_cast<int>(PI * sqrt((radiusX + radiusY) / 2)); + steps = static_cast<size_t>(PI * sqrt((radiusX + radiusY) / 2)); double si = std::sin(2 * PI / steps); double co = std::cos(2 * PI / steps); @@ -604,7 +604,7 @@ namespace Clipper2Lib { Path<T> result; result.reserve(steps); result.push_back(Point<T>(center.x + radiusX, static_cast<double>(center.y))); - for (int i = 1; i < steps; ++i) + for (size_t i = 1; i < steps; ++i) { result.push_back(Point<T>(center.x + radiusX * dx, center.y + radiusY * dy)); double x = dx * co - dy * si; @@ -614,19 +614,7 @@ namespace Clipper2Lib { return result; } - template <typename T> - inline double PerpendicDistFromLineSqrd(const Point<T>& pt, - const Point<T>& line1, const Point<T>& line2) - { - double a = static_cast<double>(pt.x - line1.x); - double b = static_cast<double>(pt.y - line1.y); - double c = static_cast<double>(line2.x - line1.x); - double d = static_cast<double>(line2.y - line1.y); - if (c == 0 && d == 0) return 0; - return Sqr(a * d - c * b) / (c * c + d * d); - } - - inline size_t GetNext(size_t current, size_t high, + inline size_t GetNext(size_t current, size_t high, const std::vector<bool>& flags) { ++current; @@ -637,7 +625,7 @@ namespace Clipper2Lib { return current; } - inline size_t GetPrior(size_t current, size_t high, + inline size_t GetPrior(size_t current, size_t high, const std::vector<bool>& flags) { if (current == 0) current = high; @@ -650,7 +638,7 @@ namespace Clipper2Lib { } template <typename T> - inline Path<T> SimplifyPath(const Path<T> &path, + inline Path<T> SimplifyPath(const Path<T> &path, double epsilon, bool isClosedPath = true) { const size_t len = path.size(), high = len -1; @@ -665,7 +653,7 @@ namespace Clipper2Lib { distSqr[0] = PerpendicDistFromLineSqrd(path[0], path[high], path[1]); distSqr[high] = PerpendicDistFromLineSqrd(path[high], path[0], path[high - 1]); } - else + else { distSqr[0] = MAX_DBL; distSqr[high] = MAX_DBL; @@ -684,7 +672,7 @@ namespace Clipper2Lib { } while (curr != start && distSqr[curr] > epsSqr); if (curr == start) break; } - + prior = GetPrior(curr, high, flags); next = GetNext(curr, high, flags); if (next == prior) break; @@ -699,7 +687,7 @@ namespace Clipper2Lib { } else prior2 = GetPrior(prior, high, flags); - + flags[curr] = true; curr = next; next = GetNext(next, high, flags); @@ -717,7 +705,7 @@ namespace Clipper2Lib { } template <typename T> - inline Paths<T> SimplifyPaths(const Paths<T> &paths, + inline Paths<T> SimplifyPaths(const Paths<T> &paths, double epsilon, bool isClosedPath = true) { Paths<T> result; diff --git a/thirdparty/clipper2/include/clipper2/clipper.minkowski.h b/thirdparty/clipper2/include/clipper2/clipper.minkowski.h index ebddd08a59..a3ddcf86f3 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.minkowski.h +++ b/thirdparty/clipper2/include/clipper2/clipper.minkowski.h @@ -15,7 +15,7 @@ #include <string> #include "clipper2/clipper.core.h" -namespace Clipper2Lib +namespace Clipper2Lib { namespace detail diff --git a/thirdparty/clipper2/include/clipper2/clipper.offset.h b/thirdparty/clipper2/include/clipper2/clipper.offset.h index 30992bfa55..bb075a6d49 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.offset.h +++ b/thirdparty/clipper2/include/clipper2/clipper.offset.h @@ -1,8 +1,8 @@ /******************************************************************************* * Author : Angus Johnson * -* Date : 19 November 2023 * +* Date : 24 March 2024 * * Website : http://www.angusj.com * -* Copyright : Angus Johnson 2010-2023 * +* Copyright : Angus Johnson 2010-2024 * * Purpose : Path Offset (Inflate/Shrink) * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ @@ -34,9 +34,7 @@ private: class Group { public: Paths64 paths_in; - std::vector<bool> is_hole_list; - std::vector<Rect64> bounds_list; - int lowest_path_idx = -1; + std::optional<size_t> lowest_path_idx{}; bool is_reversed = false; JoinType join_type; EndType end_type; @@ -52,7 +50,8 @@ private: double step_cos_ = 0.0; PathD norms; Path64 path_out; - Paths64 solution; + Paths64* solution = nullptr; + PolyTree64* solution_tree = nullptr; std::vector<Group> groups_; JoinType join_type_ = JoinType::Bevel; EndType end_type_ = EndType::Polygon; @@ -64,9 +63,10 @@ private: #ifdef USINGZ ZCallback64 zCallback64_ = nullptr; + void ZCB(const Point64& bot1, const Point64& top1, + const Point64& bot2, const Point64& top2, Point64& ip); #endif DeltaCallback64 deltaCallback64_ = nullptr; - size_t CalcSolutionCapacity(); bool CheckReverseOrientation(); void DoBevel(const Path64& path, size_t j, size_t k); @@ -83,7 +83,7 @@ private: public: explicit ClipperOffset(double miter_limit = 2.0, double arc_tolerance = 0.0, - bool preserve_collinear = false, + bool preserve_collinear = false, bool reverse_solution = false) : miter_limit_(miter_limit), arc_tolerance_(arc_tolerance), preserve_collinear_(preserve_collinear), @@ -91,7 +91,7 @@ public: ~ClipperOffset() { Clear(); }; - int ErrorCode() { return error_code_; }; + int ErrorCode() const { return error_code_; }; void AddPath(const Path64& path, JoinType jt_, EndType et_); void AddPaths(const Paths64& paths, JoinType jt_, EndType et_); void Clear() { groups_.clear(); norms.clear(); }; diff --git a/thirdparty/clipper2/include/clipper2/clipper.rectclip.h b/thirdparty/clipper2/include/clipper2/clipper.rectclip.h index ff043f25f0..bfcfacf2e7 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.rectclip.h +++ b/thirdparty/clipper2/include/clipper2/clipper.rectclip.h @@ -1,8 +1,8 @@ /******************************************************************************* * Author : Angus Johnson * -* Date : 1 November 2023 * +* Date : 5 July 2024 * * Website : http://www.angusj.com * -* Copyright : Angus Johnson 2010-2023 * +* Copyright : Angus Johnson 2010-2024 * * Purpose : FAST rectangular clipping * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ @@ -18,6 +18,7 @@ namespace Clipper2Lib { + // Location: the order is important here, see StartLocsIsClockwise() enum class Location { Left, Top, Right, Bottom, Inside }; class OutPt2; @@ -26,10 +27,10 @@ namespace Clipper2Lib class OutPt2 { public: Point64 pt; - size_t owner_idx; - OutPt2List* edge; - OutPt2* next; - OutPt2* prev; + size_t owner_idx = 0; + OutPt2List* edge = nullptr; + OutPt2* next = nullptr; + OutPt2* prev = nullptr; }; //------------------------------------------------------------------------------ @@ -50,9 +51,9 @@ namespace Clipper2Lib OutPt2List edges_[8]; // clockwise and counter-clockwise std::vector<Location> start_locs_; void CheckEdges(); - void TidyEdges(int idx, OutPt2List& cw, OutPt2List& ccw); + void TidyEdges(size_t idx, OutPt2List& cw, OutPt2List& ccw); void GetNextLocation(const Path64& path, - Location& loc, int& i, int highI); + Location& loc, size_t& i, size_t highI); OutPt2* Add(Point64 pt, bool start_new = false); void AddCorner(Location prev, Location curr); void AddCorner(Location& loc, bool isClockwise); diff --git a/thirdparty/clipper2/include/clipper2/clipper.version.h b/thirdparty/clipper2/include/clipper2/clipper.version.h index d7644067e2..61464095f6 100644 --- a/thirdparty/clipper2/include/clipper2/clipper.version.h +++ b/thirdparty/clipper2/include/clipper2/clipper.version.h @@ -1,6 +1,6 @@ #ifndef CLIPPER_VERSION_H #define CLIPPER_VERSION_H -constexpr auto CLIPPER2_VERSION = "1.3.0"; +constexpr auto CLIPPER2_VERSION = "1.4.0"; #endif // CLIPPER_VERSION_H |