diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/commands.py | 17 | ||||
| -rw-r--r-- | lib/elements/marker.py (renamed from lib/elements/pattern.py) | 13 | ||||
| -rw-r--r-- | lib/elements/satin_column.py | 5 | ||||
| -rw-r--r-- | lib/elements/stroke.py | 11 | ||||
| -rw-r--r-- | lib/elements/utils.py | 8 | ||||
| -rw-r--r-- | lib/extensions/__init__.py | 2 | ||||
| -rw-r--r-- | lib/extensions/auto_run.py | 65 | ||||
| -rw-r--r-- | lib/extensions/base.py | 8 | ||||
| -rw-r--r-- | lib/extensions/reorder.py | 2 | ||||
| -rw-r--r-- | lib/marker.py | 46 | ||||
| -rw-r--r-- | lib/patterns.py | 48 | ||||
| -rw-r--r-- | lib/stitches/auto_run.py | 284 | ||||
| -rw-r--r-- | lib/stitches/auto_satin.py | 248 | ||||
| -rw-r--r-- | lib/stitches/utils/autoroute.py | 221 |
14 files changed, 685 insertions, 293 deletions
diff --git a/lib/commands.py b/lib/commands.py index c9da782a..1d235759 100644 --- a/lib/commands.py +++ b/lib/commands.py @@ -27,6 +27,12 @@ COMMANDS = { "fill_end": N_("Fill stitch ending position"), # L10N command attached to an object + "run_start": N_("Auto-route running stitch starting position"), + + # L10N command attached to an object + "run_end": N_("Auto-route running stitch ending position"), + + # L10N command attached to an object "satin_start": N_("Auto-route satin stitch starting position"), # L10N command attached to an object @@ -54,7 +60,8 @@ COMMANDS = { "stop_position": N_("Jump destination for Stop commands (a.k.a. \"Frame Out position\")."), } -OBJECT_COMMANDS = ["fill_start", "fill_end", "satin_start", "satin_end", "stop", "trim", "ignore_object", "satin_cut_point"] +OBJECT_COMMANDS = ["fill_start", "fill_end", "run_start", "run_end", "satin_start", "satin_end", "stop", "trim", "ignore_object", "satin_cut_point"] +FREE_MOVEMENT_OBJECT_COMMANDS = ["run_start", "run_end", "satin_start", "satin_end"] LAYER_COMMANDS = ["ignore_layer"] GLOBAL_COMMANDS = ["origin", "stop_position"] @@ -288,7 +295,7 @@ def add_group(document, node, command): return group -def add_connector(document, symbol, element): +def add_connector(document, symbol, command, element): # I'd like it if I could position the connector endpoint nicely but inkscape just # moves it to the element's center immediately after the extension runs. start_pos = (symbol.get('x'), symbol.get('y')) @@ -304,12 +311,14 @@ def add_connector(document, symbol, element): "style": "stroke:#000000;stroke-width:1px;stroke-opacity:0.5;fill:none;", CONNECTION_START: "#%s" % symbol.get('id'), CONNECTION_END: "#%s" % element.node.get('id'), - CONNECTOR_TYPE: "polyline", # l10n: the name of the line that connects a command to the object it applies to INKSCAPE_LABEL: _("connector") }) + if command not in FREE_MOVEMENT_OBJECT_COMMANDS: + path.attrib[CONNECTOR_TYPE] = "polyline" + symbol.getparent().insert(0, path) @@ -383,7 +392,7 @@ def add_commands(element, commands): group = add_group(svg, element.node, command) pos = get_command_pos(element, i, len(commands)) symbol = add_symbol(svg, group, command, pos) - add_connector(svg, symbol, element) + add_connector(svg, symbol, command, element) def add_layer_commands(layer, commands): diff --git a/lib/elements/pattern.py b/lib/elements/marker.py index 4b92d366..574ce91e 100644 --- a/lib/elements/pattern.py +++ b/lib/elements/marker.py @@ -10,24 +10,23 @@ from .element import EmbroideryElement from .validation import ObjectTypeWarning -class PatternWarning(ObjectTypeWarning): - name = _("Pattern Element") +class MarkerWarning(ObjectTypeWarning): + name = _("Marker Element") description = _("This element will not be embroidered. " - "It will appear as a pattern applied to objects in the same group as it. " - "Objects in sub-groups will be ignored.") + "It will be applied to objects in the same group. Objects in sub-groups will be ignored.") steps_to_solve = [ - _("To disable pattern mode, remove the pattern marker:"), + _("Turn back to normal embroidery element mode, remove the marker:"), _('* Open the Fill and Stroke panel (Objects > Fill and Stroke)'), _('* Go to the Stroke style tab'), _('* Under "Markers" choose the first (empty) option in the first dropdown list.') ] -class PatternObject(EmbroideryElement): +class MarkerObject(EmbroideryElement): def validation_warnings(self): repr_point = next(inkex.Path(self.parse_path()).end_points) - yield PatternWarning(repr_point) + yield MarkerWarning(repr_point) def to_stitch_groups(self, last_patch): return [] diff --git a/lib/elements/satin_column.py b/lib/elements/satin_column.py index a30f16d4..83080003 100644 --- a/lib/elements/satin_column.py +++ b/lib/elements/satin_column.py @@ -216,10 +216,7 @@ class SatinColumn(EmbroideryElement): # This isn't used for satins at all, but other parts of the code # may need to know the general shape of a satin column. - flattened = self.flatten(self.parse_path()) - line_strings = [shgeo.LineString(path) for path in flattened] - - return shgeo.MultiLineString(line_strings) + return shgeo.MultiLineString(self.flattened_rails).convex_hull @property @cache diff --git a/lib/elements/stroke.py b/lib/elements/stroke.py index 307c78b8..6f8d8bb1 100644 --- a/lib/elements/stroke.py +++ b/lib/elements/stroke.py @@ -87,7 +87,7 @@ class Stroke(EmbroideryElement): # manipulate invalid path if len(flattened[0]) == 1: - return [[[flattened[0][0][0], flattened[0][0][1]], [flattened[0][0][0]+1.0, flattened[0][0][1]]]] + return [[[flattened[0][0][0], flattened[0][0][1]], [flattened[0][0][0] + 1.0, flattened[0][0][1]]]] if self.manual_stitch_mode: return [self.strip_control_points(subpath) for subpath in path] @@ -97,12 +97,13 @@ class Stroke(EmbroideryElement): @property @cache def shape(self): + return self.as_multi_line_string().convex_hull + + @cache + def as_multi_line_string(self): line_strings = [shapely.geometry.LineString(path) for path in self.paths] - # Using convex_hull here is an important optimization. Otherwise - # complex paths cause operations on the shape to take a long time. - # This especially happens when importing machine embroidery files. - return shapely.geometry.MultiLineString(line_strings).convex_hull + return shapely.geometry.MultiLineString(line_strings) @property @param('manual_stitch', diff --git a/lib/elements/utils.py b/lib/elements/utils.py index 99df7002..960f5b07 100644 --- a/lib/elements/utils.py +++ b/lib/elements/utils.py @@ -4,7 +4,7 @@ # Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. from ..commands import is_command -from ..patterns import is_pattern +from ..marker import has_marker from ..svg.tags import (EMBROIDERABLE_TAGS, SVG_IMAGE_TAG, SVG_PATH_TAG, SVG_POLYLINE_TAG, SVG_TEXT_TAG) from .auto_fill import AutoFill @@ -13,7 +13,7 @@ from .element import EmbroideryElement from .empty_d_object import EmptyDObject from .fill import Fill from .image import ImageObject -from .pattern import PatternObject +from .marker import MarkerObject from .polyline import Polyline from .satin_column import SatinColumn from .stroke import Stroke @@ -30,8 +30,8 @@ def node_to_elements(node): # noqa: C901 elif node.tag == SVG_PATH_TAG and not node.get('d', ''): return [EmptyDObject(node)] - elif is_pattern(node): - return [PatternObject(node)] + elif has_marker(node): + return [MarkerObject(node)] elif node.tag in EMBROIDERABLE_TAGS: element = EmbroideryElement(node) diff --git a/lib/extensions/__init__.py b/lib/extensions/__init__.py index b6e0d1d1..d0cfa911 100644 --- a/lib/extensions/__init__.py +++ b/lib/extensions/__init__.py @@ -6,6 +6,7 @@ from lib.extensions.troubleshoot import Troubleshoot from .apply_threadlist import ApplyThreadlist +from .auto_run import AutoRun from .auto_satin import AutoSatin from .break_apart import BreakApart from .cleanup import Cleanup @@ -61,6 +62,7 @@ __all__ = extensions = [StitchPlanPreview, ConvertToStroke, CutSatin, AutoSatin, + AutoRun, Lettering, LetteringGenerateJson, LetteringRemoveKerning, diff --git a/lib/extensions/auto_run.py b/lib/extensions/auto_run.py new file mode 100644 index 00000000..02997fd0 --- /dev/null +++ b/lib/extensions/auto_run.py @@ -0,0 +1,65 @@ +# Authors: see git history +# +# Copyright (c) 2010 Authors +# Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. + +import inkex + +from ..elements import Stroke +from ..i18n import _ +from ..stitches.auto_run import autorun +from .commands import CommandsExtension + + +class AutoRun(CommandsExtension): + COMMANDS = ["trim"] + + def __init__(self, *args, **kwargs): + CommandsExtension.__init__(self, *args, **kwargs) + + self.arg_parser.add_argument("-b", "--break_up", dest="break_up", type=inkex.Boolean, default=True) + self.arg_parser.add_argument("-p", "--preserve_order", dest="preserve_order", type=inkex.Boolean, default=False) + self.arg_parser.add_argument("-o", "--options", dest="options", type=str, default="") + self.arg_parser.add_argument("-i", "--info", dest="help", type=str, default="") + + def effect(self): + elements = self.check_selection() + if not elements: + return + + starting_point = self.get_starting_point() + ending_point = self.get_ending_point() + + break_up = self.options.break_up + + autorun(elements, self.options.preserve_order, break_up, starting_point, ending_point, self.options.trim) + + def get_starting_point(self): + return self.get_command_point("run_start") + + def get_ending_point(self): + return self.get_command_point("run_end") + + def get_command_point(self, command_type): + command = None + for stroke in self.elements: + command = stroke.get_command(command_type) + # return the first occurence directly + if command: + return command.target_point + + def check_selection(self): + if not self.get_elements(): + return + + if not self.svg.selection: + # L10N auto-route running stitch columns extension + inkex.errormsg(_("Please select one or more stroke elements.")) + return False + + elements = [element for element in self.elements if isinstance(element, Stroke)] + if len(elements) == 0: + inkex.errormsg(_("Please select at least one stroke element.")) + return False + + return elements diff --git a/lib/extensions/base.py b/lib/extensions/base.py index 75a07c5a..a5f1209a 100644 --- a/lib/extensions/base.py +++ b/lib/extensions/base.py @@ -17,7 +17,7 @@ from ..commands import is_command, layer_commands from ..elements import EmbroideryElement, nodes_to_elements from ..elements.clone import is_clone from ..i18n import _ -from ..patterns import is_pattern +from ..marker import has_marker from ..svg import generate_unique_id from ..svg.tags import (CONNECTOR_TYPE, EMBROIDERABLE_TAGS, INKSCAPE_GROUPMODE, NOT_EMBROIDERABLE_TAGS, SVG_CLIPPATH_TAG, SVG_DEFS_TAG, @@ -169,10 +169,10 @@ class InkstitchExtension(inkex.Effect): if selected: if node.tag == SVG_GROUP_TAG: pass - elif (node.tag in EMBROIDERABLE_TAGS or is_clone(node)) and not is_pattern(node): + elif (node.tag in EMBROIDERABLE_TAGS or is_clone(node)) and not has_marker(node): nodes.append(node) - # add images, text and patterns for the troubleshoot extension - elif troubleshoot and (node.tag in NOT_EMBROIDERABLE_TAGS or is_pattern(node)): + # add images, text and elements with a marker for the troubleshoot extension + elif troubleshoot and (node.tag in NOT_EMBROIDERABLE_TAGS or has_marker(node)): nodes.append(node) return nodes diff --git a/lib/extensions/reorder.py b/lib/extensions/reorder.py index 83ecfe26..956c0615 100644 --- a/lib/extensions/reorder.py +++ b/lib/extensions/reorder.py @@ -17,7 +17,7 @@ class Reorder(InkstitchExtension): objects = self.svg.selection if not objects: - errormsg(_("Please select at least to elements to reorder.")) + errormsg(_("Please select at least two elements to reorder.")) return for obj in objects: diff --git a/lib/marker.py b/lib/marker.py index 4f262abe..56a43c3b 100644 --- a/lib/marker.py +++ b/lib/marker.py @@ -7,10 +7,12 @@ from copy import deepcopy from os import path import inkex +from shapely import geometry as shgeo +from .svg.tags import EMBROIDERABLE_TAGS from .utils import cache, get_bundled_dir -MARKER = ['pattern'] +MARKER = ['pattern', 'guide-line'] def ensure_marker(svg, marker): @@ -33,5 +35,45 @@ def set_marker(node, position, marker): style = node.get('style') or '' style = style.split(";") style = [i for i in style if not i.startswith('marker-%s' % position)] - style.append('marker-%s:url(#inkstitch-pattern-marker)' % position) + style.append('marker-%s:url(#inkstitch-%s-marker)' % (position, marker)) node.set('style', ";".join(style)) + + +def get_marker_elements(node, marker, get_fills=True, get_strokes=True): + from .elements import EmbroideryElement + from .elements.stroke import Stroke + + fills = [] + strokes = [] + xpath = "./parent::svg:g/*[contains(@style, 'marker-start:url(#inkstitch-%s-marker)')]" % marker + markers = node.xpath(xpath, namespaces=inkex.NSS) + for marker in markers: + if marker.tag not in EMBROIDERABLE_TAGS: + continue + + element = EmbroideryElement(marker) + fill = element.get_style('fill') + stroke = element.get_style('stroke') + + if get_fills and fill is not None: + fill = Stroke(marker).paths + linear_rings = [shgeo.LinearRing(path) for path in fill] + for ring in linear_rings: + fills.append(shgeo.Polygon(ring)) + + if get_strokes and stroke is not None: + stroke = Stroke(marker).paths + line_strings = [shgeo.LineString(path) for path in stroke] + strokes.append(shgeo.MultiLineString(line_strings)) + + return {'fill': fills, 'stroke': strokes} + + +def has_marker(node, marker=list()): + if not marker: + marker = MARKER + for m in marker: + style = node.get('style') or '' + if "marker-start:url(#inkstitch-%s-marker)" % m in style: + return True + return False diff --git a/lib/patterns.py b/lib/patterns.py index da22f21b..aca6155c 100644 --- a/lib/patterns.py +++ b/lib/patterns.py @@ -3,25 +3,17 @@ # Copyright (c) 2010 Authors # Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. -import inkex from shapely import geometry as shgeo +from .marker import get_marker_elements from .stitch_plan import Stitch -from .svg.tags import EMBROIDERABLE_TAGS from .utils import Point -def is_pattern(node): - if node.tag not in EMBROIDERABLE_TAGS: - return False - style = node.get('style') or '' - return "marker-start:url(#inkstitch-pattern-marker)" in style - - def apply_patterns(patches, node): - patterns = _get_patterns(node) - _apply_fill_patterns(patterns['fill_patterns'], patches) - _apply_stroke_patterns(patterns['stroke_patterns'], patches) + patterns = get_marker_elements(node, "pattern") + _apply_fill_patterns(patterns['fill'], patches) + _apply_stroke_patterns(patterns['stroke'], patches) def _apply_stroke_patterns(patterns, patches): @@ -64,43 +56,13 @@ def _apply_fill_patterns(patterns, patches): patch.stitches = patch_points -def _get_patterns(node): - from .elements import EmbroideryElement - from .elements.stroke import Stroke - - fills = [] - strokes = [] - xpath = "./parent::svg:g/*[contains(@style, 'marker-start:url(#inkstitch-pattern-marker)')]" - patterns = node.xpath(xpath, namespaces=inkex.NSS) - for pattern in patterns: - if pattern.tag not in EMBROIDERABLE_TAGS: - continue - - element = EmbroideryElement(pattern) - fill = element.get_style('fill') - stroke = element.get_style('stroke') - - if fill is not None: - fill_pattern = Stroke(pattern).paths - linear_rings = [shgeo.LinearRing(path) for path in fill_pattern] - for ring in linear_rings: - fills.append(shgeo.Polygon(ring)) - - if stroke is not None: - stroke_pattern = Stroke(pattern).paths - line_strings = [shgeo.LineString(path) for path in stroke_pattern] - strokes.append(shgeo.MultiLineString(line_strings)) - - return {'fill_patterns': fills, 'stroke_patterns': strokes} - - def _get_pattern_points(first, second, pattern): points = [] intersection = shgeo.LineString([first, second]).intersection(pattern) if isinstance(intersection, shgeo.Point): points.append(Point(intersection.x, intersection.y)) if isinstance(intersection, shgeo.MultiPoint): - for point in intersection: + for point in intersection.geoms: points.append(Point(point.x, point.y)) # sort points after their distance to first points.sort(key=lambda point: point.distance(first)) diff --git a/lib/stitches/auto_run.py b/lib/stitches/auto_run.py new file mode 100644 index 00000000..847a1bcd --- /dev/null +++ b/lib/stitches/auto_run.py @@ -0,0 +1,284 @@ +# Authors: see git history +# +# Copyright (c) 2022 Authors +# Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. + +from collections import defaultdict + +import networkx as nx +from shapely.geometry import LineString, MultiLineString, MultiPoint, Point +from shapely.ops import nearest_points, substring, unary_union + +import inkex + +from ..commands import add_commands +from ..elements import Stroke +from ..i18n import _ +from ..svg import PIXELS_PER_MM, generate_unique_id +from ..svg.tags import INKSCAPE_LABEL, INKSTITCH_ATTRIBS +from .utils.autoroute import (add_elements_to_group, add_jumps, + create_new_group, find_path, + get_starting_and_ending_nodes, + preserve_original_groups, + remove_original_elements) + + +class LineSegments: + ''' + Takes elements and splits them into segments. + + Attributes: + _lines -- a list of LineStrings from the subpaths of the Stroke elements + _elements -- a list of Stroke elements for each corresponding line in _lines + _intersection_points -- a dictionary with intersection points {line_index: [intersection_points]} + segments -- (public) a list of segments and corresponding elements [[segment, element], ...] + ''' + + def __init__(self, elements): + self._lines = [] + self._elements = [] + self._intersection_points = defaultdict(list) + self.segments = [] + + self._process_elements(elements) + self._get_intersection_points() + self._get_segments() + + def _process_elements(self, elements): + for element in elements: + lines = element.as_multi_line_string().geoms + + for line in lines: + # split at self-intersections if necessary + unary_lines = unary_union(line) + if isinstance(unary_lines, MultiLineString): + for unary_line in unary_lines.geoms: + self._lines.append(unary_line) + self._elements.append(element) + else: + self._lines.append(line) + self._elements.append(element) + + def _get_intersection_points(self): + for i, line1 in enumerate(self._lines): + for j in range(i + 1, len(self._lines)): + line2 = self._lines[j] + distance = line1.distance(line2) + if distance > 50: + continue + if not distance == 0: + # add nearest points + near = nearest_points(line1, line2) + self._add_point(i, near[0]) + self._add_point(j, near[1]) + # add intersections + intersections = line1.intersection(line2) + if isinstance(intersections, Point): + self._add_point(i, intersections) + self._add_point(j, intersections) + elif isinstance(intersections, MultiPoint): + for point in intersections.geoms: + self._add_point(i, point) + self._add_point(j, point) + elif isinstance(intersections, LineString): + for point in intersections.coords: + self._add_point(i, Point(*point)) + self._add_point(j, Point(*point)) + + def _add_point(self, element, point): + self._intersection_points[element].append(point) + + def _get_segments(self): + ''' + Splits elements into segments at intersection and "almost intersecions". + The split method would make this very easy (it can split a MultiString with + MultiPoints) but sadly it fails too often, while snap moves the points away + from where we want them. So we need to calculate the distance along the line + and finally split it into segments with shapelys substring method. + ''' + self.segments = [] + for i, line in enumerate(self._lines): + length = line.length + points = self._intersection_points[i] + + distances = [0, length] + for point in points: + distances.append(line.project(point)) + distances = sorted(set(distances)) + + for j in range(len(distances) - 1): + start = distances[j] + end = distances[j + 1] + + if end - start > 0.1: + seg = substring(line, start, end) + self.segments.append([seg, self._elements[i]]) + + +def autorun(elements, preserve_order=False, break_up=None, starting_point=None, ending_point=None, trim=False): + graph = build_graph(elements, preserve_order, break_up) + graph = add_jumps(graph, elements, preserve_order) + + starting_point, ending_point = get_starting_and_ending_nodes( + graph, elements, preserve_order, starting_point, ending_point) + + path = find_path(graph, starting_point, ending_point) + path = add_path_attribs(path) + + new_elements, trims, original_parents = path_to_elements(graph, path, trim) + + if preserve_order: + preserve_original_groups(new_elements, original_parents) + else: + parent = elements[0].node.getparent() + insert_index = parent.index(elements[0].node) + group = create_new_group(parent, insert_index, _("Auto-Run")) + add_elements_to_group(new_elements, group) + + if trim: + add_trims(new_elements, trims) + + remove_original_elements(elements) + + +def build_graph(elements, preserve_order, break_up): + if preserve_order: + graph = nx.DiGraph() + else: + graph = nx.Graph() + + if not break_up: + segments = [] + for element in elements: + line_strings = [[line, element] for line in element.as_multi_line_string().geoms] + segments.extend(line_strings) + else: + segments = LineSegments(elements).segments + + for segment, element in segments: + for c1, c2 in zip(segment.coords[:-1], segment.coords[1:]): + start = Point(*c1) + end = Point(*c2) + + graph.add_node(str(start), point=start) + graph.add_node(str(end), point=end) + graph.add_edge(str(start), str(end), element=element) + + if preserve_order: + # The graph is a directed graph, but we want to allow travel in + # any direction, so we add the edge in the opposite direction too. + graph.add_edge(str(end), str(start), element=element) + + return graph + + +def add_path_attribs(path): + # find_path() will have duplicated some of the edges in the graph. We don't + # want to sew the same running stitch twice. If a running stitch section appears + # twice in the path, we'll sew the first occurrence as a simple running stitch without + # the original running stitch repetitions and bean stitch settings. + seen = set() + for i, point in reversed(list(enumerate(path))): + if point in seen: + path[i] = (*point, "underpath") + else: + path[i] = (*point, "autorun") + seen.add(point) + seen.add((point[1], point[0])) + return path + + +def path_to_elements(graph, path, trim): # noqa: C901 + element_list = [] + original_parents = [] + trims = [] + + d = "" + position = 0 + path_direction = "autorun" + just_trimmed = False + el = None + for start, end, direction in path: + element = graph[start][end].get('element') + start_coord = graph.nodes[start]['point'] + end_coord = graph.nodes[end]['point'] + if element: + el = element + + if just_trimmed: + if direction == "underpath": + # no sense in doing underpath after we trim + continue + else: + just_trimmed = False + + # create a new element if direction (purpose) changes + if direction != path_direction: + if d: + element_list.append(create_element(d, position, path_direction, el)) + original_parents.append(el.node.getparent()) + d = "" + position += 1 + path_direction = direction + + if d == "": + d = "M %s %s, %s %s" % (start_coord.x, start_coord.y, end_coord.x, end_coord.y) + else: + d += ", %s %s" % (end_coord.x, end_coord.y) + elif el and d: + # this is a jump, so complete the element whose path we've been building + element_list.append(create_element(d, position, path_direction, el)) + original_parents.append(el.node.getparent()) + d = "" + + if trim and start_coord.distance(end_coord) > 0.75 * PIXELS_PER_MM: + trims.append(position) + just_trimmed = True + + position += 1 + + if d: + element_list.append(create_element(d, position, path_direction, el)) + original_parents.append(el.node.getparent()) + + return element_list, trims, original_parents + + +def create_element(path, position, direction, element): + if not path: + return + + style = inkex.Style(element.node.get("style")) + style = style + inkex.Style("stroke-dasharray:0.5,0.5;fill:none;") + el_id = "%s_%s_" % (direction, position) + + index = position + 1 + if direction == "autorun": + label = _("AutoRun %d") % index + else: + label = _("AutoRun Underpath %d") % index + + stitch_length = element.node.get(INKSTITCH_ATTRIBS['running_stitch_length_mm'], '') + bean = element.node.get(INKSTITCH_ATTRIBS['bean_stitch_repeats'], 0) + repeats = int(element.node.get(INKSTITCH_ATTRIBS['repeats'], 1)) + if repeats % 2 == 0: + repeats -= 1 + + node = inkex.PathElement() + node.set("id", generate_unique_id(element.node, el_id)) + node.set(INKSCAPE_LABEL, label) + node.set("d", path) + node.set("style", str(style)) + if stitch_length: + node.set(INKSTITCH_ATTRIBS['running_stitch_length_mm'], stitch_length) + if direction == "autorun": + node.set(INKSTITCH_ATTRIBS['repeats'], str(repeats)) + if bean: + node.set(INKSTITCH_ATTRIBS['bean_stitch_repeats'], bean) + + return Stroke(node) + + +def add_trims(elements, trim_indices): + for i in trim_indices: + add_commands(elements[i], ["trim"]) diff --git a/lib/stitches/auto_satin.py b/lib/stitches/auto_satin.py index 2b7f0906..ba5c8698 100644 --- a/lib/stitches/auto_satin.py +++ b/lib/stitches/auto_satin.py @@ -6,19 +6,24 @@ import math from itertools import chain -import inkex import networkx as nx from shapely import geometry as shgeo from shapely.geometry import Point as ShapelyPoint +import inkex + from ..commands import add_commands from ..elements import SatinColumn, Stroke from ..i18n import _ -from ..svg import (PIXELS_PER_MM, generate_unique_id, get_correction_transform, - line_strings_to_csp) -from ..svg.tags import (INKSCAPE_LABEL, INKSTITCH_ATTRIBS) +from ..svg import PIXELS_PER_MM, generate_unique_id, line_strings_to_csp +from ..svg.tags import INKSCAPE_LABEL, INKSTITCH_ATTRIBS from ..utils import Point as InkstitchPoint from ..utils import cache, cut +from .utils.autoroute import (add_elements_to_group, add_jumps, + create_new_group, find_path, + get_starting_and_ending_nodes, + preserve_original_groups, + remove_original_elements) class SatinSegment(object): @@ -177,7 +182,7 @@ class SatinSegment(object): class JumpStitch(object): """A jump stitch between two points.""" - def __init__(self, start, end): + def __init__(self, start, end, source_element, destination_element): """Initialize a JumpStitch. Arguments: @@ -186,6 +191,8 @@ class JumpStitch(object): self.start = start self.end = end + self.source_element = source_element + self.destination_element = destination_element def is_sequential(self, other): # Don't bother joining jump stitches. @@ -196,6 +203,15 @@ class JumpStitch(object): def length(self): return self.start.distance(self.end) + def as_line_string(self): + return shgeo.LineString((self.start, self.end)) + + def should_trim(self): + actual_jump = self.as_line_string().difference(self.source_element.shape) + actual_jump = actual_jump.difference(self.destination_element.shape) + + return actual_jump.length > PIXELS_PER_MM + class RunningStitch(object): """Running stitch along a path.""" @@ -326,7 +342,7 @@ def auto_satin(elements, preserve_order=False, starting_point=None, ending_point if preserve_order: preserve_original_groups(new_elements, original_parents) else: - group = create_new_group(parent, index) + group = create_new_group(parent, index, _("Auto-Route")) add_elements_to_group(new_elements, group) name_elements(new_elements, preserve_order) @@ -358,8 +374,8 @@ def build_graph(elements, preserve_order=False): for segment in segments: # This is necessary because shapely points aren't hashable and thus # can't be used as nodes directly. - graph.add_node(str(segment.start_point), point=segment.start_point) - graph.add_node(str(segment.end_point), point=segment.end_point) + graph.add_node(str(segment.start_point), point=segment.start_point, element=element) + graph.add_node(str(segment.end_point), point=segment.end_point, element=element) graph.add_edge(str(segment.start_point), str( segment.end_point), segment=segment, element=element) @@ -373,168 +389,6 @@ def build_graph(elements, preserve_order=False): return graph -def get_starting_and_ending_nodes(graph, elements, preserve_order, starting_point, ending_point): - """Find or choose the starting and ending graph nodes. - - If points were passed, we'll find the nearest graph nodes. Since we split - every satin up into 1mm-chunks, we'll be at most 1mm away which is good - enough. - - If we weren't given starting and ending points, we'll pic kthe far left and - right nodes. - - returns: - (starting graph node, ending graph node) - """ - - nodes = [] - - nodes.append(find_node(graph, starting_point, - min, preserve_order, elements[0])) - nodes.append(find_node(graph, ending_point, - max, preserve_order, elements[-1])) - - return nodes - - -def find_node(graph, point, extreme_function, constrain_to_satin=False, satin=None): - if constrain_to_satin: - nodes = get_nodes_on_element(graph, satin) - else: - nodes = graph.nodes() - - if point is None: - return extreme_function(nodes, key=lambda node: graph.nodes[node]['point'].x) - else: - point = shgeo.Point(*point) - return min(nodes, key=lambda node: graph.nodes[node]['point'].distance(point)) - - -def get_nodes_on_element(graph, element): - nodes = set() - - for start_node, end_node, element_for_edge in graph.edges(data='element'): - if element_for_edge is element: - nodes.add(start_node) - nodes.add(end_node) - - return nodes - - -def add_jumps(graph, elements, preserve_order): - """Add jump stitches between elements as necessary. - - Jump stitches are added to ensure that all elements can be reached. Only the - minimal number and length of jumps necessary will be added. - """ - - if preserve_order: - # For each sequential pair of elements, find the shortest possible jump - # stitch between them and add it. The directions of these new edges - # will enforce stitching the satins in order. - - for element1, element2 in zip(elements[:-1], elements[1:]): - potential_edges = [] - - nodes1 = get_nodes_on_element(graph, element1) - nodes2 = get_nodes_on_element(graph, element2) - - for node1 in nodes1: - for node2 in nodes2: - point1 = graph.nodes[node1]['point'] - point2 = graph.nodes[node2]['point'] - potential_edges.append((point1, point2)) - - if potential_edges: - edge = min(potential_edges, key=lambda p1_p2: p1_p2[0].distance(p1_p2[1])) - graph.add_edge(str(edge[0]), str(edge[1]), jump=True) - else: - # networkx makes this super-easy! k_edge_agumentation tells us what edges - # we need to add to ensure that the graph is fully connected. We give it a - # set of possible edges that it can consider adding (avail). Each edge has - # a weight, which we'll set as the length of the jump stitch. The - # algorithm will minimize the total length of jump stitches added. - for jump in nx.k_edge_augmentation(graph, 1, avail=list(possible_jumps(graph))): - graph.add_edge(*jump, jump=True) - - -def possible_jumps(graph): - """All possible jump stitches in the graph with their lengths. - - Returns: a generator of tuples: (node1, node2, length) - """ - - # We'll take the easy approach and list all edges that aren't already in - # the graph. networkx's algorithm is pretty efficient at ignoring - # pointless options like jumping between two points on the same satin. - - for start, end in nx.complement(graph).edges(): - start_point = graph.nodes[start]['point'] - end_point = graph.nodes[end]['point'] - yield (start, end, start_point.distance(end_point)) - - -def find_path(graph, starting_node, ending_node): - """Find a path through the graph that sews every satin.""" - - # This is done in two steps. First, we find the shortest path from the - # start to the end. We remove it from the graph, and proceed to step 2. - # - # Then, we traverse the path node by node. At each node, we follow any - # branchings with a depth-first search. We travel down each branch of - # the tree, inserting each seen branch into the tree. When the DFS - # hits a dead-end, as it back-tracks, we also add the seen edges _again_. - # Repeat until there are no more edges left in the graph. - # - # Visiting the edges again on the way back allows us to set up - # "underpathing". As we stitch down each branch, we'll do running stitch. - # Then when we come back up, we'll do satin stitch, covering the previous - # running stitch. - path = nx.shortest_path(graph, starting_node, ending_node) - - # Copy the graph so that we can remove the edges as we visit them. - # This also converts the directed graph into an undirected graph in the - # case that "preserve_order" is set. This way we avoid going back and - # forth on each satin twice due to the satin edges being in the graph - # twice (forward and reverse). - graph = nx.Graph(graph) - graph.remove_edges_from(list(zip(path[:-1], path[1:]))) - - final_path = [] - prev = None - for node in path: - if prev is not None: - final_path.append((prev, node)) - prev = node - - for n1, n2, edge_type in list(nx.dfs_labeled_edges(graph, node)): - if n1 == n2: - # dfs_labeled_edges gives us (start, start, "forward") for - # the starting node for some reason - continue - - if edge_type == "forward": - final_path.append((n1, n2)) - graph.remove_edge(n1, n2) - elif edge_type == "reverse": - final_path.append((n2, n1)) - elif edge_type == "nontree": - # a "nontree" happens when there exists an edge from n1 to n2 - # but n2 has already been visited. It's a dead-end that runs - # into part of the graph that we've already traversed. We - # do still need to make sure that satin is sewn, so we travel - # down and back on this edge. - # - # It's possible for a given "nontree" edge to be listed more - # than once so we'll deduplicate. - if (n1, n2) in graph.edges: - final_path.append((n1, n2)) - final_path.append((n2, n1)) - graph.remove_edge(n1, n2) - - return final_path - - def reversed_path(path): """Generator for a version of the path travelling in the opposite direction. @@ -563,7 +417,10 @@ def path_to_operations(graph, path): segment = segment.reversed() operations.append(segment) else: - operations.append(JumpStitch(graph.nodes[start]['point'], graph.nodes[end]['point'])) + operations.append(JumpStitch(graph.nodes[start]['point'], + graph.nodes[end]['point'], + graph.nodes[start]['element'], + graph.nodes[end]['element'])) # find_path() will have duplicated some of the edges in the graph. We don't # want to sew the same satin twice. If a satin section appears twice in the @@ -616,59 +473,12 @@ def operations_to_elements_and_trims(operations, preserve_order): elements.append(operation.to_element()) original_parent_nodes.append(operation.original_node.getparent()) elif isinstance(operation, (JumpStitch)): - if elements and operation.length > 0.75 * PIXELS_PER_MM: + if elements and operation.should_trim(): trims.append(len(elements) - 1) return elements, list(set(trims)), original_parent_nodes -def remove_original_elements(elements): - for element in elements: - for command in element.commands: - command_group = command.use.getparent() - if command_group is not None and command_group.get('id').startswith('command_group'): - remove_from_parent(command_group) - else: - remove_from_parent(command.connector) - remove_from_parent(command.use) - remove_from_parent(element.node) - - -def remove_from_parent(node): - if node.getparent() is not None: - node.getparent().remove(node) - - -def preserve_original_groups(elements, original_parent_nodes): - """Ensure that all elements are contained in the original SVG group elements. - - When preserve_order is True, no SatinColumn or Stroke elements will be - reordered in the XML tree. This makes it possible to preserve original SVG - group membership. We'll ensure that each newly-created Element is added - to the group that contained the original SatinColumn that spawned it. - """ - - for element, parent in zip(elements, original_parent_nodes): - if parent is not None: - parent.append(element.node) - element.node.set('transform', get_correction_transform(parent, child=True)) - - -def create_new_group(parent, insert_index): - group = inkex.Group(attrib={ - INKSCAPE_LABEL: _("Auto-Satin"), - "transform": get_correction_transform(parent, child=True) - }) - parent.insert(insert_index, group) - - return group - - -def add_elements_to_group(elements, group): - for element in elements: - group.append(element.node) - - def name_elements(new_elements, preserve_order): """Give the newly-created SVG objects useful names. diff --git a/lib/stitches/utils/autoroute.py b/lib/stitches/utils/autoroute.py new file mode 100644 index 00000000..5acb1400 --- /dev/null +++ b/lib/stitches/utils/autoroute.py @@ -0,0 +1,221 @@ +# Authors: see git history +# +# Copyright (c) 2010 Authors +# Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. + +from itertools import combinations + +import networkx as nx +from shapely.geometry import Point, MultiPoint +from shapely.ops import nearest_points + +import inkex + +from ...svg import get_correction_transform +from ...svg.tags import INKSCAPE_LABEL + + +def find_path(graph, starting_node, ending_node): + """Find a path through the graph that sews every edge.""" + + # This is done in two steps. First, we find the shortest path from the + # start to the end. We remove it from the graph, and proceed to step 2. + # + # Then, we traverse the path node by node. At each node, we follow any + # branchings with a depth-first search. We travel down each branch of + # the tree, inserting each seen branch into the tree. When the DFS + # hits a dead-end, as it back-tracks, we also add the seen edges _again_. + # Repeat until there are no more edges left in the graph. + # + # Visiting the edges again on the way back allows us to set up + # "underpathing". + path = nx.shortest_path(graph, starting_node, ending_node) + + # Copy the graph so that we can remove the edges as we visit them. + # This also converts the directed graph into an undirected graph in the + # case that "preserve_order" is set. + graph = nx.Graph(graph) + graph.remove_edges_from(list(zip(path[:-1], path[1:]))) + + final_path = [] + prev = None + for node in path: + if prev is not None: + final_path.append((prev, node)) + prev = node + + for n1, n2, edge_type in list(nx.dfs_labeled_edges(graph, node)): + if n1 == n2: + # dfs_labeled_edges gives us (start, start, "forward") for + # the starting node for some reason + continue + + if edge_type == "forward": + final_path.append((n1, n2)) + graph.remove_edge(n1, n2) + elif edge_type == "reverse": + final_path.append((n2, n1)) + elif edge_type == "nontree": + # a "nontree" happens when there exists an edge from n1 to n2 + # but n2 has already been visited. It's a dead-end that runs + # into part of the graph that we've already traversed. We + # do still need to make sure that edge is sewn, so we travel + # down and back on this edge. + # + # It's possible for a given "nontree" edge to be listed more + # than once so we'll deduplicate. + if (n1, n2) in graph.edges: + final_path.append((n1, n2)) + final_path.append((n2, n1)) + graph.remove_edge(n1, n2) + + return final_path + + +def add_jumps(graph, elements, preserve_order): + """Add jump stitches between elements as necessary. + + Jump stitches are added to ensure that all elements can be reached. Only the + minimal number and length of jumps necessary will be added. + """ + + if preserve_order: + # For each sequential pair of elements, find the shortest possible jump + # stitch between them and add it. The directions of these new edges + # will enforce stitching the elements in order. + + for element1, element2 in zip(elements[:-1], elements[1:]): + potential_edges = [] + + nodes1 = get_nodes_on_element(graph, element1) + nodes2 = get_nodes_on_element(graph, element2) + + for node1 in nodes1: + for node2 in nodes2: + point1 = graph.nodes[node1]['point'] + point2 = graph.nodes[node2]['point'] + potential_edges.append((point1, point2)) + + if potential_edges: + edge = min(potential_edges, key=lambda p1_p2: p1_p2[0].distance(p1_p2[1])) + graph.add_edge(str(edge[0]), str(edge[1]), jump=True) + else: + # networkx makes this super-easy! k_edge_agumentation tells us what edges + # we need to add to ensure that the graph is fully connected. We give it a + # set of possible edges that it can consider adding (avail). Each edge has + # a weight, which we'll set as the length of the jump stitch. The + # algorithm will minimize the total length of jump stitches added. + for jump in nx.k_edge_augmentation(graph, 1, avail=list(possible_jumps(graph))): + graph.add_edge(*jump, jump=True) + + return graph + + +def possible_jumps(graph): + """All possible jump stitches in the graph with their lengths. + + Returns: a generator of tuples: (node1, node2, length) + """ + + for component1, component2 in combinations(nx.connected_components(graph), 2): + points1 = MultiPoint([graph.nodes[node]['point'] for node in component1]) + points2 = MultiPoint([graph.nodes[node]['point'] for node in component2]) + + start_point, end_point = nearest_points(points1, points2) + + yield (str(start_point), str(end_point), start_point.distance(end_point)) + + +def get_starting_and_ending_nodes(graph, elements, preserve_order, starting_point, ending_point): + """Find or choose the starting and ending graph nodes. + + If points were passed, we'll find the nearest graph nodes. Since we split + every path up into 1mm-chunks, we'll be at most 1mm away which is good + enough. + + If we weren't given starting and ending points, we'll pic kthe far left and + right nodes. + + returns: + (starting graph node, ending graph node) + """ + + nodes = [] + + nodes.append(find_node(graph, starting_point, + min, preserve_order, elements[0])) + nodes.append(find_node(graph, ending_point, + max, preserve_order, elements[-1])) + + return nodes + + +def find_node(graph, point, extreme_function, constrain_to_satin=False, satin=None): + if constrain_to_satin: + nodes = get_nodes_on_element(graph, satin) + else: + nodes = graph.nodes() + + if point is None: + return extreme_function(nodes, key=lambda node: graph.nodes[node]['point'].x) + else: + point = Point(*point) + return min(nodes, key=lambda node: graph.nodes[node]['point'].distance(point)) + + +def get_nodes_on_element(graph, element): + nodes = set() + + for start_node, end_node, element_for_edge in graph.edges(data='element'): + if element_for_edge is element: + nodes.add(start_node) + nodes.add(end_node) + + return nodes + + +def remove_original_elements(elements): + for element in elements: + for command in element.commands: + command_group = command.use.getparent() + if command_group is not None and command_group.get('id').startswith('command_group'): + remove_from_parent(command_group) + else: + remove_from_parent(command.connector) + remove_from_parent(command.use) + remove_from_parent(element.node) + + +def remove_from_parent(node): + if node.getparent() is not None: + node.getparent().remove(node) + + +def create_new_group(parent, insert_index, label): + group = inkex.Group(attrib={ + INKSCAPE_LABEL: label, + "transform": get_correction_transform(parent, child=True) + }) + parent.insert(insert_index, group) + + return group + + +def preserve_original_groups(elements, original_parent_nodes): + """Ensure that all elements are contained in the original SVG group elements. + + When preserve_order is True, no elements will be reordered in the XML tree. + This makes it possible to preserve original SVG group membership. We'll + ensure that each newly-created element is added to the group that contained + the original element that spawned it. + """ + + for element, parent in zip(elements, original_parent_nodes): + if parent is not None: + parent.append(element.node) + element.node.set('transform', get_correction_transform(parent, child=True)) + + +def add_elements_to_group(elements, group): + for element in elements: + group.append(element.node) |