Merge pull request #886 from Spartan322/merge/f128f38HEADmaster

Merge commit godotengine/godot@f128f38

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