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.cpp755
-rw-r--r--thirdparty/clipper2/src/clipper.offset.cpp561
-rw-r--r--thirdparty/clipper2/src/clipper.rectclip.cpp179
3 files changed, 874 insertions, 621 deletions
diff --git a/thirdparty/clipper2/src/clipper.engine.cpp b/thirdparty/clipper2/src/clipper.engine.cpp
index 2d61b8aafa..9358b74b70 100644
--- a/thirdparty/clipper2/src/clipper.engine.cpp
+++ b/thirdparty/clipper2/src/clipper.engine.cpp
@@ -1,6 +1,6 @@
/*******************************************************************************
* Author : Angus Johnson *
-* Date : 19 March 2023 *
+* Date : 22 November 2023 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2023 *
* Purpose : This is the main polygon clipping module *
@@ -15,6 +15,7 @@
#include <algorithm>
#include "clipper2/clipper.engine.h"
+#include "clipper2/clipper.h"
// https://github.com/AngusJohnson/Clipper2/discussions/334
// #discussioncomment-4248602
@@ -419,6 +420,12 @@ namespace Clipper2Lib {
return outrec;
}
+ inline bool IsValidOwner(OutRec* outrec, OutRec* testOwner)
+ {
+ // prevent outrec owning itself either directly or indirectly
+ while (testOwner && testOwner != outrec) testOwner = testOwner->owner;
+ return !testOwner;
+ }
inline void UncoupleOutRec(Active ae)
{
@@ -484,108 +491,135 @@ namespace Clipper2Lib {
outrec->owner = new_owner;
}
- //------------------------------------------------------------------------------
- // ClipperBase methods ...
- //------------------------------------------------------------------------------
-
- ClipperBase::~ClipperBase()
+ static PointInPolygonResult PointInOpPolygon(const Point64& pt, OutPt* op)
{
- Clear();
- }
+ if (op == op->next || op->prev == op->next)
+ return PointInPolygonResult::IsOutside;
- void ClipperBase::DeleteEdges(Active*& e)
- {
- while (e)
+ OutPt* op2 = op;
+ do
{
- Active* e2 = e;
- e = e->next_in_ael;
- delete e2;
- }
- }
+ if (op->pt.y != pt.y) break;
+ op = op->next;
+ } while (op != op2);
+ if (op->pt.y == pt.y) // not a proper polygon
+ return PointInPolygonResult::IsOutside;
- void ClipperBase::CleanUp()
- {
- DeleteEdges(actives_);
- scanline_list_ = std::priority_queue<int64_t>();
- intersect_nodes_.clear();
- DisposeAllOutRecs();
- horz_seg_list_.clear();
- horz_join_list_.clear();
- }
+ bool is_above = op->pt.y < pt.y, starting_above = is_above;
+ int val = 0;
+ op2 = op->next;
+ while (op2 != op)
+ {
+ if (is_above)
+ while (op2 != op && op2->pt.y < pt.y) op2 = op2->next;
+ else
+ while (op2 != op && op2->pt.y > pt.y) op2 = op2->next;
+ if (op2 == op) break;
+ // must have touched or crossed the pt.Y horizonal
+ // and this must happen an even number of times
- void ClipperBase::Clear()
- {
- CleanUp();
- DisposeVerticesAndLocalMinima();
- current_locmin_iter_ = minima_list_.begin();
- minima_list_sorted_ = false;
- has_open_paths_ = false;
- }
+ if (op2->pt.y == pt.y) // touching the horizontal
+ {
+ if (op2->pt.x == pt.x || (op2->pt.y == op2->prev->pt.y &&
+ (pt.x < op2->prev->pt.x) != (pt.x < op2->pt.x)))
+ return PointInPolygonResult::IsOn;
+
+ op2 = op2->next;
+ if (op2 == op) break;
+ continue;
+ }
+ if (pt.x < op2->pt.x && pt.x < op2->prev->pt.x);
+ // do nothing because
+ // we're only interested in edges crossing on the left
+ else if ((pt.x > op2->prev->pt.x && pt.x > op2->pt.x))
+ val = 1 - val; // toggle val
+ else
+ {
+ double d = CrossProduct(op2->prev->pt, op2->pt, pt);
+ if (d == 0) return PointInPolygonResult::IsOn;
+ if ((d < 0) == is_above) val = 1 - val;
+ }
+ is_above = !is_above;
+ op2 = op2->next;
+ }
- void ClipperBase::Reset()
- {
- if (!minima_list_sorted_)
+ if (is_above != starting_above)
{
- std::sort(minima_list_.begin(), minima_list_.end(), LocMinSorter());
- minima_list_sorted_ = true;
+ double d = CrossProduct(op2->prev->pt, op2->pt, pt);
+ if (d == 0) return PointInPolygonResult::IsOn;
+ if ((d < 0) == is_above) val = 1 - val;
}
- LocalMinimaList::const_reverse_iterator i;
- for (i = minima_list_.rbegin(); i != minima_list_.rend(); ++i)
- InsertScanline((*i)->vertex->pt.y);
- current_locmin_iter_ = minima_list_.begin();
- actives_ = nullptr;
- sel_ = nullptr;
- succeeded_ = true;
+ if (val == 0) return PointInPolygonResult::IsOutside;
+ else return PointInPolygonResult::IsInside;
}
-
-#ifdef USINGZ
- void ClipperBase::SetZ(const Active& e1, const Active& e2, Point64& ip)
+ inline Path64 GetCleanPath(OutPt* op)
{
- 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
+ Path64 result;
+ OutPt* op2 = op;
+ while (op2->next != op &&
+ ((op2->pt.x == op2->next->pt.x && op2->pt.x == op2->prev->pt.x) ||
+ (op2->pt.y == op2->next->pt.y && op2->pt.y == op2->prev->pt.y))) op2 = op2->next;
+ result.push_back(op2->pt);
+ OutPt* prevOp = op2;
+ op2 = op2->next;
+ while (op2 != op)
{
- 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);
+ if ((op2->pt.x != op2->next->pt.x || op2->pt.x != prevOp->pt.x) &&
+ (op2->pt.y != op2->next->pt.y || op2->pt.y != prevOp->pt.y))
+ {
+ result.push_back(op2->pt);
+ prevOp = op2;
+ }
+ op2 = op2->next;
}
+ return result;
}
-#endif
- void ClipperBase::AddPath(const Path64& path, PathType polytype, bool is_open)
+ inline bool Path1InsidePath2(OutPt* op1, OutPt* op2)
{
- Paths64 tmp;
- tmp.push_back(path);
- AddPaths(tmp, polytype, is_open);
+ // we need to make some accommodation for rounding errors
+ // so we won't jump if the first vertex is found outside
+ PointInPolygonResult result;
+ int outside_cnt = 0;
+ OutPt* op = op1;
+ do
+ {
+ result = PointInOpPolygon(op->pt, op2);
+ if (result == PointInPolygonResult::IsOutside) ++outside_cnt;
+ else if (result == PointInPolygonResult::IsInside) --outside_cnt;
+ op = op->next;
+ } while (op != op1 && std::abs(outside_cnt) < 2);
+ if (std::abs(outside_cnt) > 1) return (outside_cnt < 0);
+ // since path1's location is still equivocal, check its midpoint
+ Point64 mp = GetBounds(GetCleanPath(op1)).MidPoint();
+ Path64 path2 = GetCleanPath(op2);
+ return PointInPolygon(mp, path2) != PointInPolygonResult::IsOutside;
}
+ //------------------------------------------------------------------------------
+ //------------------------------------------------------------------------------
- void ClipperBase::AddPaths(const Paths64& paths, PathType polytype, bool is_open)
+ void AddLocMin(LocalMinimaList& list,
+ Vertex& vert, PathType polytype, bool is_open)
{
- if (is_open) has_open_paths_ = true;
- minima_list_sorted_ = false;
+ //make sure the vertex is added only once ...
+ if ((VertexFlags::LocalMin & vert.flags) != VertexFlags::None) return;
+ vert.flags = (vert.flags | VertexFlags::LocalMin);
+ list.push_back(std::make_unique <LocalMinima>(&vert, polytype, 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,
- [](const auto& a, const Path64& path)
- {return a + static_cast<unsigned>(path.size());});
+ std::accumulate(paths.begin(), paths.end(), 0,
+ [](const auto& a, const Path64& path)
+ {return a + static_cast<unsigned>(path.size()); });
if (total_vertex_count == 0) return;
Vertex* vertices = new Vertex[total_vertex_count], * v = vertices;
@@ -631,7 +665,7 @@ namespace Clipper2Lib {
if (going_up)
{
v0->flags = VertexFlags::OpenStart;
- AddLocMin(*v0, polytype, true);
+ AddLocMin(locMinList , *v0, polytype, true);
}
else
v0->flags = VertexFlags::OpenStart | VertexFlags::LocalMax;
@@ -659,7 +693,7 @@ namespace Clipper2Lib {
else if (curr_v->pt.y < prev_v->pt.y && !going_up)
{
going_up = true;
- AddLocMin(*prev_v, polytype, is_open);
+ AddLocMin(locMinList, *prev_v, polytype, is_open);
}
prev_v = curr_v;
curr_v = curr_v->next;
@@ -671,18 +705,161 @@ namespace Clipper2Lib {
if (going_up)
prev_v->flags = prev_v->flags | VertexFlags::LocalMax;
else
- AddLocMin(*prev_v, polytype, is_open);
+ AddLocMin(locMinList, *prev_v, polytype, is_open);
}
else if (going_up != going_up0)
{
- if (going_up0) AddLocMin(*prev_v, polytype, false);
+ if (going_up0) AddLocMin(locMinList, *prev_v, polytype, false);
else prev_v->flags = prev_v->flags | VertexFlags::LocalMax;
}
} // end processing current path
- vertex_lists_.emplace_back(vertices);
- } // end AddPaths
+ vertexLists.emplace_back(vertices);
+ }
+ //------------------------------------------------------------------------------
+ // ReuseableDataContainer64 methods ...
+ //------------------------------------------------------------------------------
+
+ void ReuseableDataContainer64::AddLocMin(Vertex& vert, PathType polytype, bool is_open)
+ {
+ //make sure the vertex is added only once ...
+ if ((VertexFlags::LocalMin & vert.flags) != VertexFlags::None) return;
+
+ vert.flags = (vert.flags | VertexFlags::LocalMin);
+ minima_list_.push_back(std::make_unique <LocalMinima>(&vert, polytype, is_open));
+ }
+
+ void ReuseableDataContainer64::AddPaths(const Paths64& paths,
+ PathType polytype, bool is_open)
+ {
+ AddPaths_(paths, polytype, is_open, vertex_lists_, minima_list_);
+ }
+
+ ReuseableDataContainer64::~ReuseableDataContainer64()
+ {
+ Clear();
+ }
+
+ void ReuseableDataContainer64::Clear()
+ {
+ minima_list_.clear();
+ for (auto v : vertex_lists_) delete[] v;
+ vertex_lists_.clear();
+ }
+
+ //------------------------------------------------------------------------------
+ // ClipperBase methods ...
+ //------------------------------------------------------------------------------
+
+ ClipperBase::~ClipperBase()
+ {
+ Clear();
+ }
+
+ void ClipperBase::DeleteEdges(Active*& e)
+ {
+ while (e)
+ {
+ Active* e2 = e;
+ e = e->next_in_ael;
+ delete e2;
+ }
+ }
+
+ void ClipperBase::CleanUp()
+ {
+ DeleteEdges(actives_);
+ scanline_list_ = std::priority_queue<int64_t>();
+ intersect_nodes_.clear();
+ DisposeAllOutRecs();
+ horz_seg_list_.clear();
+ horz_join_list_.clear();
+ }
+
+
+ void ClipperBase::Clear()
+ {
+ CleanUp();
+ DisposeVerticesAndLocalMinima();
+ current_locmin_iter_ = minima_list_.begin();
+ minima_list_sorted_ = false;
+ has_open_paths_ = false;
+ }
+
+
+ void ClipperBase::Reset()
+ {
+ if (!minima_list_sorted_)
+ {
+ std::stable_sort(minima_list_.begin(), minima_list_.end(), LocMinSorter()); //#594
+ minima_list_sorted_ = true;
+ }
+ LocalMinimaList::const_reverse_iterator i;
+ for (i = minima_list_.rbegin(); i != minima_list_.rend(); ++i)
+ InsertScanline((*i)->vertex->pt.y);
+
+ current_locmin_iter_ = minima_list_.begin();
+ actives_ = nullptr;
+ sel_ = nullptr;
+ succeeded_ = true;
+ }
+
+
+#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)
+ {
+ Paths64 tmp;
+ tmp.push_back(path);
+ AddPaths(tmp, polytype, is_open);
+ }
+
+ void ClipperBase::AddPaths(const Paths64& paths, PathType polytype, bool is_open)
+ {
+ 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)
+ {
+ // nb: reuseable_data will continue to own the vertices
+ // and remains responsible for their clean up.
+ succeeded_ = false;
+ minima_list_sorted_ = false;
+ LocalMinimaList::const_iterator i;
+ for (i = reuseable_data.minima_list_.cbegin(); i != reuseable_data.minima_list_.cend(); ++i)
+ {
+ minima_list_.push_back(std::make_unique <LocalMinima>((*i)->vertex, (*i)->polytype, (*i)->is_open));
+ if ((*i)->is_open) has_open_paths_ = true;
+ }
+ }
void ClipperBase::InsertScanline(int64_t y)
{
@@ -1236,7 +1413,7 @@ namespace Clipper2Lib {
else
SetOwner(&outrec, e->outrec);
// nb: outRec.owner here is likely NOT the real
- // owner but this will be checked in DeepCheckOwner()
+ // owner but this will be checked in RecursiveCheckOwners()
}
UncoupleOutRec(e1);
@@ -1293,13 +1470,14 @@ namespace Clipper2Lib {
e2.outrec->front_edge = nullptr;
e2.outrec->back_edge = nullptr;
e2.outrec->pts = nullptr;
- SetOwner(e2.outrec, e1.outrec);
if (IsOpenEnd(e1))
{
e2.outrec->pts = e1.outrec->pts;
e1.outrec->pts = nullptr;
}
+ else
+ SetOwner(e2.outrec, e1.outrec);
//and e1 and e2 are maxima and are about to be dropped from the Actives list.
e1.outrec = nullptr;
@@ -1315,6 +1493,7 @@ namespace Clipper2Lib {
result->owner = nullptr;
result->polypath = nullptr;
result->is_open = false;
+ result->splits = nullptr;
return result;
}
@@ -1364,7 +1543,7 @@ namespace Clipper2Lib {
//NB if preserveCollinear == true, then only remove 180 deg. spikes
if ((CrossProduct(op2->prev->pt, op2->pt, op2->next->pt) == 0) &&
(op2->pt == op2->prev->pt ||
- op2->pt == op2->next->pt || !PreserveCollinear ||
+ op2->pt == op2->next->pt || !preserve_collinear_ ||
DotProduct(op2->prev->pt, op2->pt, op2->next->pt) < 0))
{
@@ -1409,11 +1588,6 @@ namespace Clipper2Lib {
return;
}
- // nb: area1 is the path's area *before* splitting, whereas area2 is
- // the area of the triangle containing splitOp & splitOp.next.
- // So the only way for these areas to have the same sign is if
- // the split triangle is larger than the path containing prevOp or
- // if there's more than one self=intersection.
double area2 = AreaTriangle(ip, splitOp->pt, splitOp->next->pt);
double absArea2 = std::fabs(area2);
@@ -1433,18 +1607,17 @@ namespace Clipper2Lib {
prevOp->next = newOp2;
}
+ // area1 is the path's area *before* splitting, whereas area2 is
+ // the area of the triangle containing splitOp & splitOp.next.
+ // So the only way for these areas to have the same sign is if
+ // the split triangle is larger than the path containing prevOp or
+ // if there's more than one self-intersection.
if (absArea2 >= 1 &&
(absArea2 > absArea1 || (area2 > 0) == (area1 > 0)))
{
OutRec* newOr = NewOutRec();
newOr->owner = outrec->owner;
- if (using_polytree_)
- {
- if (!outrec->splits) outrec->splits = new OutRecList();
- outrec->splits->push_back(newOr);
- }
-
splitOp->outrec = newOr;
splitOp->next->outrec = newOr;
OutPt* newOp = new OutPt(ip, newOr);
@@ -1453,6 +1626,20 @@ namespace Clipper2Lib {
newOr->pts = newOp;
splitOp->prev = newOp;
splitOp->next->next = newOp;
+
+ if (using_polytree_)
+ {
+ if (Path1InsidePath2(prevOp, newOp))
+ {
+ newOr->splits = new OutRecList();
+ newOr->splits->push_back(outrec);
+ }
+ else
+ {
+ if (!outrec->splits) outrec->splits = new OutRecList();
+ outrec->splits->push_back(newOr);
+ }
+ }
}
else
{
@@ -1521,6 +1708,28 @@ namespace Clipper2Lib {
return op;
}
+ inline void TrimHorz(Active& horzEdge, bool preserveCollinear)
+ {
+ bool wasTrimmed = false;
+ Point64 pt = NextVertex(horzEdge)->pt;
+ while (pt.y == horzEdge.top.y)
+ {
+ //always trim 180 deg. spikes (in closed paths)
+ //but otherwise break if preserveCollinear = true
+ if (preserveCollinear &&
+ ((pt.x < horzEdge.top.x) != (horzEdge.bot.x < horzEdge.top.x)))
+ break;
+
+ horzEdge.vertex_top = NextVertex(horzEdge);
+ horzEdge.top = pt;
+ wasTrimmed = true;
+ if (IsMaxima(horzEdge)) break;
+ pt = NextVertex(horzEdge)->pt;
+ }
+
+ if (wasTrimmed) SetDx(horzEdge); // +/-infinity
+ }
+
inline void ClipperBase::UpdateEdgeIntoAEL(Active* e)
{
@@ -1532,11 +1741,15 @@ namespace Clipper2Lib {
if (IsJoined(*e)) Split(*e, e->bot);
- if (IsHorizontal(*e)) return;
- InsertScanline(e->top.y);
+ if (IsHorizontal(*e))
+ {
+ if (!IsOpen(*e)) TrimHorz(*e, preserve_collinear_);
+ return;
+ }
+ InsertScanline(e->top.y);
CheckJoinLeft(*e, e->bot);
- CheckJoinRight(*e, e->bot);
+ CheckJoinRight(*e, e->bot, true); // (#500)
}
Active* FindEdgeWithMatchingLocMin(Active* e)
@@ -1596,17 +1809,14 @@ namespace Clipper2Lib {
default: if (std::abs(edge_c->wind_cnt) != 1) return nullptr; break;
}
+ OutPt* resultOp;
//toggle contribution ...
if (IsHotEdge(*edge_o))
{
- OutPt* resultOp = AddOutPt(*edge_o, pt);
-#ifdef USINGZ
- if (zCallback_) SetZ(e1, e2, resultOp->pt);
-#endif
+ resultOp = AddOutPt(*edge_o, pt);
if (IsFront(*edge_o)) edge_o->outrec->front_edge = nullptr;
else edge_o->outrec->back_edge = nullptr;
edge_o->outrec = nullptr;
- return resultOp;
}
//horizontal edges can pass under open paths at a LocMins
@@ -1626,11 +1836,16 @@ namespace Clipper2Lib {
return e3->outrec->pts;
}
else
- return StartOpenPath(*edge_o, pt);
+ resultOp = StartOpenPath(*edge_o, pt);
}
else
- return StartOpenPath(*edge_o, pt);
- }
+ resultOp = StartOpenPath(*edge_o, pt);
+
+#ifdef USINGZ
+ if (zCallback_) SetZ(*edge_o, *edge_c, resultOp->pt);
+#endif
+ return resultOp;
+ } // end of an open path intersection
//MANAGING CLOSED PATHS FROM HERE ON
@@ -1895,105 +2110,6 @@ namespace Clipper2Lib {
} while (op != outrec->pts);
}
- inline Rect64 GetBounds(OutPt* op)
- {
- Rect64 result(op->pt.x, op->pt.y, op->pt.x, op->pt.y);
- OutPt* op2 = op->next;
- while (op2 != op)
- {
- if (op2->pt.x < result.left) result.left = op2->pt.x;
- else if (op2->pt.x > result.right) result.right = op2->pt.x;
- if (op2->pt.y < result.top) result.top = op2->pt.y;
- else if (op2->pt.y > result.bottom) result.bottom = op2->pt.y;
- op2 = op2->next;
- }
- return result;
- }
-
- static PointInPolygonResult PointInOpPolygon(const Point64& pt, OutPt* op)
- {
- if (op == op->next || op->prev == op->next)
- return PointInPolygonResult::IsOutside;
-
- OutPt* op2 = op;
- do
- {
- if (op->pt.y != pt.y) break;
- op = op->next;
- } while (op != op2);
- if (op->pt.y == pt.y) // not a proper polygon
- return PointInPolygonResult::IsOutside;
-
- bool is_above = op->pt.y < pt.y, starting_above = is_above;
- int val = 0;
- op2 = op->next;
- while (op2 != op)
- {
- if (is_above)
- while (op2 != op && op2->pt.y < pt.y) op2 = op2->next;
- else
- while (op2 != op && op2->pt.y > pt.y) op2 = op2->next;
- if (op2 == op) break;
-
- // must have touched or crossed the pt.Y horizonal
- // and this must happen an even number of times
-
- if (op2->pt.y == pt.y) // touching the horizontal
- {
- if (op2->pt.x == pt.x || (op2->pt.y == op2->prev->pt.y &&
- (pt.x < op2->prev->pt.x) != (pt.x < op2->pt.x)))
- return PointInPolygonResult::IsOn;
-
- op2 = op2->next;
- if (op2 == op) break;
- continue;
- }
-
- if (pt.x < op2->pt.x && pt.x < op2->prev->pt.x);
- // do nothing because
- // we're only interested in edges crossing on the left
- else if ((pt.x > op2->prev->pt.x && pt.x > op2->pt.x))
- val = 1 - val; // toggle val
- else
- {
- double d = CrossProduct(op2->prev->pt, op2->pt, pt);
- if (d == 0) return PointInPolygonResult::IsOn;
- if ((d < 0) == is_above) val = 1 - val;
- }
- is_above = !is_above;
- op2 = op2->next;
- }
-
- if (is_above != starting_above)
- {
- double d = CrossProduct(op2->prev->pt, op2->pt, pt);
- if (d == 0) return PointInPolygonResult::IsOn;
- if ((d < 0) == is_above) val = 1 - val;
- }
-
- if (val == 0) return PointInPolygonResult::IsOutside;
- else return PointInPolygonResult::IsInside;
- }
-
- inline bool Path1InsidePath2(OutPt* op1, OutPt* op2)
- {
- // we need to make some accommodation for rounding errors
- // so we won't jump if the first vertex is found outside
- int outside_cnt = 0;
- OutPt* op = op1;
- do
- {
- PointInPolygonResult result = PointInOpPolygon(op->pt, op2);
- if (result == PointInPolygonResult::IsOutside) ++outside_cnt;
- else if (result == PointInPolygonResult::IsInside) --outside_cnt;
- op = op->next;
- } while (op != op1 && std::abs(outside_cnt) < 2);
- if (std::abs(outside_cnt) > 1) return (outside_cnt < 0);
- // since path1's location is still equivocal, check its midpoint
- Point64 mp = GetBounds(op).MidPoint();
- return PointInOpPolygon(mp, op2) == PointInPolygonResult::IsInside;
- }
-
inline bool SetHorzSegHeadingForward(HorzSegment& hs, OutPt* opP, OutPt* opN)
{
if (opP->pt.x == opN->pt.x) return false;
@@ -2051,7 +2167,7 @@ namespace Clipper2Lib {
horz_seg_list_.end(),
[](HorzSegment& hs) { return UpdateHorzSegment(hs); });
if (j < 2) return;
- std::sort(horz_seg_list_.begin(), horz_seg_list_.end(), HorzSegSorter());
+ std::stable_sort(horz_seg_list_.begin(), horz_seg_list_.end(), HorzSegSorter());
HorzSegmentList::iterator hs1 = horz_seg_list_.begin(), hs2;
HorzSegmentList::iterator hs_end = hs1 +j;
@@ -2061,8 +2177,8 @@ namespace Clipper2Lib {
{
for (hs2 = hs1 + 1; hs2 != hs_end; ++hs2)
{
- if (hs2->left_op->pt.x >= hs1->right_op->pt.x) break;
- if (hs2->left_to_right == hs1->left_to_right ||
+ if ((hs2->left_op->pt.x >= hs1->right_op->pt.x) ||
+ (hs2->left_to_right == hs1->left_to_right) ||
(hs2->right_op->pt.x <= hs1->left_op->pt.x)) continue;
int64_t curr_y = hs1->left_op->pt.y;
if (hs1->left_to_right)
@@ -2095,6 +2211,17 @@ namespace Clipper2Lib {
}
}
+ void MoveSplits(OutRec* fromOr, OutRec* toOr)
+ {
+ if (!fromOr->splits) return;
+ if (!toOr->splits) toOr->splits = new OutRecList();
+ OutRecList::iterator orIter = fromOr->splits->begin();
+ for (; orIter != fromOr->splits->end(); ++orIter)
+ toOr->splits->push_back(*orIter);
+ fromOr->splits->clear();
+ }
+
+
void ClipperBase::ProcessHorzJoins()
{
for (const HorzJoin& j : horz_join_list_)
@@ -2109,36 +2236,53 @@ namespace Clipper2Lib {
op1b->prev = op2b;
op2b->next = op1b;
- if (or1 == or2)
+ if (or1 == or2) // 'join' is really a split
{
- or2 = new OutRec();
+ or2 = NewOutRec();
or2->pts = op1b;
FixOutRecPts(or2);
+
+ //if or1->pts has moved to or2 then update or1->pts!!
if (or1->pts->outrec == or2)
{
or1->pts = j.op1;
or1->pts->outrec = or1;
}
- if (using_polytree_)
+ if (using_polytree_) //#498, #520, #584, D#576, #618
{
- if (Path1InsidePath2(or2->pts, or1->pts))
- SetOwner(or2, or1);
- else if (Path1InsidePath2(or1->pts, or2->pts))
- SetOwner(or1, or2);
- else
+ if (Path1InsidePath2(or1->pts, or2->pts))
+ {
+ //swap or1's & or2's pts
+ OutPt* tmp = or1->pts;
+ or1->pts = or2->pts;
+ or2->pts = tmp;
+ FixOutRecPts(or1);
+ FixOutRecPts(or2);
+ //or2 is now inside or1
or2->owner = or1;
+ }
+ else if (Path1InsidePath2(or2->pts, or1->pts))
+ {
+ or2->owner = or1;
+ }
+ else
+ or2->owner = or1->owner;
+
+ if (!or1->splits) or1->splits = new OutRecList();
+ or1->splits->push_back(or2);
}
else
or2->owner = or1;
-
- outrec_list_.push_back(or2);
}
else
{
or2->pts = nullptr;
if (using_polytree_)
+ {
SetOwner(or2, or1);
+ MoveSplits(or2, or1); //#618
+ }
else
or2->owner = or1;
}
@@ -2335,35 +2479,6 @@ namespace Clipper2Lib {
}
}
- inline bool HorzIsSpike(const Active& horzEdge)
- {
- Point64 nextPt = NextVertex(horzEdge)->pt;
- return (nextPt.y == horzEdge.bot.y) &&
- (horzEdge.bot.x < horzEdge.top.x) != (horzEdge.top.x < nextPt.x);
- }
-
- inline void TrimHorz(Active& horzEdge, bool preserveCollinear)
- {
- bool wasTrimmed = false;
- Point64 pt = NextVertex(horzEdge)->pt;
- while (pt.y == horzEdge.top.y)
- {
- //always trim 180 deg. spikes (in closed paths)
- //but otherwise break if preserveCollinear = true
- if (preserveCollinear &&
- ((pt.x < horzEdge.top.x) != (horzEdge.bot.x < horzEdge.top.x)))
- break;
-
- horzEdge.vertex_top = NextVertex(horzEdge);
- horzEdge.top = pt;
- wasTrimmed = true;
- if (IsMaxima(horzEdge)) break;
- pt = NextVertex(horzEdge)->pt;
- }
-
- if (wasTrimmed) SetDx(horzEdge); // +/-infinity
- }
-
void ClipperBase::DoHorizontal(Active& horz)
/*******************************************************************************
* Notes: Horizontal edges (HEs) at scanline intersections (ie at the top or *
@@ -2389,10 +2504,10 @@ namespace Clipper2Lib {
else
vertex_max = GetCurrYMaximaVertex(horz);
- // remove 180 deg.spikes and also simplify
- // consecutive horizontals when PreserveCollinear = true
- if (vertex_max && !horzIsOpen && vertex_max != horz.vertex_top)
- TrimHorz(horz, PreserveCollinear);
+ //// remove 180 deg.spikes and also simplify
+ //// consecutive horizontals when PreserveCollinear = true
+ //if (!horzIsOpen && vertex_max != horz.vertex_top)
+ // TrimHorz(horz, PreserveCollinear);
int64_t horz_left, horz_right;
bool is_left_to_right =
@@ -2407,7 +2522,6 @@ namespace Clipper2Lib {
#endif
AddTrialHorzJoin(op);
}
- OutRec* currHorzOutrec = horz.outrec;
while (true) // loop through consec. horizontal edges
{
@@ -2422,6 +2536,9 @@ namespace Clipper2Lib {
if (IsHotEdge(horz) && IsJoined(*e))
Split(*e, e->top);
+ //if (IsHotEdge(horz) != IsHotEdge(*e))
+ // DoError(undefined_error_i);
+
if (IsHotEdge(horz))
{
while (horz.vertex_top != vertex_max)
@@ -2476,6 +2593,7 @@ namespace Clipper2Lib {
{
IntersectEdges(horz, *e, pt);
SwapPositionsInAEL(horz, *e);
+ CheckJoinLeft(*e, pt);
horz.curr_x = e->curr_x;
e = horz.next_in_ael;
}
@@ -2483,13 +2601,13 @@ namespace Clipper2Lib {
{
IntersectEdges(*e, horz, pt);
SwapPositionsInAEL(*e, horz);
+ CheckJoinRight(*e, pt);
horz.curr_x = e->curr_x;
e = horz.prev_in_ael;
}
- if (horz.outrec && horz.outrec != currHorzOutrec)
+ if (horz.outrec)
{
- currHorzOutrec = horz.outrec;
//nb: The outrec containining the op returned by IntersectEdges
//above may no longer be associated with horzEdge.
AddTrialHorzJoin(GetLastOp(horz));
@@ -2519,14 +2637,16 @@ namespace Clipper2Lib {
AddOutPt(horz, horz.top);
UpdateEdgeIntoAEL(&horz);
- if (PreserveCollinear && !horzIsOpen && HorzIsSpike(horz))
- TrimHorz(horz, true);
-
is_left_to_right =
ResetHorzDirection(horz, vertex_max, horz_left, horz_right);
}
- if (IsHotEdge(horz)) AddOutPt(horz, horz.top);
+ if (IsHotEdge(horz))
+ {
+ OutPt* op = AddOutPt(horz, horz.top);
+ AddTrialHorzJoin(op);
+ }
+
UpdateEdgeIntoAEL(&horz); // end of an intermediate horiz.
}
@@ -2638,10 +2758,10 @@ namespace Clipper2Lib {
const Point64& pt, bool check_curr_x)
{
Active* prev = e.prev_in_ael;
- if (IsOpen(e) || !IsHotEdge(e) || !prev ||
- IsOpen(*prev) || !IsHotEdge(*prev) ||
- pt.y < e.top.y + 2 || pt.y < prev->top.y + 2) // avoid trivial joins
- return;
+ if (IsOpen(e) || !IsHotEdge(e) || !prev ||
+ IsOpen(*prev) || !IsHotEdge(*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
if (check_curr_x)
{
@@ -2664,10 +2784,10 @@ namespace Clipper2Lib {
const Point64& pt, bool check_curr_x)
{
Active* next = e.next_in_ael;
- if (IsOpen(e) || !IsHotEdge(e) ||
- !next || IsOpen(*next) || !IsHotEdge(*next) ||
- pt.y < e.top.y +2 || pt.y < next->top.y +2) // avoids trivial joins
- return;
+ if (IsOpen(e) || !IsHotEdge(e) ||
+ !next || IsOpen(*next) || !IsHotEdge(*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
if (check_curr_x)
{
@@ -2682,6 +2802,7 @@ namespace Clipper2Lib {
JoinOutrecPaths(e, *next);
else
JoinOutrecPaths(*next, e);
+
e.join_with = JoinWith::Right;
next->join_with = JoinWith::Left;
}
@@ -2752,12 +2873,34 @@ namespace Clipper2Lib {
if (!outrec->bounds.IsEmpty()) return true;
CleanCollinear(outrec);
if (!outrec->pts ||
- !BuildPath64(outrec->pts, ReverseSolution, false, outrec->path))
- return false;
+ !BuildPath64(outrec->pts, reverse_solution_, false, outrec->path)){
+ return false;}
outrec->bounds = GetBounds(outrec->path);
return true;
}
+ bool ClipperBase::CheckSplitOwner(OutRec* outrec, OutRecList* splits)
+ {
+ for (auto split : *splits)
+ {
+ split = GetRealOutRec(split);
+ if(!split || split == outrec || split->recursive_split == outrec) continue;
+ split->recursive_split = outrec; // prevent infinite loops
+
+ if (split->splits && CheckSplitOwner(outrec, split->splits))
+ return true;
+ else if (CheckBounds(split) &&
+ IsValidOwner(outrec, split) &&
+ split->bounds.Contains(outrec->bounds) &&
+ Path1InsidePath2(outrec->pts, split->pts))
+ {
+ outrec->owner = split; //found in split
+ return true;
+ }
+ }
+ return false;
+ }
+
void ClipperBase::RecursiveCheckOwners(OutRec* outrec, PolyPath* polypath)
{
// pre-condition: outrec will have valid bounds
@@ -2765,52 +2908,25 @@ namespace Clipper2Lib {
if (outrec->polypath || outrec->bounds.IsEmpty()) return;
- while (outrec->owner &&
- (!outrec->owner->pts || !CheckBounds(outrec->owner)))
- outrec->owner = outrec->owner->owner;
-
- if (outrec->owner && !outrec->owner->polypath)
- RecursiveCheckOwners(outrec->owner, polypath);
-
while (outrec->owner)
- if (outrec->owner->bounds.Contains(outrec->bounds) &&
- Path1InsidePath2(outrec->pts, outrec->owner->pts))
- break; // found - owner contain outrec!
- else
- outrec->owner = outrec->owner->owner;
+ {
+ if (outrec->owner->splits && CheckSplitOwner(outrec, outrec->owner->splits)) break;
+ if (outrec->owner->pts && CheckBounds(outrec->owner) &&
+ outrec->owner->bounds.Contains(outrec->bounds) &&
+ Path1InsidePath2(outrec->pts, outrec->owner->pts)) break;
+ outrec->owner = outrec->owner->owner;
+ }
if (outrec->owner)
+ {
+ if (!outrec->owner->polypath)
+ RecursiveCheckOwners(outrec->owner, polypath);
outrec->polypath = outrec->owner->polypath->AddChild(outrec->path);
+ }
else
outrec->polypath = polypath->AddChild(outrec->path);
}
- void ClipperBase::DeepCheckOwners(OutRec* outrec, PolyPath* polypath)
- {
- RecursiveCheckOwners(outrec, polypath);
-
- while (outrec->owner && outrec->owner->splits)
- {
- OutRec* split = nullptr;
- for (auto s : *outrec->owner->splits)
- {
- split = GetRealOutRec(s);
- if (split && split != outrec &&
- split != outrec->owner && CheckBounds(split) &&
- split->bounds.Contains(outrec->bounds) &&
- Path1InsidePath2(outrec->pts, split->pts))
- {
- RecursiveCheckOwners(split, polypath);
- outrec->owner = split; //found in split
- break; // inner 'for' loop
- }
- else
- split = nullptr;
- }
- if (!split) break;
- }
- }
-
void Clipper64::BuildPaths64(Paths64& solutionClosed, Paths64* solutionOpen)
{
solutionClosed.resize(0);
@@ -2832,7 +2948,7 @@ namespace Clipper2Lib {
Path64 path;
if (solutionOpen && outrec->is_open)
{
- if (BuildPath64(outrec->pts, ReverseSolution, true, path))
+ if (BuildPath64(outrec->pts, reverse_solution_, true, path))
solutionOpen->emplace_back(std::move(path));
}
else
@@ -2840,7 +2956,7 @@ namespace Clipper2Lib {
// nb: CleanCollinear can add to outrec_list_
CleanCollinear(outrec);
//closed paths should always return a Positive orientation
- if (BuildPath64(outrec->pts, ReverseSolution, false, path))
+ if (BuildPath64(outrec->pts, reverse_solution_, false, path))
solutionClosed.emplace_back(std::move(path));
}
}
@@ -2863,13 +2979,13 @@ namespace Clipper2Lib {
if (outrec->is_open)
{
Path64 path;
- if (BuildPath64(outrec->pts, ReverseSolution, true, path))
+ if (BuildPath64(outrec->pts, reverse_solution_, true, path))
open_paths.push_back(path);
continue;
}
if (CheckBounds(outrec))
- DeepCheckOwners(outrec, &polytree);
+ RecursiveCheckOwners(outrec, &polytree);
}
}
@@ -2940,14 +3056,14 @@ namespace Clipper2Lib {
PathD path;
if (solutionOpen && outrec->is_open)
{
- if (BuildPathD(outrec->pts, ReverseSolution, true, path, invScale_))
+ if (BuildPathD(outrec->pts, reverse_solution_, true, path, invScale_))
solutionOpen->emplace_back(std::move(path));
}
else
{
CleanCollinear(outrec);
//closed paths should always return a Positive orientation
- if (BuildPathD(outrec->pts, ReverseSolution, false, path, invScale_))
+ if (BuildPathD(outrec->pts, reverse_solution_, false, path, invScale_))
solutionClosed.emplace_back(std::move(path));
}
}
@@ -2960,19 +3076,22 @@ namespace Clipper2Lib {
if (has_open_paths_)
open_paths.reserve(outrec_list_.size());
- for (OutRec* outrec : outrec_list_)
+ // outrec_list_.size() is not static here because
+ // BuildPathD below can indirectly add additional OutRec //#607
+ for (size_t i = 0; i < outrec_list_.size(); ++i)
{
+ OutRec* outrec = outrec_list_[i];
if (!outrec || !outrec->pts) continue;
if (outrec->is_open)
{
PathD path;
- if (BuildPathD(outrec->pts, ReverseSolution, true, path, invScale_))
+ if (BuildPathD(outrec->pts, reverse_solution_, true, path, invScale_))
open_paths.push_back(path);
continue;
}
if (CheckBounds(outrec))
- DeepCheckOwners(outrec, &polytree);
+ RecursiveCheckOwners(outrec, &polytree);
}
}
diff --git a/thirdparty/clipper2/src/clipper.offset.cpp b/thirdparty/clipper2/src/clipper.offset.cpp
index 78cd82376a..0282aa49bb 100644
--- a/thirdparty/clipper2/src/clipper.offset.cpp
+++ b/thirdparty/clipper2/src/clipper.offset.cpp
@@ -1,6 +1,6 @@
/*******************************************************************************
* Author : Angus Johnson *
-* Date : 22 March 2023 *
+* Date : 28 November 2023 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2023 *
* Purpose : Path Offset (Inflate/Shrink) *
@@ -20,38 +20,63 @@ const double floating_point_tolerance = 1e-12;
// Miscellaneous methods
//------------------------------------------------------------------------------
-void GetBoundsAndLowestPolyIdx(const Paths64& paths, Rect64& r, int & idx)
+inline bool ToggleBoolIf(bool val, bool condition)
{
- idx = -1;
- r = MaxInvalidRect64;
- int64_t lpx = 0;
- for (int i = 0; i < static_cast<int>(paths.size()); ++i)
- for (const Point64& p : paths[i])
+ 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)
{
- if (p.y >= r.bottom)
- {
- if (p.y > r.bottom || p.x < lpx)
- {
- idx = i;
- lpx = p.x;
- r.bottom = p.y;
- }
- }
- else if (p.y < r.top) r.top = p.y;
- if (p.x > r.right) r.right = p.x;
- else if (p.x < r.left) r.left = p.x;
+ 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;
}
- //if (idx < 0) r = Rect64(0, 0, 0, 0);
- //if (r.top == INT64_MIN) r.bottom = r.top;
- //if (r.left == INT64_MIN) r.left = r.right;
+ recList.push_back(r);
+ }
}
-bool IsSafeOffset(const Rect64& r, double abs_delta)
+bool ValidateBounds(std::vector<Rect64>& recList, double delta)
{
- return r.left > min_coord + abs_delta &&
- r.right < max_coord - abs_delta &&
- r.top > min_coord + abs_delta &&
- r.bottom < max_coord - abs_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;
+ 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))
+ {
+ botPt = Point64(r.left, r.bottom);
+ result = static_cast<int>(i);
+ }
+ }
+ return result;
}
PointD GetUnitNormal(const Point64& pt1, const Point64& pt2)
@@ -78,8 +103,7 @@ inline double Hypot(double x, double 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;
@@ -126,6 +150,44 @@ inline void NegatePath(PathD& path)
}
}
+
+//------------------------------------------------------------------------------
+// ClipperOffset::Group methods
+//------------------------------------------------------------------------------
+
+ClipperOffset::Group::Group(const Paths64& _paths, JoinType _join_type, EndType _end_type):
+ paths_in(_paths), join_type(_join_type), end_type(_end_type)
+{
+ bool is_joined =
+ (end_type == EndType::Polygon) ||
+ (end_type == EndType::Joined);
+ 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);
+ // 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();
+ }
+ else
+ {
+ lowest_path_idx = -1;
+ is_reversed = false;
+ is_hole_list.resize(paths_in.size());
+ }
+}
+
+
//------------------------------------------------------------------------------
// ClipperOffset methods
//------------------------------------------------------------------------------
@@ -148,10 +210,10 @@ void ClipperOffset::BuildNormals(const Path64& path)
norms.clear();
norms.reserve(path.size());
if (path.size() == 0) return;
- Path64::const_iterator path_iter, path_last_iter = --path.cend();
- for (path_iter = path.cbegin(); path_iter != path_last_iter; ++path_iter)
+ Path64::const_iterator path_iter, path_stop_iter = --path.cend();
+ for (path_iter = path.cbegin(); path_iter != path_stop_iter; ++path_iter)
norms.push_back(GetUnitNormal(*path_iter,*(path_iter +1)));
- norms.push_back(GetUnitNormal(*path_last_iter, *(path.cbegin())));
+ norms.push_back(GetUnitNormal(*path_stop_iter, *(path.cbegin())));
}
inline PointD TranslatePoint(const PointD& pt, double dx, double dy)
@@ -201,19 +263,39 @@ PointD IntersectPoint(const PointD& pt1a, const PointD& pt1b,
}
}
-void ClipperOffset::DoSquare(Group& group, const Path64& path, size_t j, size_t k)
+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_);
+ 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);
+ }
+ 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);
+ }
+ path_out.push_back(Point64(pt1));
+ path_out.push_back(Point64(pt2));
+}
+
+void ClipperOffset::DoSquare(const Path64& path, size_t j, size_t k)
{
PointD vec;
if (j == k)
- vec = PointD(norms[0].y, -norms[0].x);
+ vec = PointD(norms[j].y, -norms[j].x);
else
vec = GetAvgUnitVector(
PointD(-norms[k].y, norms[k].x),
PointD(norms[j].y, -norms[j].x));
+ double abs_delta = std::abs(group_delta_);
+
// now offset the original vertex delta units along unit vector
PointD ptQ = PointD(path[j]);
- ptQ = TranslatePoint(ptQ, abs_group_delta_ * vec.x, abs_group_delta_ * vec.y);
+ ptQ = TranslatePoint(ptQ, abs_delta * vec.x, abs_delta * vec.y);
// get perpendicular vertices
PointD pt1 = TranslatePoint(ptQ, group_delta_ * vec.y, group_delta_ * -vec.x);
PointD pt2 = TranslatePoint(ptQ, group_delta_ * -vec.y, group_delta_ * vec.x);
@@ -227,8 +309,8 @@ void ClipperOffset::DoSquare(Group& group, const Path64& path, size_t j, size_t
pt.z = ptQ.z;
#endif
//get the second intersect point through reflecion
- group.path.push_back(Point64(ReflectPoint(pt, ptQ)));
- group.path.push_back(Point64(pt));
+ path_out.push_back(Point64(ReflectPoint(pt, ptQ)));
+ path_out.push_back(Point64(pt));
}
else
{
@@ -237,57 +319,67 @@ void ClipperOffset::DoSquare(Group& group, const Path64& path, size_t j, size_t
#ifdef USINGZ
pt.z = ptQ.z;
#endif
- group.path.push_back(Point64(pt));
+ path_out.push_back(Point64(pt));
//get the second intersect point through reflecion
- group.path.push_back(Point64(ReflectPoint(pt, ptQ)));
+ path_out.push_back(Point64(ReflectPoint(pt, ptQ)));
}
}
-void ClipperOffset::DoMiter(Group& group, const Path64& path, size_t j, size_t k, double cos_a)
+void ClipperOffset::DoMiter(const Path64& path, size_t j, size_t k, double cos_a)
{
double q = group_delta_ / (cos_a + 1);
#ifdef USINGZ
- group.path.push_back(Point64(
+ path_out.push_back(Point64(
path[j].x + (norms[k].x + norms[j].x) * q,
path[j].y + (norms[k].y + norms[j].y) * q,
path[j].z));
#else
- group.path.push_back(Point64(
+ path_out.push_back(Point64(
path[j].x + (norms[k].x + norms[j].x) * q,
path[j].y + (norms[k].y + norms[j].y) * q));
#endif
}
-void ClipperOffset::DoRound(Group& group, const Path64& path, size_t j, size_t k, double angle)
+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,
+ // 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 ?
+ std::min(abs_delta, arc_tolerance_) :
+ std::log10(2 + abs_delta) * default_arc_tolerance);
+ double steps_per_360 = std::min(PI / std::acos(1 - arcTol / abs_delta), abs_delta * PI);
+ step_sin_ = std::sin(2 * PI / steps_per_360);
+ step_cos_ = std::cos(2 * PI / steps_per_360);
+ if (group_delta_ < 0.0) step_sin_ = -step_sin_;
+ steps_per_rad_ = steps_per_360 / (2 * PI);
+ }
+
Point64 pt = path[j];
PointD offsetVec = PointD(norms[k].x * group_delta_, norms[k].y * group_delta_);
if (j == k) offsetVec.Negate();
#ifdef USINGZ
- group.path.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y, pt.z));
+ path_out.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y, pt.z));
#else
- group.path.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y));
+ path_out.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y));
#endif
- if (angle > -PI + 0.01) // avoid 180deg concave
+ int steps = static_cast<int>(std::ceil(steps_per_rad_ * std::abs(angle))); // #448, #456
+ for (int i = 1; i < steps; ++i) // ie 1 less than steps
{
- int steps = static_cast<int>(std::ceil(steps_per_rad_ * std::abs(angle))); // #448, #456
- for (int i = 1; i < steps; ++i) // ie 1 less than steps
- {
- offsetVec = PointD(offsetVec.x * step_cos_ - step_sin_ * offsetVec.y,
- offsetVec.x * step_sin_ + offsetVec.y * step_cos_);
+ offsetVec = PointD(offsetVec.x * step_cos_ - step_sin_ * offsetVec.y,
+ offsetVec.x * step_sin_ + offsetVec.y * step_cos_);
#ifdef USINGZ
- group.path.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y, pt.z));
+ path_out.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y, pt.z));
#else
- group.path.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y));
+ path_out.push_back(Point64(pt.x + offsetVec.x, pt.y + offsetVec.y));
#endif
-
- }
}
- group.path.push_back(GetPerpendic(path[j], norms[j], group_delta_));
+ path_out.push_back(GetPerpendic(path[j], norms[j], group_delta_));
}
-void ClipperOffset::OffsetPoint(Group& group, Path64& path, size_t j, size_t& k)
+void ClipperOffset::OffsetPoint(Group& group, const Path64& path, size_t j, size_t k)
{
// Let A = change in angle where edges join
// A == 0: ie no change in angle (flat join)
@@ -302,50 +394,57 @@ void ClipperOffset::OffsetPoint(Group& group, Path64& path, size_t j, size_t& k)
if (sin_a > 1.0) sin_a = 1.0;
else if (sin_a < -1.0) sin_a = -1.0;
- if (cos_a > 0.99) // almost straight - less than 8 degrees
+ if (deltaCallback64_) {
+ group_delta_ = deltaCallback64_(path, norms, j, k);
+ if (group.is_reversed) group_delta_ = -group_delta_;
+ }
+ if (std::fabs(group_delta_) <= floating_point_tolerance)
{
- group.path.push_back(GetPerpendic(path[j], norms[k], group_delta_));
- if (cos_a < 0.9998) // greater than 1 degree (#424)
- group.path.push_back(GetPerpendic(path[j], norms[j], group_delta_)); // (#418)
+ path_out.push_back(path[j]);
+ return;
}
- else if (cos_a > -0.99 && (sin_a * group_delta_ < 0))
+
+ if (cos_a > -0.99 && (sin_a * group_delta_ < 0)) // test for concavity first (#593)
{
// is concave
- group.path.push_back(GetPerpendic(path[j], norms[k], group_delta_));
+ 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
- group.path.push_back(path[j]); // (#405)
- group.path.push_back(GetPerpendic(path[j], norms[j], group_delta_));
- }
- else if (join_type_ == JoinType::Round)
- DoRound(group, path, j, k, std::atan2(sin_a, cos_a));
+ // path reversals are fully cleaned with the trailing clipper
+ path_out.push_back(path[j]); // (#405)
+ path_out.push_back(GetPerpendic(path[j], norms[j], group_delta_));
+ }
+ else if (cos_a > 0.999 && join_type_ != JoinType::Round)
+ {
+ // almost straight - less than 2.5 degree (#424, #482, #526 & #724)
+ DoMiter(path, j, k, cos_a);
+ }
else if (join_type_ == JoinType::Miter)
{
- // miter unless the angle is so acute the miter would exceeds ML
- if (cos_a > temp_lim_ - 1) DoMiter(group, path, j, k, cos_a);
- else DoSquare(group, path, j, k);
+ // miter unless the angle is sufficiently acute to exceed ML
+ if (cos_a > temp_lim_ - 1) DoMiter(path, j, k, cos_a);
+ else DoSquare(path, j, k);
}
- // don't bother squaring angles that deviate < ~20 degrees because
- // squaring will be indistinguishable from mitering and just be a lot slower
- else if (cos_a > 0.9)
- DoMiter(group, path, j, k, cos_a);
+ else if (join_type_ == JoinType::Round)
+ DoRound(path, j, k, std::atan2(sin_a, cos_a));
+ else if ( join_type_ == JoinType::Bevel)
+ DoBevel(path, j, k);
else
- DoSquare(group, path, j, k);
-
- k = j;
+ DoSquare(path, j, k);
}
-void ClipperOffset::OffsetPolygon(Group& group, Path64& path)
+void ClipperOffset::OffsetPolygon(Group& group, const Path64& path)
{
- for (Path64::size_type i = 0, j = path.size() -1; i < path.size(); j = i, ++i)
- OffsetPoint(group, path, i, j);
- group.paths_out.push_back(group.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);
}
-void ClipperOffset::OffsetOpenJoined(Group& group, Path64& path)
+void ClipperOffset::OffsetOpenJoined(Group& group, const Path64& path)
{
OffsetPolygon(group, path);
- std::reverse(path.begin(), path.end());
+ Path64 reverse_path(path);
+ std::reverse(reverse_path.begin(), reverse_path.end());
//rebuild normals // BuildNormals(path);
std::reverse(norms.begin(), norms.end());
@@ -353,41 +452,36 @@ void ClipperOffset::OffsetOpenJoined(Group& group, Path64& path)
norms.erase(norms.begin());
NegatePath(norms);
- group.path.clear();
- OffsetPolygon(group, path);
+ OffsetPolygon(group, reverse_path);
}
-void ClipperOffset::OffsetOpenPath(Group& group, Path64& path)
+void ClipperOffset::OffsetOpenPath(Group& group, const Path64& path)
{
// do the line start cap
- switch (end_type_)
+ if (deltaCallback64_) group_delta_ = deltaCallback64_(path, norms, 0, 0);
+
+ if (std::fabs(group_delta_) <= floating_point_tolerance)
+ path_out.push_back(path[0]);
+ else
{
- case EndType::Butt:
-#ifdef USINGZ
- group.path.push_back(Point64(
- path[0].x - norms[0].x * group_delta_,
- path[0].y - norms[0].y * group_delta_,
- path[0].z));
-#else
- group.path.push_back(Point64(
- path[0].x - norms[0].x * group_delta_,
- path[0].y - norms[0].y * group_delta_));
-#endif
- group.path.push_back(GetPerpendic(path[0], norms[0], group_delta_));
- break;
- case EndType::Round:
- DoRound(group, path, 0,0, PI);
- break;
- default:
- DoSquare(group, path, 0, 0);
- break;
+ switch (end_type_)
+ {
+ case EndType::Butt:
+ DoBevel(path, 0, 0);
+ break;
+ case EndType::Round:
+ DoRound(path, 0, 0, PI);
+ break;
+ default:
+ DoSquare(path, 0, 0);
+ break;
+ }
}
-
+
size_t highI = path.size() - 1;
-
// offset the left side going forward
- for (Path64::size_type i = 1, k = 0; i < highI; ++i)
- OffsetPoint(group, path, i, k);
+ for (Path64::size_type j = 1, k = 0; j < highI; k = j, ++j)
+ OffsetPoint(group, path, j, k);
// reverse normals
for (size_t i = highI; i > 0; --i)
@@ -395,60 +489,46 @@ void ClipperOffset::OffsetOpenPath(Group& group, Path64& path)
norms[0] = norms[highI];
// do the line end cap
- switch (end_type_)
+ if (deltaCallback64_)
+ group_delta_ = deltaCallback64_(path, norms, highI, highI);
+
+ if (std::fabs(group_delta_) <= floating_point_tolerance)
+ path_out.push_back(path[highI]);
+ else
{
- case EndType::Butt:
-#ifdef USINGZ
- group.path.push_back(Point64(
- path[highI].x - norms[highI].x * group_delta_,
- path[highI].y - norms[highI].y * group_delta_,
- path[highI].z));
-#else
- group.path.push_back(Point64(
- path[highI].x - norms[highI].x * group_delta_,
- path[highI].y - norms[highI].y * group_delta_));
-#endif
- group.path.push_back(GetPerpendic(path[highI], norms[highI], group_delta_));
- break;
- case EndType::Round:
- DoRound(group, path, highI, highI, PI);
- break;
- default:
- DoSquare(group, path, highI, highI);
- break;
+ switch (end_type_)
+ {
+ case EndType::Butt:
+ DoBevel(path, highI, highI);
+ break;
+ case EndType::Round:
+ DoRound(path, highI, highI, PI);
+ break;
+ default:
+ DoSquare(path, highI, highI);
+ break;
+ }
}
- for (size_t i = highI, k = 0; i > 0; --i)
- OffsetPoint(group, path, i, k);
- group.paths_out.push_back(group.path);
+ for (size_t j = highI, k = 0; j > 0; k = j, --j)
+ OffsetPoint(group, path, j, k);
+ solution.push_back(path_out);
}
void ClipperOffset::DoGroupOffset(Group& group)
{
- Rect64 r;
- int idx = -1;
- //the lowermost polygon must be an outer polygon. So we can use that as the
- //designated orientation for outer polygons (needed for tidy-up clipping)
- GetBoundsAndLowestPolyIdx(group.paths_in, r, idx);
- if (idx < 0) return;
-
if (group.end_type == EndType::Polygon)
{
- double area = Area(group.paths_in[idx]);
- //if (area == 0) return; // probably unhelpful (#430)
- group.is_reversed = (area < 0);
- if (group.is_reversed) group_delta_ = -delta_;
- else group_delta_ = delta_;
- }
- else
- {
- group.is_reversed = false;
- group_delta_ = std::abs(delta_) * 0.5;
+ // 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_);
+ group_delta_ = (group.is_reversed) ? -delta_ : delta_;
}
- abs_group_delta_ = std::fabs(group_delta_);
+ else
+ group_delta_ = std::abs(delta_);// *0.5;
- // do range checking
- if (!IsSafeOffset(r, abs_group_delta_))
+ double abs_delta = std::fabs(group_delta_);
+ if (!ValidateBounds(group.bounds_list, abs_delta))
{
DoError(range_error_i);
error_code_ |= range_error_i;
@@ -458,80 +538,98 @@ void ClipperOffset::DoGroupOffset(Group& group)
join_type_ = group.join_type;
end_type_ = group.end_type;
- //calculate a sensible number of steps (for 360 deg for the given offset
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
double arcTol = (arc_tolerance_ > floating_point_tolerance ?
- std::min(abs_group_delta_, arc_tolerance_) :
- std::log10(2 + abs_group_delta_) * default_arc_tolerance);
- double steps_per_360 = PI / std::acos(1 - arcTol / abs_group_delta_);
- if (steps_per_360 > abs_group_delta_ * PI)
- steps_per_360 = abs_group_delta_ * PI; //ie avoids excessive precision
+ std::min(abs_delta, arc_tolerance_) :
+ std::log10(2 + abs_delta) * default_arc_tolerance);
+ double steps_per_360 = std::min(PI / std::acos(1 - arcTol / abs_delta), abs_delta * PI);
step_sin_ = std::sin(2 * PI / steps_per_360);
step_cos_ = std::cos(2 * PI / steps_per_360);
- if (group_delta_ < 0.0) step_sin_ = -step_sin_;
- steps_per_rad_ = steps_per_360 / (2 *PI);
+ if (group_delta_ < 0.0) step_sin_ = -step_sin_;
+ steps_per_rad_ = steps_per_360 / (2 * PI);
}
- bool is_joined =
- (end_type_ == EndType::Polygon) ||
- (end_type_ == EndType::Joined);
- Paths64::const_iterator path_iter;
- for(path_iter = group.paths_in.cbegin(); path_iter != group.paths_in.cend(); ++path_iter)
+ 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();
+ 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)
{
- Path64 path = StripDuplicates(*path_iter, is_joined);
- Path64::size_type cnt = path.size();
- if (cnt == 0 || ((cnt < 3) && group.end_type == EndType::Polygon))
- continue;
+ if (!path_rect_it->IsValid()) continue;
+ Path64::size_type pathLen = path_in_it->size();
+ path_out.clear();
- group.path.clear();
- if (cnt == 1) // single point - only valid with open paths
+ if (pathLen == 1) // single point
{
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_group_delta_;
- group.path = Ellipse(path[0], radius, radius);
+ double radius = abs_delta;
+ int steps = static_cast<int>(std::ceil(steps_per_rad_ * 2 * PI)); //#617
+ path_out = Ellipse(pt, radius, radius, steps);
#ifdef USINGZ
- for (auto& p : group.path) p.z = path[0].z;
+ for (auto& p : path_out) p.z = pt.z;
#endif
}
else
{
- int d = (int)std::ceil(abs_group_delta_);
- r = Rect64(path[0].x - d, path[0].y - d, path[0].x + d, path[0].y + d);
- group.path = r.AsPath();
+ int d = (int)std::ceil(abs_delta);
+ Rect64 r = Rect64(pt.x - d, pt.y - d, pt.x + d, pt.y + d);
+ path_out = r.AsPath();
#ifdef USINGZ
- for (auto& p : group.path) p.z = path[0].z;
+ for (auto& p : path_out) p.z = pt.z;
#endif
}
- group.paths_out.push_back(group.path);
- }
- else
- {
- if ((cnt == 2) && (group.end_type == EndType::Joined))
- {
- if (group.join_type == JoinType::Round)
- end_type_ = EndType::Round;
- else
- end_type_ = EndType::Square;
- }
+ 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;
+
+ if ((pathLen == 2) && (group.end_type == EndType::Joined))
+ end_type_ = (group.join_type == JoinType::Round) ?
+ EndType::Round :
+ EndType::Square;
+
+ BuildNormals(*path_in_it);
+ if (end_type_ == EndType::Polygon) OffsetPolygon(group, *path_in_it);
+ else if (end_type_ == EndType::Joined) OffsetOpenJoined(group, *path_in_it);
+ else OffsetOpenPath(group, *path_in_it);
+ }
+}
+
+
+size_t ClipperOffset::CalcSolutionCapacity()
+{
+ size_t result = 0;
+ for (const Group& g : groups_)
+ result += (g.end_type == EndType::Joined) ? g.paths_in.size() * 2 : g.paths_in.size();
+ return result;
+}
- BuildNormals(path);
- if (end_type_ == EndType::Polygon) OffsetPolygon(group, path);
- else if (end_type_ == EndType::Joined) OffsetOpenJoined(group, path);
- else OffsetOpenPath(group, path);
+bool ClipperOffset::CheckReverseOrientation()
+{
+ // nb: this assumes there's consistency in orientation between groups
+ bool is_reversed_orientation = false;
+ for (const Group& g : groups_)
+ if (g.end_type == EndType::Polygon)
+ {
+ is_reversed_orientation = g.is_reversed;
+ break;
}
- }
- solution.reserve(solution.size() + group.paths_out.size());
- copy(group.paths_out.begin(), group.paths_out.end(), back_inserter(solution));
- group.paths_out.clear();
+ return is_reversed_orientation;
}
void ClipperOffset::ExecuteInternal(double delta)
@@ -539,29 +637,29 @@ void ClipperOffset::ExecuteInternal(double delta)
error_code_ = 0;
solution.clear();
if (groups_.size() == 0) return;
+ solution.reserve(CalcSolutionCapacity());
- if (std::abs(delta) < 0.5)
+ 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);
for (const Group& group : groups_)
- {
- solution.reserve(solution.size() + group.paths_in.size());
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_);
+ return;
+ }
- 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();
- }
+ 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();
}
}
@@ -572,19 +670,17 @@ void ClipperOffset::Execute(double delta, Paths64& paths)
ExecuteInternal(delta);
if (!solution.size()) return;
- paths = solution;
+ bool paths_reversed = CheckReverseOrientation();
//clean up self-intersections ...
Clipper64 c;
- c.PreserveCollinear = false;
+ c.PreserveCollinear(false);
//the solution should retain the orientation of the input
- c.ReverseSolution = reverse_solution_ != groups_[0].is_reversed;
+ c.ReverseSolution(reverse_solution_ != paths_reversed);
#ifdef USINGZ
- if (zCallback64_) {
- c.SetZCallback(zCallback64_);
- }
+ if (zCallback64_) { c.SetZCallback(zCallback64_); }
#endif
c.AddSubject(solution);
- if (groups_[0].is_reversed)
+ if (paths_reversed)
c.Execute(ClipType::Union, FillRule::Negative, paths);
else
c.Execute(ClipType::Union, FillRule::Positive, paths);
@@ -598,21 +694,30 @@ void ClipperOffset::Execute(double delta, PolyTree64& polytree)
ExecuteInternal(delta);
if (!solution.size()) return;
+ bool paths_reversed = CheckReverseOrientation();
//clean up self-intersections ...
Clipper64 c;
- c.PreserveCollinear = false;
+ c.PreserveCollinear(false);
//the solution should retain the orientation of the input
- c.ReverseSolution = reverse_solution_ != groups_[0].is_reversed;
+ c.ReverseSolution (reverse_solution_ != paths_reversed);
#ifdef USINGZ
if (zCallback64_) {
c.SetZCallback(zCallback64_);
}
#endif
c.AddSubject(solution);
- if (groups_[0].is_reversed)
+
+
+ if (paths_reversed)
c.Execute(ClipType::Union, FillRule::Negative, polytree);
else
c.Execute(ClipType::Union, FillRule::Positive, polytree);
}
+void ClipperOffset::Execute(DeltaCallback64 delta_cb, Paths64& paths)
+{
+ deltaCallback64_ = delta_cb;
+ Execute(1.0, paths);
+}
+
} // namespace
diff --git a/thirdparty/clipper2/src/clipper.rectclip.cpp b/thirdparty/clipper2/src/clipper.rectclip.cpp
index 959972b440..9aa0fc0f76 100644
--- a/thirdparty/clipper2/src/clipper.rectclip.cpp
+++ b/thirdparty/clipper2/src/clipper.rectclip.cpp
@@ -1,6 +1,6 @@
/*******************************************************************************
* Author : Angus Johnson *
-* Date : 14 February 2023 *
+* Date : 8 September 2023 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2023 *
* Purpose : FAST rectangular clipping *
@@ -24,11 +24,11 @@ namespace Clipper2Lib {
for (const Point64& pt : path2)
{
PointInPolygonResult pip = PointInPolygon(pt, path1);
- switch (pip)
+ switch (pip)
{
case PointInPolygonResult::IsOutside: ++io_count; break;
- case PointInPolygonResult::IsInside: --io_count; break;
- default: continue;
+ case PointInPolygonResult::IsInside: --io_count; break;
+ default: continue;
}
if (std::abs(io_count) > 1) break;
}
@@ -66,6 +66,56 @@ namespace Clipper2Lib {
return true;
}
+ inline bool IsHorizontal(const Point64& pt1, const Point64& pt2)
+ {
+ return pt1.y == pt2.y;
+ }
+
+ inline bool GetSegmentIntersection(const Point64& p1,
+ const Point64& p2, const Point64& p3, const Point64& p4, Point64& ip)
+ {
+ double res1 = CrossProduct(p1, p3, p4);
+ double res2 = CrossProduct(p2, p3, p4);
+ if (res1 == 0)
+ {
+ ip = p1;
+ if (res2 == 0) return false; // segments are collinear
+ else if (p1 == p3 || p1 == p4) return true;
+ //else if (p2 == p3 || p2 == p4) { ip = p2; return true; }
+ else if (IsHorizontal(p3, p4)) return ((p1.x > p3.x) == (p1.x < p4.x));
+ else return ((p1.y > p3.y) == (p1.y < p4.y));
+ }
+ else if (res2 == 0)
+ {
+ ip = p2;
+ if (p2 == p3 || p2 == p4) return true;
+ else if (IsHorizontal(p3, p4)) return ((p2.x > p3.x) == (p2.x < p4.x));
+ else return ((p2.y > p3.y) == (p2.y < p4.y));
+ }
+ if ((res1 > 0) == (res2 > 0)) return false;
+
+ double res3 = CrossProduct(p3, p1, p2);
+ double res4 = CrossProduct(p4, p1, p2);
+ if (res3 == 0)
+ {
+ ip = p3;
+ if (p3 == p1 || p3 == p2) return true;
+ else if (IsHorizontal(p1, p2)) return ((p3.x > p1.x) == (p3.x < p2.x));
+ else return ((p3.y > p1.y) == (p3.y < p2.y));
+ }
+ else if (res4 == 0)
+ {
+ ip = p4;
+ if (p4 == p1 || p4 == p2) return true;
+ else if (IsHorizontal(p1, p2)) return ((p4.x > p1.x) == (p4.x < p2.x));
+ else return ((p4.y > p1.y) == (p4.y < p2.y));
+ }
+ if ((res3 > 0) == (res4 > 0)) return false;
+
+ // segments must intersect to get here
+ return GetIntersectPoint(p1, p2, p3, p4, ip);
+ }
+
inline bool GetIntersection(const Path64& rectPath,
const Point64& p, const Point64& p2, Location& loc, Point64& ip)
{
@@ -74,100 +124,84 @@ namespace Clipper2Lib {
switch (loc)
{
case Location::Left:
- if (SegmentsIntersect(p, p2, rectPath[0], rectPath[3], true))
- GetIntersectPoint(p, p2, rectPath[0], rectPath[3], ip);
- else if (p.y < rectPath[0].y &&
- SegmentsIntersect(p, p2, rectPath[0], rectPath[1], true))
+ 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))
{
- GetIntersectPoint(p, p2, rectPath[0], rectPath[1], ip);
loc = Location::Top;
+ return true;
}
- else if (SegmentsIntersect(p, p2, rectPath[2], rectPath[3], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[2], rectPath[3], ip))
{
- GetIntersectPoint(p, p2, rectPath[2], rectPath[3], ip);
loc = Location::Bottom;
+ return true;
}
else return false;
- break;
case Location::Top:
- if (SegmentsIntersect(p, p2, rectPath[0], rectPath[1], true))
- GetIntersectPoint(p, p2, rectPath[0], rectPath[1], ip);
- else if (p.x < rectPath[0].x &&
- SegmentsIntersect(p, p2, rectPath[0], rectPath[3], true))
+ if (GetSegmentIntersection(p, p2, rectPath[0], rectPath[1], ip)) return true;
+ else if ((p.x < rectPath[0].x) && GetSegmentIntersection(p, p2, rectPath[0], rectPath[3], ip))
{
- GetIntersectPoint(p, p2, rectPath[0], rectPath[3], ip);
loc = Location::Left;
+ return true;
}
- else if (p.x > rectPath[1].x &&
- SegmentsIntersect(p, p2, rectPath[1], rectPath[2], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[1], rectPath[2], ip))
{
- GetIntersectPoint(p, p2, rectPath[1], rectPath[2], ip);
loc = Location::Right;
+ return true;
}
else return false;
- break;
case Location::Right:
- if (SegmentsIntersect(p, p2, rectPath[1], rectPath[2], true))
- GetIntersectPoint(p, p2, rectPath[1], rectPath[2], ip);
- else if (p.y < rectPath[0].y &&
- SegmentsIntersect(p, p2, rectPath[0], rectPath[1], true))
+ if (GetSegmentIntersection(p, p2, rectPath[1], rectPath[2], ip)) return true;
+ else if ((p.y < rectPath[1].y) && GetSegmentIntersection(p, p2, rectPath[0], rectPath[1], ip))
{
- GetIntersectPoint(p, p2, rectPath[0], rectPath[1], ip);
loc = Location::Top;
+ return true;
}
- else if (SegmentsIntersect(p, p2, rectPath[2], rectPath[3], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[2], rectPath[3], ip))
{
- GetIntersectPoint(p, p2, rectPath[2], rectPath[3], ip);
loc = Location::Bottom;
+ return true;
}
else return false;
- break;
case Location::Bottom:
- if (SegmentsIntersect(p, p2, rectPath[2], rectPath[3], true))
- GetIntersectPoint(p, p2, rectPath[2], rectPath[3], ip);
- else if (p.x < rectPath[3].x &&
- SegmentsIntersect(p, p2, rectPath[0], rectPath[3], true))
+ if (GetSegmentIntersection(p, p2, rectPath[2], rectPath[3], ip)) return true;
+ else if ((p.x < rectPath[3].x) && GetSegmentIntersection(p, p2, rectPath[0], rectPath[3], ip))
{
- GetIntersectPoint(p, p2, rectPath[0], rectPath[3], ip);
loc = Location::Left;
+ return true;
}
- else if (p.x > rectPath[2].x &&
- SegmentsIntersect(p, p2, rectPath[1], rectPath[2], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[1], rectPath[2], ip))
{
- GetIntersectPoint(p, p2, rectPath[1], rectPath[2], ip);
loc = Location::Right;
+ return true;
}
else return false;
- break;
default: // loc == rInside
- if (SegmentsIntersect(p, p2, rectPath[0], rectPath[3], true))
+ if (GetSegmentIntersection(p, p2, rectPath[0], rectPath[3], ip))
{
- GetIntersectPoint(p, p2, rectPath[0], rectPath[3], ip);
loc = Location::Left;
+ return true;
}
- else if (SegmentsIntersect(p, p2, rectPath[0], rectPath[1], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[0], rectPath[1], ip))
{
- GetIntersectPoint(p, p2, rectPath[0], rectPath[1], ip);
loc = Location::Top;
+ return true;
}
- else if (SegmentsIntersect(p, p2, rectPath[1], rectPath[2], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[1], rectPath[2], ip))
{
- GetIntersectPoint(p, p2, rectPath[1], rectPath[2], ip);
loc = Location::Right;
+ return true;
}
- else if (SegmentsIntersect(p, p2, rectPath[2], rectPath[3], true))
+ else if (GetSegmentIntersection(p, p2, rectPath[2], rectPath[3], ip))
{
- GetIntersectPoint(p, p2, rectPath[2], rectPath[3], ip);
loc = Location::Bottom;
+ return true;
}
else return false;
- break;
}
- return true;
}
inline Location GetAdjacentLocation(Location loc, bool isClockwise)
@@ -281,7 +315,7 @@ namespace Clipper2Lib {
// RectClip64
//----------------------------------------------------------------------------
- OutPt2* RectClip::Add(Point64 pt, bool start_new)
+ OutPt2* RectClip64::Add(Point64 pt, bool start_new)
{
// this method is only called by InternalExecute.
// Later splitting & rejoining won't create additional op's,
@@ -312,7 +346,7 @@ namespace Clipper2Lib {
return result;
}
- void RectClip::AddCorner(Location prev, Location curr)
+ void RectClip64::AddCorner(Location prev, Location curr)
{
if (HeadingClockwise(prev, curr))
Add(rect_as_path_[static_cast<int>(prev)]);
@@ -320,7 +354,7 @@ namespace Clipper2Lib {
Add(rect_as_path_[static_cast<int>(curr)]);
}
- void RectClip::AddCorner(Location& loc, bool isClockwise)
+ void RectClip64::AddCorner(Location& loc, bool isClockwise)
{
if (isClockwise)
{
@@ -334,7 +368,7 @@ namespace Clipper2Lib {
}
}
- void RectClip::GetNextLocation(const Path64& path,
+ void RectClip64::GetNextLocation(const Path64& path,
Location& loc, int& i, int highI)
{
switch (loc)
@@ -389,7 +423,7 @@ namespace Clipper2Lib {
} //switch
}
- void RectClip::ExecuteInternal(const Path64& path)
+ void RectClip64::ExecuteInternal(const Path64& path)
{
int i = 0, highI = static_cast<int>(path.size()) - 1;
Location prev = Location::Inside, loc;
@@ -474,7 +508,7 @@ namespace Clipper2Lib {
// intersect pt but we'll also need the first intersect pt (ip2)
loc = prev;
GetIntersection(rect_as_path_, prev_pt, path[i], loc, ip2);
- if (crossing_prev != Location::Inside)
+ if (crossing_prev != Location::Inside && crossing_prev != loc) //579
AddCorner(crossing_prev, loc);
if (first_cross_ == Location::Inside)
@@ -546,7 +580,7 @@ namespace Clipper2Lib {
}
}
- void RectClip::CheckEdges()
+ void RectClip64::CheckEdges()
{
for (size_t i = 0; i < results_.size(); ++i)
{
@@ -606,7 +640,7 @@ namespace Clipper2Lib {
}
}
- void RectClip::TidyEdges(int idx, OutPt2List& cw, OutPt2List& ccw)
+ void RectClip64::TidyEdges(int idx, OutPt2List& cw, OutPt2List& ccw)
{
if (ccw.empty()) return;
bool isHorz = ((idx == 1) || (idx == 3));
@@ -619,7 +653,7 @@ namespace Clipper2Lib {
p1 = cw[i];
if (!p1 || p1->next == p1->prev)
{
- cw[i++]->edge = nullptr;
+ cw[i++] = nullptr;
j = 0;
continue;
}
@@ -784,7 +818,7 @@ namespace Clipper2Lib {
}
}
- Path64 RectClip::GetPath(OutPt2*& op)
+ Path64 RectClip64::GetPath(OutPt2*& op)
{
if (!op || op->next == op->prev) return Path64();
@@ -814,13 +848,13 @@ namespace Clipper2Lib {
return result;
}
- Paths64 RectClip::Execute(const Paths64& paths, bool convex_only)
+ Paths64 RectClip64::Execute(const Paths64& paths)
{
Paths64 result;
if (rect_.IsEmpty()) return result;
- for (const auto& path : paths)
- {
+ for (const Path64& path : paths)
+ {
if (path.size() < 3) continue;
path_bounds_ = GetBounds(path);
if (!rect_.Intersects(path_bounds_))
@@ -833,13 +867,10 @@ namespace Clipper2Lib {
}
ExecuteInternal(path);
- if (!convex_only)
- {
- CheckEdges();
- for (int i = 0; i < 4; ++i)
- TidyEdges(i, edges_[i * 2], edges_[i * 2 + 1]);
- }
-
+ CheckEdges();
+ for (int i = 0; i < 4; ++i)
+ TidyEdges(i, edges_[i * 2], edges_[i * 2 + 1]);
+
for (OutPt2*& op : results_)
{
Path64 tmp = GetPath(op);
@@ -850,26 +881,24 @@ namespace Clipper2Lib {
//clean up after every loop
op_container_ = std::deque<OutPt2>();
results_.clear();
- for (OutPt2List edge : edges_) edge.clear();
+ for (OutPt2List &edge : edges_) edge.clear();
start_locs_.clear();
}
return result;
}
//------------------------------------------------------------------------------
- // RectClipLines
+ // RectClipLines64
//------------------------------------------------------------------------------
- Paths64 RectClipLines::Execute(const Paths64& paths)
+ Paths64 RectClipLines64::Execute(const Paths64& paths)
{
Paths64 result;
if (rect_.IsEmpty()) return result;
for (const auto& path : paths)
{
- if (path.size() < 2) continue;
Rect64 pathrec = GetBounds(path);
-
if (!rect_.Intersects(pathrec)) continue;
ExecuteInternal(path);
@@ -888,7 +917,7 @@ namespace Clipper2Lib {
return result;
}
- void RectClipLines::ExecuteInternal(const Path64& path)
+ void RectClipLines64::ExecuteInternal(const Path64& path)
{
if (rect_.IsEmpty() || path.size() < 2) return;
@@ -958,7 +987,7 @@ namespace Clipper2Lib {
///////////////////////////////////////////////////
}
- Path64 RectClipLines::GetPath(OutPt2*& op)
+ Path64 RectClipLines64::GetPath(OutPt2*& op)
{
Path64 result;
if (!op || op == op->next) return result;