From dae4573bd2b11e9dcf5c9afe93104ef91befda2e Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 25 Aug 2022 16:19:54 -0400
Subject: add smooth_path

---
 lib/utils/geometry.py | 56 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)

(limited to 'lib/utils')

diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index 789f8720..c07172c7 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -7,6 +7,8 @@ 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):
@@ -147,6 +149,60 @@ 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 smooth_path(path, smoothness=100.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.
+    """
+
+    # splprep blows up on duplicated consecutive points with "Invalid inputs"
+    coords = _remove_duplicate_coordinates(np.array(path))
+    num_points = len(coords)
+
+    # splprep's s parameter seems to depend on the number of points you pass
+    # as per the docs, so let's normalize it.
+    s = round(smoothness / 100 * num_points)
+
+    # .T transposes the array (for some reason splprep expects
+    # [[x1, x2, ...], [y1, y2, ...]]
+    tck, fp, ier, msg = splprep(coords.T, s=s, 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
-- 
cgit v1.2.3


From 0ace1ce72c72aa3293d97e5d55e9e614b66d5ee2 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 25 Aug 2022 23:08:49 -0400
Subject: add clamp_path_to_polygon

---
 lib/utils/clamp_path.py | 121 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 121 insertions(+)
 create mode 100644 lib/utils/clamp_path.py

(limited to 'lib/utils')

diff --git a/lib/utils/clamp_path.py b/lib/utils/clamp_path.py
new file mode 100644
index 00000000..acf6f675
--- /dev/null
+++ b/lib/utils/clamp_path.py
@@ -0,0 +1,121 @@
+from shapely.geometry import LineString, Point as ShapelyPoint, MultiPolygon
+from shapely.prepared import prep
+from .geometry import Point, ensure_multi_line_string
+
+
+def path_to_segments(path):
+    """Convert a path of Points into a list of segments as LineStrings"""
+    for start, end in zip(path[:-1], path[1:]):
+        yield LineString((start, end))
+
+
+def segments_to_path(segments):
+    """Convert a list of contiguous LineStrings into a list of Points."""
+    coords = [segments[0].coords[0]]
+
+    for segment in segments:
+        coords.extend(segment.coords[1:])
+
+    return [Point(x, y) for x, y in coords]
+
+
+def fix_starting_point(border_pieces):
+    """Reconnect the starting point of a polygon border's pieces.
+
+    When splitting a polygon border with two lines, we want to get two
+    pieces.  However, that's not quite how Shapely works.  The outline
+    of the polygon is a LinearRing that starts and ends at the same place,
+    but Shapely still knows where that starting point is and splits there
+    too.
+
+    We don't want that third piece, so we'll reconnect the segments that
+    touch the starting point.
+    """
+
+    if len(border_pieces) == 3:
+        # Fortunately, Shapely keeps the starting point of the LinearRing
+        # as the starting point of the first segment.  That means it's also
+        # the ending point of the last segment.  Reconnecting is super simple:
+        return [border_pieces[1],
+                LineString(border_pieces[2].coords[:] + border_pieces[0].coords[1:])]
+    else:
+        # We probably cut exactly at the starting point.
+        return border_pieces
+
+
+def adjust_line_end(line, end):
+    """Reverse line if necessary to ensure that it ends near end."""
+
+    line_start = ShapelyPoint(*line.coords[0])
+    line_end = ShapelyPoint(*line.coords[-1])
+
+    if line_end.distance(end) < line_start.distance(end):
+        return line
+    else:
+        return LineString(line.coords[::-1])
+
+
+def find_border(polygon, point):
+    for border in polygon.interiors:
+        if border.intersects(point):
+            return border
+    else:
+        return polygon.exterior
+
+
+def clamp_path_to_polygon(path, polygon):
+    """Constrain a path to a Polygon.
+
+    Description: https://gis.stackexchange.com/questions/428848/clamp-linestring-to-polygon
+    """
+
+    path = LineString(path)
+
+    # This splits the path at the points where it intersects with the polygon
+    # border and returns the pieces in the same order as the original path.
+    split_path = ensure_multi_line_string(path.difference(polygon.boundary))
+
+    # contains() checks can fail without this.
+    buffered_polygon = prep(polygon.buffer(1e-9))
+
+    last_segment_inside = None
+    was_inside = False
+    result = []
+
+    for segment in split_path.geoms:
+        if buffered_polygon.contains(segment):
+            if not was_inside:
+                if last_segment_inside is not None:
+                    # The path crossed out of the polygon, and now it's crossed
+                    # back in.  We need to add a path along the border between
+                    # the exiting and entering points.
+
+                    # First, find the two points.  Buffer them just a bit to
+                    # ensure intersection with the border.
+                    x, y = last_segment_inside.coords[-1]
+                    exit_point = ShapelyPoint(x, y).buffer(0.01, resolution=1)
+                    x, y = segment.coords[0]
+                    entry_point = ShapelyPoint(x, y).buffer(0.01, resolution=1)
+
+                    if not exit_point.intersects(entry_point):
+                        # Now break the border into pieces using those points.
+                        border = find_border(polygon, exit_point)
+                        border_pieces = border.difference(MultiPolygon((entry_point, exit_point)))
+                        border_pieces = fix_starting_point(border_pieces)
+
+                        # Pick the shortest way to get from the exiting to the
+                        # entering point along the border.
+                        shorter = min(border_pieces, key=lambda piece: piece.length)
+
+                        # We don't know which direction the polygon border
+                        # piece should be.  adjust_line_end() will figure
+                        # that out.
+                        result.append(adjust_line_end(shorter, entry_point))
+
+            result.append(segment)
+            was_inside = True
+            last_segment_inside = segment
+        else:
+            was_inside = False
+
+    return segments_to_path(result)
-- 
cgit v1.2.3


From 8cead6e3d9f9223bd4d74b30ec6964802f52d9b2 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 25 Aug 2022 23:10:16 -0400
Subject: add smoothness option for contour fill

---
 lib/utils/geometry.py | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

(limited to 'lib/utils')

diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index c07172c7..2903bc56 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -182,13 +182,17 @@ def smooth_path(path, smoothness=100.0):
     coords = _remove_duplicate_coordinates(np.array(path))
     num_points = len(coords)
 
-    # splprep's s parameter seems to depend on the number of points you pass
-    # as per the docs, so let's normalize it.
-    s = round(smoothness / 100 * num_points)
+    # 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, nest=-1, full_output=1)
+    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}")
-- 
cgit v1.2.3


From ba835b4f5e33f404b7bed9369a1b425a67b312c5 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Mon, 16 Jan 2023 14:27:06 -0500
Subject: meander fill: initial version

---
 lib/utils/list.py | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
 create mode 100644 lib/utils/list.py

(limited to 'lib/utils')

diff --git a/lib/utils/list.py b/lib/utils/list.py
new file mode 100644
index 00000000..2bfe2cd7
--- /dev/null
+++ b/lib/utils/list.py
@@ -0,0 +1,15 @@
+from random import randrange
+
+
+def poprandom(sequence):
+    index = randrange(len(sequence))
+    item = sequence[index]
+
+    # It's O(1) to pop the last item, and O(n) to pop any other item. So we'll
+    # always pop the last item and put it in the slot vacated by the item we're
+    # popping.
+    last_item = sequence.pop()
+    if index < len(sequence):
+        sequence[index] = last_item
+
+    return item
-- 
cgit v1.2.3


From 85f921cd33b402733cea4ce53206aa70a6092d49 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Mon, 16 Jan 2023 14:31:51 -0500
Subject: typo fix

---
 lib/utils/prng.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'lib/utils')

diff --git a/lib/utils/prng.py b/lib/utils/prng.py
index 2ec037c6..9face2be 100644
--- a/lib/utils/prng.py
+++ b/lib/utils/prng.py
@@ -3,7 +3,7 @@ from math import ceil
 from itertools import count, chain
 import numpy as np
 
-# Framework for reproducable pseudo-random number generation.
+# Framework for reproducible pseudo-random number generation.
 
 # Unlike python's random module (which uses a stateful generator based on global variables),
 # a counter-mode PRNG like uniformFloats can be used to generate multiple, independent random streams
-- 
cgit v1.2.3


From e2965e78f03fb41c9a02c92ef120caf038b837ae Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Mon, 16 Jan 2023 14:34:29 -0500
Subject: use snake case

per python coding standard
---
 lib/utils/prng.py | 26 +++++++++++++-------------
 1 file changed, 13 insertions(+), 13 deletions(-)

(limited to 'lib/utils')

diff --git a/lib/utils/prng.py b/lib/utils/prng.py
index 9face2be..33102205 100644
--- a/lib/utils/prng.py
+++ b/lib/utils/prng.py
@@ -13,7 +13,7 @@ import numpy as np
 # Using multiple counters for n-dimentional random streams is also possible and is useful for grid-like structures.
 
 
-def joinArgs(*args):
+def join_args(*args):
     # Stringifies parameters into a slash-separated string for use in hash keys.
     # Idempotent and associative.
     return "/".join([str(x) for x in args])
@@ -22,37 +22,37 @@ def joinArgs(*args):
 MAX_UNIFORM_INT = 2 ** 32 - 1
 
 
-def uniformInts(*args):
+def uniform_ints(*args):
     # Single pseudo-random drawing determined by the joined parameters.
     # To get a longer sequence of random numbers, call this loop with a counter as one of the parameters.
     # Returns 8 uniformly random uint32.
 
-    s = joinArgs(*args)
+    s = join_args(*args)
     # blake2s is python's fastest hash algorithm for small inputs and is designed to be usable as a PRNG.
     h = blake2s(s.encode()).hexdigest()
     nums = []
     for i in range(0, 64, 8):
-        nums.append(int(h[i:i+8], 16))
+        nums.append(int(h[i:i + 8], 16))
     return np.array(nums)
 
 
-def uniformFloats(*args):
+def uniform_floats(*args):
     # Single pseudo-random drawing determined by the joined parameters.
     # To get a longer sequence of random numbers, call this loop with a counter as one of the parameters.
     # Returns an array of 8 floats in the range [0,1]
-    return uniformInts(*args) / MAX_UNIFORM_INT
+    return uniform_ints(*args) / MAX_UNIFORM_INT
 
 
-def nUniformFloats(n: int, *args):
+def n_uniform_floats(n: int, *args):
     # returns a fixed number (which may exceed 8) of floats in the range [0,1]
-    seed = joinArgs(*args)
-    nBlocks = ceil(n/8)
-    blocks = [uniformFloats(seed, x) for x in range(nBlocks)]
+    seed = join_args(*args)
+    nBlocks = ceil(n / 8)
+    blocks = [uniform_floats(seed, x) for x in range(nBlocks)]
     return np.concatenate(blocks)[0:n]
 
 
-def iterUniformFloats(*args):
+def iter_uniform_floats(*args):
     # returns an infinite sequence of floats in the range [0,1]
-    seed = joinArgs(*args)
-    blocks = map(lambda x: list(uniformFloats(seed, x)), count(0))
+    seed = join_args(*args)
+    blocks = map(lambda x: list(uniform_floats(seed, x)), count(0))
     return chain.from_iterable(blocks)
-- 
cgit v1.2.3


From 847e133f97d570e2967dfa7dcfc16a212dc2bbbc Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 17 Jan 2023 21:44:23 -0500
Subject: meander fill: more work

---
 lib/utils/geometry.py | 12 ++++++++++--
 lib/utils/list.py     | 14 +++++++++++---
 lib/utils/string.py   |  7 +++++++
 3 files changed, 28 insertions(+), 5 deletions(-)

(limited to 'lib/utils')

diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index 2903bc56..366a433f 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -166,7 +166,7 @@ def _remove_duplicate_coordinates(coords_array):
     return coords_array[keepers]
 
 
-def smooth_path(path, smoothness=100.0):
+def smooth_path(path, smoothness=1.0):
     """Smooth a path of coordinates.
 
     Arguments:
@@ -178,6 +178,11 @@ def smooth_path(path, smoothness=100.0):
         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)
@@ -188,7 +193,7 @@ def smooth_path(path, smoothness=100.0):
     # 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
+    s = num_points * (smoothness ** 2)
 
     # .T transposes the array (for some reason splprep expects
     # [[x1, x2, ...], [y1, y2, ...]]
@@ -280,6 +285,9 @@ class Point:
     def rotate(self, angle):
         return self.__class__(self.x * math.cos(angle) - self.y * math.sin(angle), self.y * math.cos(angle) + self.x * math.sin(angle))
 
+    def scale(self, x_scale, y_scale):
+        return self.__class__(self.x * x_scale, self.y * y_scale)
+
     def as_int(self):
         return self.__class__(int(round(self.x)), int(round(self.y)))
 
diff --git a/lib/utils/list.py b/lib/utils/list.py
index 2bfe2cd7..efa3969e 100644
--- a/lib/utils/list.py
+++ b/lib/utils/list.py
@@ -1,8 +1,16 @@
-from random import randrange
+import random
 
 
-def poprandom(sequence):
-    index = randrange(len(sequence))
+def _uniform_rng():
+    while True:
+        yield random.uniform(0, 1)
+
+
+_rng = _uniform_rng()
+
+
+def poprandom(sequence, rng=_rng):
+    index = int(round(next(rng) * (len(sequence) - 1)))
     item = sequence[index]
 
     # It's O(1) to pop the last item, and O(n) to pop any other item. So we'll
diff --git a/lib/utils/string.py b/lib/utils/string.py
index cb852ce3..e9204076 100644
--- a/lib/utils/string.py
+++ b/lib/utils/string.py
@@ -8,3 +8,10 @@ def string_to_floats(string, delimiter=","):
 
     floats = string.split(delimiter)
     return [float(num) for num in floats]
+
+
+def remove_suffix(string, suffix):
+    if string.endswith(suffix):
+        return string[:-len(suffix)]
+    else:
+        return string
-- 
cgit v1.2.3


From 68249fa783b8ca788f31cfb72490c78b163ee1a4 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sat, 28 Jan 2023 21:35:02 -0500
Subject: avoid weird end of line after smoothing

---
 lib/utils/geometry.py | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

(limited to 'lib/utils')

diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index 366a433f..e7fd5b76 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -166,6 +166,27 @@ def _remove_duplicate_coordinates(coords_array):
     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.
 
@@ -187,6 +208,10 @@ def smooth_path(path, smoothness=1.0):
     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
@@ -195,6 +220,8 @@ def smooth_path(path, smoothness=1.0):
     # 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)
-- 
cgit v1.2.3


From 9ccf8b9b7780b997c1f801a87dafd99f86f048a1 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Fri, 17 Feb 2023 21:13:13 -0500
Subject: better smoothing algorithm

---
 lib/utils/geometry.py  | 96 +++-----------------------------------------------
 lib/utils/smoothing.py | 84 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 88 insertions(+), 92 deletions(-)
 create mode 100644 lib/utils/smoothing.py

(limited to 'lib/utils')

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]
-- 
cgit v1.2.3


From 7fa3fec5346a4c87ff1f95dca94cf771455d8cb0 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sat, 18 Feb 2023 16:48:32 -0500
Subject: fix deprecation warning

---
 lib/utils/clamp_path.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'lib/utils')

diff --git a/lib/utils/clamp_path.py b/lib/utils/clamp_path.py
index acf6f675..e5ef78d8 100644
--- a/lib/utils/clamp_path.py
+++ b/lib/utils/clamp_path.py
@@ -100,7 +100,7 @@ def clamp_path_to_polygon(path, polygon):
                     if not exit_point.intersects(entry_point):
                         # Now break the border into pieces using those points.
                         border = find_border(polygon, exit_point)
-                        border_pieces = border.difference(MultiPolygon((entry_point, exit_point)))
+                        border_pieces = border.difference(MultiPolygon((entry_point, exit_point))).geoms
                         border_pieces = fix_starting_point(border_pieces)
 
                         # Pick the shortest way to get from the exiting to the
-- 
cgit v1.2.3