diff options
Diffstat (limited to 'src/libslic3r/Polyline.cpp')
-rw-r--r-- | src/libslic3r/Polyline.cpp | 256 |
1 files changed, 256 insertions, 0 deletions
diff --git a/src/libslic3r/Polyline.cpp b/src/libslic3r/Polyline.cpp new file mode 100644 index 000000000..af155468a --- /dev/null +++ b/src/libslic3r/Polyline.cpp @@ -0,0 +1,256 @@ +#include "BoundingBox.hpp" +#include "Polyline.hpp" +#include "ExPolygon.hpp" +#include "ExPolygonCollection.hpp" +#include "Line.hpp" +#include "Polygon.hpp" +#include <iostream> +#include <utility> + +namespace Slic3r { + +Polyline::operator Polylines() const +{ + Polylines polylines; + polylines.push_back(*this); + return polylines; +} + +Polyline::operator Line() const +{ + if (this->points.size() > 2) + throw std::invalid_argument("Can't convert polyline with more than two points to a line"); + return Line(this->points.front(), this->points.back()); +} + +Point +Polyline::last_point() const +{ + return this->points.back(); +} + +Point +Polyline::leftmost_point() const +{ + Point p = this->points.front(); + for (Points::const_iterator it = this->points.begin() + 1; it != this->points.end(); ++it) { + if ((*it)(0) < p(0)) p = *it; + } + return p; +} + +Lines +Polyline::lines() const +{ + Lines lines; + if (this->points.size() >= 2) { + lines.reserve(this->points.size() - 1); + for (Points::const_iterator it = this->points.begin(); it != this->points.end()-1; ++it) { + lines.push_back(Line(*it, *(it + 1))); + } + } + return lines; +} + +// removes the given distance from the end of the polyline +void Polyline::clip_end(double distance) +{ + while (distance > 0) { + Vec2d last_point = this->last_point().cast<double>(); + this->points.pop_back(); + if (this->points.empty()) + break; + Vec2d v = this->last_point().cast<double>() - last_point; + double lsqr = v.squaredNorm(); + if (lsqr > distance * distance) { + this->points.emplace_back((last_point + v * (distance / sqrt(lsqr))).cast<coord_t>()); + return; + } + distance -= sqrt(lsqr); + } +} + +// removes the given distance from the start of the polyline +void Polyline::clip_start(double distance) +{ + this->reverse(); + this->clip_end(distance); + if (this->points.size() >= 2) + this->reverse(); +} + +void Polyline::extend_end(double distance) +{ + // relocate last point by extending the last segment by the specified length + Vec2d v = (this->points.back() - *(this->points.end() - 2)).cast<double>().normalized(); + this->points.back() += (v * distance).cast<coord_t>(); +} + +void Polyline::extend_start(double distance) +{ + // relocate first point by extending the first segment by the specified length + Vec2d v = (this->points.front() - this->points[1]).cast<double>().normalized(); + this->points.front() += (v * distance).cast<coord_t>(); +} + +/* this method returns a collection of points picked on the polygon contour + so that they are evenly spaced according to the input distance */ +Points Polyline::equally_spaced_points(double distance) const +{ + Points points; + points.emplace_back(this->first_point()); + double len = 0; + + for (Points::const_iterator it = this->points.begin() + 1; it != this->points.end(); ++it) { + Vec2d p1 = (it-1)->cast<double>(); + Vec2d v = it->cast<double>() - p1; + double segment_length = v.norm(); + len += segment_length; + if (len < distance) + continue; + if (len == distance) { + points.emplace_back(*it); + len = 0; + continue; + } + double take = segment_length - (len - distance); // how much we take of this segment + points.emplace_back((p1 + v * (take / v.norm())).cast<coord_t>()); + -- it; + len = - take; + } + return points; +} + +void Polyline::simplify(double tolerance) +{ + this->points = MultiPoint::_douglas_peucker(this->points, tolerance); +} + +/* This method simplifies all *lines* contained in the supplied area */ +template <class T> +void Polyline::simplify_by_visibility(const T &area) +{ + Points &pp = this->points; + + size_t s = 0; + bool did_erase = false; + for (size_t i = s+2; i < pp.size(); i = s + 2) { + if (area.contains(Line(pp[s], pp[i]))) { + pp.erase(pp.begin() + s + 1, pp.begin() + i); + did_erase = true; + } else { + ++s; + } + } + if (did_erase) + this->simplify_by_visibility(area); +} +template void Polyline::simplify_by_visibility<ExPolygon>(const ExPolygon &area); +template void Polyline::simplify_by_visibility<ExPolygonCollection>(const ExPolygonCollection &area); + +void Polyline::split_at(const Point &point, Polyline* p1, Polyline* p2) const +{ + if (this->points.empty()) return; + + // find the line to split at + size_t line_idx = 0; + Point p = this->first_point(); + double min = (p - point).cast<double>().norm(); + Lines lines = this->lines(); + for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line) { + Point p_tmp = point.projection_onto(*line); + if ((p_tmp - point).cast<double>().norm() < min) { + p = p_tmp; + min = (p - point).cast<double>().norm(); + line_idx = line - lines.begin(); + } + } + + // create first half + p1->points.clear(); + for (Lines::const_iterator line = lines.begin(); line != lines.begin() + line_idx + 1; ++line) + if (line->a != p) + p1->points.push_back(line->a); + // we add point instead of p because they might differ because of numerical issues + // and caller might want to rely on point belonging to result polylines + p1->points.push_back(point); + + // create second half + p2->points.clear(); + p2->points.push_back(point); + for (Lines::const_iterator line = lines.begin() + line_idx; line != lines.end(); ++line) { + p2->points.push_back(line->b); + } +} + +bool Polyline::is_straight() const +{ + // Check that each segment's direction is equal to the line connecting + // first point and last point. (Checking each line against the previous + // one would cause the error to accumulate.) + double dir = Line(this->first_point(), this->last_point()).direction(); + for (const auto &line: this->lines()) + if (! line.parallel_to(dir)) + return false; + return true; +} + +BoundingBox get_extents(const Polyline &polyline) +{ + return polyline.bounding_box(); +} + +BoundingBox get_extents(const Polylines &polylines) +{ + BoundingBox bb; + if (! polylines.empty()) { + bb = polylines.front().bounding_box(); + for (size_t i = 1; i < polylines.size(); ++ i) + bb.merge(polylines[i]); + } + return bb; +} + +bool remove_degenerate(Polylines &polylines) +{ + bool modified = false; + size_t j = 0; + for (size_t i = 0; i < polylines.size(); ++ i) { + if (polylines[i].points.size() >= 2) { + if (j < i) + std::swap(polylines[i].points, polylines[j].points); + ++ j; + } else + modified = true; + } + if (j < polylines.size()) + polylines.erase(polylines.begin() + j, polylines.end()); + return modified; +} + +ThickLines ThickPolyline::thicklines() const +{ + ThickLines lines; + if (this->points.size() >= 2) { + lines.reserve(this->points.size() - 1); + for (size_t i = 0; i + 1 < this->points.size(); ++ i) + lines.emplace_back(this->points[i], this->points[i + 1], this->width[2 * i], this->width[2 * i + 1]); + } + return lines; +} + +Lines3 Polyline3::lines() const +{ + Lines3 lines; + if (points.size() >= 2) + { + lines.reserve(points.size() - 1); + for (Points3::const_iterator it = points.begin(); it != points.end() - 1; ++it) + { + lines.emplace_back(*it, *(it + 1)); + } + } + return lines; +} + +} |