Follow-up to a4ecf2f2a6d140a25e9b76e90ae5f4cf8457bd91. Refactoring of the function for removing duplicate points.

3 files changed, 53 insertions, 45 deletions

diff --git a/src/libslic3r/MultiMaterialSegmentation.cpp b/src/libslic3r/MultiMaterialSegmentation.cpp
index f9a53b51d..9560096be 100644
--- a/src/libslic3r/MultiMaterialSegmentation.cpp
+++ b/src/libslic3r/MultiMaterialSegmentation.cpp
@@ -1676,50 +1676,6 @@ static bool has_layer_only_one_color(const std::vector<std::vector<ColoredLine>>
     return true;
 }
 
-// Remove nearly duplicate points. If a distance between two points is less than point_eps
-// and if the angle between its surrounding lines is less than max_angle, the point will be removed.
-void remove_duplicates_points(MutablePolygon &polygon, double point_eps, double max_angle)
-{
-    if (polygon.size() >= 3) {
-        auto eps2  = point_eps * point_eps;
-        auto begin = polygon.begin();
-        auto it    = begin;
-        for (++it; it != begin;) {
-            auto prev = it.prev();
-            auto next = (it.next() == polygon.end() ? begin : it.next());
-            if ((*it - *prev).cast<double>().squaredNorm() < eps2) {
-                Vec2i64 vector1 = (*it - *prev).cast<int64_t>();
-                Vec2i64 vector2 = (*next - *prev).cast<int64_t>();
-                if (double angle = atan2(cross2(vector1, vector2), vector1.dot(vector2)); angle < max_angle) {
-                    it = it.remove();
-                    continue;
-                }
-            }
-            ++it;
-        }
-    }
-}
-
-// Remove nearly duplicate points. If a distance between two points is less than point_eps
-// and if the angle between its surrounding lines is less than max_angle, the point will be removed.
-inline ExPolygons remove_duplicates_points(ExPolygons expolygons, double point_eps, double max_angle)
-{
-    MutablePolygon mp;
-    for (ExPolygon &expolygon : expolygons) {
-        mp.assign(expolygon.contour, expolygon.contour.size() * 2);
-        remove_duplicates_points(mp, point_eps, max_angle);
-        mp.polygon(expolygon.contour);
-        for (Polygon &hole : expolygon.holes) {
-            mp.assign(hole, hole.size() * 2);
-            remove_duplicates_points(mp, point_eps, max_angle);
-            mp.polygon(hole);
-        }
-        expolygon.holes.erase(std::remove_if(expolygon.holes.begin(), expolygon.holes.end(), [](const auto &p) { return p.empty(); }), expolygon.holes.end());
-    }
-    expolygons.erase(std::remove_if(expolygons.begin(), expolygons.end(), [](const auto &p) { return p.empty(); }), expolygons.end());
-    return expolygons;
-}
-
 std::vector<std::vector<ExPolygons>> multi_material_segmentation_by_painting(const PrintObject &print_object, const std::function<void()> &throw_on_cancel_callback)
 {
     const size_t                          num_extruders = print_object.print()->config().nozzle_diameter.size();
@@ -1755,7 +1711,7 @@ std::vector<std::vector<ExPolygons>> multi_material_segmentation_by_painting(con
             // Such close points sometimes caused that the Voronoi diagram has self-intersecting edges around these vertices.
             // This consequently leads to issues with the extraction of colored segments by function extract_colored_segments.
             // Calling expolygons_simplify fixed these issues.
-            input_expolygons[layer_idx] = remove_duplicates_points(expolygons_simplify(offset_ex(ex_polygons, -10.f * float(SCALED_EPSILON)), 5 * SCALED_EPSILON), scaled<double>(0.01), PI/6);
+            input_expolygons[layer_idx] = remove_duplicates(expolygons_simplify(offset_ex(ex_polygons, -10.f * float(SCALED_EPSILON)), 5 * SCALED_EPSILON), scaled<coord_t>(0.01), PI/6);
 
 #ifdef MMU_SEGMENTATION_DEBUG_INPUT
             {
diff --git a/src/libslic3r/MutablePolygon.cpp b/src/libslic3r/MutablePolygon.cpp
index 403d625bf..45c74d0a6 100644
--- a/src/libslic3r/MutablePolygon.cpp
+++ b/src/libslic3r/MutablePolygon.cpp
@@ -37,6 +37,36 @@ void remove_duplicates(MutablePolygon &polygon, double eps)
     }
 }
 
+// Remove nearly duplicate points. If a distance between two points is less than scaled_eps
+// and if the angle between its surrounding lines is less than max_angle, the point will be removed.
+// May reduce the polygon down to empty polygon.
+void remove_duplicates(MutablePolygon &polygon, coord_t scaled_eps, const double max_angle)
+{
+    if (polygon.size() >= 3) {
+        auto cos_max_angle_2 = Slic3r::sqr<double>(cos(max_angle));
+        auto scaled_eps_sqr  = Slic3r::sqr<int64_t>(scaled_eps);
+        auto begin           = polygon.begin();
+        auto it              = begin;
+        for (++it; it != begin;) {
+            auto    prev        = it.prev();
+            auto    next        = it.next();
+            Vec2i64 v1          = (*it - *prev).cast<int64_t>();
+            int64_t v1_sqr_norm = v1.squaredNorm();
+            if (v1_sqr_norm < scaled_eps_sqr) {
+                if (Vec2i64 v2 = (*next - *prev).cast<int64_t>();
+                    Slic3r::sqr<double>(double(v1.dot(v2))) > cos_max_angle_2 * double(v1_sqr_norm) * double(v2.squaredNorm())) {
+                    it = it.remove();
+                    continue;
+                }
+            }
+            it = next;
+        }
+    }
+
+    if (polygon.size() < 3)
+        polygon.clear();
+}
+
 // Adapted from Cura ConstPolygonRef::smooth_corner_complex() by Tim Kuipers.
 // A concave corner at it1 with position p1 has been removed by the caller between it0 and it2, where |p2 - p0| < shortcut_length.
 // Now try to close a concave crack by walking left from it0 and right from it2 as long as the new clipping edge is smaller than shortcut_length
diff --git a/src/libslic3r/MutablePolygon.hpp b/src/libslic3r/MutablePolygon.hpp
index 1b2b4e445..ea41d6fb4 100644
--- a/src/libslic3r/MutablePolygon.hpp
+++ b/src/libslic3r/MutablePolygon.hpp
@@ -309,6 +309,28 @@ inline bool operator!=(const MutablePolygon &p1, const MutablePolygon &p2) { ret
 void remove_duplicates(MutablePolygon &polygon);
 void remove_duplicates(MutablePolygon &polygon, double eps);
 
+// Remove nearly duplicate points. If a distance between two points is less than scaled_eps
+// and if the angle between its surrounding lines is less than max_angle, the point will be removed.
+// May reduce the polygon down to empty polygon.
+void remove_duplicates(MutablePolygon &polygon, coord_t scaled_eps, const double max_angle);
+inline ExPolygons remove_duplicates(ExPolygons expolygons, coord_t scaled_eps, double max_angle)
+{
+    MutablePolygon mp;
+    for (ExPolygon &expolygon : expolygons) {
+        mp.assign(expolygon.contour, expolygon.contour.size() * 2);
+        remove_duplicates(mp, scaled_eps, max_angle);
+        mp.polygon(expolygon.contour);
+        for (Polygon &hole : expolygon.holes) {
+            mp.assign(hole, hole.size() * 2);
+            remove_duplicates(mp, scaled_eps, max_angle);
+            mp.polygon(hole);
+        }
+        expolygon.holes.erase(std::remove_if(expolygon.holes.begin(), expolygon.holes.end(), [](const auto &p) { return p.empty(); }), expolygon.holes.end());
+    }
+    expolygons.erase(std::remove_if(expolygons.begin(), expolygons.end(), [](const auto &p) { return p.empty(); }), expolygons.end());
+    return expolygons;
+}
+
 void smooth_outward(MutablePolygon &polygon, coord_t clip_dist_scaled);
 
 inline Polygon smooth_outward(Polygon polygon, coord_t clip_dist_scaled)