diff options
Diffstat (limited to 'thirdparty/clipper2/src/clipper.offset.cpp')
| -rw-r--r-- | thirdparty/clipper2/src/clipper.offset.cpp | 561 |
1 files changed, 333 insertions, 228 deletions
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 |