diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/stitches/contour_fill.py | 2 | ||||
| -rw-r--r-- | lib/stitches/meander_fill.py | 2 | ||||
| -rw-r--r-- | lib/utils/geometry.py | 96 | ||||
| -rw-r--r-- | lib/utils/smoothing.py | 84 |
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] |