/******************************************************************************* * Author : Angus Johnson * * Date : 12 May 2024 * * Website : http://www.angusj.com * * Copyright : Angus Johnson 2010-2024 * * Purpose : Core Clipper Library structures and functions * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ #ifndef CLIPPER_CORE_H #define CLIPPER_CORE_H #include <cstdint> #include <cstdlib> #include <cmath> #include <vector> #include <string> #include <iostream> #include <algorithm> #include <climits> #include <numeric> #include <optional> #include "clipper2/clipper.version.h" #define CLIPPER2_THROW(exception) … namespace Clipper2Lib { #if (defined(__cpp_exceptions) && __cpp_exceptions) || (defined(__EXCEPTIONS) && __EXCEPTIONS) class Clipper2Exception : public std::exception { public: explicit Clipper2Exception(const char* description) : m_descr(description) {} virtual const char* what() const throw() override { return m_descr.c_str(); } private: std::string m_descr; }; static const char* precision_error = "Precision exceeds the permitted range"; static const char* range_error = "Values exceed permitted range"; static const char* scale_error = "Invalid scale (either 0 or too large)"; static const char* non_pair_error = "There must be 2 values for each coordinate"; static const char* undefined_error = "There is an undefined error in Clipper2"; #endif // error codes (2^n) const int precision_error_i = …; // non-fatal const int scale_error_i = …; // non-fatal const int non_pair_error_i = …; // non-fatal const int undefined_error_i = …; // fatal const int range_error_i = …; #ifndef PI static const double PI = …; #endif #ifdef CLIPPER2_MAX_DECIMAL_PRECISION const int CLIPPER2_MAX_DEC_PRECISION = CLIPPER2_MAX_DECIMAL_PRECISION; #else const int CLIPPER2_MAX_DEC_PRECISION = …; // see Discussions #564 #endif static const int64_t MAX_COORD = …; static const int64_t MIN_COORD = …; static const int64_t INVALID = …; const double max_coord = …; const double min_coord = …; static const double MAX_DBL = …; static void DoError([[maybe_unused]] int error_code) { … } // can we call std::round on T? (default false) (#824) template <typename T, typename = void> struct is_round_invocable : std::false_type { … }; is_round_invocable<T, std::void_t<decltype(std::round(std::declval<T>()))>>; //By far the most widely used filling rules for polygons are EvenOdd //and NonZero, sometimes called Alternate and Winding respectively. //https://en.wikipedia.org/wiki/Nonzero-rule enum class FillRule { … }; // Point ------------------------------------------------------------------------ template <typename T> struct Point { … }; //nb: using 'using' here (instead of typedef) as they can be used in templates Point64; PointD; Path; Paths; Path64; PathD; Paths64; PathsD; static const Point64 InvalidPoint64 = …; static const PointD InvalidPointD = …; template<typename T> static inline Point<T> MidPoint(const Point<T>& p1, const Point<T>& p2) { … } // Rect ------------------------------------------------------------------------ template <typename T> struct Rect; Rect64; RectD; template <typename T> struct Rect { … }; template <typename T1, typename T2> inline Rect<T1> ScaleRect(const Rect<T2>& rect, double scale) { … } static const Rect64 InvalidRect64 = …; static const RectD InvalidRectD = …; template <typename T> Rect<T> GetBounds(const Path<T>& path) { … } template <typename T> Rect<T> GetBounds(const Paths<T>& paths) { … } template <typename T, typename T2> Rect<T> GetBounds(const Path<T2>& path) { … } template <typename T, typename T2> Rect<T> GetBounds(const Paths<T2>& paths) { … } template <typename T> std::ostream& operator << (std::ostream& outstream, const Path<T>& path) { … } template <typename T> std::ostream& operator << (std::ostream& outstream, const Paths<T>& paths) { … } template <typename T1, typename T2> inline Path<T1> ScalePath(const Path<T2>& path, double scale_x, double scale_y, int& error_code) { … } template <typename T1, typename T2> inline Path<T1> ScalePath(const Path<T2>& path, double scale, int& error_code) { … } template <typename T1, typename T2> inline Paths<T1> ScalePaths(const Paths<T2>& paths, double scale_x, double scale_y, int& error_code) { … } template <typename T1, typename T2> inline Paths<T1> ScalePaths(const Paths<T2>& paths, double scale, int& error_code) { … } template <typename T1, typename T2> inline Path<T1> TransformPath(const Path<T2>& path) { … } template <typename T1, typename T2> inline Paths<T1> TransformPaths(const Paths<T2>& paths) { … } template<typename T> inline double Sqr(T val) { … } template<typename T> inline bool NearEqual(const Point<T>& p1, const Point<T>& p2, double max_dist_sqrd) { … } template<typename T> inline Path<T> StripNearEqual(const Path<T>& path, double max_dist_sqrd, bool is_closed_path) { … } template<typename T> inline Paths<T> StripNearEqual(const Paths<T>& paths, double max_dist_sqrd, bool is_closed_path) { … } template<typename T> inline void StripDuplicates( Path<T>& path, bool is_closed_path) { … } template<typename T> inline void StripDuplicates( Paths<T>& paths, bool is_closed_path) { … } // Miscellaneous ------------------------------------------------------------ inline void CheckPrecisionRange(int& precision, int& error_code) { … } inline void CheckPrecisionRange(int& precision) { … } inline int TriSign(int64_t x) // returns 0, 1 or -1 { … } struct MultiplyUInt64Result { … }; inline MultiplyUInt64Result Multiply(uint64_t a, uint64_t b) // #834, #835 { … } // 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) { … } template <typename T> inline bool IsCollinear(const Point<T>& pt1, const Point<T>& sharedPt, const Point<T>& pt2) // #777 { … } template <typename T> inline double CrossProduct(const Point<T>& pt1, const Point<T>& pt2, const Point<T>& pt3) { … } template <typename T> inline double CrossProduct(const Point<T>& vec1, const Point<T>& vec2) { … } template <typename T> inline double DotProduct(const Point<T>& pt1, const Point<T>& pt2, const Point<T>& pt3) { … } template <typename T> inline double DotProduct(const Point<T>& vec1, const Point<T>& vec2) { … } template <typename T> inline double DistanceSqr(const Point<T> pt1, const Point<T> pt2) { … } template <typename T> inline double PerpendicDistFromLineSqrd(const Point<T>& pt, const Point<T>& line1, const Point<T>& line2) { … } template <typename T> inline double Area(const Path<T>& path) { … } template <typename T> inline double Area(const Paths<T>& paths) { … } template <typename T> inline bool IsPositive(const Path<T>& poly) { … } #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 … #define CC_MAX … 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) { … } #endif template<typename T> inline Point<T> TranslatePoint(const Point<T>& pt, double dx, double dy) { … } template<typename T> inline Point<T> ReflectPoint(const Point<T>& pt, const Point<T>& pivot) { … } template<typename T> inline int GetSign(const T& val) { … } inline bool SegmentsIntersect(const Point64& seg1a, const Point64& seg1b, const Point64& seg2a, const Point64& seg2b, bool inclusive = false) { … } template<typename T> inline Point<T> GetClosestPointOnSegment(const Point<T>& offPt, const Point<T>& seg1, const Point<T>& seg2) { … } enum class PointInPolygonResult { … }; template <typename T> inline PointInPolygonResult PointInPolygon(const Point<T>& pt, const Path<T>& polygon) { … } } // namespace #endif // CLIPPER_CORE_H
Codebase Browser
godot