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>

1 files changed, 29 insertions, 219 deletions

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.