Auto route for running stitch (#1638)

* add auto route for running stitch
* introduce free motion commands

Co-authored-by: Lex Neva <github.com@lexneva.name>

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)