diff options
author | bubnikv <bubnikv@gmail.com> | 2016-04-15 19:01:08 +0300 |
---|---|---|
committer | bubnikv <bubnikv@gmail.com> | 2016-04-15 19:01:08 +0300 |
commit | 79c5e0a52d3a797967756a807989dd7c0f4b94c3 (patch) | |
tree | b71c574e7fed97adba9832a1bb03b7aa0e2b1703 /xs/src | |
parent | 42d9db04f2b9d9bfad4a29b8794fd5cd1be68207 (diff) |
Optimize remove_duplicate_points.
Diffstat (limited to 'xs/src')
-rw-r--r-- | xs/src/libslic3r/MultiPoint.cpp | 28 | ||||
-rw-r--r-- | xs/src/libslic3r/MultiPoint.hpp | 5 |
2 files changed, 27 insertions, 6 deletions
diff --git a/xs/src/libslic3r/MultiPoint.cpp b/xs/src/libslic3r/MultiPoint.cpp index 49aceacaf..627420628 100644 --- a/xs/src/libslic3r/MultiPoint.cpp +++ b/xs/src/libslic3r/MultiPoint.cpp @@ -102,15 +102,33 @@ MultiPoint::bounding_box() const return BoundingBox(this->points); } -void +bool +MultiPoint::has_duplicate_points() const +{ + for (size_t i = 1; i < points.size(); ++i) + if (points[i-1].coincides_with(points[i])) + return true; + return false; +} + +bool MultiPoint::remove_duplicate_points() { - for (size_t i = 1; i < this->points.size(); ++i) { - if (this->points.at(i).coincides_with(this->points.at(i-1))) { - this->points.erase(this->points.begin() + i); - --i; + size_t j = 0; + for (size_t i = 1; i < points.size(); ++i) { + if (points[j].coincides_with(points[i])) { + // Just increase index i. + } else { + ++ j; + if (j < i) + points[j] = points[i]; } } + if (++ j < points.size()) { + points.erase(points.begin() + j, points.end()); + return true; + } + return false; } void diff --git a/xs/src/libslic3r/MultiPoint.hpp b/xs/src/libslic3r/MultiPoint.hpp index 0f31fd318..e6fe4f2f2 100644 --- a/xs/src/libslic3r/MultiPoint.hpp +++ b/xs/src/libslic3r/MultiPoint.hpp @@ -33,7 +33,10 @@ class MultiPoint int find_point(const Point &point) const; bool has_boundary_point(const Point &point) const; BoundingBox bounding_box() const; - void remove_duplicate_points(); + // Return true if there are exact duplicates. + bool has_duplicate_points() const; + // Remove exact duplicates, return true if any duplicate has been removed. + bool remove_duplicate_points(); void append(const Point &point); void append(const Points &points); void append(const Points::const_iterator &begin, const Points::const_iterator &end); |