/******************************************************************************* * Author : Angus Johnson * * Date : 22 November 2023 * * Website : http://www.angusj.com * * Copyright : Angus Johnson 2010-2023 * * Purpose : This is the main polygon clipping module * * License : http://www.boost.org/LICENSE_1_0.txt * *******************************************************************************/ #include <cstdlib> #include <cmath> #include <stdexcept> #include <vector> #include <numeric> #include <algorithm> #include "clipper2/clipper.engine.h" #include "clipper2/clipper.h" // https://github.com/AngusJohnson/Clipper2/discussions/334 // #discussioncomment-4248602 #if defined(_MSC_VER) && ( defined(_M_AMD64) || defined(_M_X64) ) #include <xmmintrin.h> #include <emmintrin.h> #define fmin … #define fmax … #define nearbyint … #endif namespace Clipper2Lib { static const Rect64 invalid_rect = …; // Every closed path (or polygon) is made up of a series of vertices forming // edges that alternate between going up (relative to the Y-axis) and going // down. Edges consecutively going up or consecutively going down are called // 'bounds' (ie sides if they're simple polygons). 'Local Minima' refer to // vertices where descending bounds become ascending ones. struct Scanline { … }; struct HorzSegSorter { … }; struct LocMinSorter { … }; inline bool IsOdd(int val) { … } inline bool IsHotEdge(const Active& e) { … } inline bool IsOpen(const Active& e) { … } inline bool IsOpenEnd(const Vertex& v) { … } inline bool IsOpenEnd(const Active& ae) { … } inline Active* GetPrevHotEdge(const Active& e) { … } inline bool IsFront(const Active& e) { … } inline bool IsInvalidPath(OutPt* op) { … } /******************************************************************************* * Dx: 0(90deg) * * | * * +inf (180deg) <--- o ---> -inf (0deg) * *******************************************************************************/ inline double GetDx(const Point64& pt1, const Point64& pt2) { … } inline int64_t TopX(const Active& ae, const int64_t currentY) { … } inline bool IsHorizontal(const Active& e) { … } inline bool IsHeadingRightHorz(const Active& e) { … } inline bool IsHeadingLeftHorz(const Active& e) { … } inline void SwapActives(Active*& e1, Active*& e2) { … } inline PathType GetPolyType(const Active& e) { … } inline bool IsSamePolyType(const Active& e1, const Active& e2) { … } inline void SetDx(Active& e) { … } inline Vertex* NextVertex(const Active& e) { … } //PrevPrevVertex: useful to get the (inverted Y-axis) top of the //alternate edge (ie left or right bound) during edge insertion. inline Vertex* PrevPrevVertex(const Active& ae) { … } inline Active* ExtractFromSEL(Active* ae) { … } inline void Insert1Before2InSEL(Active* ae1, Active* ae2) { … } inline bool IsMaxima(const Vertex& v) { … } inline bool IsMaxima(const Active& e) { … } inline Vertex* GetCurrYMaximaVertex_Open(const Active& e) { … } inline Vertex* GetCurrYMaximaVertex(const Active& e) { … } Active* GetMaximaPair(const Active& e) { … } inline int PointCount(OutPt* op) { … } inline OutPt* DuplicateOp(OutPt* op, bool insert_after) { … } inline OutPt* DisposeOutPt(OutPt* op) { … } inline void DisposeOutPts(OutRec* outrec) { … } bool IntersectListSort(const IntersectNode& a, const IntersectNode& b) { … } inline void SetSides(OutRec& outrec, Active& start_edge, Active& end_edge) { … } void SwapOutrecs(Active& e1, Active& e2) { … } double Area(OutPt* op) { … } inline double AreaTriangle(const Point64& pt1, const Point64& pt2, const Point64& pt3) { … } void ReverseOutPts(OutPt* op) { … } inline void SwapSides(OutRec& outrec) { … } inline OutRec* GetRealOutRec(OutRec* outrec) { … } inline bool IsValidOwner(OutRec* outrec, OutRec* testOwner) { … } inline void UncoupleOutRec(Active ae) { … } inline bool PtsReallyClose(const Point64& pt1, const Point64& pt2) { … } inline bool IsVerySmallTriangle(const OutPt& op) { … } inline bool IsValidClosedPath(const OutPt* op) { … } inline bool OutrecIsAscending(const Active* hotEdge) { … } inline void SwapFrontBackSides(OutRec& outrec) { … } inline bool EdgesAdjacentInAEL(const IntersectNode& inode) { … } inline bool IsJoined(const Active& e) { … } inline void SetOwner(OutRec* outrec, OutRec* new_owner) { … } static PointInPolygonResult PointInOpPolygon(const Point64& pt, OutPt* op) { … } inline Path64 GetCleanPath(OutPt* op) { … } inline bool Path1InsidePath2(OutPt* op1, OutPt* op2) { … } //------------------------------------------------------------------------------ //------------------------------------------------------------------------------ void AddLocMin(LocalMinimaList& list, Vertex& vert, PathType polytype, bool is_open) { … } void AddPaths_(const Paths64& paths, PathType polytype, bool is_open, std::vector<Vertex*>& vertexLists, LocalMinimaList& locMinList) { … } //------------------------------------------------------------------------------ // ReuseableDataContainer64 methods ... //------------------------------------------------------------------------------ void ReuseableDataContainer64::AddLocMin(Vertex& vert, PathType polytype, bool is_open) { … } void ReuseableDataContainer64::AddPaths(const Paths64& paths, PathType polytype, bool is_open) { … } ReuseableDataContainer64::~ReuseableDataContainer64() { … } void ReuseableDataContainer64::Clear() { … } //------------------------------------------------------------------------------ // ClipperBase methods ... //------------------------------------------------------------------------------ ClipperBase::~ClipperBase() { … } void ClipperBase::DeleteEdges(Active*& e) { … } void ClipperBase::CleanUp() { … } void ClipperBase::Clear() { … } void ClipperBase::Reset() { … } #ifdef USINGZ void ClipperBase::SetZ(const Active& e1, const Active& e2, Point64& ip) { if (!zCallback_) return; // prioritize subject over clip vertices by passing // subject vertices before clip vertices in the callback if (GetPolyType(e1) == PathType::Subject) { if (ip == e1.bot) ip.z = e1.bot.z; else if (ip == e1.top) ip.z = e1.top.z; else if (ip == e2.bot) ip.z = e2.bot.z; else if (ip == e2.top) ip.z = e2.top.z; else ip.z = DefaultZ; zCallback_(e1.bot, e1.top, e2.bot, e2.top, ip); } else { if (ip == e2.bot) ip.z = e2.bot.z; else if (ip == e2.top) ip.z = e2.top.z; else if (ip == e1.bot) ip.z = e1.bot.z; else if (ip == e1.top) ip.z = e1.top.z; else ip.z = DefaultZ; zCallback_(e2.bot, e2.top, e1.bot, e1.top, ip); } } #endif void ClipperBase::AddPath(const Path64& path, PathType polytype, bool is_open) { … } void ClipperBase::AddPaths(const Paths64& paths, PathType polytype, bool is_open) { … } void ClipperBase::AddReuseableData(const ReuseableDataContainer64& reuseable_data) { … } void ClipperBase::InsertScanline(int64_t y) { … } bool ClipperBase::PopScanline(int64_t& y) { … } bool ClipperBase::PopLocalMinima(int64_t y, LocalMinima*& local_minima) { … } void ClipperBase::DisposeAllOutRecs() { … } void ClipperBase::DisposeVerticesAndLocalMinima() { … } void ClipperBase::AddLocMin(Vertex& vert, PathType polytype, bool is_open) { … } bool ClipperBase::IsContributingClosed(const Active& e) const { … } inline bool ClipperBase::IsContributingOpen(const Active& e) const { … } void ClipperBase::SetWindCountForClosedPathEdge(Active& e) { … } void ClipperBase::SetWindCountForOpenPathEdge(Active& e) { … } bool IsValidAelOrder(const Active& resident, const Active& newcomer) { … } void ClipperBase::InsertLeftEdge(Active& e) { … } void InsertRightEdge(Active& e, Active& e2) { … } void ClipperBase::InsertLocalMinimaIntoAEL(int64_t bot_y) { … } inline void ClipperBase::PushHorz(Active& e) { … } inline bool ClipperBase::PopHorz(Active*& e) { … } OutPt* ClipperBase::AddLocalMinPoly(Active& e1, Active& e2, const Point64& pt, bool is_new) { … } OutPt* ClipperBase::AddLocalMaxPoly(Active& e1, Active& e2, const Point64& pt) { … } void ClipperBase::JoinOutrecPaths(Active& e1, Active& e2) { … } OutRec* ClipperBase::NewOutRec() { … } OutPt* ClipperBase::AddOutPt(const Active& e, const Point64& pt) { … } void ClipperBase::CleanCollinear(OutRec* outrec) { … } void ClipperBase::DoSplitOp(OutRec* outrec, OutPt* splitOp) { … } void ClipperBase::FixSelfIntersects(OutRec* outrec) { … } inline void UpdateOutrecOwner(OutRec* outrec) { … } OutPt* ClipperBase::StartOpenPath(Active& e, const Point64& pt) { … } inline void TrimHorz(Active& horzEdge, bool preserveCollinear) { … } inline void ClipperBase::UpdateEdgeIntoAEL(Active* e) { … } Active* FindEdgeWithMatchingLocMin(Active* e) { … } OutPt* ClipperBase::IntersectEdges(Active& e1, Active& e2, const Point64& pt) { … } inline void ClipperBase::DeleteFromAEL(Active& e) { … } inline void ClipperBase::AdjustCurrXAndCopyToSEL(const int64_t top_y) { … } bool ClipperBase::ExecuteInternal(ClipType ct, FillRule fillrule, bool use_polytrees) { … } inline void FixOutRecPts(OutRec* outrec) { … } inline bool SetHorzSegHeadingForward(HorzSegment& hs, OutPt* opP, OutPt* opN) { … } inline bool UpdateHorzSegment(HorzSegment& hs) { … } void ClipperBase::ConvertHorzSegsToJoins() { … } void MoveSplits(OutRec* fromOr, OutRec* toOr) { … } void ClipperBase::ProcessHorzJoins() { … } void ClipperBase::DoIntersections(const int64_t top_y) { … } void ClipperBase::AddNewIntersectNode(Active& e1, Active& e2, int64_t top_y) { … } bool ClipperBase::BuildIntersectList(const int64_t top_y) { … } void ClipperBase::ProcessIntersectList() { … } void ClipperBase::SwapPositionsInAEL(Active& e1, Active& e2) { … } inline OutPt* GetLastOp(const Active& hot_edge) { … } void ClipperBase::AddTrialHorzJoin(OutPt* op) { … } bool ClipperBase::ResetHorzDirection(const Active& horz, const Vertex* max_vertex, int64_t& horz_left, int64_t& horz_right) { … } void ClipperBase::DoHorizontal(Active& horz) /******************************************************************************* * Notes: Horizontal edges (HEs) at scanline intersections (ie at the top or * * bottom of a scanbeam) are processed as if layered.The order in which HEs * * are processed doesn't matter. HEs intersect with the bottom vertices of * * other HEs[#] and with non-horizontal edges [*]. Once these intersections * * are completed, intermediate HEs are 'promoted' to the next edge in their * * bounds, and they in turn may be intersected[%] by other HEs. * * * * eg: 3 horizontals at a scanline: / | / / * * | / | (HE3)o ========%========== o * * o ======= o(HE2) / | / / * * o ============#=========*======*========#=========o (HE1) * * / | / | / * *******************************************************************************/ { … } void ClipperBase::DoTopOfScanbeam(const int64_t y) { … } Active* ClipperBase::DoMaxima(Active& e) { … } void ClipperBase::Split(Active& e, const Point64& pt) { … } void ClipperBase::CheckJoinLeft(Active& e, const Point64& pt, bool check_curr_x) { … } void ClipperBase::CheckJoinRight(Active& e, const Point64& pt, bool check_curr_x) { … } inline bool GetHorzExtendedHorzSeg(OutPt*& op, OutPt*& op2) { … } bool BuildPath64(OutPt* op, bool reverse, bool isOpen, Path64& path) { … } bool ClipperBase::CheckBounds(OutRec* outrec) { … } bool ClipperBase::CheckSplitOwner(OutRec* outrec, OutRecList* splits) { … } void ClipperBase::RecursiveCheckOwners(OutRec* outrec, PolyPath* polypath) { … } void Clipper64::BuildPaths64(Paths64& solutionClosed, Paths64* solutionOpen) { … } void Clipper64::BuildTree64(PolyPath64& polytree, Paths64& open_paths) { … } bool BuildPathD(OutPt* op, bool reverse, bool isOpen, PathD& path, double inv_scale) { … } void ClipperD::BuildPathsD(PathsD& solutionClosed, PathsD* solutionOpen) { … } void ClipperD::BuildTreeD(PolyPathD& polytree, PathsD& open_paths) { … } } // namespace clipper2lib
Codebase Browser
godot