better smoothing algorithm

4 files changed, 91 insertions, 93 deletions

diff --git a/lib/stitches/contour_fill.py b/lib/stitches/contour_fill.py
index 8e47518f..f5f2a3ee 100644
--- a/lib/stitches/contour_fill.py
+++ b/lib/stitches/contour_fill.py
@@ -12,9 +12,11 @@ from shapely.validation import make_valid
 
 from ..stitch_plan import Stitch
 from ..utils import DotDict
+from ..utils.clamp_path import clamp_path_to_polygon
 from ..utils.geometry import (cut, ensure_geometry_collection,
                               ensure_multi_polygon, reverse_line_string,
                               roll_linear_ring)
+from ..utils.smoothing import smooth_path
 from ..utils.threading import check_stop_flag
 from .running_stitch import running_stitch
 
diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py
index ca3b7d69..2cd235fb 100644
--- a/lib/stitches/meander_fill.py
+++ b/lib/stitches/meander_fill.py
@@ -6,7 +6,7 @@ from .running_stitch import running_stitch
 from .. import tiles
 from ..debug import debug
 from ..stitch_plan import Stitch
-from ..utils import smooth_path
+from ..utils.smoothing import smooth_path
 from ..utils.geometry import Point as InkStitchPoint, ensure_geometry_collection
 from ..utils.list import poprandom
 from ..utils.prng import iter_uniform_floats
diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index e7fd5b76..8f34c467 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -7,8 +7,6 @@ import math
 
 from shapely.geometry import LineString, LinearRing, MultiLineString, Polygon, MultiPolygon, MultiPoint, GeometryCollection
 from shapely.geometry import Point as ShapelyPoint
-from scipy.interpolate import splprep, splev
-import numpy as np
 
 
 def cut(line, distance, normalized=False):
@@ -149,96 +147,6 @@ def cut_path(points, length):
     return [Point(*point) for point in subpath.coords]
 
 
-def _remove_duplicate_coordinates(coords_array):
-    """Remove consecutive duplicate points from an array.
-
-    Arguments:
-        coords_array -- numpy.array
-
-    Returns:
-        a numpy.array of coordinates, minus consecutive duplicates
-    """
-
-    differences = np.diff(coords_array, axis=0)
-    zero_differences = np.isclose(differences, 0)
-    keepers = np.r_[True, np.any(zero_differences == False, axis=1)]  # noqa: E712
-
-    return coords_array[keepers]
-
-
-def _add_extra_points(coords):
-    """Add points at the start and end of the path.
-
-    The spline-based smoothing in smooth_path sometimes makes a wild deviation at the
-    start or end.  Adding 3 extra points almost identical to the start and end points
-    seems to avoid this.
-    """
-
-    direction = coords[1] - coords[0]
-    amount = direction * 0.001
-
-    start_points = [coords[0], coords[0] + amount, coords[0] + amount * 2, coords[0] + amount * 3]
-
-    direction = coords[-2] - coords[-1]
-    amount = direction * 0.001
-
-    end_points = [coords[-1] + amount * 3, coords[-1] + amount * 2, coords[-1] + amount, coords[-1]]
-
-    return np.concatenate((start_points, coords[1:-1], end_points), axis=0)
-
-
-def smooth_path(path, smoothness=1.0):
-    """Smooth a path of coordinates.
-
-    Arguments:
-        path -- an iterable of coordinate tuples or Points
-        smoothness -- float, how much smoothing to apply.  Bigger numbers
-            smooth more.
-
-    Returns:
-        A list of Points.
-    """
-
-    if smoothness == 0:
-        # s of exactly zero seems to indicate a default level of smoothing
-        # in splprep, so we'll just exit instead.
-        return path
-
-    # splprep blows up on duplicated consecutive points with "Invalid inputs"
-    coords = _remove_duplicate_coordinates(np.array(path))
-    num_points = len(coords)
-
-    if num_points <= 3:
-        # splprep throws an error unless num_points > k
-        return path
-
-    # s is explained in this issue: https://github.com/scipy/scipy/issues/11916
-    # the smoothness parameter limits how much the smoothed path can deviate
-    # from the original path.  The standard deviation of the distance between
-    # the smoothed path and the original path is equal to the smoothness.
-    # In practical terms, if smoothness is 1mm, then the smoothed path can be
-    # up to 1mm away from the original path.
-    s = num_points * (smoothness ** 2)
-
-    coords = _add_extra_points(coords)
-
-    # .T transposes the array (for some reason splprep expects
-    # [[x1, x2, ...], [y1, y2, ...]]
-    tck, fp, ier, msg = splprep(coords.T, s=s, k=3, nest=-1, full_output=1)
-    if ier > 0:
-        from ..debug import debug
-        debug.log(f"error {ier} smoothing path: {msg}")
-        return path
-
-    # Evaluate the spline curve at many points along its length to produce the
-    # smoothed point list.  2 * num_points seems to be a good number, but it
-    # does produce a lot of points.
-    smoothed_x_values, smoothed_y_values = splev(np.linspace(0, 1, num_points * 2), tck[0])
-    coords = np.array([smoothed_x_values, smoothed_y_values]).T
-
-    return [Point(x, y) for x, y in coords]
-
-
 class Point:
     def __init__(self, x: float, y: float):
         self.x = x
@@ -333,3 +241,7 @@ class Point:
 
 def line_string_to_point_list(line_string):
     return [Point(*point) for point in line_string.coords]
+
+
+def coordinate_list_to_point_list(coordinate_list):
+    return [Point.from_tuple(coords) for coords in coordinate_list]
diff --git a/lib/utils/smoothing.py b/lib/utils/smoothing.py
new file mode 100644
index 00000000..9d43a9f1
--- /dev/null
+++ b/lib/utils/smoothing.py
@@ -0,0 +1,84 @@
+import numpy as np
+from scipy.interpolate import splprep, splev
+
+from .geometry import Point, coordinate_list_to_point_list
+from ..stitches.running_stitch import running_stitch
+from ..debug import debug
+
+
+def _remove_duplicate_coordinates(coords_array):
+    """Remove consecutive duplicate points from an array.
+
+    Arguments:
+        coords_array -- numpy.array
+
+    Returns:
+        a numpy.array of coordinates, minus consecutive duplicates
+    """
+
+    differences = np.diff(coords_array, axis=0)
+    zero_differences = np.isclose(differences, 0)
+    keepers = np.r_[True, np.any(zero_differences == False, axis=1)]  # noqa: E712
+
+    return coords_array[keepers]
+
+
+@debug.time
+def smooth_path(path, smoothness=1.0):
+    """Smooth a path of coordinates.
+
+    Arguments:
+        path -- an iterable of coordinate tuples or Points
+        smoothness -- float, how much smoothing to apply.  Bigger numbers
+            smooth more.
+
+    Returns:
+        A list of Points.
+    """
+    from ..debug import debug
+
+    if smoothness == 0:
+        # s of exactly zero seems to indicate a default level of smoothing
+        # in splprep, so we'll just exit instead.
+        return path
+
+    # Smoothing seems to look nicer if the line segments in the path are mostly
+    # similar in length.  If we have some especially long segments, then the
+    # smoothed path sometimes diverges more from the original path as the
+    # spline curve struggles to fit the path.  This can be especially bad at
+    # the start and end.
+    #
+    # Fortunately, we can convert the path to segments that are mostly the same
+    # length by using the running stitch algorithm.
+    path = running_stitch(coordinate_list_to_point_list(path), 5 * smoothness, smoothness / 2)
+
+    # splprep blows up on duplicated consecutive points with "Invalid inputs"
+    coords = _remove_duplicate_coordinates(np.array(path))
+    num_points = len(coords)
+
+    if num_points <= 3:
+        # splprep throws an error unless num_points > k
+        return path
+
+    # s is explained in this issue: https://github.com/scipy/scipy/issues/11916
+    # the smoothness parameter limits how much the smoothed path can deviate
+    # from the original path.  The standard deviation of the distance between
+    # the smoothed path and the original path is equal to the smoothness.
+    # In practical terms, if smoothness is 1mm, then the smoothed path can be
+    # up to 1mm away from the original path.
+    s = num_points * (smoothness ** 2)
+
+    # .T transposes the array (for some reason splprep expects
+    # [[x1, x2, ...], [y1, y2, ...]]
+    tck, fp, ier, msg = splprep(coords.T, s=s, k=3, nest=-1, full_output=1)
+    if ier > 0:
+        debug.log(f"error {ier} smoothing path: {msg}")
+        return path
+
+    # Evaluate the spline curve at many points along its length to produce the
+    # smoothed point list.  2 * num_points seems to be a good number, but it
+    # does produce a lot of points.
+    smoothed_x_values, smoothed_y_values = splev(np.linspace(0, 1, int(num_points * 2)), tck[0])
+    coords = np.array([smoothed_x_values, smoothed_y_values]).T
+
+    return [Point(x, y) for x, y in coords]