diff options
| -rw-r--r-- | lib/elements/fill_stitch.py | 21 | ||||
| -rw-r--r-- | lib/stitches/meander_fill.py | 104 | ||||
| -rw-r--r-- | lib/svg/tags.py | 1 | ||||
| -rw-r--r-- | lib/tiles.py | 96 | ||||
| -rw-r--r-- | lib/utils/list.py | 15 |
5 files changed, 200 insertions, 37 deletions
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) @@ -157,6 +159,12 @@ class FillStitch(EmbroideryElement): 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'), tooltip=_('The angle increases in a counter-clockwise direction. 0 is horizontal. Negative angles are allowed.'), @@ -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 |