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') 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.3.1 From 0ace1ce72c72aa3293d97e5d55e9e614b66d5ee2 Mon Sep 17 00:00:00 2001 From: Lex Neva 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.3.1 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/elements/fill_stitch.py | 16 ++++++++++++++++ lib/stitches/contour_fill.py | 7 ++++++- lib/svg/tags.py | 1 + lib/utils/geometry.py | 12 ++++++++---- 4 files changed, 31 insertions(+), 5 deletions(-) (limited to 'lib/utils') diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index 77b4ac7c..fb8838cc 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -137,6 +137,20 @@ class FillStitch(EmbroideryElement): def avoid_self_crossing(self): return self.get_boolean_param('avoid_self_crossing', False) + @property + @param('smoothness_mm', _('Smoothness'), + tooltip=_( + 'Smooth the stitch path. Smoothness limits how far the smoothed stitch path ' + + 'is allowed to deviate from the original path. Hint: a lower stitchc tolerance may be needed too.' + ), + type='integer', + unit='mm', + default=0, + select_items=[('fill_method', 1)], + sort_index=5) + def smoothness(self): + return self.get_float_param('smoothness_mm', 0) + @property @param('clockwise', _('Clockwise'), type='boolean', default=True, select_items=[('fill_method', 1)], sort_index=5) def clockwise(self): @@ -651,9 +665,11 @@ class FillStitch(EmbroideryElement): if self.contour_strategy == 0: stitches = contour_fill.inner_to_outer( tree, + polygon, self.row_spacing, self.max_stitch_length, self.running_stitch_tolerance, + self.smoothness, starting_point, self.avoid_self_crossing ) diff --git a/lib/stitches/contour_fill.py b/lib/stitches/contour_fill.py index 885a7e6c..8e47518f 100644 --- a/lib/stitches/contour_fill.py +++ b/lib/stitches/contour_fill.py @@ -406,11 +406,16 @@ def _find_path_inner_to_outer(tree, node, offset, starting_point, avoid_self_cro return LineString(result_coords) -def inner_to_outer(tree, offset, stitch_length, tolerance, starting_point, avoid_self_crossing): +def inner_to_outer(tree, polygon, offset, stitch_length, tolerance, smoothness, starting_point, avoid_self_crossing): """Fill a shape with spirals, from innermost to outermost.""" stitch_path = _find_path_inner_to_outer(tree, 'root', offset, starting_point, avoid_self_crossing) points = [Stitch(*point) for point in stitch_path.coords] + + if smoothness > 0: + smoothed = smooth_path(points, smoothness) + points = clamp_path_to_polygon(smoothed, polygon) + stitches = running_stitch(points, stitch_length, tolerance) return stitches diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 64f6c2f3..8c1dd558 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -66,6 +66,7 @@ inkstitch_attribs = [ 'guided_fill_strategy', 'join_style', 'avoid_self_crossing', + 'smoothness_mm', 'clockwise', 'reverse', 'expand_mm', 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.3.1 From ba835b4f5e33f404b7bed9369a1b425a67b312c5 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 16 Jan 2023 14:27:06 -0500 Subject: meander fill: initial version --- lib/elements/fill_stitch.py | 21 ++++++++- lib/stitches/meander_fill.py | 104 +++++++++++++++++++++++++++++++++++++++++++ lib/svg/tags.py | 1 + lib/tiles.py | 96 ++++++++++++++++++++++++--------------- lib/utils/list.py | 15 +++++++ 5 files changed, 200 insertions(+), 37 deletions(-) create mode 100644 lib/stitches/meander_fill.py create mode 100644 lib/utils/list.py (limited to 'lib/utils') diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index fb8838cc..fbaab0c2 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -17,8 +17,10 @@ from ..i18n import _ from ..marker import get_marker_elements from ..stitch_plan import StitchGroup from ..stitches import auto_fill, contour_fill, guided_fill, legacy_fill +from ..stitches.meander_fill import meander_fill from ..svg import PIXELS_PER_MM from ..svg.tags import INKSCAPE_LABEL +from .. import tiles from ..utils import cache, version from .element import EmbroideryElement, param from .validation import ValidationError, ValidationWarning @@ -107,7 +109,7 @@ class FillStitch(EmbroideryElement): @property @param('fill_method', _('Fill method'), type='dropdown', default=0, - options=[_("Auto Fill"), _("Contour Fill"), _("Guided Fill"), _("Legacy Fill")], sort_index=2) + options=[_("Auto Fill"), _("Contour Fill"), _("Guided Fill"), _("Legacy Fill"), _("Meander Fill")], sort_index=2) def fill_method(self): return self.get_int_param('fill_method', 0) @@ -146,7 +148,7 @@ class FillStitch(EmbroideryElement): type='integer', unit='mm', default=0, - select_items=[('fill_method', 1)], + select_items=[('fill_method', 1), ('fill_method', 4)], sort_index=5) def smoothness(self): return self.get_float_param('smoothness_mm', 0) @@ -156,6 +158,12 @@ class FillStitch(EmbroideryElement): def clockwise(self): return self.get_boolean_param('clockwise', True) + @property + @param('meander_pattern', _('Meander Pattern'), type='dropdown', default=0, + options=[tile.name for tile in tiles.all_tiles()], select_items=[('fill_method', 4)], sort_index=3) + def meander_pattern(self): + return self.get_param('meander_pattern', None) + @property @param('angle', _('Angle of lines of stitches'), @@ -592,6 +600,8 @@ class FillStitch(EmbroideryElement): stitch_groups.extend(self.do_contour_fill(fill_shape, previous_stitch_group, start)) elif self.fill_method == 2: stitch_groups.extend(self.do_guided_fill(fill_shape, previous_stitch_group, start, end)) + elif self.fill_method == 4: + stitch_groups.extend(self.do_meander_fill(fill_shape, start, end)) except ExitThread: raise except Exception: @@ -723,6 +733,13 @@ class FillStitch(EmbroideryElement): )) return [stitch_group] + def do_meander_fill(self, shape, starting_point, ending_point): + stitch_group = StitchGroup( + color=self.color, + tags=("meander_fill", "meander_fill_top"), + stitches=meander_fill(self, shape, starting_point, ending_point)) + return [stitch_group] + @cache def _get_guide_lines(self, multiple=False): guide_lines = get_marker_elements(self.node, "guide-line", False, True) diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py new file mode 100644 index 00000000..2ac3cd03 --- /dev/null +++ b/lib/stitches/meander_fill.py @@ -0,0 +1,104 @@ +from shapely.geometry import MultiPoint, Point +from shapely.ops import nearest_points +import networkx as nx + +from .. import tiles +from ..debug import debug +from ..utils.list import poprandom + + +def meander_fill(fill, shape, starting_point, ending_point): + tile = get_tile(fill.meander_pattern) + if not tile: + return [] + + graph = tile.to_graph(shape) + start, end = find_starting_and_ending_nodes(graph, starting_point, ending_point) + + return generate_meander_path(graph, start, end) + + +def get_tile(tile_name): + all_tiles = {tile.name: tile for tile in tiles.all_tiles()} + + try: + return all_tiles.get(tile_name, all_tiles.popitem()[1]) + except KeyError: + return None + + +def find_starting_and_ending_nodes(graph, starting_point, ending_point): + all_points = MultiPoint(list(graph)) + + starting_node = nearest_points(starting_point, all_points)[1].coords[0] + ending_node = nearest_points(ending_point, all_points)[1].coords[0] + + if starting_node == ending_node: + # We need a path to start with, so pick a new ending node + all_points = all_points.difference(Point(starting_node)) + ending_node = nearest_points(ending_point, all_points)[1].coords[0] + + return starting_node, ending_node + + +def find_initial_path(graph, start, end): + # We need some path to start with. We could use + # nx.all_simple_paths(graph, start, end) and choose the first one. + # However, that tends to pick a really "orderly" path. Shortest + # path looks more random. + return nx.shortest_path(graph, start, end) + + +def generate_meander_path(graph, start, end): + path = find_initial_path(graph, start, end) + path_edges = list(zip(path[:-1], path[1:])) + graph.remove_edges_from(path_edges) + graph_nodes = set(graph) - set(path) + + edges_to_consider = list(path_edges) + meander_path = path_edges + while edges_to_consider: + while edges_to_consider: + edge = poprandom(edges_to_consider) + edges_to_consider.extend(replace_edge(meander_path, edge, graph, graph_nodes)) + + edge_pairs = list(zip(path[:-1], path[1:])) + while edge_pairs: + edge1, edge2 = poprandom(edge_pairs) + edges_to_consider.extend(replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)) + + return meander_path + + +def replace_edge(path, edge, graph, graph_nodes): + subgraph = graph.subgraph(graph_nodes | set(edge)) + new_path = None + for new_path in nx.all_simple_edge_paths(subgraph, edge[0], edge[1], 7): + if len(new_path) > 1: + break + if new_path is None or len(new_path) == 1: + return [] + i = path.index(edge) + path[i:i + 1] = new_path + graph.remove_edges_from(new_path) + graph_nodes.difference_update(start for start, end in new_path) + debug.log(f"found new path of length {len(new_path)} at position {i}") + + return new_path + + +def replace_edge_pair(path, edge1, edge2, graph, graph_nodes): + subgraph = graph.subgraph(graph_nodes | {edge1[0], edge2[1]}) + new_path = None + for new_path in nx.all_simple_edge_paths(subgraph, edge1[0], edge2[1], 10): + if len(new_path) > 2: + break + if new_path is None or len(new_path) <= 2: + return [] + i = path.index(edge1) + path[i:i + 2] = new_path + graph.remove_edges_from(new_path) + graph_nodes.difference_update(start for start, end in new_path) + debug.log(f"found new pair path of length {len(new_path)} at position {i}") + + return new_path diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 8c1dd558..4979b58a 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -69,6 +69,7 @@ inkstitch_attribs = [ 'smoothness_mm', 'clockwise', 'reverse', + 'meander_pattern', 'expand_mm', 'fill_underlay', 'fill_underlay_angle', diff --git a/lib/tiles.py b/lib/tiles.py index 34097f67..e9f0305a 100644 --- a/lib/tiles.py +++ b/lib/tiles.py @@ -5,8 +5,10 @@ import os from shapely.geometry import LineString from shapely.prepared import prep +from .debug import debug from .svg import apply_transforms -from .utils import get_bundled_dir, guess_inkscape_config_path, Point +from .svg.tags import SODIPODI_NAMEDVIEW +from .utils import cache, get_bundled_dir, guess_inkscape_config_path, Point from random import random @@ -15,51 +17,68 @@ class Tile: self._load_tile(path) def _load_tile(self, tile_path): - tile_svg = inkex.load_svg(tile_path) - self.name = self._get_name(tile_path) - self._load_paths(tile_svg) - self._load_dimensions(tile_svg) - self._load_buffer_size(tile_svg) - self._load_parallelogram(tile_svg) + self.tile_svg = inkex.load_svg(tile_path) + self.tile_path = tile_path + self.name = self._get_name(self.tile_svg, tile_path) + self.tile = None + self.width = None + self.height = None + self.buffer_size = None + self.shift0 = None + self.shift1 = None def __repr__(self): return f"Tile({self.name}, {self.shift0}, {self.shift1})" __str__ = __repr__ - def _get_name(self, tile_path): - return os.path.splitext(os.path.basename(tile_path))[0] + def _get_name(self, tile_svg, tile_path): + name = tile_svg.get(SODIPODI_NAMEDVIEW) + if name: + return name + else: + return os.path.splitext(os.path.basename(tile_path))[0] + + def _load(self): + self._load_paths(self.tile_svg) + self._load_dimensions(self.tile_svg) + self._load_buffer_size(self.tile_svg) + self._load_parallelogram(self.tile_svg) def _load_paths(self, tile_svg): - path_elements = tile_svg.findall('.//svg:path', namespaces=inkex.NSS) - self.tile = self._path_elements_to_line_strings(path_elements) - # self.center, ignore, ignore = self._get_center_and_dimensions(self.tile) + if self.tile is None: + path_elements = tile_svg.findall('.//svg:path', namespaces=inkex.NSS) + self.tile = self._path_elements_to_line_strings(path_elements) + # self.center, ignore, ignore = self._get_center_and_dimensions(self.tile) def _load_dimensions(self, tile_svg): - svg_element = tile_svg.getroot() - self.width = svg_element.viewport_width - self.height = svg_element.viewport_height + if self.width is None: + svg_element = tile_svg.getroot() + self.width = svg_element.viewport_width + self.height = svg_element.viewport_height def _load_buffer_size(self, tile_svg): - circle_elements = tile_svg.findall('.//svg:circle', namespaces=inkex.NSS) - if circle_elements: - self.buffer_size = circle_elements[0].radius - else: - self.buffer_size = 0 + if self.buffer_size is None: + circle_elements = tile_svg.findall('.//svg:circle', namespaces=inkex.NSS) + if circle_elements: + self.buffer_size = circle_elements[0].radius + else: + self.buffer_size = 0 def _load_parallelogram(self, tile_svg): - parallelogram_elements = tile_svg.findall(".//svg:*[@class='para']", namespaces=inkex.NSS) - if parallelogram_elements: - path_element = parallelogram_elements[0] - path = apply_transforms(path_element.get_path(), path_element) - subpaths = path.to_superpath() - subpath = subpaths[0] - points = [Point.from_tuple(p[1]) for p in subpath] - self.shift0 = points[1] - points[0] - self.shift1 = points[2] - points[1] - else: - self.shift0 = Point(self.width, 0) - self.shift1 = Point(0, self.height) + if self.shift0 is None: + parallelogram_elements = tile_svg.findall(".//svg:*[@class='para']", namespaces=inkex.NSS) + if parallelogram_elements: + path_element = parallelogram_elements[0] + path = apply_transforms(path_element.get_path(), path_element) + subpaths = path.to_superpath() + subpath = subpaths[0] + points = [Point.from_tuple(p[1]) for p in subpath] + self.shift0 = points[1] - points[0] + self.shift1 = points[2] - points[1] + else: + self.shift0 = Point(self.width, 0) + self.shift1 = Point(0, self.height) def _path_elements_to_line_strings(self, path_elements): lines = [] @@ -80,7 +99,7 @@ class Tile: return center, width, height - def translate_tile(self, shift): + def _translate_tile(self, shift): translated_tile = [] for start, end in self.tile: @@ -90,6 +109,7 @@ class Tile: return translated_tile + @debug.time def to_graph(self, shape, only_inside=True, pad=True): """Apply this tile to a shape, repeating as necessary. @@ -98,6 +118,8 @@ class Tile: Each edge has an attribute 'line_string' with the LineString representation of this edge. """ + self._load() + shape_center, shape_width, shape_height = self._get_center_and_dimensions(shape) shape_diagonal = (shape_width ** 2 + shape_height ** 2) ** 0.5 graph = Graph() @@ -113,7 +135,7 @@ class Tile: for repeat1 in range(floor(-tiles1 / 2), ceil(tiles1 / 2)): shift0 = repeat0 * self.shift0 + shape_center shift1 = repeat1 * self.shift1 + shape_center - this_tile = self.translate_tile(shift0 + shift1) + this_tile = self._translate_tile(shift0 + shift1) for line in this_tile: line_string = LineString(line) if not only_inside or prepared_shape.contains(line_string): @@ -127,10 +149,14 @@ def all_tile_paths(): get_bundled_dir('tiles')] +@cache def all_tiles(): + tiles = [] for tile_dir in all_tile_paths(): try: for tile_file in sorted(os.listdir(tile_dir)): - yield Tile(os.path.join(tile_dir, tile_file)) + tiles.append(Tile(os.path.join(tile_dir, tile_file))) except FileNotFoundError: pass + + return tiles 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.3.1 From 85f921cd33b402733cea4ce53206aa70a6092d49 Mon Sep 17 00:00:00 2001 From: Lex Neva 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.3.1 From e2965e78f03fb41c9a02c92ef120caf038b837ae Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 16 Jan 2023 14:34:29 -0500 Subject: use snake case per python coding standard --- lib/elements/satin_column.py | 8 ++++---- lib/stitches/running_stitch.py | 6 +++--- lib/utils/prng.py | 26 +++++++++++++------------- 3 files changed, 20 insertions(+), 20 deletions(-) (limited to 'lib/utils') diff --git a/lib/elements/satin_column.py b/lib/elements/satin_column.py index 4028ad27..eba63c6c 100644 --- a/lib/elements/satin_column.py +++ b/lib/elements/satin_column.py @@ -783,7 +783,7 @@ class SatinColumn(EmbroideryElement): # pre-cache ramdomised parameters to avoid property calls in loop if use_random: - seed = prng.joinArgs(self.random_seed, "satin-points") + seed = prng.join_args(self.random_seed, "satin-points") offset_proportional_min = np.array(offset_proportional) - self.random_width_decrease offset_range = (self.random_width_increase + self.random_width_decrease) spacing_sigma = spacing * self.random_zigzag_spacing @@ -857,7 +857,7 @@ class SatinColumn(EmbroideryElement): if to_travel <= 0: if use_random: - roll = prng.uniformFloats(seed, cycle) + roll = prng.uniform_floats(seed, cycle) offset_prop = offset_proportional_min + roll[0:2] * offset_range to_travel = spacing + ((roll[2] - 0.5) * 2 * spacing_sigma) else: @@ -987,7 +987,7 @@ class SatinColumn(EmbroideryElement): if last_point is not None: split_points, _ = self.get_split_points( last_point, a, last_short_point, a_short, max_stitch_length, last_count, - length_sigma, random_phase, min_split_length, prng.joinArgs(seed, 'satin-split', 2*i)) + length_sigma, random_phase, min_split_length, prng.join_args(seed, 'satin-split', 2 * i)) patch.add_stitches(split_points, ("satin_column", "satin_split_stitch")) patch.add_stitch(a_short) @@ -995,7 +995,7 @@ class SatinColumn(EmbroideryElement): split_points, last_count = self.get_split_points( a, b, a_short, b_short, max_stitch_length, None, - length_sigma, random_phase, min_split_length, prng.joinArgs(seed, 'satin-split', 2*i+1)) + length_sigma, random_phase, min_split_length, prng.join_args(seed, 'satin-split', 2 * i + 1)) patch.add_stitches(split_points, ("satin_column", "satin_split_stitch")) patch.add_stitch(b_short) diff --git a/lib/stitches/running_stitch.py b/lib/stitches/running_stitch.py index 8ba53498..1dbfcaaf 100644 --- a/lib/stitches/running_stitch.py +++ b/lib/stitches/running_stitch.py @@ -24,7 +24,7 @@ def split_segment_even_n(a, b, segments: int, jitter_sigma: float = 0.0, random_ splits = np.array(range(1, segments)) / segments if random_seed is not None: - jitters = (prng.nUniformFloats(len(splits), random_seed) * 2) - 1 + jitters = (prng.n_uniform_floats(len(splits), random_seed) * 2) - 1 splits = splits + jitters * (jitter_sigma / segments) # sort the splits in case a bad roll transposes any of them @@ -39,12 +39,12 @@ def split_segment_even_dist(a, b, max_length: float, jitter_sigma: float = 0.0, def split_segment_random_phase(a, b, length: float, length_sigma: float, random_seed: str) -> typing.List[shgeo.Point]: line = shgeo.LineString([a, b]) - progress = length * prng.uniformFloats(random_seed, "phase")[0] + progress = length * prng.uniform_floats(random_seed, "phase")[0] splits = [progress] distance = line.length if progress >= distance: return [] - for x in prng.iterUniformFloats(random_seed): + for x in prng.iter_uniform_floats(random_seed): progress += length * (1 + length_sigma * (x - 0.5) * 2) if progress >= distance: break 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.3.1 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/debug.py | 9 ++ lib/elements/fill_stitch.py | 23 +++-- lib/extensions/params.py | 21 ++++- lib/stitches/meander_fill.py | 72 ++++++++++++--- lib/svg/tags.py | 2 + lib/tiles.py | 113 ++++++++++++++---------- lib/utils/geometry.py | 12 ++- lib/utils/list.py | 14 ++- lib/utils/string.py | 7 ++ tiles/N3-11a.svg | 14 +++ tiles/N3-12.svg | 14 +++ tiles/N3-16a.svg | 14 +++ tiles/N3-17.svg | 14 +++ tiles/N3-18-modified.svg | 14 +++ tiles/N3-18.svg | 14 +++ tiles/N3-20.svg | 14 +++ tiles/N3-21.svg | 14 +++ tiles/N3-23b.svg | 14 +++ tiles/N3-25c.svg | 14 +++ tiles/N3-26b.svg | 14 +++ tiles/N3-27.svg | 14 +++ tiles/N3-2a.svg | 14 +++ tiles/N3-2b.svg | 14 +++ tiles/N3-30a.svg | 14 +++ tiles/N3-4a.svg | 14 +++ tiles/N3-4b.svg | 14 +++ tiles/N3-51b.svg | 14 +++ tiles/N3-57f.svg | 14 +++ tiles/N3-58b.svg | 14 +++ tiles/N3-6.svg | 14 +++ tiles/N3-7.svg | 14 +++ tiles/N3-8a-mistake.svg | 14 +++ tiles/N3-8a.svg | 16 ++++ tiles/N3-8b.svg | 14 +++ tiles/N4-13b-awesome.svg | 14 +++ tiles/N4-13d-awesome.svg | 206 +++++++++++++++++++++++++++++++++++++++++++ tiles/N4-13e-awesome.svg | 14 +++ tiles/N4-13f-awesome.svg | 14 +++ tiles/N4-16a-awesome.svg | 14 +++ tiles/N4-19.svg | 14 +++ tiles/N4-20.svg | 14 +++ tiles/N4-21c.svg | 14 +++ tiles/N4-22-awesome.svg | 14 +++ tiles/N4-23a.svg | 14 +++ tiles/N4-23c.svg | 14 +++ tiles/N4-27.svg | 14 +++ tiles/N4-29e.svg | 14 +++ tiles/N4-29f.svg | 14 +++ tiles/N4-31-awesome.svg | 14 +++ tiles/N4-38.svg | 14 +++ tiles/N4-42e.svg | 14 +++ tiles/N4-44.svg | 14 +++ tiles/N4-52.svg | 14 +++ tiles/N4-54d.svg | 14 +++ tiles/N4-5a-2.svg | 14 +++ tiles/N4-5a.svg | 14 +++ tiles/N4-82.svg | 14 +++ tiles/N4-85d.svg | 14 +++ tiles/N5-1e1.svg | 14 +++ tiles/N5-1q2-awesome.svg | 14 +++ tiles/N5-1t.svg | 14 +++ tiles/N6-2.svg | 14 +++ tiles/N6-5b.svg | 14 +++ tiles/N6-6a.svg | 14 +++ tiles/N6-6c.svg | 14 +++ tiles/NC5-11a.svg | 14 +++ tiles/NC5-20a.svg | 14 +++ tiles/P3-1.svg | 14 +++ tiles/P3-12.svg | 14 +++ tiles/P4-1.svg | 14 +++ tiles/P4-10.svg | 14 +++ tiles/P4-15.svg | 14 +++ tiles/P4-19.svg | 85 ++++++++++++++++++ tiles/P4-23.svg | 14 +++ tiles/P4-24.svg | 14 +++ tiles/P4-25.svg | 14 +++ tiles/P4-42.svg | 14 +++ tiles/P4-43-mod.svg | 14 +++ tiles/P4-43.svg | 14 +++ tiles/P4-47.svg | 14 +++ tiles/P5-10_11-awesome.svg | 14 +++ tiles/P5-19.svg | 14 +++ tiles/P5-23_24.svg | 14 +++ tiles/P5-4.svg | 14 +++ tiles/P6-6_11.svg | 14 +++ tiles/hex_N6-1.svg | 60 +++++++++++++ tiles/tile_test4.svg | 58 ++++++++++++ tiles/weird_one.svg | 126 ++++++++++++++++++++++++++ 88 files changed, 1769 insertions(+), 77 deletions(-) create mode 100644 tiles/N3-11a.svg create mode 100644 tiles/N3-12.svg create mode 100644 tiles/N3-16a.svg create mode 100644 tiles/N3-17.svg create mode 100644 tiles/N3-18-modified.svg create mode 100644 tiles/N3-18.svg create mode 100644 tiles/N3-20.svg create mode 100644 tiles/N3-21.svg create mode 100644 tiles/N3-23b.svg create mode 100644 tiles/N3-25c.svg create mode 100644 tiles/N3-26b.svg create mode 100644 tiles/N3-27.svg create mode 100644 tiles/N3-2a.svg create mode 100644 tiles/N3-2b.svg create mode 100644 tiles/N3-30a.svg create mode 100644 tiles/N3-4a.svg create mode 100644 tiles/N3-4b.svg create mode 100644 tiles/N3-51b.svg create mode 100644 tiles/N3-57f.svg create mode 100644 tiles/N3-58b.svg create mode 100644 tiles/N3-6.svg create mode 100644 tiles/N3-7.svg create mode 100644 tiles/N3-8a-mistake.svg create mode 100644 tiles/N3-8a.svg create mode 100644 tiles/N3-8b.svg create mode 100644 tiles/N4-13b-awesome.svg create mode 100644 tiles/N4-13d-awesome.svg create mode 100644 tiles/N4-13e-awesome.svg create mode 100644 tiles/N4-13f-awesome.svg create mode 100644 tiles/N4-16a-awesome.svg create mode 100644 tiles/N4-19.svg create mode 100644 tiles/N4-20.svg create mode 100644 tiles/N4-21c.svg create mode 100644 tiles/N4-22-awesome.svg create mode 100644 tiles/N4-23a.svg create mode 100644 tiles/N4-23c.svg create mode 100644 tiles/N4-27.svg create mode 100644 tiles/N4-29e.svg create mode 100644 tiles/N4-29f.svg create mode 100644 tiles/N4-31-awesome.svg create mode 100644 tiles/N4-38.svg create mode 100644 tiles/N4-42e.svg create mode 100644 tiles/N4-44.svg create mode 100644 tiles/N4-52.svg create mode 100644 tiles/N4-54d.svg create mode 100644 tiles/N4-5a-2.svg create mode 100644 tiles/N4-5a.svg create mode 100644 tiles/N4-82.svg create mode 100644 tiles/N4-85d.svg create mode 100644 tiles/N5-1e1.svg create mode 100644 tiles/N5-1q2-awesome.svg create mode 100644 tiles/N5-1t.svg create mode 100644 tiles/N6-2.svg create mode 100644 tiles/N6-5b.svg create mode 100644 tiles/N6-6a.svg create mode 100644 tiles/N6-6c.svg create mode 100644 tiles/NC5-11a.svg create mode 100644 tiles/NC5-20a.svg create mode 100644 tiles/P3-1.svg create mode 100644 tiles/P3-12.svg create mode 100644 tiles/P4-1.svg create mode 100644 tiles/P4-10.svg create mode 100644 tiles/P4-15.svg create mode 100644 tiles/P4-19.svg create mode 100644 tiles/P4-23.svg create mode 100644 tiles/P4-24.svg create mode 100644 tiles/P4-25.svg create mode 100644 tiles/P4-42.svg create mode 100644 tiles/P4-43-mod.svg create mode 100644 tiles/P4-43.svg create mode 100644 tiles/P4-47.svg create mode 100644 tiles/P5-10_11-awesome.svg create mode 100644 tiles/P5-19.svg create mode 100644 tiles/P5-23_24.svg create mode 100644 tiles/P5-4.svg create mode 100644 tiles/P6-6_11.svg create mode 100644 tiles/hex_N6-1.svg create mode 100644 tiles/tile_test4.svg create mode 100644 tiles/weird_one.svg (limited to 'lib/utils') diff --git a/lib/debug.py b/lib/debug.py index 0d6af104..94d32cea 100644 --- a/lib/debug.py +++ b/lib/debug.py @@ -233,6 +233,15 @@ class Debug(object): INKSCAPE_LABEL: name })) + @check_enabled + def log_point(self, point, name="point", color=None): + self.log_svg_element(etree.Element("circle", { + "cx": str(point.x), + "cy": str(point.y), + "r": "1", + "style": str(inkex.Style({"fill": "#000000"})), + })) + @check_enabled def log_graph(self, graph, name="Graph", color=None): d = "" diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index fbaab0c2..790eec5c 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -5,6 +5,7 @@ import logging import math +import numpy as np import re import sys import traceback @@ -142,7 +143,7 @@ class FillStitch(EmbroideryElement): @property @param('smoothness_mm', _('Smoothness'), tooltip=_( - 'Smooth the stitch path. Smoothness limits how far the smoothed stitch path ' + + 'Smooth the stitch path. Smoothness limits approximately how far the smoothed stitch path ' + 'is allowed to deviate from the original path. Hint: a lower stitchc tolerance may be needed too.' ), type='integer', @@ -159,11 +160,21 @@ class FillStitch(EmbroideryElement): return self.get_boolean_param('clockwise', True) @property - @param('meander_pattern', _('Meander Pattern'), type='dropdown', default=0, + @param('meander_pattern', _('Meander Pattern'), type='select', default=0, options=[tile.name for tile in tiles.all_tiles()], select_items=[('fill_method', 4)], sort_index=3) def meander_pattern(self): return self.get_param('meander_pattern', None) + @property + @param('meander_scale_percent', _('Meander pattern scale'), type='float', unit="%", default=100, select_items=[('fill_method', 4)], sort_index=4) + def meander_scale(self): + return np.maximum(self.get_split_float_param('meander_scale_percent', (100, 100)), (10, 10)) / 100 + + @property + @param('meander_padding_mm', _('Meander padding'), type='float', unit="mm", default=0, select_items=[('fill_method', 4)], sort_index=5) + def meander_padding(self): + return self.get_float_param('meander_padding_mm', 0) + @property @param('angle', _('Angle of lines of stitches'), @@ -593,7 +604,7 @@ class FillStitch(EmbroideryElement): stitch_groups.extend(underlay_stitch_groups) fill_shapes = self.fill_shape(shape) - for fill_shape in fill_shapes.geoms: + for i, fill_shape in enumerate(fill_shapes.geoms): if self.fill_method == 0: stitch_groups.extend(self.do_auto_fill(fill_shape, previous_stitch_group, start, end)) if self.fill_method == 1: @@ -601,7 +612,7 @@ class FillStitch(EmbroideryElement): elif self.fill_method == 2: stitch_groups.extend(self.do_guided_fill(fill_shape, previous_stitch_group, start, end)) elif self.fill_method == 4: - stitch_groups.extend(self.do_meander_fill(fill_shape, start, end)) + stitch_groups.extend(self.do_meander_fill(fill_shape, i, start, end)) except ExitThread: raise except Exception: @@ -733,11 +744,11 @@ class FillStitch(EmbroideryElement): )) return [stitch_group] - def do_meander_fill(self, shape, starting_point, ending_point): + def do_meander_fill(self, shape, i, starting_point, ending_point): stitch_group = StitchGroup( color=self.color, tags=("meander_fill", "meander_fill_top"), - stitches=meander_fill(self, shape, starting_point, ending_point)) + stitches=meander_fill(self, shape, i, starting_point, ending_point)) return [stitch_group] @cache diff --git a/lib/extensions/params.py b/lib/extensions/params.py index 1262ceb6..a34aeeae 100644 --- a/lib/extensions/params.py +++ b/lib/extensions/params.py @@ -190,8 +190,13 @@ class ParamsTab(ScrolledPanel): try: values[name] = input.GetValue() except AttributeError: - # dropdown - values[name] = input.GetSelection() + param = self.dict_of_choices[name]['param'] + if param.type == 'dropdown': + # dropdown + values[name] = input.GetSelection() + elif param.type == 'select': + selection = input.GetSelection() + values[name] = param.options[selection] return values @@ -368,9 +373,17 @@ class ParamsTab(ScrolledPanel): input.SetValue(param.values[0]) input.Bind(wx.EVT_CHECKBOX, self.changed) - elif param.type == 'dropdown': + elif param.type in ('dropdown', 'select'): input = wx.Choice(self, wx.ID_ANY, choices=param.options) - input.SetSelection(int(param.values[0])) + + if param.type == 'dropdown': + input.SetSelection(int(param.values[0])) + else: + try: + input.SetSelection(param.options.index(param.values[0])) + except ValueError: + input.SetSelection(param.default) + input.Bind(wx.EVT_CHOICE, self.changed) input.Bind(wx.EVT_CHOICE, self.update_choice_state) self.dict_of_choices[param.name] = { diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 2ac3cd03..cb6e3f4e 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -1,21 +1,33 @@ +import networkx as nx from shapely.geometry import MultiPoint, Point from shapely.ops import nearest_points -import networkx as nx +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.geometry import Point as InkStitchPoint from ..utils.list import poprandom +from ..utils.prng import iter_uniform_floats -def meander_fill(fill, shape, starting_point, ending_point): +def meander_fill(fill, shape, shape_index, starting_point, ending_point): + debug.log(f"meander pattern: {fill.meander_pattern}") tile = get_tile(fill.meander_pattern) if not tile: return [] - graph = tile.to_graph(shape) - start, end = find_starting_and_ending_nodes(graph, starting_point, ending_point) + debug.log(f"tile name: {tile.name}") - return generate_meander_path(graph, start, end) + # debug.log_line_strings(ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') + graph = tile.to_graph(shape, fill.meander_scale, fill.meander_padding) + # debug.log_graph(graph, 'Meander graph') + # debug.log(f"graph connected? {nx.is_connected(graph)}") + start, end = find_starting_and_ending_nodes(graph, shape, starting_point, ending_point) + rng = iter_uniform_floats(fill.random_seed, 'meander-fill', shape_index) + + return post_process(generate_meander_path(graph, start, end, rng), fill) def get_tile(tile_name): @@ -27,7 +39,16 @@ def get_tile(tile_name): return None -def find_starting_and_ending_nodes(graph, starting_point, ending_point): +def find_starting_and_ending_nodes(graph, shape, starting_point, ending_point): + if starting_point is None: + starting_point = shape.exterior.coords[0] + starting_point = Point(starting_point) + + if ending_point is None: + ending_point = starting_point + else: + ending_point = Point(ending_point) + all_points = MultiPoint(list(graph)) starting_node = nearest_points(starting_point, all_points)[1].coords[0] @@ -49,7 +70,8 @@ def find_initial_path(graph, start, end): return nx.shortest_path(graph, start, end) -def generate_meander_path(graph, start, end): +@debug.time +def generate_meander_path(graph, start, end, rng): path = find_initial_path(graph, start, end) path_edges = list(zip(path[:-1], path[1:])) graph.remove_edges_from(path_edges) @@ -59,15 +81,16 @@ def generate_meander_path(graph, start, end): meander_path = path_edges while edges_to_consider: while edges_to_consider: - edge = poprandom(edges_to_consider) + edge = poprandom(edges_to_consider, rng) edges_to_consider.extend(replace_edge(meander_path, edge, graph, graph_nodes)) - edge_pairs = list(zip(path[:-1], path[1:])) + edge_pairs = list(zip(meander_path[:-1], meander_path[1:])) while edge_pairs: - edge1, edge2 = poprandom(edge_pairs) + edge1, edge2 = poprandom(edge_pairs, rng) edges_to_consider.extend(replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)) + break - return meander_path + return path_to_points(meander_path) def replace_edge(path, edge, graph, graph_nodes): @@ -81,8 +104,9 @@ def replace_edge(path, edge, graph, graph_nodes): i = path.index(edge) path[i:i + 1] = new_path graph.remove_edges_from(new_path) + # do I need to remove the last one too? graph_nodes.difference_update(start for start, end in new_path) - debug.log(f"found new path of length {len(new_path)} at position {i}") + # debug.log(f"found new path of length {len(new_path)} at position {i}") return new_path @@ -98,7 +122,29 @@ def replace_edge_pair(path, edge1, edge2, graph, graph_nodes): i = path.index(edge1) path[i:i + 2] = new_path graph.remove_edges_from(new_path) + # do I need to remove the last one too? graph_nodes.difference_update(start for start, end in new_path) - debug.log(f"found new pair path of length {len(new_path)} at position {i}") + # debug.log(f"found new pair path of length {len(new_path)} at position {i}") return new_path + + +@debug.time +def post_process(points, fill): + debug.log(f"smoothness: {fill.smoothness}") + # debug.log_line_string(LineString(points), "pre-smoothed", "#FF0000") + smoothed_points = smooth_path(points, fill.smoothness) + smoothed_points = [InkStitchPoint.from_tuple(point) for point in smoothed_points] + + stitches = running_stitch(smoothed_points, fill.running_stitch_length, fill.running_stitch_tolerance) + stitches = [Stitch(point) for point in stitches] + + return stitches + + +def path_to_points(path): + points = [start for start, end in path] + if path: + points.append(path[-1][1]) + + return points diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 4979b58a..32744d1b 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -70,6 +70,8 @@ inkstitch_attribs = [ 'clockwise', 'reverse', 'meander_pattern', + 'meander_scale_percent', + 'meander_padding_mm', 'expand_mm', 'fill_underlay', 'fill_underlay_angle', diff --git a/lib/tiles.py b/lib/tiles.py index e9f0305a..2bef7a19 100644 --- a/lib/tiles.py +++ b/lib/tiles.py @@ -1,15 +1,15 @@ -import inkex +import os from math import ceil, floor + +import inkex +import lxml from networkx import Graph -import os from shapely.geometry import LineString from shapely.prepared import prep from .debug import debug from .svg import apply_transforms -from .svg.tags import SODIPODI_NAMEDVIEW -from .utils import cache, get_bundled_dir, guess_inkscape_config_path, Point -from random import random +from .utils import Point, cache, get_bundled_dir, guess_inkscape_config_path class Tile: @@ -33,11 +33,7 @@ class Tile: __str__ = __repr__ def _get_name(self, tile_svg, tile_path): - name = tile_svg.get(SODIPODI_NAMEDVIEW) - if name: - return name - else: - return os.path.splitext(os.path.basename(tile_path))[0] + return os.path.splitext(os.path.basename(tile_path)[0]) def _load(self): self._load_paths(self.tile_svg) @@ -46,39 +42,35 @@ class Tile: self._load_parallelogram(self.tile_svg) def _load_paths(self, tile_svg): - if self.tile is None: - path_elements = tile_svg.findall('.//svg:path', namespaces=inkex.NSS) - self.tile = self._path_elements_to_line_strings(path_elements) - # self.center, ignore, ignore = self._get_center_and_dimensions(self.tile) + path_elements = tile_svg.findall('.//svg:path', namespaces=inkex.NSS) + self.tile = self._path_elements_to_line_strings(path_elements) + # self.center, ignore, ignore = self._get_center_and_dimensions(self.tile) def _load_dimensions(self, tile_svg): - if self.width is None: - svg_element = tile_svg.getroot() - self.width = svg_element.viewport_width - self.height = svg_element.viewport_height + svg_element = tile_svg.getroot() + self.width = svg_element.viewport_width + self.height = svg_element.viewport_height def _load_buffer_size(self, tile_svg): - if self.buffer_size is None: - circle_elements = tile_svg.findall('.//svg:circle', namespaces=inkex.NSS) - if circle_elements: - self.buffer_size = circle_elements[0].radius - else: - self.buffer_size = 0 + circle_elements = tile_svg.findall('.//svg:circle', namespaces=inkex.NSS) + if circle_elements: + self.buffer_size = circle_elements[0].radius + else: + self.buffer_size = 0 def _load_parallelogram(self, tile_svg): - if self.shift0 is None: - parallelogram_elements = tile_svg.findall(".//svg:*[@class='para']", namespaces=inkex.NSS) - if parallelogram_elements: - path_element = parallelogram_elements[0] - path = apply_transforms(path_element.get_path(), path_element) - subpaths = path.to_superpath() - subpath = subpaths[0] - points = [Point.from_tuple(p[1]) for p in subpath] - self.shift0 = points[1] - points[0] - self.shift1 = points[2] - points[1] - else: - self.shift0 = Point(self.width, 0) - self.shift1 = Point(0, self.height) + parallelogram_elements = tile_svg.findall(".//svg:*[@class='para']", namespaces=inkex.NSS) + if parallelogram_elements: + path_element = parallelogram_elements[0] + path = apply_transforms(path_element.get_path(), path_element) + subpaths = path.to_superpath() + subpath = subpaths[0] + points = [Point.from_tuple(p[1]) for p in subpath] + self.shift0 = points[1] - points[0] + self.shift1 = points[2] - points[1] + else: + self.shift0 = Point(self.width, 0) + self.shift1 = Point(0, self.height) def _path_elements_to_line_strings(self, path_elements): lines = [] @@ -109,8 +101,19 @@ class Tile: return translated_tile + def _scale(self, x_scale, y_scale): + self.shift0 = self.shift0.scale(x_scale, y_scale) + self.shift1 = self.shift1.scale(x_scale, y_scale) + + scaled_tile = [] + for start, end in self.tile: + start = start.scale(x_scale, y_scale) + end = end.scale(x_scale, y_scale) + scaled_tile.append((start, end)) + self.tile = scaled_tile + @debug.time - def to_graph(self, shape, only_inside=True, pad=True): + def to_graph(self, shape, scale, buffer=None): """Apply this tile to a shape, repeating as necessary. Return value: @@ -119,27 +122,36 @@ class Tile: representation of this edge. """ self._load() + x_scale, y_scale = scale + self._scale(x_scale, y_scale) shape_center, shape_width, shape_height = self._get_center_and_dimensions(shape) - shape_diagonal = (shape_width ** 2 + shape_height ** 2) ** 0.5 - graph = Graph() + shape_diagonal = Point(shape_width, shape_height).length() + + if not buffer: + average_scale = (x_scale + y_scale) / 2 + buffer = self.buffer_size * average_scale - if pad: - shape = shape.buffer(-self.buffer_size) + contracted_shape = shape.buffer(-buffer) + prepared_shape = prep(contracted_shape) - prepared_shape = prep(shape) + # debug.log_line_string(contracted_shape.exterior, "contracted shape") + return self._generate_graph(prepared_shape, shape_center, shape_diagonal) + + def _generate_graph(self, shape, shape_center, shape_diagonal): + graph = Graph() tiles0 = ceil(shape_diagonal / self.shift0.length()) + 2 tiles1 = ceil(shape_diagonal / self.shift1.length()) + 2 for repeat0 in range(floor(-tiles0 / 2), ceil(tiles0 / 2)): for repeat1 in range(floor(-tiles1 / 2), ceil(tiles1 / 2)): - shift0 = repeat0 * self.shift0 + shape_center - shift1 = repeat1 * self.shift1 + shape_center - this_tile = self._translate_tile(shift0 + shift1) + shift0 = repeat0 * self.shift0 + shift1 = repeat1 * self.shift1 + this_tile = self._translate_tile(shift0 + shift1 + shape_center) for line in this_tile: line_string = LineString(line) - if not only_inside or prepared_shape.contains(line_string): - graph.add_edge(line[0], line[1], line_string=line_string, weight=random() + 0.1) + if shape.contains(line_string): + graph.add_edge(line[0], line[1]) return graph @@ -155,7 +167,10 @@ def all_tiles(): for tile_dir in all_tile_paths(): try: for tile_file in sorted(os.listdir(tile_dir)): - tiles.append(Tile(os.path.join(tile_dir, tile_file))) + try: + tiles.append(Tile(os.path.join(tile_dir, tile_file))) + except (OSError, lxml.etree.XMLSyntaxError): + pass except FileNotFoundError: pass 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 diff --git a/tiles/N3-11a.svg b/tiles/N3-11a.svg new file mode 100644 index 00000000..3195b983 --- /dev/null +++ b/tiles/N3-11a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-12.svg b/tiles/N3-12.svg new file mode 100644 index 00000000..666f7e7f --- /dev/null +++ b/tiles/N3-12.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-16a.svg b/tiles/N3-16a.svg new file mode 100644 index 00000000..844ad5a1 --- /dev/null +++ b/tiles/N3-16a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-17.svg b/tiles/N3-17.svg new file mode 100644 index 00000000..26447e8b --- /dev/null +++ b/tiles/N3-17.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-18-modified.svg b/tiles/N3-18-modified.svg new file mode 100644 index 00000000..5e65e625 --- /dev/null +++ b/tiles/N3-18-modified.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-18.svg b/tiles/N3-18.svg new file mode 100644 index 00000000..07993c7b --- /dev/null +++ b/tiles/N3-18.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-20.svg b/tiles/N3-20.svg new file mode 100644 index 00000000..8995a922 --- /dev/null +++ b/tiles/N3-20.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-21.svg b/tiles/N3-21.svg new file mode 100644 index 00000000..61f3b5da --- /dev/null +++ b/tiles/N3-21.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-23b.svg b/tiles/N3-23b.svg new file mode 100644 index 00000000..c687badc --- /dev/null +++ b/tiles/N3-23b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-25c.svg b/tiles/N3-25c.svg new file mode 100644 index 00000000..c6eea00c --- /dev/null +++ b/tiles/N3-25c.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-26b.svg b/tiles/N3-26b.svg new file mode 100644 index 00000000..ed9b254e --- /dev/null +++ b/tiles/N3-26b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-27.svg b/tiles/N3-27.svg new file mode 100644 index 00000000..1780cfbd --- /dev/null +++ b/tiles/N3-27.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-2a.svg b/tiles/N3-2a.svg new file mode 100644 index 00000000..0abd3299 --- /dev/null +++ b/tiles/N3-2a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-2b.svg b/tiles/N3-2b.svg new file mode 100644 index 00000000..8b6fe4df --- /dev/null +++ b/tiles/N3-2b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-30a.svg b/tiles/N3-30a.svg new file mode 100644 index 00000000..17b886f8 --- /dev/null +++ b/tiles/N3-30a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-4a.svg b/tiles/N3-4a.svg new file mode 100644 index 00000000..b27629ea --- /dev/null +++ b/tiles/N3-4a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-4b.svg b/tiles/N3-4b.svg new file mode 100644 index 00000000..b42ecde9 --- /dev/null +++ b/tiles/N3-4b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-51b.svg b/tiles/N3-51b.svg new file mode 100644 index 00000000..2ec42348 --- /dev/null +++ b/tiles/N3-51b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-57f.svg b/tiles/N3-57f.svg new file mode 100644 index 00000000..96d14616 --- /dev/null +++ b/tiles/N3-57f.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-58b.svg b/tiles/N3-58b.svg new file mode 100644 index 00000000..1acddd23 --- /dev/null +++ b/tiles/N3-58b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-6.svg b/tiles/N3-6.svg new file mode 100644 index 00000000..0c8dc6ee --- /dev/null +++ b/tiles/N3-6.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-7.svg b/tiles/N3-7.svg new file mode 100644 index 00000000..b1a23a82 --- /dev/null +++ b/tiles/N3-7.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-8a-mistake.svg b/tiles/N3-8a-mistake.svg new file mode 100644 index 00000000..562ded37 --- /dev/null +++ b/tiles/N3-8a-mistake.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N3-8a.svg b/tiles/N3-8a.svg new file mode 100644 index 00000000..9c47b82b --- /dev/null +++ b/tiles/N3-8a.svg @@ -0,0 +1,16 @@ + + + + + + + diff --git a/tiles/N3-8b.svg b/tiles/N3-8b.svg new file mode 100644 index 00000000..0e547774 --- /dev/null +++ b/tiles/N3-8b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-13b-awesome.svg b/tiles/N4-13b-awesome.svg new file mode 100644 index 00000000..4dcaeccd --- /dev/null +++ b/tiles/N4-13b-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-13d-awesome.svg b/tiles/N4-13d-awesome.svg new file mode 100644 index 00000000..9dcbfb4f --- /dev/null +++ b/tiles/N4-13d-awesome.svg @@ -0,0 +1,206 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tiles/N4-13e-awesome.svg b/tiles/N4-13e-awesome.svg new file mode 100644 index 00000000..716f3cc7 --- /dev/null +++ b/tiles/N4-13e-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-13f-awesome.svg b/tiles/N4-13f-awesome.svg new file mode 100644 index 00000000..762f602a --- /dev/null +++ b/tiles/N4-13f-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-16a-awesome.svg b/tiles/N4-16a-awesome.svg new file mode 100644 index 00000000..5fdb9c6e --- /dev/null +++ b/tiles/N4-16a-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-19.svg b/tiles/N4-19.svg new file mode 100644 index 00000000..f7abf8c5 --- /dev/null +++ b/tiles/N4-19.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-20.svg b/tiles/N4-20.svg new file mode 100644 index 00000000..d1a87c96 --- /dev/null +++ b/tiles/N4-20.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-21c.svg b/tiles/N4-21c.svg new file mode 100644 index 00000000..47e7885b --- /dev/null +++ b/tiles/N4-21c.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-22-awesome.svg b/tiles/N4-22-awesome.svg new file mode 100644 index 00000000..275f5f69 --- /dev/null +++ b/tiles/N4-22-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-23a.svg b/tiles/N4-23a.svg new file mode 100644 index 00000000..5637fec3 --- /dev/null +++ b/tiles/N4-23a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-23c.svg b/tiles/N4-23c.svg new file mode 100644 index 00000000..bfd2d96f --- /dev/null +++ b/tiles/N4-23c.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-27.svg b/tiles/N4-27.svg new file mode 100644 index 00000000..dd341fc3 --- /dev/null +++ b/tiles/N4-27.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-29e.svg b/tiles/N4-29e.svg new file mode 100644 index 00000000..62991ed2 --- /dev/null +++ b/tiles/N4-29e.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-29f.svg b/tiles/N4-29f.svg new file mode 100644 index 00000000..a864da67 --- /dev/null +++ b/tiles/N4-29f.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-31-awesome.svg b/tiles/N4-31-awesome.svg new file mode 100644 index 00000000..62a377d3 --- /dev/null +++ b/tiles/N4-31-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-38.svg b/tiles/N4-38.svg new file mode 100644 index 00000000..92655513 --- /dev/null +++ b/tiles/N4-38.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-42e.svg b/tiles/N4-42e.svg new file mode 100644 index 00000000..c8e76ee6 --- /dev/null +++ b/tiles/N4-42e.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-44.svg b/tiles/N4-44.svg new file mode 100644 index 00000000..1d93d1fe --- /dev/null +++ b/tiles/N4-44.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-52.svg b/tiles/N4-52.svg new file mode 100644 index 00000000..1b6554fe --- /dev/null +++ b/tiles/N4-52.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-54d.svg b/tiles/N4-54d.svg new file mode 100644 index 00000000..0cb4f6d6 --- /dev/null +++ b/tiles/N4-54d.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-5a-2.svg b/tiles/N4-5a-2.svg new file mode 100644 index 00000000..328781bf --- /dev/null +++ b/tiles/N4-5a-2.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-5a.svg b/tiles/N4-5a.svg new file mode 100644 index 00000000..c905d788 --- /dev/null +++ b/tiles/N4-5a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-82.svg b/tiles/N4-82.svg new file mode 100644 index 00000000..e9787c67 --- /dev/null +++ b/tiles/N4-82.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N4-85d.svg b/tiles/N4-85d.svg new file mode 100644 index 00000000..322d5096 --- /dev/null +++ b/tiles/N4-85d.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N5-1e1.svg b/tiles/N5-1e1.svg new file mode 100644 index 00000000..c03d39d7 --- /dev/null +++ b/tiles/N5-1e1.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N5-1q2-awesome.svg b/tiles/N5-1q2-awesome.svg new file mode 100644 index 00000000..7f482bdd --- /dev/null +++ b/tiles/N5-1q2-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N5-1t.svg b/tiles/N5-1t.svg new file mode 100644 index 00000000..8608ab26 --- /dev/null +++ b/tiles/N5-1t.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N6-2.svg b/tiles/N6-2.svg new file mode 100644 index 00000000..06e0439b --- /dev/null +++ b/tiles/N6-2.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N6-5b.svg b/tiles/N6-5b.svg new file mode 100644 index 00000000..c53d4a4a --- /dev/null +++ b/tiles/N6-5b.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N6-6a.svg b/tiles/N6-6a.svg new file mode 100644 index 00000000..8f0f9abb --- /dev/null +++ b/tiles/N6-6a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/N6-6c.svg b/tiles/N6-6c.svg new file mode 100644 index 00000000..55212b16 --- /dev/null +++ b/tiles/N6-6c.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/NC5-11a.svg b/tiles/NC5-11a.svg new file mode 100644 index 00000000..c8f73251 --- /dev/null +++ b/tiles/NC5-11a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/NC5-20a.svg b/tiles/NC5-20a.svg new file mode 100644 index 00000000..be8fd672 --- /dev/null +++ b/tiles/NC5-20a.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P3-1.svg b/tiles/P3-1.svg new file mode 100644 index 00000000..8e452a96 --- /dev/null +++ b/tiles/P3-1.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P3-12.svg b/tiles/P3-12.svg new file mode 100644 index 00000000..f51e0bb0 --- /dev/null +++ b/tiles/P3-12.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-1.svg b/tiles/P4-1.svg new file mode 100644 index 00000000..74a6ce1f --- /dev/null +++ b/tiles/P4-1.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-10.svg b/tiles/P4-10.svg new file mode 100644 index 00000000..5b12947c --- /dev/null +++ b/tiles/P4-10.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-15.svg b/tiles/P4-15.svg new file mode 100644 index 00000000..ae550133 --- /dev/null +++ b/tiles/P4-15.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-19.svg b/tiles/P4-19.svg new file mode 100644 index 00000000..2dc65480 --- /dev/null +++ b/tiles/P4-19.svg @@ -0,0 +1,85 @@ + + + + + + + + + + + + + + + + diff --git a/tiles/P4-23.svg b/tiles/P4-23.svg new file mode 100644 index 00000000..0eac019b --- /dev/null +++ b/tiles/P4-23.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-24.svg b/tiles/P4-24.svg new file mode 100644 index 00000000..dbe56c31 --- /dev/null +++ b/tiles/P4-24.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-25.svg b/tiles/P4-25.svg new file mode 100644 index 00000000..be56ae99 --- /dev/null +++ b/tiles/P4-25.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-42.svg b/tiles/P4-42.svg new file mode 100644 index 00000000..d5b9ada9 --- /dev/null +++ b/tiles/P4-42.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-43-mod.svg b/tiles/P4-43-mod.svg new file mode 100644 index 00000000..bf67672e --- /dev/null +++ b/tiles/P4-43-mod.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-43.svg b/tiles/P4-43.svg new file mode 100644 index 00000000..d7b34c29 --- /dev/null +++ b/tiles/P4-43.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P4-47.svg b/tiles/P4-47.svg new file mode 100644 index 00000000..19074686 --- /dev/null +++ b/tiles/P4-47.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P5-10_11-awesome.svg b/tiles/P5-10_11-awesome.svg new file mode 100644 index 00000000..d6873899 --- /dev/null +++ b/tiles/P5-10_11-awesome.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P5-19.svg b/tiles/P5-19.svg new file mode 100644 index 00000000..d6711f38 --- /dev/null +++ b/tiles/P5-19.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P5-23_24.svg b/tiles/P5-23_24.svg new file mode 100644 index 00000000..9281ef1f --- /dev/null +++ b/tiles/P5-23_24.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P5-4.svg b/tiles/P5-4.svg new file mode 100644 index 00000000..0c36e998 --- /dev/null +++ b/tiles/P5-4.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/P6-6_11.svg b/tiles/P6-6_11.svg new file mode 100644 index 00000000..ab713c2e --- /dev/null +++ b/tiles/P6-6_11.svg @@ -0,0 +1,14 @@ + + + + + diff --git a/tiles/hex_N6-1.svg b/tiles/hex_N6-1.svg new file mode 100644 index 00000000..072a2488 --- /dev/null +++ b/tiles/hex_N6-1.svg @@ -0,0 +1,60 @@ + + + + + + + + + diff --git a/tiles/tile_test4.svg b/tiles/tile_test4.svg new file mode 100644 index 00000000..c73cfa55 --- /dev/null +++ b/tiles/tile_test4.svg @@ -0,0 +1,58 @@ + + + + + + + + + diff --git a/tiles/weird_one.svg b/tiles/weird_one.svg new file mode 100644 index 00000000..347a43fe --- /dev/null +++ b/tiles/weird_one.svg @@ -0,0 +1,126 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + -- cgit v1.3.1 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') 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.3.1 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/stitches/contour_fill.py | 2 + lib/stitches/meander_fill.py | 2 +- lib/utils/geometry.py | 96 ++------------------------------------------ lib/utils/smoothing.py | 84 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 91 insertions(+), 93 deletions(-) create mode 100644 lib/utils/smoothing.py (limited to 'lib/utils') 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] -- cgit v1.3.1 From 7fa3fec5346a4c87ff1f95dca94cf771455d8cb0 Mon Sep 17 00:00:00 2001 From: Lex Neva 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.3.1