summaryrefslogtreecommitdiffstats
path: root/thirdparty/clipper2/src
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/clipper2/src')
-rw-r--r--thirdparty/clipper2/src/clipper.engine.cpp225
-rw-r--r--thirdparty/clipper2/src/clipper.offset.cpp364
-rw-r--r--thirdparty/clipper2/src/clipper.rectclip.cpp111
3 files changed, 348 insertions, 352 deletions
diff --git a/thirdparty/clipper2/src/clipper.engine.cpp b/thirdparty/clipper2/src/clipper.engine.cpp
index 9358b74b70..8f120267c3 100644
--- a/thirdparty/clipper2/src/clipper.engine.cpp
+++ b/thirdparty/clipper2/src/clipper.engine.cpp
@@ -1,8 +1,8 @@
/*******************************************************************************
* Author : Angus Johnson *
-* Date : 22 November 2023 *
+* Date : 27 April 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 *
*******************************************************************************/
@@ -31,11 +31,11 @@ namespace Clipper2Lib {
static const Rect64 invalid_rect = Rect64(false);
- // 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.
+ // Every closed path (ie polygon) is made up of a series of vertices forming edge
+ // 'bounds' that alternate between ascending bounds (containing edges going up
+ // relative to the Y-axis) and descending bounds. 'Local Minima' refers to
+ // vertices where ascending and descending bounds join at the bottom, and
+ // 'Local Maxima' are where ascending and descending bounds join at the top.
struct Scanline {
int64_t y = 0;
@@ -63,6 +63,7 @@ namespace Clipper2Lib {
}
};
+
inline bool IsOdd(int val)
{
return (val & 1) ? true : false;
@@ -188,7 +189,7 @@ namespace Clipper2Lib {
}
//PrevPrevVertex: useful to get the (inverted Y-axis) top of the
- //alternate edge (ie left or right bound) during edge insertion.
+ //alternate edge (ie left or right bound) during edge insertion.
inline Vertex* PrevPrevVertex(const Active& ae)
{
if (ae.wind_dx > 0)
@@ -233,15 +234,15 @@ namespace Clipper2Lib {
Vertex* result = e.vertex_top;
if (e.wind_dx > 0)
while ((result->next->pt.y == result->pt.y) &&
- ((result->flags & (VertexFlags::OpenEnd |
+ ((result->flags & (VertexFlags::OpenEnd |
VertexFlags::LocalMax)) == VertexFlags::None))
result = result->next;
else
while (result->prev->pt.y == result->pt.y &&
- ((result->flags & (VertexFlags::OpenEnd |
+ ((result->flags & (VertexFlags::OpenEnd |
VertexFlags::LocalMax)) == VertexFlags::None))
result = result->prev;
- if (!IsMaxima(*result)) result = nullptr; // not a maxima
+ if (!IsMaxima(*result)) result = nullptr; // not a maxima
return result;
}
@@ -252,7 +253,7 @@ namespace Clipper2Lib {
while (result->next->pt.y == result->pt.y) result = result->next;
else
while (result->prev->pt.y == result->pt.y) result = result->prev;
- if (!IsMaxima(*result)) result = nullptr; // not a maxima
+ if (!IsMaxima(*result)) result = nullptr; // not a maxima
return result;
}
@@ -613,13 +614,13 @@ namespace Clipper2Lib {
list.push_back(std::make_unique <LocalMinima>(&vert, polytype, is_open));
}
- void AddPaths_(const Paths64& paths, PathType polytype, bool is_open,
+ void AddPaths_(const Paths64& paths, PathType polytype, bool is_open,
std::vector<Vertex*>& vertexLists, LocalMinimaList& locMinList)
{
const auto total_vertex_count =
- std::accumulate(paths.begin(), paths.end(), 0,
+ std::accumulate(paths.begin(), paths.end(), size_t(0),
[](const auto& a, const Path64& path)
- {return a + static_cast<unsigned>(path.size()); });
+ {return a + path.size(); });
if (total_vertex_count == 0) return;
Vertex* vertices = new Vertex[total_vertex_count], * v = vertices;
@@ -810,7 +811,7 @@ namespace Clipper2Lib {
void ClipperBase::SetZ(const Active& e1, const Active& e2, Point64& ip)
{
if (!zCallback_) return;
- // prioritize subject over clip vertices by passing
+ // prioritize subject over clip vertices by passing
// subject vertices before clip vertices in the callback
if (GetPolyType(e1) == PathType::Subject)
{
@@ -845,11 +846,11 @@ namespace Clipper2Lib {
if (is_open) has_open_paths_ = true;
minima_list_sorted_ = false;
AddPaths_(paths, polytype, is_open, vertex_lists_, minima_list_);
- }
+ }
- void ClipperBase::AddReuseableData(const ReuseableDataContainer64& reuseable_data)
+ void ClipperBase::AddReuseableData(const ReuseableDataContainer64& reuseable_data)
{
- // nb: reuseable_data will continue to own the vertices
+ // nb: reuseable_data will continue to own the vertices
// and remains responsible for their clean up.
succeeded_ = false;
minima_list_sorted_ = false;
@@ -1117,7 +1118,6 @@ namespace Clipper2Lib {
}
}
-
bool IsValidAelOrder(const Active& resident, const Active& newcomer)
{
if (newcomer.curr_x != resident.curr_x)
@@ -1149,8 +1149,8 @@ namespace Clipper2Lib {
//resident must also have just been inserted
else if (resident.is_left_bound != newcomerIsLeft)
return newcomerIsLeft;
- else if (CrossProduct(PrevPrevVertex(resident)->pt,
- resident.bot, resident.top) == 0) return true;
+ else if (IsCollinear(PrevPrevVertex(resident)->pt,
+ resident.bot, resident.top)) return true;
else
//compare turning direction of the alternate bound
return (CrossProduct(PrevPrevVertex(resident)->pt,
@@ -1385,7 +1385,7 @@ namespace Clipper2Lib {
{
if (IsJoined(e1)) Split(e1, pt);
if (IsJoined(e2)) Split(e2, pt);
-
+
if (IsFront(e1) == IsFront(e2))
{
if (IsOpenEnd(e1))
@@ -1409,7 +1409,7 @@ namespace Clipper2Lib {
{
Active* e = GetPrevHotEdge(e1);
if (!e)
- outrec.owner = nullptr;
+ outrec.owner = nullptr;
else
SetOwner(&outrec, e->outrec);
// nb: outRec.owner here is likely NOT the real
@@ -1476,7 +1476,7 @@ namespace Clipper2Lib {
e2.outrec->pts = e1.outrec->pts;
e1.outrec->pts = nullptr;
}
- else
+ else
SetOwner(e2.outrec, e1.outrec);
//and e1 and e2 are maxima and are about to be dropped from the Actives list.
@@ -1526,7 +1526,6 @@ namespace Clipper2Lib {
return new_op;
}
-
void ClipperBase::CleanCollinear(OutRec* outrec)
{
outrec = GetRealOutRec(outrec);
@@ -1541,7 +1540,7 @@ namespace Clipper2Lib {
for (; ; )
{
//NB if preserveCollinear == true, then only remove 180 deg. spikes
- if ((CrossProduct(op2->prev->pt, op2->pt, op2->next->pt) == 0) &&
+ if (IsCollinear(op2->prev->pt, op2->pt, op2->next->pt) &&
(op2->pt == op2->prev->pt ||
op2->pt == op2->next->pt || !preserve_collinear_ ||
DotProduct(op2->prev->pt, op2->pt, op2->next->pt) < 0))
@@ -1566,14 +1565,14 @@ namespace Clipper2Lib {
void ClipperBase::DoSplitOp(OutRec* outrec, OutPt* splitOp)
{
- // splitOp.prev -> splitOp &&
+ // splitOp.prev -> splitOp &&
// splitOp.next -> splitOp.next.next are intersecting
OutPt* prevOp = splitOp->prev;
OutPt* nextNextOp = splitOp->next->next;
outrec->pts = prevOp;
Point64 ip;
- GetIntersectPoint(prevOp->pt, splitOp->pt,
+ GetSegmentIntersectPt(prevOp->pt, splitOp->pt,
splitOp->next->pt, nextNextOp->pt, ip);
#ifdef USINGZ
@@ -1617,7 +1616,7 @@ namespace Clipper2Lib {
{
OutRec* newOr = NewOutRec();
newOr->owner = outrec->owner;
-
+
splitOp->outrec = newOr;
splitOp->next->outrec = newOr;
OutPt* newOp = new OutPt(ip, newOr);
@@ -1772,12 +1771,12 @@ namespace Clipper2Lib {
}
- OutPt* ClipperBase::IntersectEdges(Active& e1, Active& e2, const Point64& pt)
+ void ClipperBase::IntersectEdges(Active& e1, Active& e2, const Point64& pt)
{
//MANAGE OPEN PATH INTERSECTIONS SEPARATELY ...
if (has_open_paths_ && (IsOpen(e1) || IsOpen(e2)))
{
- if (IsOpen(e1) && IsOpen(e2)) return nullptr;
+ if (IsOpen(e1) && IsOpen(e2)) return;
Active* edge_o, * edge_c;
if (IsOpen(e1))
{
@@ -1791,29 +1790,40 @@ namespace Clipper2Lib {
}
if (IsJoined(*edge_c)) Split(*edge_c, pt); // needed for safety
- if (abs(edge_c->wind_cnt) != 1) return nullptr;
+ if (abs(edge_c->wind_cnt) != 1) return;
switch (cliptype_)
{
case ClipType::Union:
- if (!IsHotEdge(*edge_c)) return nullptr;
+ if (!IsHotEdge(*edge_c)) return;
break;
default:
if (edge_c->local_min->polytype == PathType::Subject)
- return nullptr;
+ return;
}
switch (fillrule_)
{
- case FillRule::Positive: if (edge_c->wind_cnt != 1) return nullptr; break;
- case FillRule::Negative: if (edge_c->wind_cnt != -1) return nullptr; break;
- default: if (std::abs(edge_c->wind_cnt) != 1) return nullptr; break;
+ case FillRule::Positive:
+ if (edge_c->wind_cnt != 1) return;
+ break;
+ case FillRule::Negative:
+ if (edge_c->wind_cnt != -1) return;
+ break;
+ default:
+ if (std::abs(edge_c->wind_cnt) != 1) return;
}
+#ifdef USINGZ
OutPt* resultOp;
+#endif
//toggle contribution ...
if (IsHotEdge(*edge_o))
{
+#ifdef USINGZ
resultOp = AddOutPt(*edge_o, pt);
+#else
+ AddOutPt(*edge_o, pt);
+#endif
if (IsFront(*edge_o)) edge_o->outrec->front_edge = nullptr;
else edge_o->outrec->back_edge = nullptr;
edge_o->outrec = nullptr;
@@ -1833,18 +1843,26 @@ namespace Clipper2Lib {
SetSides(*e3->outrec, *edge_o, *e3);
else
SetSides(*e3->outrec, *e3, *edge_o);
- return e3->outrec->pts;
+ return;
}
else
+#ifdef USINGZ
resultOp = StartOpenPath(*edge_o, pt);
+#else
+ StartOpenPath(*edge_o, pt);
+#endif
}
else
+#ifdef USINGZ
resultOp = StartOpenPath(*edge_o, pt);
+#else
+ StartOpenPath(*edge_o, pt);
+#endif
#ifdef USINGZ
if (zCallback_) SetZ(*edge_o, *edge_c, resultOp->pt);
#endif
- return resultOp;
+ return;
} // end of an open path intersection
//MANAGING CLOSED PATHS FROM HERE ON
@@ -1913,22 +1931,25 @@ namespace Clipper2Lib {
const bool e1_windcnt_in_01 = old_e1_windcnt == 0 || old_e1_windcnt == 1;
const bool e2_windcnt_in_01 = old_e2_windcnt == 0 || old_e2_windcnt == 1;
- if ((!IsHotEdge(e1) && !e1_windcnt_in_01) || (!IsHotEdge(e2) && !e2_windcnt_in_01))
- {
- return nullptr;
- }
+ if ((!IsHotEdge(e1) && !e1_windcnt_in_01) ||
+ (!IsHotEdge(e2) && !e2_windcnt_in_01))
+ return;
//NOW PROCESS THE INTERSECTION ...
+#ifdef USINGZ
OutPt* resultOp = nullptr;
+#endif
//if both edges are 'hot' ...
if (IsHotEdge(e1) && IsHotEdge(e2))
{
if ((old_e1_windcnt != 0 && old_e1_windcnt != 1) || (old_e2_windcnt != 0 && old_e2_windcnt != 1) ||
(e1.local_min->polytype != e2.local_min->polytype && cliptype_ != ClipType::Xor))
{
- resultOp = AddLocalMaxPoly(e1, e2, pt);
#ifdef USINGZ
+ resultOp = AddLocalMaxPoly(e1, e2, pt);
if (zCallback_ && resultOp) SetZ(e1, e2, resultOp->pt);
+#else
+ AddLocalMaxPoly(e1, e2, pt);
#endif
}
else if (IsFront(e1) || (e1.outrec == e2.outrec))
@@ -1937,19 +1958,20 @@ namespace Clipper2Lib {
//it's sensible to split polygons that ony touch at
//a common vertex (not at common edges).
- resultOp = AddLocalMaxPoly(e1, e2, pt);
#ifdef USINGZ
+ resultOp = AddLocalMaxPoly(e1, e2, pt);
OutPt* op2 = AddLocalMinPoly(e1, e2, pt);
if (zCallback_ && resultOp) SetZ(e1, e2, resultOp->pt);
if (zCallback_) SetZ(e1, e2, op2->pt);
#else
+ AddLocalMaxPoly(e1, e2, pt);
AddLocalMinPoly(e1, e2, pt);
#endif
}
else
{
- resultOp = AddOutPt(e1, pt);
#ifdef USINGZ
+ resultOp = AddOutPt(e1, pt);
OutPt* op2 = AddOutPt(e2, pt);
if (zCallback_)
{
@@ -1957,6 +1979,7 @@ namespace Clipper2Lib {
SetZ(e1, e2, op2->pt);
}
#else
+ AddOutPt(e1, pt);
AddOutPt(e2, pt);
#endif
SwapOutrecs(e1, e2);
@@ -1964,17 +1987,21 @@ namespace Clipper2Lib {
}
else if (IsHotEdge(e1))
{
- resultOp = AddOutPt(e1, pt);
#ifdef USINGZ
+ resultOp = AddOutPt(e1, pt);
if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#else
+ AddOutPt(e1, pt);
#endif
SwapOutrecs(e1, e2);
}
else if (IsHotEdge(e2))
{
- resultOp = AddOutPt(e2, pt);
#ifdef USINGZ
+ resultOp = AddOutPt(e2, pt);
if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#else
+ AddOutPt(e2, pt);
#endif
SwapOutrecs(e1, e2);
}
@@ -2004,33 +2031,53 @@ namespace Clipper2Lib {
if (!IsSamePolyType(e1, e2))
{
- resultOp = AddLocalMinPoly(e1, e2, pt, false);
#ifdef USINGZ
+ resultOp = AddLocalMinPoly(e1, e2, pt, false);
if (zCallback_) SetZ(e1, e2, resultOp->pt);
+#else
+ AddLocalMinPoly(e1, e2, pt, false);
#endif
}
else if (old_e1_windcnt == 1 && old_e2_windcnt == 1)
{
+#ifdef USINGZ
resultOp = nullptr;
+#endif
switch (cliptype_)
{
case ClipType::Union:
if (e1Wc2 <= 0 && e2Wc2 <= 0)
+#ifdef USINGZ
resultOp = AddLocalMinPoly(e1, e2, pt, false);
+#else
+ AddLocalMinPoly(e1, e2, pt, false);
+#endif
break;
case ClipType::Difference:
if (((GetPolyType(e1) == PathType::Clip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
((GetPolyType(e1) == PathType::Subject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
{
+#ifdef USINGZ
resultOp = AddLocalMinPoly(e1, e2, pt, false);
+#else
+ AddLocalMinPoly(e1, e2, pt, false);
+#endif
}
break;
case ClipType::Xor:
+#ifdef USINGZ
resultOp = AddLocalMinPoly(e1, e2, pt, false);
+#else
+ AddLocalMinPoly(e1, e2, pt, false);
+#endif
break;
default:
if (e1Wc2 > 0 && e2Wc2 > 0)
+#ifdef USINGZ
resultOp = AddLocalMinPoly(e1, e2, pt, false);
+#else
+ AddLocalMinPoly(e1, e2, pt, false);
+#endif
break;
}
#ifdef USINGZ
@@ -2038,7 +2085,6 @@ namespace Clipper2Lib {
#endif
}
}
- return resultOp;
}
inline void ClipperBase::DeleteFromAEL(Active& e)
@@ -2065,7 +2111,7 @@ namespace Clipper2Lib {
e->next_in_sel = e->next_in_ael;
e->jump = e->next_in_sel;
if (e->join_with == JoinWith::Left)
- e->curr_x = e->prev_in_ael->curr_x; // also avoids complications
+ e->curr_x = e->prev_in_ael->curr_x; // also avoids complications
else
e->curr_x = TopX(*e, top_y);
e = e->next_in_ael;
@@ -2138,7 +2184,7 @@ namespace Clipper2Lib {
if (outrecHasEdges)
{
OutPt* opA = outrec->pts, * opZ = opA->next;
- while (opP != opZ && opP->prev->pt.y == curr_y)
+ while (opP != opZ && opP->prev->pt.y == curr_y)
opP = opP->prev;
while (opN != opA && opN->next->pt.y == curr_y)
opN = opN->next;
@@ -2150,7 +2196,7 @@ namespace Clipper2Lib {
while (opN->next != opP && opN->next->pt.y == curr_y)
opN = opN->next;
}
- bool result =
+ bool result =
SetHorzSegHeadingForward(hs, opP, opN) &&
!hs.left_op->horz;
@@ -2160,13 +2206,14 @@ namespace Clipper2Lib {
hs.right_op = nullptr; // (for sorting)
return result;
}
-
+
void ClipperBase::ConvertHorzSegsToJoins()
{
- auto j = std::count_if(horz_seg_list_.begin(),
+ auto j = std::count_if(horz_seg_list_.begin(),
horz_seg_list_.end(),
[](HorzSegment& hs) { return UpdateHorzSegment(hs); });
if (j < 2) return;
+
std::stable_sort(horz_seg_list_.begin(), horz_seg_list_.end(), HorzSegSorter());
HorzSegmentList::iterator hs1 = horz_seg_list_.begin(), hs2;
@@ -2207,8 +2254,8 @@ namespace Clipper2Lib {
DuplicateOp(hs1->left_op, false));
horz_join_list_.push_back(join);
}
- }
- }
+ }
+ }
}
void MoveSplits(OutRec* fromOr, OutRec* toOr)
@@ -2301,7 +2348,7 @@ namespace Clipper2Lib {
void ClipperBase::AddNewIntersectNode(Active& e1, Active& e2, int64_t top_y)
{
Point64 ip;
- if (!GetIntersectPoint(e1.bot, e1.top, e2.bot, e2.top, ip))
+ if (!GetSegmentIntersectPt(e1.bot, e1.top, e2.bot, e2.top, ip))
ip = Point64(e1.curr_x, top_y); //parallel edges
//rounding errors can occasionally place the calculated intersection
@@ -2321,7 +2368,7 @@ namespace Clipper2Lib {
ip = GetClosestPointOnSegment(ip, e1.bot, e1.top);
else if (abs_dx2 > 100)
ip = GetClosestPointOnSegment(ip, e2.bot, e2.top);
- else
+ else
{
if (ip.y < top_y) ip.y = top_y;
else ip.y = bot_y_;
@@ -2453,7 +2500,7 @@ namespace Clipper2Lib {
horz_seg_list_.push_back(HorzSegment(op));
}
- bool ClipperBase::ResetHorzDirection(const Active& horz,
+ bool ClipperBase::ResetHorzDirection(const Active& horz,
const Vertex* max_vertex, int64_t& horz_left, int64_t& horz_right)
{
if (horz.bot.x == horz.top.x)
@@ -2536,8 +2583,8 @@ namespace Clipper2Lib {
if (IsHotEdge(horz) && IsJoined(*e))
Split(*e, e->top);
- //if (IsHotEdge(horz) != IsHotEdge(*e))
- // DoError(undefined_error_i);
+ //if (IsHotEdge(horz) != IsHotEdge(*e))
+ // DoError(undefined_error_i);
if (IsHotEdge(horz))
{
@@ -2641,7 +2688,7 @@ namespace Clipper2Lib {
ResetHorzDirection(horz, vertex_max, horz_left, horz_right);
}
- if (IsHotEdge(horz))
+ if (IsHotEdge(horz))
{
OutPt* op = AddOutPt(horz, horz.top);
AddTrialHorzJoin(op);
@@ -2754,21 +2801,23 @@ namespace Clipper2Lib {
}
}
- void ClipperBase::CheckJoinLeft(Active& e,
+ void ClipperBase::CheckJoinLeft(Active& e,
const Point64& pt, bool check_curr_x)
{
Active* prev = e.prev_in_ael;
- if (IsOpen(e) || !IsHotEdge(e) || !prev ||
- IsOpen(*prev) || !IsHotEdge(*prev)) return;
+ if (!prev ||
+ !IsHotEdge(e) || !IsHotEdge(*prev) ||
+ IsHorizontal(e) || IsHorizontal(*prev) ||
+ IsOpen(e) || IsOpen(*prev) ) return;
if ((pt.y < e.top.y + 2 || pt.y < prev->top.y + 2) &&
- ((e.bot.y > pt.y) || (prev->bot.y > pt.y))) return; // avoid trivial joins
+ ((e.bot.y > pt.y) || (prev->bot.y > pt.y))) return; // avoid trivial joins
if (check_curr_x)
{
- if (DistanceFromLineSqrd(pt, prev->bot, prev->top) > 0.25) return;
+ if (PerpendicDistFromLineSqrd(pt, prev->bot, prev->top) > 0.25) return;
}
else if (e.curr_x != prev->curr_x) return;
- if (CrossProduct(e.top, pt, prev->top)) return;
+ if (!IsCollinear(e.top, pt, prev->top)) return;
if (e.outrec->idx == prev->outrec->idx)
AddLocalMaxPoly(*prev, e, pt);
@@ -2780,22 +2829,24 @@ namespace Clipper2Lib {
e.join_with = JoinWith::Left;
}
- void ClipperBase::CheckJoinRight(Active& e,
+ void ClipperBase::CheckJoinRight(Active& e,
const Point64& pt, bool check_curr_x)
{
Active* next = e.next_in_ael;
- if (IsOpen(e) || !IsHotEdge(e) ||
- !next || IsOpen(*next) || !IsHotEdge(*next)) return;
+ if (!next ||
+ !IsHotEdge(e) || !IsHotEdge(*next) ||
+ IsHorizontal(e) || IsHorizontal(*next) ||
+ IsOpen(e) || IsOpen(*next)) return;
if ((pt.y < e.top.y +2 || pt.y < next->top.y +2) &&
- ((e.bot.y > pt.y) || (next->bot.y > pt.y))) return; // avoid trivial joins
+ ((e.bot.y > pt.y) || (next->bot.y > pt.y))) return; // avoid trivial joins
if (check_curr_x)
{
- if (DistanceFromLineSqrd(pt, next->bot, next->top) > 0.35) return;
+ if (PerpendicDistFromLineSqrd(pt, next->bot, next->top) > 0.35) return;
}
else if (e.curr_x != next->curr_x) return;
- if (CrossProduct(e.top, pt, next->top)) return;
-
+ if (!IsCollinear(e.top, pt, next->top)) return;
+
if (e.outrec->idx == next->outrec->idx)
AddLocalMaxPoly(e, *next, pt);
else if (e.outrec->idx < next->outrec->idx)
@@ -2863,7 +2914,7 @@ namespace Clipper2Lib {
op2 = op2->next;
}
- if (path.size() == 3 && IsVerySmallTriangle(*op2)) return false;
+ if (!isOpen && path.size() == 3 && IsVerySmallTriangle(*op2)) return false;
else return true;
}
@@ -2872,8 +2923,8 @@ namespace Clipper2Lib {
if (!outrec->pts) return false;
if (!outrec->bounds.IsEmpty()) return true;
CleanCollinear(outrec);
- if (!outrec->pts ||
- !BuildPath64(outrec->pts, reverse_solution_, false, outrec->path)){
+ if (!outrec->pts ||
+ !BuildPath64(outrec->pts, reverse_solution_, false, outrec->path)){
return false;}
outrec->bounds = GetBounds(outrec->path);
return true;
@@ -2887,10 +2938,10 @@ namespace Clipper2Lib {
if(!split || split == outrec || split->recursive_split == outrec) continue;
split->recursive_split = outrec; // prevent infinite loops
- if (split->splits && CheckSplitOwner(outrec, split->splits))
+ if (split->splits && CheckSplitOwner(outrec, split->splits))
return true;
- else if (CheckBounds(split) &&
- IsValidOwner(outrec, split) &&
+ else if (CheckBounds(split) &&
+ IsValidOwner(outrec, split) &&
split->bounds.Contains(outrec->bounds) &&
Path1InsidePath2(outrec->pts, split->pts))
{
@@ -2919,7 +2970,7 @@ namespace Clipper2Lib {
if (outrec->owner)
{
- if (!outrec->owner->polypath)
+ if (!outrec->owner->polypath)
RecursiveCheckOwners(outrec->owner, polypath);
outrec->polypath = outrec->owner->polypath->AddChild(outrec->path);
}
@@ -2968,7 +3019,7 @@ namespace Clipper2Lib {
open_paths.resize(0);
if (has_open_paths_)
open_paths.reserve(outrec_list_.size());
-
+
// outrec_list_.size() is not static here because
// CheckBounds below can indirectly add additional
// OutRec (via FixOutRecPts & CleanCollinear)
@@ -2991,7 +3042,7 @@ namespace Clipper2Lib {
bool BuildPathD(OutPt* op, bool reverse, bool isOpen, PathD& path, double inv_scale)
{
- if (!op || op->next == op || (!isOpen && op->next == op->prev))
+ if (!op || op->next == op || (!isOpen && op->next == op->prev))
return false;
path.resize(0);
@@ -3024,7 +3075,7 @@ namespace Clipper2Lib {
#else
path.push_back(PointD(lastPt.x * inv_scale, lastPt.y * inv_scale));
#endif
-
+
}
if (reverse)
op2 = op2->prev;
diff --git a/thirdparty/clipper2/src/clipper.offset.cpp b/thirdparty/clipper2/src/clipper.offset.cpp
index 0282aa49bb..508a7f0831 100644
--- a/thirdparty/clipper2/src/clipper.offset.cpp
+++ b/thirdparty/clipper2/src/clipper.offset.cpp
@@ -1,8 +1,8 @@
/*******************************************************************************
* Author : Angus Johnson *
-* Date : 28 November 2023 *
+* Date : 17 April 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 *
*******************************************************************************/
@@ -20,60 +20,19 @@ const double floating_point_tolerance = 1e-12;
// Miscellaneous methods
//------------------------------------------------------------------------------
-inline bool ToggleBoolIf(bool val, bool condition)
+std::optional<size_t> GetLowestClosedPathIdx(const Paths64& paths)
{
- return condition ? !val : val;
-}
-
-void GetMultiBounds(const Paths64& paths, std::vector<Rect64>& recList)
-{
- recList.reserve(paths.size());
- for (const Path64& path : paths)
- {
- if (path.size() < 1)
- {
- recList.push_back(InvalidRect64);
- continue;
- }
- int64_t x = path[0].x, y = path[0].y;
- Rect64 r = Rect64(x, y, x, y);
- for (const Point64& pt : path)
- {
- if (pt.y > r.bottom) r.bottom = pt.y;
- else if (pt.y < r.top) r.top = pt.y;
- if (pt.x > r.right) r.right = pt.x;
- else if (pt.x < r.left) r.left = pt.x;
- }
- recList.push_back(r);
- }
-}
-
-bool ValidateBounds(std::vector<Rect64>& recList, double delta)
-{
- int64_t int_delta = static_cast<int64_t>(delta);
- int64_t big = MAX_COORD - int_delta;
- int64_t small = MIN_COORD + int_delta;
- for (const Rect64& r : recList)
- {
- if (!r.IsValid()) continue; // ignore invalid paths
- else if (r.left < small || r.right > big ||
- r.top < small || r.bottom > big) return false;
- }
- return true;
-}
-
-int GetLowestClosedPathIdx(std::vector<Rect64>& boundsList)
-{
- int i = -1, result = -1;
+ std::optional<size_t> result;
Point64 botPt = Point64(INT64_MAX, INT64_MIN);
- for (const Rect64& r : boundsList)
- {
- ++i;
- if (!r.IsValid()) continue; // ignore invalid paths
- else if (r.bottom > botPt.y || (r.bottom == botPt.y && r.left < botPt.x))
+ for (size_t i = 0; i < paths.size(); ++i)
+ {
+ for (const Point64& pt : paths[i])
{
- botPt = Point64(r.left, r.bottom);
- result = static_cast<int>(i);
+ if ((pt.y < botPt.y) ||
+ ((pt.y == botPt.y) && (pt.x >= botPt.x))) continue;
+ result = i;
+ botPt.x = pt.x;
+ botPt.y = pt.y;
}
}
return result;
@@ -96,14 +55,14 @@ inline bool AlmostZero(double value, double epsilon = 0.001)
return std::fabs(value) < epsilon;
}
-inline double Hypot(double x, double y)
+inline double Hypot(double x, double y)
{
//see https://stackoverflow.com/a/32436148/359538
return std::sqrt(x * x + y * y);
}
inline PointD NormalizeVector(const PointD& vec)
-{
+{
double h = Hypot(vec.x, vec.y);
if (AlmostZero(h)) return PointD(0,0);
double inverseHypot = 1 / h;
@@ -164,30 +123,21 @@ ClipperOffset::Group::Group(const Paths64& _paths, JoinType _join_type, EndType
for (Path64& p: paths_in)
StripDuplicates(p, is_joined);
- // get bounds of each path --> bounds_list
- GetMultiBounds(paths_in, bounds_list);
-
if (end_type == EndType::Polygon)
{
- is_hole_list.reserve(paths_in.size());
- for (const Path64& path : paths_in)
- is_hole_list.push_back(Area(path) < 0);
- lowest_path_idx = GetLowestClosedPathIdx(bounds_list);
+ lowest_path_idx = GetLowestClosedPathIdx(paths_in);
// the lowermost path must be an outer path, so if its orientation is negative,
// then flag the whole group is 'reversed' (will negate delta etc.)
// as this is much more efficient than reversing every path.
- is_reversed = (lowest_path_idx >= 0) && is_hole_list[lowest_path_idx];
- if (is_reversed) is_hole_list.flip();
+ is_reversed = (lowest_path_idx.has_value()) && Area(paths_in[lowest_path_idx.value()]) < 0;
}
else
{
- lowest_path_idx = -1;
+ lowest_path_idx = std::nullopt;
is_reversed = false;
- is_hole_list.resize(paths_in.size());
}
}
-
//------------------------------------------------------------------------------
// ClipperOffset methods
//------------------------------------------------------------------------------
@@ -216,66 +166,29 @@ void ClipperOffset::BuildNormals(const Path64& path)
norms.push_back(GetUnitNormal(*path_stop_iter, *(path.cbegin())));
}
-inline PointD TranslatePoint(const PointD& pt, double dx, double dy)
-{
-#ifdef USINGZ
- return PointD(pt.x + dx, pt.y + dy, pt.z);
-#else
- return PointD(pt.x + dx, pt.y + dy);
-#endif
-}
-
-inline PointD ReflectPoint(const PointD& pt, const PointD& pivot)
-{
-#ifdef USINGZ
- return PointD(pivot.x + (pivot.x - pt.x), pivot.y + (pivot.y - pt.y), pt.z);
-#else
- return PointD(pivot.x + (pivot.x - pt.x), pivot.y + (pivot.y - pt.y));
-#endif
-}
-
-PointD IntersectPoint(const PointD& pt1a, const PointD& pt1b,
- const PointD& pt2a, const PointD& pt2b)
-{
- if (pt1a.x == pt1b.x) //vertical
- {
- if (pt2a.x == pt2b.x) return PointD(0, 0);
-
- double m2 = (pt2b.y - pt2a.y) / (pt2b.x - pt2a.x);
- double b2 = pt2a.y - m2 * pt2a.x;
- return PointD(pt1a.x, m2 * pt1a.x + b2);
- }
- else if (pt2a.x == pt2b.x) //vertical
- {
- double m1 = (pt1b.y - pt1a.y) / (pt1b.x - pt1a.x);
- double b1 = pt1a.y - m1 * pt1a.x;
- return PointD(pt2a.x, m1 * pt2a.x + b1);
- }
- else
- {
- double m1 = (pt1b.y - pt1a.y) / (pt1b.x - pt1a.x);
- double b1 = pt1a.y - m1 * pt1a.x;
- double m2 = (pt2b.y - pt2a.y) / (pt2b.x - pt2a.x);
- double b2 = pt2a.y - m2 * pt2a.x;
- if (m1 == m2) return PointD(0, 0);
- double x = (b2 - b1) / (m1 - m2);
- return PointD(x, m1 * x + b1);
- }
-}
-
void ClipperOffset::DoBevel(const Path64& path, size_t j, size_t k)
{
PointD pt1, pt2;
if (j == k)
{
double abs_delta = std::abs(group_delta_);
+#ifdef USINGZ
+ pt1 = PointD(path[j].x - abs_delta * norms[j].x, path[j].y - abs_delta * norms[j].y, path[j].z);
+ pt2 = PointD(path[j].x + abs_delta * norms[j].x, path[j].y + abs_delta * norms[j].y, path[j].z);
+#else
pt1 = PointD(path[j].x - abs_delta * norms[j].x, path[j].y - abs_delta * norms[j].y);
pt2 = PointD(path[j].x + abs_delta * norms[j].x, path[j].y + abs_delta * norms[j].y);
- }
+#endif
+ }
else
{
+#ifdef USINGZ
+ pt1 = PointD(path[j].x + group_delta_ * norms[k].x, path[j].y + group_delta_ * norms[k].y, path[j].z);
+ pt2 = PointD(path[j].x + group_delta_ * norms[j].x, path[j].y + group_delta_ * norms[j].y, path[j].z);
+#else
pt1 = PointD(path[j].x + group_delta_ * norms[k].x, path[j].y + group_delta_ * norms[k].y);
pt2 = PointD(path[j].x + group_delta_ * norms[j].x, path[j].y + group_delta_ * norms[j].y);
+#endif
}
path_out.push_back(Point64(pt1));
path_out.push_back(Point64(pt2));
@@ -284,7 +197,7 @@ void ClipperOffset::DoBevel(const Path64& path, size_t j, size_t k)
void ClipperOffset::DoSquare(const Path64& path, size_t j, size_t k)
{
PointD vec;
- if (j == k)
+ if (j == k)
vec = PointD(norms[j].y, -norms[j].x);
else
vec = GetAvgUnitVector(
@@ -304,10 +217,8 @@ void ClipperOffset::DoSquare(const Path64& path, size_t j, size_t k)
if (j == k)
{
PointD pt4 = PointD(pt3.x + vec.x * group_delta_, pt3.y + vec.y * group_delta_);
- PointD pt = IntersectPoint(pt1, pt2, pt3, pt4);
-#ifdef USINGZ
- pt.z = ptQ.z;
-#endif
+ PointD pt = ptQ;
+ GetSegmentIntersectPt(pt1, pt2, pt3, pt4, pt);
//get the second intersect point through reflecion
path_out.push_back(Point64(ReflectPoint(pt, ptQ)));
path_out.push_back(Point64(pt));
@@ -315,10 +226,8 @@ void ClipperOffset::DoSquare(const Path64& path, size_t j, size_t k)
else
{
PointD pt4 = GetPerpendicD(path[j], norms[k], group_delta_);
- PointD pt = IntersectPoint(pt1, pt2, pt3, pt4);
-#ifdef USINGZ
- pt.z = ptQ.z;
-#endif
+ PointD pt = ptQ;
+ GetSegmentIntersectPt(pt1, pt2, pt3, pt4, pt);
path_out.push_back(Point64(pt));
//get the second intersect point through reflecion
path_out.push_back(Point64(ReflectPoint(pt, ptQ)));
@@ -343,7 +252,7 @@ void ClipperOffset::DoMiter(const Path64& path, size_t j, size_t k, double cos_a
void ClipperOffset::DoRound(const Path64& path, size_t j, size_t k, double angle)
{
if (deltaCallback64_) {
- // when deltaCallback64_ is assigned, group_delta_ won't be constant,
+ // when deltaCallback64_ is assigned, group_delta_ won't be constant,
// so we'll need to do the following calculations for *every* vertex.
double abs_delta = std::fabs(group_delta_);
double arcTol = (arc_tolerance_ > floating_point_tolerance ?
@@ -387,7 +296,7 @@ void ClipperOffset::OffsetPoint(Group& group, const Path64& path, size_t j, size
// sin(A) < 0: right turning
// cos(A) < 0: change in angle is more than 90 degree
- if (path[j] == path[k]) { k = j; return; }
+ if (path[j] == path[k]) return;
double sin_a = CrossProduct(norms[j], norms[k]);
double cos_a = DotProduct(norms[j], norms[k]);
@@ -404,18 +313,29 @@ void ClipperOffset::OffsetPoint(Group& group, const Path64& path, size_t j, size
return;
}
- if (cos_a > -0.99 && (sin_a * group_delta_ < 0)) // test for concavity first (#593)
+ if (cos_a > -0.999 && (sin_a * group_delta_ < 0)) // test for concavity first (#593)
{
- // is concave
+ // is concave (so insert 3 points that will create a negative region)
+#ifdef USINGZ
+ path_out.push_back(Point64(GetPerpendic(path[j], norms[k], group_delta_), path[j].z));
+#else
path_out.push_back(GetPerpendic(path[j], norms[k], group_delta_));
- // this extra point is the only (simple) way to ensure that
- // path reversals are fully cleaned with the trailing clipper
- path_out.push_back(path[j]); // (#405)
+#endif
+
+ // this extra point is the only simple way to ensure that path reversals
+ // (ie over-shrunk paths) are fully cleaned out with the trailing union op.
+ // However it's probably safe to skip this whenever an angle is almost flat.
+ if (cos_a < 0.99) path_out.push_back(path[j]); // (#405)
+
+#ifdef USINGZ
+ path_out.push_back(Point64(GetPerpendic(path[j], norms[j], group_delta_), path[j].z));
+#else
path_out.push_back(GetPerpendic(path[j], norms[j], group_delta_));
+#endif
}
- else if (cos_a > 0.999 && join_type_ != JoinType::Round)
+ else if (cos_a > 0.999 && join_type_ != JoinType::Round)
{
- // almost straight - less than 2.5 degree (#424, #482, #526 & #724)
+ // almost straight - less than 2.5 degree (#424, #482, #526 & #724)
DoMiter(path, j, k, cos_a);
}
else if (join_type_ == JoinType::Miter)
@@ -435,9 +355,9 @@ void ClipperOffset::OffsetPoint(Group& group, const Path64& path, size_t j, size
void ClipperOffset::OffsetPolygon(Group& group, const Path64& path)
{
path_out.clear();
- for (Path64::size_type j = 0, k = path.size() -1; j < path.size(); k = j, ++j)
- OffsetPoint(group, path, j, k);
- solution.push_back(path_out);
+ for (Path64::size_type j = 0, k = path.size() - 1; j < path.size(); k = j, ++j)
+ OffsetPoint(group, path, j, k);
+ solution->push_back(path_out);
}
void ClipperOffset::OffsetOpenJoined(Group& group, const Path64& path)
@@ -445,8 +365,8 @@ void ClipperOffset::OffsetOpenJoined(Group& group, const Path64& path)
OffsetPolygon(group, path);
Path64 reverse_path(path);
std::reverse(reverse_path.begin(), reverse_path.end());
-
- //rebuild normals // BuildNormals(path);
+
+ //rebuild normals
std::reverse(norms.begin(), norms.end());
norms.push_back(norms[0]);
norms.erase(norms.begin());
@@ -459,7 +379,7 @@ void ClipperOffset::OffsetOpenPath(Group& group, const Path64& path)
{
// do the line start cap
if (deltaCallback64_) group_delta_ = deltaCallback64_(path, norms, 0, 0);
-
+
if (std::fabs(group_delta_) <= floating_point_tolerance)
path_out.push_back(path[0]);
else
@@ -477,13 +397,13 @@ void ClipperOffset::OffsetOpenPath(Group& group, const Path64& path)
break;
}
}
-
+
size_t highI = path.size() - 1;
// offset the left side going forward
for (Path64::size_type j = 1, k = 0; j < highI; k = j, ++j)
OffsetPoint(group, path, j, k);
- // reverse normals
+ // reverse normals
for (size_t i = highI; i > 0; --i)
norms[i] = PointD(-norms[i - 1].x, -norms[i - 1].y);
norms[0] = norms[highI];
@@ -510,41 +430,34 @@ void ClipperOffset::OffsetOpenPath(Group& group, const Path64& path)
}
}
- for (size_t j = highI, k = 0; j > 0; k = j, --j)
+ for (size_t j = highI -1, k = highI; j > 0; k = j, --j)
OffsetPoint(group, path, j, k);
- solution.push_back(path_out);
+ solution->push_back(path_out);
}
void ClipperOffset::DoGroupOffset(Group& group)
{
if (group.end_type == EndType::Polygon)
{
- // a straight path (2 points) can now also be 'polygon' offset
+ // a straight path (2 points) can now also be 'polygon' offset
// where the ends will be treated as (180 deg.) joins
- if (group.lowest_path_idx < 0) delta_ = std::abs(delta_);
+ if (!group.lowest_path_idx.has_value()) delta_ = std::abs(delta_);
group_delta_ = (group.is_reversed) ? -delta_ : delta_;
}
else
group_delta_ = std::abs(delta_);// *0.5;
double abs_delta = std::fabs(group_delta_);
- if (!ValidateBounds(group.bounds_list, abs_delta))
- {
- DoError(range_error_i);
- error_code_ |= range_error_i;
- return;
- }
-
join_type_ = group.join_type;
end_type_ = group.end_type;
if (group.join_type == JoinType::Round || group.end_type == EndType::Round)
{
- // calculate a sensible number of steps (for 360 deg for the given offset)
- // arcTol - when arc_tolerance_ is undefined (0), the amount of
- // curve imprecision that's allowed is based on the size of the
- // offset (delta). Obviously very large offsets will almost always
- // require much less precision. See also offset_triginometry2.svg
+ // calculate the number of steps required to approximate a circle
+ // (see http://www.angusj.com/clipper2/Docs/Trigonometry.htm)
+ // arcTol - when arc_tolerance_ is undefined (0) then curve imprecision
+ // will be relative to the size of the offset (delta). Obviously very
+ //large offsets will almost always require much less precision.
double arcTol = (arc_tolerance_ > floating_point_tolerance ?
std::min(abs_delta, arc_tolerance_) :
std::log10(2 + abs_delta) * default_arc_tolerance);
@@ -556,24 +469,29 @@ void ClipperOffset::DoGroupOffset(Group& group)
steps_per_rad_ = steps_per_360 / (2 * PI);
}
- std::vector<Rect64>::const_iterator path_rect_it = group.bounds_list.cbegin();
- std::vector<bool>::const_iterator is_hole_it = group.is_hole_list.cbegin();
+ //double min_area = PI * Sqr(group_delta_);
Paths64::const_iterator path_in_it = group.paths_in.cbegin();
- for ( ; path_in_it != group.paths_in.cend(); ++path_in_it, ++path_rect_it, ++is_hole_it)
+ for ( ; path_in_it != group.paths_in.cend(); ++path_in_it)
{
- if (!path_rect_it->IsValid()) continue;
Path64::size_type pathLen = path_in_it->size();
path_out.clear();
if (pathLen == 1) // single point
{
+ if (deltaCallback64_)
+ {
+ group_delta_ = deltaCallback64_(*path_in_it, norms, 0, 0);
+ if (group.is_reversed) group_delta_ = -group_delta_;
+ abs_delta = std::fabs(group_delta_);
+ }
+
if (group_delta_ < 1) continue;
const Point64& pt = (*path_in_it)[0];
//single vertex so build a circle or square ...
if (group.join_type == JoinType::Round)
{
double radius = abs_delta;
- int steps = static_cast<int>(std::ceil(steps_per_rad_ * 2 * PI)); //#617
+ size_t steps = steps_per_rad_ > 0 ? static_cast<size_t>(std::ceil(steps_per_rad_ * 2 * PI)) : 0; //#617
path_out = Ellipse(pt, radius, radius, steps);
#ifdef USINGZ
for (auto& p : path_out) p.z = pt.z;
@@ -588,19 +506,14 @@ void ClipperOffset::DoGroupOffset(Group& group)
for (auto& p : path_out) p.z = pt.z;
#endif
}
- solution.push_back(path_out);
- continue;
- } // end of offsetting a single point
- // when shrinking outer paths, make sure they can shrink this far (#593)
- // also when shrinking holes, make sure they too can shrink this far (#715)
- if ((group_delta_ > 0) == ToggleBoolIf(*is_hole_it, group.is_reversed) &&
- (std::min(path_rect_it->Width(), path_rect_it->Height()) <= -group_delta_ * 2) )
- continue;
+ solution->push_back(path_out);
+ continue;
+ } // end of offsetting a single point
if ((pathLen == 2) && (group.end_type == EndType::Joined))
- end_type_ = (group.join_type == JoinType::Round) ?
- EndType::Round :
+ end_type_ = (group.join_type == JoinType::Round) ?
+ EndType::Round :
EndType::Square;
BuildNormals(*path_in_it);
@@ -610,6 +523,16 @@ void ClipperOffset::DoGroupOffset(Group& group)
}
}
+#ifdef USINGZ
+void ClipperOffset::ZCB(const Point64& bot1, const Point64& top1,
+ const Point64& bot2, const Point64& top2, Point64& ip)
+{
+ if (bot1.z && ((bot1.z == bot2.z) || (bot1.z == top2.z))) ip.z = bot1.z;
+ else if (bot2.z && (bot2.z == top1.z)) ip.z = bot2.z;
+ else if (top1.z && (top1.z == top2.z)) ip.z = top1.z;
+ else if (zCallback64_) zCallback64_(bot1, top1, bot2, top2, ip);
+}
+#endif
size_t ClipperOffset::CalcSolutionCapacity()
{
@@ -635,40 +558,35 @@ bool ClipperOffset::CheckReverseOrientation()
void ClipperOffset::ExecuteInternal(double delta)
{
error_code_ = 0;
- solution.clear();
if (groups_.size() == 0) return;
- solution.reserve(CalcSolutionCapacity());
+ solution->reserve(CalcSolutionCapacity());
- if (std::abs(delta) < 0.5) // ie: offset is insignificant
+ if (std::abs(delta) < 0.5) // ie: offset is insignificant
{
Paths64::size_type sol_size = 0;
for (const Group& group : groups_) sol_size += group.paths_in.size();
- solution.reserve(sol_size);
+ solution->reserve(sol_size);
for (const Group& group : groups_)
- copy(group.paths_in.begin(), group.paths_in.end(), back_inserter(solution));
- return;
+ copy(group.paths_in.begin(), group.paths_in.end(), back_inserter(*solution));
}
+ else
+ {
- temp_lim_ = (miter_limit_ <= 1) ?
- 2.0 :
- 2.0 / (miter_limit_ * miter_limit_);
+ temp_lim_ = (miter_limit_ <= 1) ?
+ 2.0 :
+ 2.0 / (miter_limit_ * miter_limit_);
- delta_ = delta;
- std::vector<Group>::iterator git;
- for (git = groups_.begin(); git != groups_.end(); ++git)
- {
- DoGroupOffset(*git);
- if (!error_code_) continue; // all OK
- solution.clear();
+ delta_ = delta;
+ std::vector<Group>::iterator git;
+ for (git = groups_.begin(); git != groups_.end(); ++git)
+ {
+ DoGroupOffset(*git);
+ if (!error_code_) continue; // all OK
+ solution->clear();
+ }
}
-}
-void ClipperOffset::Execute(double delta, Paths64& paths)
-{
- paths.clear();
-
- ExecuteInternal(delta);
- if (!solution.size()) return;
+ if (!solution->size()) return;
bool paths_reversed = CheckReverseOrientation();
//clean up self-intersections ...
@@ -677,41 +595,45 @@ void ClipperOffset::Execute(double delta, Paths64& paths)
//the solution should retain the orientation of the input
c.ReverseSolution(reverse_solution_ != paths_reversed);
#ifdef USINGZ
- if (zCallback64_) { c.SetZCallback(zCallback64_); }
+ auto fp = std::bind(&ClipperOffset::ZCB, this, std::placeholders::_1,
+ std::placeholders::_2, std::placeholders::_3,
+ std::placeholders::_4, std::placeholders::_5);
+ c.SetZCallback(fp);
#endif
- c.AddSubject(solution);
- if (paths_reversed)
- c.Execute(ClipType::Union, FillRule::Negative, paths);
+ c.AddSubject(*solution);
+ if (solution_tree)
+ {
+ if (paths_reversed)
+ c.Execute(ClipType::Union, FillRule::Negative, *solution_tree);
+ else
+ c.Execute(ClipType::Union, FillRule::Positive, *solution_tree);
+ }
else
- c.Execute(ClipType::Union, FillRule::Positive, paths);
+ {
+ if (paths_reversed)
+ c.Execute(ClipType::Union, FillRule::Negative, *solution);
+ else
+ c.Execute(ClipType::Union, FillRule::Positive, *solution);
+ }
+}
+
+void ClipperOffset::Execute(double delta, Paths64& paths)
+{
+ paths.clear();
+ solution = &paths;
+ solution_tree = nullptr;
+ ExecuteInternal(delta);
}
void ClipperOffset::Execute(double delta, PolyTree64& polytree)
{
polytree.Clear();
-
+ solution_tree = &polytree;
+ solution = new Paths64();
ExecuteInternal(delta);
- if (!solution.size()) return;
-
- bool paths_reversed = CheckReverseOrientation();
- //clean up self-intersections ...
- Clipper64 c;
- c.PreserveCollinear(false);
- //the solution should retain the orientation of the input
- c.ReverseSolution (reverse_solution_ != paths_reversed);
-#ifdef USINGZ
- if (zCallback64_) {
- c.SetZCallback(zCallback64_);
- }
-#endif
- c.AddSubject(solution);
-
-
- if (paths_reversed)
- c.Execute(ClipType::Union, FillRule::Negative, polytree);
- else
- c.Execute(ClipType::Union, FillRule::Positive, polytree);
+ delete solution;
+ solution = nullptr;
}
void ClipperOffset::Execute(DeltaCallback64 delta_cb, Paths64& paths)
diff --git a/thirdparty/clipper2/src/clipper.rectclip.cpp b/thirdparty/clipper2/src/clipper.rectclip.cpp
index 9aa0fc0f76..23809b5ef6 100644
--- a/thirdparty/clipper2/src/clipper.rectclip.cpp
+++ b/thirdparty/clipper2/src/clipper.rectclip.cpp
@@ -1,8 +1,8 @@
/*******************************************************************************
* Author : Angus Johnson *
-* Date : 8 September 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 *
*******************************************************************************/
@@ -71,7 +71,7 @@ namespace Clipper2Lib {
return pt1.y == pt2.y;
}
- inline bool GetSegmentIntersection(const Point64& p1,
+ bool GetSegmentIntersection(const Point64& p1,
const Point64& p2, const Point64& p3, const Point64& p4, Point64& ip)
{
double res1 = CrossProduct(p1, p3, p4);
@@ -113,7 +113,7 @@ namespace Clipper2Lib {
if ((res3 > 0) == (res4 > 0)) return false;
// segments must intersect to get here
- return GetIntersectPoint(p1, p2, p3, p4, ip);
+ return GetSegmentIntersectPt(p1, p2, p3, p4, ip);
}
inline bool GetIntersection(const Path64& rectPath,
@@ -125,7 +125,7 @@ namespace Clipper2Lib {
{
case Location::Left:
if (GetSegmentIntersection(p, p2, rectPath[0], rectPath[3], ip)) return true;
- else if ((p.y < rectPath[0].y) && GetSegmentIntersection(p, p2, rectPath[0], rectPath[1], ip))
+ else if ((p.y < rectPath[0].y) && GetSegmentIntersection(p, p2, rectPath[0], rectPath[1], ip))
{
loc = Location::Top;
return true;
@@ -180,7 +180,7 @@ namespace Clipper2Lib {
else return false;
default: // loc == rInside
- if (GetSegmentIntersection(p, p2, rectPath[0], rectPath[3], ip))
+ if (GetSegmentIntersection(p, p2, rectPath[0], rectPath[3], ip))
{
loc = Location::Left;
return true;
@@ -320,9 +320,9 @@ namespace Clipper2Lib {
// this method is only called by InternalExecute.
// Later splitting & rejoining won't create additional op's,
// though they will change the (non-storage) results_ count.
- int curr_idx = static_cast<int>(results_.size()) - 1;
+ size_t curr_idx = results_.size();
OutPt2* result;
- if (curr_idx < 0 || start_new)
+ if (curr_idx == 0 || start_new)
{
result = &op_container_.emplace_back(OutPt2());
result->pt = pt;
@@ -332,6 +332,7 @@ namespace Clipper2Lib {
}
else
{
+ --curr_idx;
OutPt2* prevOp = results_[curr_idx];
if (prevOp->pt == pt) return prevOp;
result = &op_container_.emplace_back(OutPt2());
@@ -349,27 +350,27 @@ namespace Clipper2Lib {
void RectClip64::AddCorner(Location prev, Location curr)
{
if (HeadingClockwise(prev, curr))
- Add(rect_as_path_[static_cast<int>(prev)]);
+ Add(rect_as_path_[static_cast<size_t>(prev)]);
else
- Add(rect_as_path_[static_cast<int>(curr)]);
+ Add(rect_as_path_[static_cast<size_t>(curr)]);
}
void RectClip64::AddCorner(Location& loc, bool isClockwise)
{
if (isClockwise)
{
- Add(rect_as_path_[static_cast<int>(loc)]);
+ Add(rect_as_path_[static_cast<size_t>(loc)]);
loc = GetAdjacentLocation(loc, true);
}
else
{
loc = GetAdjacentLocation(loc, false);
- Add(rect_as_path_[static_cast<int>(loc)]);
+ Add(rect_as_path_[static_cast<size_t>(loc)]);
}
}
void RectClip64::GetNextLocation(const Path64& path,
- Location& loc, int& i, int highI)
+ Location& loc, size_t& i, size_t highI)
{
switch (loc)
{
@@ -420,31 +421,52 @@ namespace Clipper2Lib {
break; //inner loop
}
break;
- } //switch
+ } //switch
+ }
+
+ bool StartLocsAreClockwise(const std::vector<Location>& startlocs)
+ {
+ int result = 0;
+ for (size_t i = 1; i < startlocs.size(); ++i)
+ {
+ int d = static_cast<int>(startlocs[i]) - static_cast<int>(startlocs[i - 1]);
+ switch (d)
+ {
+ case -1: result -= 1; break;
+ case 1: result += 1; break;
+ case -3: result += 1; break;
+ case 3: result -= 1; break;
+ }
+ }
+ return result > 0;
}
void RectClip64::ExecuteInternal(const Path64& path)
{
- int i = 0, highI = static_cast<int>(path.size()) - 1;
+ if (path.size() < 1)
+ return;
+
+ size_t highI = path.size() - 1;
Location prev = Location::Inside, loc;
Location crossing_loc = Location::Inside;
Location first_cross_ = Location::Inside;
if (!GetLocation(rect_, path[highI], loc))
{
- i = highI - 1;
- while (i >= 0 && !GetLocation(rect_, path[i], prev)) --i;
- if (i < 0)
+ size_t i = highI;
+ while (i > 0 && !GetLocation(rect_, path[i - 1], prev))
+ --i;
+ if (i == 0)
{
// all of path must be inside fRect
for (const auto& pt : path) Add(pt);
return;
}
if (prev == Location::Inside) loc = Location::Inside;
- i = 0;
}
- Location startingLoc = loc;
+ Location starting_loc = loc;
///////////////////////////////////////////////////
+ size_t i = 0;
while (i <= highI)
{
prev = loc;
@@ -454,12 +476,12 @@ namespace Clipper2Lib {
if (i > highI) break;
Point64 ip, ip2;
- Point64 prev_pt = (i) ?
- path[static_cast<size_t>(i - 1)] :
+ Point64 prev_pt = (i) ?
+ path[static_cast<size_t>(i - 1)] :
path[highI];
crossing_loc = loc;
- if (!GetIntersection(rect_as_path_,
+ if (!GetIntersection(rect_as_path_,
path[i], prev_pt, crossing_loc, ip))
{
// ie remaining outside
@@ -470,7 +492,7 @@ namespace Clipper2Lib {
start_locs_.push_back(prev);
prev = GetAdjacentLocation(prev, isClockw);
} while (prev != loc);
- crossing_loc = crossing_prev; // still not crossed
+ crossing_loc = crossing_prev; // still not crossed
}
else if (prev != Location::Inside && prev != loc)
{
@@ -504,7 +526,7 @@ namespace Clipper2Lib {
}
else if (prev != Location::Inside)
{
- // passing right through rect. 'ip' here will be the second
+ // passing right through rect. 'ip' here will be the second
// intersect pt but we'll also need the first intersect pt (ip2)
loc = prev;
GetIntersection(rect_as_path_, prev_pt, path[i], loc, ip2);
@@ -543,7 +565,7 @@ namespace Clipper2Lib {
if (first_cross_ == Location::Inside)
{
// path never intersects
- if (startingLoc != Location::Inside)
+ if (starting_loc != Location::Inside)
{
// path is outside rect
// but being outside, it still may not contain rect
@@ -552,11 +574,13 @@ namespace Clipper2Lib {
{
// yep, the path does fully contain rect
// so add rect to the solution
+ bool is_clockwise_path = StartLocsAreClockwise(start_locs_);
for (size_t j = 0; j < 4; ++j)
{
- Add(rect_as_path_[j]);
+ size_t k = is_clockwise_path ? j : 3 - j; // reverses result path
+ Add(rect_as_path_[k]);
// we may well need to do some splitting later, so
- AddToEdge(edges_[j * 2], results_[0]);
+ AddToEdge(edges_[k * 2], results_[0]);
}
}
}
@@ -589,8 +613,7 @@ namespace Clipper2Lib {
OutPt2* op2 = op;
do
{
- if (!CrossProduct(op2->prev->pt,
- op2->pt, op2->next->pt))
+ if (IsCollinear(op2->prev->pt, op2->pt, op2->next->pt))
{
if (op2 == op)
{
@@ -640,7 +663,7 @@ namespace Clipper2Lib {
}
}
- void RectClip64::TidyEdges(int idx, OutPt2List& cw, OutPt2List& ccw)
+ void RectClip64::TidyEdges(size_t idx, OutPt2List& cw, OutPt2List& ccw)
{
if (ccw.empty()) return;
bool isHorz = ((idx == 1) || (idx == 3));
@@ -648,7 +671,7 @@ namespace Clipper2Lib {
size_t i = 0, j = 0;
OutPt2* p1, * p2, * p1a, * p2a, * op, * op2;
- while (i < cw.size())
+ while (i < cw.size())
{
p1 = cw[i];
if (!p1 || p1->next == p1->prev)
@@ -825,8 +848,8 @@ namespace Clipper2Lib {
OutPt2* op2 = op->next;
while (op2 && op2 != op)
{
- if (CrossProduct(op2->prev->pt,
- op2->pt, op2->next->pt) == 0)
+ if (IsCollinear(op2->prev->pt,
+ op2->pt, op2->next->pt))
{
op = op2->prev;
op2 = UnlinkOp(op2);
@@ -854,7 +877,7 @@ namespace Clipper2Lib {
if (rect_.IsEmpty()) return result;
for (const Path64& path : paths)
- {
+ {
if (path.size() < 3) continue;
path_bounds_ = GetBounds(path);
if (!rect_.Intersects(path_bounds_))
@@ -868,9 +891,9 @@ namespace Clipper2Lib {
ExecuteInternal(path);
CheckEdges();
- for (int i = 0; i < 4; ++i)
+ for (size_t i = 0; i < 4; ++i)
TidyEdges(i, edges_[i * 2], edges_[i * 2 + 1]);
-
+
for (OutPt2*& op : results_)
{
Path64 tmp = GetPath(op);
@@ -925,14 +948,14 @@ namespace Clipper2Lib {
op_container_ = std::deque<OutPt2>();
start_locs_.clear();
- int i = 1, highI = static_cast<int>(path.size()) - 1;
+ size_t i = 1, highI = path.size() - 1;
Location prev = Location::Inside, loc;
Location crossing_loc;
if (!GetLocation(rect_, path[0], loc))
{
while (i <= highI && !GetLocation(rect_, path[i], prev)) ++i;
- if (i > highI)
+ if (i > highI)
{
// all of path must be inside fRect
for (const auto& pt : path) Add(pt);
@@ -953,7 +976,7 @@ namespace Clipper2Lib {
Point64 prev_pt = path[static_cast<size_t>(i - 1)];
crossing_loc = loc;
- if (!GetIntersection(rect_as_path_,
+ if (!GetIntersection(rect_as_path_,
path[i], prev_pt, crossing_loc, ip))
{
// ie remaining outside
@@ -971,10 +994,10 @@ namespace Clipper2Lib {
}
else if (prev != Location::Inside)
{
- // passing right through rect. 'ip' here will be the second
+ // passing right through rect. 'ip' here will be the second
// intersect pt but we'll also need the first intersect pt (ip2)
crossing_loc = prev;
- GetIntersection(rect_as_path_,
+ GetIntersection(rect_as_path_,
prev_pt, path[i], crossing_loc, ip2);
Add(ip2, true);
Add(ip);
@@ -991,14 +1014,14 @@ namespace Clipper2Lib {
{
Path64 result;
if (!op || op == op->next) return result;
- op = op->next; // starting at path beginning
+ op = op->next; // starting at path beginning
result.push_back(op->pt);
OutPt2 *op2 = op->next;
while (op2 != op)
{
result.push_back(op2->pt);
op2 = op2->next;
- }
+ }
return result;
}