From dae4573bd2b11e9dcf5c9afe93104ef91befda2e Mon Sep 17 00:00:00 2001 From: Lex Neva 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/geometry.py') 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 8cead6e3d9f9223bd4d74b30ec6964802f52d9b2 Mon Sep 17 00:00:00 2001 From: Lex Neva 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/geometry.py') 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 847e133f97d570e2967dfa7dcfc16a212dc2bbbc Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Tue, 17 Jan 2023 21:44:23 -0500 Subject: meander fill: more work --- lib/utils/geometry.py | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) (limited to 'lib/utils/geometry.py') 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))) -- cgit v1.2.3 From 68249fa783b8ca788f31cfb72490c78b163ee1a4 Mon Sep 17 00:00:00 2001 From: Lex Neva 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/geometry.py') 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 Date: Fri, 17 Feb 2023 21:13:13 -0500 Subject: better smoothing algorithm --- lib/utils/geometry.py | 96 +++------------------------------------------------ 1 file changed, 4 insertions(+), 92 deletions(-) (limited to 'lib/utils/geometry.py') 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] -- cgit v1.2.3