From 0b9f95ed88f6d4eb47c774c69e4fa9a03546b4b5 Mon Sep 17 00:00:00 2001
From: Kaalleen <36401965+kaalleen@users.noreply.github.com>
Date: Wed, 6 Mar 2019 17:49:43 +0100
Subject: keep color when convert to satin column

---
 lib/extensions/convert_to_satin.py | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

(limited to 'lib')

diff --git a/lib/extensions/convert_to_satin.py b/lib/extensions/convert_to_satin.py
index 2b586e36..1227b207 100644
--- a/lib/extensions/convert_to_satin.py
+++ b/lib/extensions/convert_to_satin.py
@@ -40,6 +40,7 @@ class ConvertToSatin(InkstitchExtension):
             index = parent.index(element.node)
             correction_transform = get_correction_transform(element.node)
             style_args = self.join_style_args(element)
+            path_style = self.path_style(element)
 
             for path in element.paths:
                 path = self.remove_duplicate_points(path)
@@ -62,7 +63,7 @@ class ConvertToSatin(InkstitchExtension):
 
                     return
 
-                parent.insert(index, self.satin_to_svg_node(rails, rungs, correction_transform))
+                parent.insert(index, self.satin_to_svg_node(rails, rungs, correction_transform, path_style))
 
             parent.remove(element.node)
 
@@ -273,7 +274,11 @@ class ConvertToSatin(InkstitchExtension):
 
         return rungs
 
-    def satin_to_svg_node(self, rails, rungs, correction_transform):
+    def path_style(self, element):
+        color = element.get_style('stroke', '#000000')
+        return "stroke:%s;stroke-width:1px;fill:none" % (color)
+
+    def satin_to_svg_node(self, rails, rungs, correction_transform, path_style):
         d = ""
         for path in chain(rails, rungs):
             d += "M"
@@ -284,7 +289,7 @@ class ConvertToSatin(InkstitchExtension):
         return inkex.etree.Element(SVG_PATH_TAG,
                                    {
                                        "id": self.uniqueId("path"),
-                                       "style": "stroke:#000000;stroke-width:1px;fill:none",
+                                       "style": path_style,
                                        "transform": correction_transform,
                                        "d": d,
                                        "embroider_satin_column": "true",
-- 
cgit v1.2.3


From 110dca3c9a6861fda9eac555157396d532ef9c3a Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sun, 10 Mar 2019 18:24:10 -0400
Subject: make debugging auto-fill easier

---
 lib/elements/auto_fill.py | 5 +++++
 1 file changed, 5 insertions(+)

(limited to 'lib')

diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index b8d8d15f..1308b9e3 100644
--- a/lib/elements/auto_fill.py
+++ b/lib/elements/auto_fill.py
@@ -1,4 +1,5 @@
 import math
+import sys
 import traceback
 
 from shapely import geometry as shgeo
@@ -185,6 +186,10 @@ class AutoFill(Fill):
             # for one of our exceptions, just print the message
             self.fatal(_("Unable to autofill: ") + str(exc))
         except Exception, exc:
+            if hasattr(sys, 'gettrace') and sys.gettrace():
+                # if we're debugging, let the exception bubble up
+                raise
+
             # for an uncaught exception, give a little more info so that they can create a bug report
             message = ""
             message += _("Error during autofill!  This means that there is a problem with Ink/Stitch.")
-- 
cgit v1.2.3


From 0a06fa740cbaa64f0c7d0541a88c6db59d6e51d8 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 12 Mar 2019 22:32:56 -0400
Subject: shapely.geometry -> shgeo for brevity

---
 lib/stitches/auto_fill.py | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 0f07b795..bf660a93 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -3,7 +3,7 @@ from itertools import groupby, izip
 import sys
 
 import networkx
-import shapely
+from shapely import geometry as shgeo
 
 from ..exceptions import InkstitchException
 from ..i18n import _
@@ -78,7 +78,7 @@ def which_outline(shape, coords):
     # I'd use an intersection check, but floating point errors make it
     # fail sometimes.
 
-    point = shapely.geometry.Point(*coords)
+    point = shgeo.Point(*coords)
     outlines = enumerate(list(shape.boundary))
     closest = min(outlines, key=lambda index_outline: index_outline[1].distance(point))
 
@@ -92,7 +92,7 @@ def project(shape, coords, outline_index):
     """
 
     outline = list(shape.boundary)[outline_index]
-    return outline.project(shapely.geometry.Point(*coords))
+    return outline.project(shgeo.Point(*coords))
 
 
 def build_graph(shape, segments, angle, row_spacing, max_stitch_length):
@@ -320,9 +320,9 @@ def insert_loop(path, loop):
 
 
 def nearest_node_on_outline(graph, point, outline_index=0):
-    point = shapely.geometry.Point(*point)
+    point = shgeo.Point(*point)
     outline_nodes = [node for node, data in graph.nodes(data=True) if data['index'] == outline_index]
-    nearest = min(outline_nodes, key=lambda node: shapely.geometry.Point(*node).distance(point))
+    nearest = min(outline_nodes, key=lambda node: shgeo.Point(*node).distance(point))
 
     return nearest
 
@@ -483,9 +483,9 @@ def connect_points(shape, start, end, running_stitch_length, row_spacing):
     # First, figure out the start and end position along the outline.  The
     # projection gives us the distance travelled down the outline to get to
     # that point.
-    start = shapely.geometry.Point(start)
+    start = shgeo.Point(start)
     start_projection = outline.project(start)
-    end = shapely.geometry.Point(end)
+    end = shgeo.Point(end)
     end_projection = outline.project(end)
 
     # If the points are pretty close, just jump there.  There's a slight
@@ -519,7 +519,7 @@ def connect_points(shape, start, end, running_stitch_length, row_spacing):
         # Make a new outline, starting from the starting point.  This is
         # like rotating the clock so that now our starting point is
         # at 12 o'clock.
-        outline = shapely.geometry.LineString(list(after.coords) + list(before.coords))
+        outline = shgeo.LineString(list(after.coords) + list(before.coords))
 
     # Now figure out where our ending point is on the newly-rotated clock.
     end_projection = outline.project(end)
-- 
cgit v1.2.3


From 8ffa9ca90e28a3dd0cb47bf0379735d915eb72bb Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 12 Mar 2019 22:33:44 -0400
Subject: faster, simpler auto-fill algorithm

---
 lib/stitches/auto_fill.py | 74 ++++++++++++++++++++++++++++-------------------
 1 file changed, 44 insertions(+), 30 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index bf660a93..3b2b56dc 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -392,48 +392,62 @@ def find_stitch_path(graph, segments, starting_point=None, ending_point=None):
     """
 
     graph = graph.copy()
-    num_segments = len(segments)
-    segments_visited = 0
-    nodes_visited = deque()
 
     if starting_point is None:
         starting_point = segments[0][0]
 
-    path = find_initial_path(graph, starting_point, ending_point)
+    starting_node = nearest_node_on_outline(graph, starting_point)
 
-    # Our graph is Eulerian: every node has an even degree.  An Eulerian graph
-    # must have an Eulerian Circuit which visits every edge and ends where it
-    # starts.
-    #
-    # However, we're starting with a path and _not_ removing the edges of that
-    # path from the graph.  By doing this, we're implicitly adding those edges
-    # to the graph, after which the starting and ending point (and only those
-    # two) will now have odd degree.  A graph that's Eulerian except for two
-    # nodes must have an Eulerian Path that starts and ends at those two nodes.
-    # That's how we force the starting and ending point.
+    if ending_point is None:
+        ending_node = starting_node
+    else:
+        ending_node = nearest_node_on_outline(graph, ending_point)
 
-    nodes_visited.append(path[0][0])
+    # The algorithm below is adapted from networkx.eulerian_circuit().
+    path = []
+    vertex_stack = [(ending_node, None)]
+    last_vertex = None
+    last_key = None
+
+    while vertex_stack:
+        current_vertex, current_key = vertex_stack[-1]
+        if graph.degree(current_vertex) == 0:
+            if last_vertex is not None:
+                path.append(PathEdge((last_vertex, current_vertex), last_key))
+            last_vertex, last_key = current_vertex, current_key
+            vertex_stack.pop()
+        else:
+            ignore, next_vertex, next_key = pick_edge(graph.edges(current_vertex, keys=True))
+            vertex_stack.append((next_vertex, next_key))
+            graph.remove_edge(current_vertex, next_vertex, next_key)
 
-    while segments_visited < num_segments:
-        loop = find_loop(graph, nodes_visited)
+    # The above has the excellent property that it tends to do travel stitches
+    # before the rows in that area, so we can hide the travel stitches under
+    # the rows.
+    #
+    # The only downside is that the path is a loop starting and ending at the
+    # ending node.  We need to start at the starting node, so we'll just
+    # start off by traveling to the ending node.
+    #
+    # Note, it's quite possible that part of this PathEdge will be eliminated by
+    # collapse_sequential_outline_edges().
 
-        if not loop:
-            print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.")
-            break
+    if starting_node is not ending_node:
+        path.insert(0, PathEdge((starting_node, ending_node), key="initial"))
+
+    return path
 
-        segments_visited += sum(1 for edge in loop if edge.is_segment())
-        nodes_visited.extend(edge[0] for edge in loop)
-        graph.remove_edges_from(loop)
 
-        insert_loop(path, loop)
+def pick_edge(edges):
+    """Pick the next edge to traverse in the pathfinding algorithm"""
 
-    if ending_point is None:
-        # If they didn't specify an ending point, then the end of the path travels
-        # around the outline back to the start (see find_initial_path()). This
-        # isn't necessary, so remove it.
-        trim_end(path)
+    # Prefer a segment if one is available.  This has the effect of
+    # creating long sections of back-and-forth row traversal.
+    for source, node, key in edges:
+        if key == 'segment':
+            return source, node, key
 
-    return path
+    return list(edges)[0]
 
 
 def collapse_sequential_outline_edges(graph, path):
-- 
cgit v1.2.3


From 8323bd5f0ffb708a116bc826792ee571cbc930f0 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 12 Mar 2019 22:53:40 -0400
Subject: remove unused code

---
 lib/stitches/auto_fill.py | 220 ++--------------------------------------------
 1 file changed, 9 insertions(+), 211 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 3b2b56dc..7386e08f 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -12,10 +12,6 @@ from .fill import intersect_region_with_grating, row_num, stitch_row
 from .running_stitch import running_stitch
 
 
-class MaxQueueLengthExceeded(InkstitchException):
-    pass
-
-
 class InvalidPath(InkstitchException):
     pass
 
@@ -55,17 +51,14 @@ def auto_fill(shape,
               skip_last,
               starting_point,
               ending_point=None):
-    stitches = []
 
     rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing)
     segments = [segment for row in rows_of_segments for segment in row]
-
-    graph = build_graph(shape, segments, angle, row_spacing, max_stitch_length)
+    graph = build_graph(shape, segments)
+    check_graph(graph, shape, max_stitch_length)
     path = find_stitch_path(graph, segments, starting_point, ending_point)
 
-    stitches.extend(path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last))
-
-    return stitches
+    return path_to_stitches(path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
 
 
 def which_outline(shape, coords):
@@ -95,7 +88,7 @@ def project(shape, coords, outline_index):
     return outline.project(shgeo.Point(*coords))
 
 
-def build_graph(shape, segments, angle, row_spacing, max_stitch_length):
+def build_graph(shape, segments):
     """build a graph representation of the grating segments
 
     This function builds a specialized graph (as in graph theory) that will
@@ -150,36 +143,14 @@ def build_graph(shape, segments, angle, row_spacing, max_stitch_length):
     for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']):
         nodes = [node for node, data in nodes]
 
-        # heuristic: change the order I visit the nodes in the outline if necessary.
-        # If the start and endpoints are in the same row, I can't tell which row
-        # I should treat it as being in.
-        for i in xrange(len(nodes)):
-            row0 = row_num(InkstitchPoint(*nodes[0]), angle, row_spacing)
-            row1 = row_num(InkstitchPoint(*nodes[1]), angle, row_spacing)
-
-            if row0 == row1:
-                nodes = nodes[1:] + [nodes[0]]
-            else:
-                break
-
-        # heuristic: it's useful to try to keep the duplicated edges in the same rows.
-        # this prevents the BFS from having to search a ton of edges.
-        min_row_num = min(row0, row1)
-        if min_row_num % 2 == 0:
-            edge_set = 0
-        else:
-            edge_set = 1
-
         # add an edge between each successive node
         for i, (node1, node2) in enumerate(zip(nodes, nodes[1:] + [nodes[0]])):
             graph.add_edge(node1, node2, key="outline")
 
-            # duplicate every other edge around this outline
-            if i % 2 == edge_set:
+            # duplicate every other edge
+            if i % 2 == 0:
                 graph.add_edge(node1, node2, key="extra")
 
-    check_graph(graph, shape, max_stitch_length)
-
     return graph
 
 
@@ -193,132 +164,6 @@ def check_graph(graph, shape, max_stitch_length):
                                 "This most often happens because your shape is made up of multiple sections that aren't connected."))
 
 
-def node_list_to_edge_list(node_list):
-    return zip(node_list[:-1], node_list[1:])
-
-
-def bfs_for_loop(graph, starting_node, max_queue_length=2000):
-    to_search = deque()
-    to_search.append((None, set()))
-
-    while to_search:
-        if len(to_search) > max_queue_length:
-            raise MaxQueueLengthExceeded()
-
-        path, visited_edges = to_search.pop()
-
-        if path is None:
-            # This is the very first time through the loop, so initialize.
-            path = []
-            ending_node = starting_node
-        else:
-            ending_node = path[-1][-1]
-
-        # get a list of neighbors paired with the key of the edge I can follow to get there
-        neighbors = [
-            (node, key)
-            for node, adj in graph.adj[ending_node].iteritems()
-            for key in adj
-        ]
-
-        # heuristic: try grating segments first
-        neighbors.sort(key=lambda dest_key: dest_key[1] == "segment", reverse=True)
-
-        for next_node, key in neighbors:
-            # skip if I've already followed this edge
-            edge = PathEdge((ending_node, next_node), key)
-            if edge in visited_edges:
-                continue
-
-            new_path = path + [edge]
-
-            if next_node == starting_node:
-                # ignore trivial loops (down and back a doubled edge)
-                if len(new_path) > 3:
-                    return new_path
-
-            new_visited_edges = visited_edges.copy()
-            new_visited_edges.add(edge)
-
-            to_search.appendleft((new_path, new_visited_edges))
-
-
-def find_loop(graph, starting_nodes):
-    """find a loop in the graph that is connected to the existing path
-
-    Start at a candidate node and search through edges to find a path
-    back to that node.  We'll use a breadth-first search (BFS) in order to
-    find the shortest available loop.
-
-    In most cases, the BFS should not need to search far to find a loop.
-    The queue should stay relatively short.
-
-    An added heuristic will be used: if the BFS queue's length becomes
-    too long, we'll abort and try a different starting point.  Due to
-    the way we've set up the graph, there's bound to be a better choice
-    somewhere else.
-    """
-
-    loop = None
-    retry = []
-    max_queue_length = 2000
-
-    while not loop:
-        while not loop and starting_nodes:
-            starting_node = starting_nodes.pop()
-
-            try:
-                # Note: if bfs_for_loop() returns None, no loop can be
-                # constructed from the starting_node (because the
-                # necessary edges have already been consumed).  In that
-                # case we discard that node and try the next.
-                loop = bfs_for_loop(graph, starting_node, max_queue_length)
-
-            except MaxQueueLengthExceeded:
-                # We're giving up on this node for now.  We could try
-                # this node again later, so add it to the bottm of the
-                # stack.
-                retry.append(starting_node)
-
-        # Darn, couldn't find a loop.  Try harder.
-        starting_nodes.extendleft(retry)
-        max_queue_length *= 2
-
-    starting_nodes.extendleft(retry)
-    return loop
-
-
-def insert_loop(path, loop):
-    """insert a sub-loop into an existing path
-
-    The path will be a series of edges describing a path through the graph
-    that ends where it starts.  The loop will be similar, and its starting
-    point will be somewhere along the path.
-
-    Insert the loop into the path, resulting in a longer path.
-
-    Both the path and the loop will be a list of edges specified as a
-    start and end point.  The points will be specified in order, such
-    that they will look like this:
-
-    ((p1, p2), (p2, p3), (p3, p4), ...)
-
-    path will be modified in place.
-    """
-
-    loop_start = loop[0][0]
-
-    for i, (start, end) in enumerate(path):
-        if start == loop_start:
-            break
-    else:
-        # if we didn't find the start of the loop in the list at all, it must
-        # be the endpoint of the last segment
-        i += 1
-
-    path[i:i] = loop
-
-
 def nearest_node_on_outline(graph, point, outline_index=0):
     point = shgeo.Point(*point)
     outline_nodes = [node for node, data in graph.nodes(data=True) if data['index'] == outline_index]
@@ -327,48 +172,6 @@ def nearest_node_on_outline(graph, point, outline_index=0):
     return nearest
 
 
-def get_outline_nodes(graph, outline_index=0):
-    outline_nodes = [(node, data['projection'])
-                     for node, data
-                     in graph.nodes(data=True)
-                     if data['index'] == outline_index]
-    outline_nodes.sort(key=lambda node_projection: node_projection[1])
-    outline_nodes = [node for node, data in outline_nodes]
-
-    return outline_nodes
-
-
-def find_initial_path(graph, starting_point, ending_point=None):
-    starting_node = nearest_node_on_outline(graph, starting_point)
-
-    if ending_point is not None:
-        ending_node = nearest_node_on_outline(graph, ending_point)
-
-    if ending_point is None or starting_node is ending_node:
-        # If they didn't give an ending point, pick either neighboring node
-        # along the outline -- doesn't matter which.  We do this because
-        # the algorithm requires we start with _some_ path.
-        neighbors = [n for n, keys in graph.adj[starting_node].iteritems() if 'outline' in keys]
-        return [PathEdge((starting_node, neighbors[0]), "initial")]
-    else:
-        outline_nodes = get_outline_nodes(graph)
-
-        # Multiply the outline_nodes list by 2 (duplicate it) because
-        # the ending_node may occur first.
-        outline_nodes *= 2
-        start_index = outline_nodes.index(starting_node)
-        end_index = outline_nodes.index(ending_node, start_index)
-        nodes = outline_nodes[start_index:end_index + 1]
-
-        # we have a series of sequential points, but we need to
-        # turn it into an edge list
-        path = []
-        for start, end in izip(nodes[:-1], nodes[1:]):
-            path.append(PathEdge((start, end), "initial"))
-
-        return path
-
-
 def find_stitch_path(graph, segments, starting_point=None, ending_point=None):
     """find a path that visits every grating segment exactly once
 
@@ -450,7 +253,7 @@ def pick_edge(edges):
     return list(edges)[0]
 
 
-def collapse_sequential_outline_edges(graph, path):
+def collapse_sequential_outline_edges(path):
     """collapse sequential edges that fall on the same outline
 
     When the path follows multiple edges along the outline of the region,
@@ -559,13 +362,8 @@ def connect_points(shape, start, end, running_stitch_length, row_spacing):
     return stitches[1:]
 
 
-def trim_end(path):
-    while path and path[-1].is_outline():
-        path.pop()
-
-
-def path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
-    path = collapse_sequential_outline_edges(graph, path)
+def path_to_stitches(path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
+    path = collapse_sequential_outline_edges(path)
 
     stitches = []
 
-- 
cgit v1.2.3


From 30ea54dc6de707b084ea1fc4a66a64bbd7a9c974 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 13 Mar 2019 20:11:07 -0400
Subject: tidy up the code a bit

---
 lib/stitches/auto_fill.py | 30 ++++++++++++++++--------------
 1 file changed, 16 insertions(+), 14 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 7386e08f..c2e2e0bb 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -52,13 +52,11 @@ def auto_fill(shape,
               starting_point,
               ending_point=None):
 
-    rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing)
-    segments = [segment for row in rows_of_segments for segment in row]
-    graph = build_graph(shape, segments)
+    graph = build_graph(shape, angle, row_spacing, end_row_spacing)
     check_graph(graph, shape, max_stitch_length)
-    path = find_stitch_path(graph, segments, starting_point, ending_point)
+    path = find_stitch_path(graph, starting_point, ending_point)
 
-    return path_to_stitches(path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
+    return path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
 
 
 def which_outline(shape, coords):
@@ -88,7 +86,7 @@ def project(shape, coords, outline_index):
     return outline.project(shgeo.Point(*coords))
 
 
-def build_graph(shape, segments):
+def build_graph(shape, angle, row_spacing, end_row_spacing):
     """build a graph representation of the grating segments
 
     This function builds a specialized graph (as in graph theory) that will
@@ -121,6 +119,10 @@ def build_graph(shape, segments):
     path must exist.
     """
 
+    # Convert the shape into a set of parallel line segments.
+    rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing)
+    segments = [segment for row in rows_of_segments for segment in row]
+
     graph = networkx.MultiGraph()
 
     # First, add the grating segments as edges.  We'll use the coordinates
@@ -172,7 +174,7 @@ def nearest_node_on_outline(graph, point, outline_index=0):
     return nearest
 
 
-def find_stitch_path(graph, segments, starting_point=None, ending_point=None):
+def find_stitch_path(graph, starting_point=None, ending_point=None):
     """find a path that visits every grating segment exactly once
 
     Theoretically, we just need to find an Eulerian Path in the graph.
@@ -197,7 +199,7 @@ def find_stitch_path(graph, segments, starting_point=None, ending_point=None):
     graph = graph.copy()
 
     if starting_point is None:
-        starting_point = segments[0][0]
+        starting_point = graph.nodes.keys()[0]
 
     starting_node = nearest_node_on_outline(graph, starting_point)
 
@@ -283,7 +285,7 @@ def collapse_sequential_outline_edges(path):
     return new_path
 
 
-def connect_points(shape, start, end, running_stitch_length, row_spacing):
+def connect_points(graph, shape, start, end, running_stitch_length, row_spacing):
     """Create stitches to get from one point on an outline of the shape to another.
 
     An outline is essentially a loop (a path of points that ends where it starts).
@@ -294,16 +296,16 @@ def connect_points(shape, start, end, running_stitch_length, row_spacing):
     """
 
     # We may be on the outer boundary or on on of the hole boundaries.
-    outline_index = which_outline(shape, start)
+    outline_index = graph.nodes[start]['index']
     outline = shape.boundary[outline_index]
 
     # First, figure out the start and end position along the outline.  The
     # projection gives us the distance travelled down the outline to get to
     # that point.
+    start_projection = graph.nodes[start]['projection']
     start = shgeo.Point(start)
-    start_projection = outline.project(start)
+    end_projection = graph.nodes[end]['projection']
     end = shgeo.Point(end)
-    end_projection = outline.project(end)
 
     # If the points are pretty close, just jump there.  There's a slight
     # risk that we're going to sew outside the shape here.  The way to
@@ -362,7 +364,7 @@ def connect_points(shape, start, end, running_stitch_length, row_spacing):
     return stitches[1:]
 
 
-def path_to_stitches(path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
+def path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
     path = collapse_sequential_outline_edges(path)
 
     stitches = []
@@ -371,6 +373,6 @@ def path_to_stitches(path, shape, angle, row_spacing, max_stitch_length, running
         if edge.is_segment():
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last)
         else:
-            stitches.extend(connect_points(shape, edge[0], edge[1], running_stitch_length, row_spacing))
+            stitches.extend(connect_points(graph, shape, edge[0], edge[1], running_stitch_length, row_spacing))
 
     return stitches
-- 
cgit v1.2.3


From e616061e85fda0160ebfc7d071358d730b0c613f Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 14 Mar 2019 21:02:47 -0400
Subject: underpathing!

---
 lib/stitches/auto_fill.py | 137 +++++++++++++++++++---------------------------
 lib/stitches/fill.py      |   4 +-
 2 files changed, 59 insertions(+), 82 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index c2e2e0bb..2e424267 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -1,14 +1,14 @@
-from collections import deque
-from itertools import groupby, izip
-import sys
+from itertools import groupby, chain
+import math
 
 import networkx
 from shapely import geometry as shgeo
 
 from ..exceptions import InkstitchException
 from ..i18n import _
+from ..svg import PIXELS_PER_MM
 from ..utils.geometry import Point as InkstitchPoint, cut
-from .fill import intersect_region_with_grating, row_num, stitch_row
+from .fill import intersect_region_with_grating, stitch_row
 from .running_stitch import running_stitch
 
 
@@ -50,13 +50,16 @@ def auto_fill(shape,
               staggers,
               skip_last,
               starting_point,
-              ending_point=None):
+              ending_point=None,
+              underpath=True):
 
     graph = build_graph(shape, angle, row_spacing, end_row_spacing)
     check_graph(graph, shape, max_stitch_length)
+    travel_graph = build_travel_graph(graph, shape, angle, underpath)
     path = find_stitch_path(graph, starting_point, ending_point)
+    result = path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
 
-    return path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
+    return result
 
 
 def which_outline(shape, coords):
@@ -156,6 +159,48 @@ def build_graph(shape, angle, row_spacing, end_row_spacing):
     return graph
 
 
+def build_travel_graph(top_stitch_graph, shape, top_stitch_angle, underpath):
+    graph = networkx.Graph()
+    graph.add_nodes_from(top_stitch_graph.nodes(data=True))
+
+    if underpath:
+        # need to concatenate all the rows
+        grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
+        grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
+
+        endpoints = [coord for mls in (grating1, grating2)
+                     for ls in mls
+                     for coord in ls.coords]
+
+        for node in endpoints:
+            outline_index = which_outline(shape, node)
+            outline_projection = project(shape, node, outline_index)
+
+            # Tag each node with its index and projection.
+            graph.add_node(node, index=outline_index, projection=outline_projection)
+
+    nodes = list(graph.nodes(data=True))  # returns a list of tuples: [(node, {data}), (node, {data}) ...]
+    nodes.sort(key=lambda node: (node[1]['index'], node[1]['projection']))
+
+    for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']):
+        nodes = [node for node, data in nodes]
+
+        # add an edge between each successive node
+        for node1, node2 in zip(nodes, nodes[1:] + [nodes[0]]):
+            p1 = InkstitchPoint(*node1)
+            p2 = InkstitchPoint(*node2)
+            graph.add_edge(node1, node2, weight=3 * p1.distance(p2))
+
+    if underpath:
+        interior_edges = grating1.symmetric_difference(grating2)
+        for ls in interior_edges.geoms:
+            p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords]
+
+            graph.add_edge(p1.as_tuple(), p2.as_tuple(), weight=p1.distance(p2))
+
+    return graph
+
+
 def check_graph(graph, shape, max_stitch_length):
     if networkx.is_empty(graph) or not networkx.is_eulerian(graph):
         if shape.area < max_stitch_length ** 2:
@@ -285,86 +330,18 @@ def collapse_sequential_outline_edges(path):
     return new_path
 
 
-def connect_points(graph, shape, start, end, running_stitch_length, row_spacing):
-    """Create stitches to get from one point on an outline of the shape to another.
-
-    An outline is essentially a loop (a path of points that ends where it starts).
-    Given point A and B on that loop, we want to take the shortest path from one
-    to the other.  Due to the way our path-finding algorithm above works, it may
-    have had to take the long way around the shape to get from A to B, but we'd
-    rather ignore that and just get there the short way.
-    """
-
-    # We may be on the outer boundary or on on of the hole boundaries.
-    outline_index = graph.nodes[start]['index']
-    outline = shape.boundary[outline_index]
-
-    # First, figure out the start and end position along the outline.  The
-    # projection gives us the distance travelled down the outline to get to
-    # that point.
-    start_projection = graph.nodes[start]['projection']
-    start = shgeo.Point(start)
-    end_projection = graph.nodes[end]['projection']
-    end = shgeo.Point(end)
-
-    # If the points are pretty close, just jump there.  There's a slight
-    # risk that we're going to sew outside the shape here.  The way to
-    # avoid that is to use running_stitch() even for these really short
-    # connections, but that would be really slow for all of the
-    # connections from one row to the next.
-    #
-    # This seems to do a good job of avoiding going outside the shape in
-    # most cases.  1.4 is chosen as approximately the length of the
-    # stitch connecting two rows if the side of the shape is at a 45
-    # degree angle to the rows of stitches (sqrt(2)).
-    direct_distance = abs(end_projection - start_projection)
-    if direct_distance < row_spacing * 1.4 and direct_distance < running_stitch_length:
-        return [InkstitchPoint(end.x, end.y)]
-
-    # The outline path has a "natural" starting point.  Think of this as
-    # 0 or 12 on an analog clock.
-
-    # Cut the outline into two paths at the starting point.  The first
-    # section will go from 12 o'clock to the starting point.  The second
-    # section will go from the starting point all the way around and end
-    # up at 12 again.
-    result = cut(outline, start_projection)
-
-    # result[0] will be None if our starting point happens to already be at
-    # 12 o'clock.
-    if result[0] is not None:
-        before, after = result
-
-        # Make a new outline, starting from the starting point.  This is
-        # like rotating the clock so that now our starting point is
-        # at 12 o'clock.
-        outline = shgeo.LineString(list(after.coords) + list(before.coords))
-
-    # Now figure out where our ending point is on the newly-rotated clock.
-    end_projection = outline.project(end)
-
-    # Cut the new path at the ending point.  before and after now represent
-    # two ways to get from the starting point to the ending point.  One
-    # will most likely be longer than the other.
-    before, after = cut(outline, end_projection)
-
-    if before.length <= after.length:
-        points = list(before.coords)
-    else:
-        # after goes from the ending point to the starting point, so reverse
-        # it to get from start to end.
-        points = list(reversed(after.coords))
+def travel(graph, travel_graph, shape, start, end, running_stitch_length, row_spacing):
+    """Create stitches to get from one point on an outline of the shape to another."""
 
-    # Now do running stitch along the path we've found.  running_stitch() will
-    # avoid cutting sharp corners.
-    path = [InkstitchPoint(*p) for p in points]
+    path = networkx.shortest_path(travel_graph, start, end, weight='weight')
+    path = [InkstitchPoint(*p) for p in path]
     stitches = running_stitch(path, running_stitch_length)
 
     # The row of stitches already stitched the first point, so skip it.
     return stitches[1:]
 
 
-def path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
+def path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
     path = collapse_sequential_outline_edges(path)
 
     stitches = []
@@ -373,6 +350,6 @@ def path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length,
         if edge.is_segment():
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last)
         else:
-            stitches.extend(connect_points(graph, shape, edge[0], edge[1], running_stitch_length, row_spacing))
+            stitches.extend(travel(graph, travel_graph, shape, edge[0], edge[1], running_stitch_length, row_spacing))
 
     return stitches
diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py
index e00d66de..924f64f6 100644
--- a/lib/stitches/fill.py
+++ b/lib/stitches/fill.py
@@ -140,7 +140,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non
         res = grating_line.intersection(shape)
 
         if (isinstance(res, shapely.geometry.MultiLineString)):
-            runs = map(lambda line_string: line_string.coords, res.geoms)
+            runs = [line_string.coords for line_string in res.geoms]
         else:
             if res.is_empty or len(res.coords) == 1:
                 # ignore if we intersected at a single point or no points
@@ -153,7 +153,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non
 
             if flip:
                 runs.reverse()
-                runs = map(lambda run: tuple(reversed(run)), runs)
+                runs = [tuple(reversed(run)) for run in runs]
 
             rows.append(runs)
 
-- 
cgit v1.2.3


From 200e2ac5f73c207b95ff815e754e42c427ccc58e Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 14 Mar 2019 21:46:44 -0400
Subject: deduplicate and comment code

---
 lib/stitches/auto_fill.py | 107 ++++++++++++++++++++++++++++++++++------------
 1 file changed, 79 insertions(+), 28 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 2e424267..82b4a99e 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -1,3 +1,5 @@
+# -*- coding: UTF-8 -*-
+
 from itertools import groupby, chain
 import math
 
@@ -74,7 +76,7 @@ def which_outline(shape, coords):
 
     point = shgeo.Point(*coords)
     outlines = enumerate(list(shape.boundary))
-    closest = min(outlines, key=lambda index_outline: index_outline[1].distance(point))
+    closest = min(outlines, key=lambda (index, outline): outline.distance(point))
 
     return closest[0]
 
@@ -135,6 +137,8 @@ def build_graph(shape, angle, row_spacing, end_row_spacing):
         # mark this one as a grating segment.
         graph.add_edge(*segment, key="segment")
 
+    tag_nodes_with_outline_and_projection(graph, shape, graph.nodes())
+
     for node in graph.nodes():
         outline_index = which_outline(shape, node)
         outline_projection = project(shape, node, outline_index)
@@ -142,54 +146,101 @@ def build_graph(shape, angle, row_spacing, end_row_spacing):
         # Tag each node with its index and projection.
         graph.add_node(node, index=outline_index, projection=outline_projection)
 
+    add_edges_between_outline_nodes(graph, key="outline")
+
+    for node1, node2, key, data in graph.edges(keys=True, data=True):
+        if key == "outline":
+            # duplicate every other edge
+            if data['index'] % 2 == 0:
+                graph.add_edge(node1, node2, key="extra")
+
+    return graph
+
+
+def tag_nodes_with_outline_and_projection(graph, shape, nodes):
+    for node in nodes:
+        outline_index = which_outline(shape, node)
+        outline_projection = project(shape, node, outline_index)
+
+        graph.add_node(node, outline=outline_index, projection=outline_projection)
+
+
+def add_edges_between_outline_nodes(graph, key=None):
+    """Add edges around the outlines of the graph, connecting sequential nodes.
+
+    This function assumes that all nodes in the graph are on the outline of the
+    shape.  It figures out which nodes are next to each other on the shape and
+    connects them in the graph with an edge.
+
+    Edges are tagged with their outline number and their position on that
+    outline.
+    """
+
     nodes = list(graph.nodes(data=True))  # returns a list of tuples: [(node, {data}), (node, {data}) ...]
-    nodes.sort(key=lambda node: (node[1]['index'], node[1]['projection']))
+    nodes.sort(key=lambda node: (node[1]['outline'], node[1]['projection']))
 
-    for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']):
+    for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['outline']):
         nodes = [node for node, data in nodes]
 
         # add an edge between each successive node
         for i, (node1, node2) in enumerate(zip(nodes, nodes[1:] + [nodes[0]])):
-            graph.add_edge(node1, node2, key="outline")
+            data = dict(outline=outline_index, index=i)
+            if key:
+                graph.add_edge(node1, node2, key=key, **data)
+            else:
+                graph.add_edge(node1, node2, **data)
 
-            # duplicate every other edge
-            if i % 2 == 0:
-                graph.add_edge(node1, node2, key="extra")
 
-    return graph
+def build_travel_graph(top_stitch_graph, shape, top_stitch_angle, underpath):
+    """Build a graph for travel stitches.
 
+    This graph will be used to find a stitch path between two spots on the
+    outline of the shape.
+
+    If underpath is False, we'll just be traveling
+    around the outline of the shape, so the graph will only contain outline
+    edges.
+
+    If underpath is True, we'll also allow travel inside the shape.  We'll
+    fill the shape with a cross-hatched grid of lines 2mm apart, at ±45
+    degrees from the fill stitch angle.  This will ensure that travel stitches
+    won't be visible and won't disrupt the fill stitch.
+
+    When underpathing, we "encourage" the travel() function to travel inside
+    the shape rather than on the boundary.  We do this by weighting the
+    boundary edges extra so that they're more "expensive" in the shortest path
+    calculation.
+    """
 
-def build_travel_graph(top_stitch_graph, shape, top_stitch_angle, underpath):
     graph = networkx.Graph()
+
+    # Add all the nodes from the main graph.  This will be all of the endpoints
+    # of the rows of stitches.  Every node will be on the outline of the shape.
+    # They'll all already have their `outline` and `projection` tags set.
     graph.add_nodes_from(top_stitch_graph.nodes(data=True))
 
     if underpath:
-        # need to concatenate all the rows
+        # These two MultiLineStrings will make up the cross-hatched grid.
         grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
         grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
 
+        # We'll add the endpoints of the crosshatch grating lines too  These
+        # will all be on the outline of the shape.  This will ensure that a
+        # path traveling inside the shape can reach its target on the outline,
+        # which will be one of the points added above.
         endpoints = [coord for mls in (grating1, grating2)
                      for ls in mls
                      for coord in ls.coords]
+        tag_nodes_with_outline_and_projection(graph, shape, endpoints)
 
-        for node in endpoints:
-            outline_index = which_outline(shape, node)
-            outline_projection = project(shape, node, outline_index)
-
-            # Tag each node with its index and projection.
-            graph.add_node(node, index=outline_index, projection=outline_projection)
-
-    nodes = list(graph.nodes(data=True))  # returns a list of tuples: [(node, {data}), (node, {data}) ...]
-    nodes.sort(key=lambda node: (node[1]['index'], node[1]['projection']))
-
-    for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']):
-        nodes = [node for node, data in nodes]
+    add_edges_between_outline_nodes(graph)
+    for start, end in graph.edges:
+        p1 = InkstitchPoint(*start)
+        p2 = InkstitchPoint(*end)
 
-        # add an edge between each successive node
-        for node1, node2 in zip(nodes, nodes[1:] + [nodes[0]]):
-            p1 = InkstitchPoint(*node1)
-            p2 = InkstitchPoint(*node2)
-            graph.add_edge(node1, node2, weight=3 * p1.distance(p2))
+        # Set the weight equal to triple the edge length, to encourage travel()
+        # to avoid them when underpathing is enabled.
+        graph.add_edge(start, end, weight=3 * p1.distance(p2))
 
     if underpath:
         interior_edges = grating1.symmetric_difference(grating2)
@@ -213,7 +264,7 @@ def check_graph(graph, shape, max_stitch_length):
 
 def nearest_node_on_outline(graph, point, outline_index=0):
     point = shgeo.Point(*point)
-    outline_nodes = [node for node, data in graph.nodes(data=True) if data['index'] == outline_index]
+    outline_nodes = [node for node, data in graph.nodes(data=True) if data['outline'] == outline_index]
     nearest = min(outline_nodes, key=lambda node: shgeo.Point(*node).distance(point))
 
     return nearest
-- 
cgit v1.2.3


From ec14fe7343e966286ce30ff329146feb3af4476b Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 14 Mar 2019 21:54:51 -0400
Subject: more cleanup

---
 lib/stitches/auto_fill.py | 35 ++++++++++++++++++-----------------
 1 file changed, 18 insertions(+), 17 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 82b4a99e..f64f6f28 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -9,7 +9,7 @@ from shapely import geometry as shgeo
 from ..exceptions import InkstitchException
 from ..i18n import _
 from ..svg import PIXELS_PER_MM
-from ..utils.geometry import Point as InkstitchPoint, cut
+from ..utils.geometry import Point as InkstitchPoint
 from .fill import intersect_region_with_grating, stitch_row
 from .running_stitch import running_stitch
 
@@ -55,11 +55,11 @@ def auto_fill(shape,
               ending_point=None,
               underpath=True):
 
-    graph = build_graph(shape, angle, row_spacing, end_row_spacing)
-    check_graph(graph, shape, max_stitch_length)
-    travel_graph = build_travel_graph(graph, shape, angle, underpath)
-    path = find_stitch_path(graph, starting_point, ending_point)
-    result = path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
+    fill_stitch_graph = build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing)
+    check_graph(fill_stitch_graph, shape, max_stitch_length)
+    travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
+    path = find_stitch_path(fill_stitch_graph, starting_point, ending_point)
+    result = path_to_stitches(path, travel_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
 
     return result
 
@@ -75,10 +75,11 @@ def which_outline(shape, coords):
     # fail sometimes.
 
     point = shgeo.Point(*coords)
-    outlines = enumerate(list(shape.boundary))
-    closest = min(outlines, key=lambda (index, outline): outline.distance(point))
+    outlines = list(shape.boundary)
+    outline_indices = range(len(outlines))
+    closest = min(outline_indices, key=lambda index: outlines[index].distance(point))
 
-    return closest[0]
+    return closest
 
 
 def project(shape, coords, outline_index):
@@ -91,7 +92,7 @@ def project(shape, coords, outline_index):
     return outline.project(shgeo.Point(*coords))
 
 
-def build_graph(shape, angle, row_spacing, end_row_spacing):
+def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
     """build a graph representation of the grating segments
 
     This function builds a specialized graph (as in graph theory) that will
@@ -191,7 +192,7 @@ def add_edges_between_outline_nodes(graph, key=None):
                 graph.add_edge(node1, node2, **data)
 
 
-def build_travel_graph(top_stitch_graph, shape, top_stitch_angle, underpath):
+def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
     """Build a graph for travel stitches.
 
     This graph will be used to find a stitch path between two spots on the
@@ -217,12 +218,12 @@ def build_travel_graph(top_stitch_graph, shape, top_stitch_angle, underpath):
     # Add all the nodes from the main graph.  This will be all of the endpoints
     # of the rows of stitches.  Every node will be on the outline of the shape.
     # They'll all already have their `outline` and `projection` tags set.
-    graph.add_nodes_from(top_stitch_graph.nodes(data=True))
+    graph.add_nodes_from(fill_stitch_graph.nodes(data=True))
 
     if underpath:
         # These two MultiLineStrings will make up the cross-hatched grid.
-        grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
-        grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
+        grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
+        grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
 
         # We'll add the endpoints of the crosshatch grating lines too  These
         # will all be on the outline of the shape.  This will ensure that a
@@ -381,7 +382,7 @@ def collapse_sequential_outline_edges(path):
     return new_path
 
 
-def travel(graph, travel_graph, shape, start, end, running_stitch_length, row_spacing):
+def travel(travel_graph, start, end, running_stitch_length):
     """Create stitches to get from one point on an outline of the shape to another."""
 
     path = networkx.shortest_path(travel_graph, start, end, weight='weight')
@@ -392,7 +393,7 @@ def travel(graph, travel_graph, shape, start, end, running_stitch_length, row_sp
     return stitches[1:]
 
 
-def path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
+def path_to_stitches(path, travel_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
     path = collapse_sequential_outline_edges(path)
 
     stitches = []
@@ -401,6 +402,6 @@ def path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_s
         if edge.is_segment():
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last)
         else:
-            stitches.extend(travel(graph, travel_graph, shape, edge[0], edge[1], running_stitch_length, row_spacing))
+            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length))
 
     return stitches
-- 
cgit v1.2.3


From 2ba333c8a74245ee86b213809c734fcd7509c823 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Mon, 18 Mar 2019 20:57:05 -0400
Subject: avoid putting underpathing on top

---
 lib/stitches/auto_fill.py | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index f64f6f28..1eabfac9 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -59,7 +59,8 @@ def auto_fill(shape,
     check_graph(fill_stitch_graph, shape, max_stitch_length)
     travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
     path = find_stitch_path(fill_stitch_graph, starting_point, ending_point)
-    result = path_to_stitches(path, travel_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last)
+    result = path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing,
+                              max_stitch_length, running_stitch_length, staggers, skip_last)
 
     return result
 
@@ -136,7 +137,7 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
     for segment in segments:
         # networkx allows us to label nodes with arbitrary data.  We'll
         # mark this one as a grating segment.
-        graph.add_edge(*segment, key="segment")
+        graph.add_edge(*segment, key="segment", underpath_edges=[])
 
     tag_nodes_with_outline_and_projection(graph, shape, graph.nodes())
 
@@ -244,11 +245,21 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         graph.add_edge(start, end, weight=3 * p1.distance(p2))
 
     if underpath:
+        segments = []
+        for start, end, key, data in fill_stitch_graph.edges(keys=True, data=True):
+            if key == 'segment':
+                segments.append((shgeo.LineString((start, end)), data))
+
         interior_edges = grating1.symmetric_difference(grating2)
         for ls in interior_edges.geoms:
             p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords]
+            edge = (p1.as_tuple(), p2.as_tuple())
+
+            for segment, data in segments:
+                if ls.crosses(segment):
+                    data['underpath_edges'].append(edge)
 
-            graph.add_edge(p1.as_tuple(), p2.as_tuple(), weight=p1.distance(p2))
+            graph.add_edge(*edge, weight=p1.distance(p2))
 
     return graph
 
@@ -393,7 +404,7 @@ def travel(travel_graph, start, end, running_stitch_length):
     return stitches[1:]
 
 
-def path_to_stitches(path, travel_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
+def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
     path = collapse_sequential_outline_edges(path)
 
     stitches = []
@@ -401,6 +412,7 @@ def path_to_stitches(path, travel_graph, angle, row_spacing, max_stitch_length,
     for edge in path:
         if edge.is_segment():
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last)
+            travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', []))
         else:
             stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length))
 
-- 
cgit v1.2.3


From ba2b78d3499f3b274611440b9b2257b9ee0f1820 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 19 Mar 2019 19:59:40 -0400
Subject: use blazing-fast STRtree for intersection detection

---
 lib/stitches/auto_fill.py | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 1eabfac9..c4132fcc 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -5,6 +5,7 @@ import math
 
 import networkx
 from shapely import geometry as shgeo
+from shapely.strtree import STRtree
 
 from ..exceptions import InkstitchException
 from ..i18n import _
@@ -248,16 +249,22 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         segments = []
         for start, end, key, data in fill_stitch_graph.edges(keys=True, data=True):
             if key == 'segment':
-                segments.append((shgeo.LineString((start, end)), data))
+                segments.append(shgeo.LineString((start, end)))
+
+        # The shapely documentation is pretty unclear on this.  An STRtree
+        # allows for building a set of shapes and then efficiently testing
+        # the set for intersection.  This allows us to do blazing-fast
+        # queries of which line segments overlap each underpath edge.
+        rtree = STRtree(segments)
 
         interior_edges = grating1.symmetric_difference(grating2)
         for ls in interior_edges.geoms:
             p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords]
             edge = (p1.as_tuple(), p2.as_tuple())
 
-            for segment, data in segments:
-                if ls.crosses(segment):
-                    data['underpath_edges'].append(edge)
+            for segment in rtree.query(ls):
+                start, end = segment.coords
+                fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
 
             graph.add_edge(*edge, weight=p1.distance(p2))
 
-- 
cgit v1.2.3


From 8520d4e63c8ad05bc8edf67d29fc797b0f335c3e Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 19 Mar 2019 20:26:25 -0400
Subject: avoid cutting corners

---
 lib/stitches/auto_fill.py | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index c4132fcc..7ca354bb 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -400,15 +400,27 @@ def collapse_sequential_outline_edges(path):
     return new_path
 
 
-def travel(travel_graph, start, end, running_stitch_length):
+def travel(travel_graph, start, end, running_stitch_length, skip_last):
     """Create stitches to get from one point on an outline of the shape to another."""
 
     path = networkx.shortest_path(travel_graph, start, end, weight='weight')
     path = [InkstitchPoint(*p) for p in path]
     stitches = running_stitch(path, running_stitch_length)
 
-    # The row of stitches already stitched the first point, so skip it.
-    return stitches[1:]
+    # The path's first stitch will start at the end of a row of stitches.  We
+    # don't want to double that last stitch, so we'd like to skip it.
+    if skip_last and len(path) > 2:
+        # However, we don't want to skip it if we've had to do any actual
+        # travel in the interior of the shape.  The reason is that we can
+        # potentially cut a corner and stitch outside the shape.
+        #
+        # If the path is longer than two nodes, then it is not a simple
+        # transition from one row to the next, so we'll keep the stitch.
+        return stitches
+    else:
+        # Just a normal transition from one row to the next, so skip the first
+        # stitch.
+        return stitches[1:]
 
 
 def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
@@ -421,6 +433,6 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing,
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last)
             travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', []))
         else:
-            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length))
+            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, skip_last))
 
     return stitches
-- 
cgit v1.2.3


From 6b8121fb04075b135f6f67954a9f7686460ce5f5 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 19 Mar 2019 22:30:07 -0400
Subject: add underpath checkboxes for underlay and top stitching

---
 lib/elements/auto_fill.py | 28 ++++++++++++++++++++++++++--
 1 file changed, 26 insertions(+), 2 deletions(-)

(limited to 'lib')

diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index 1308b9e3..e78943ec 100644
--- a/lib/elements/auto_fill.py
+++ b/lib/elements/auto_fill.py
@@ -119,6 +119,28 @@ class AutoFill(Fill):
     def expand(self):
         return self.get_float_param('expand_mm', 0)
 
+    @property
+    @param('underpath',
+           _('Underpath'),
+           tooltip=_('Travel inside the shape when moving from section to section.  Underpath '
+                     'stitches avoid traveling in the direction of the row angle so that they '
+                     'are not visible.  This gives them a jagged appearance.'),
+           type='boolean',
+           default=True)
+    def underpath(self):
+        return self.get_boolean_param('underpath', True)
+
+    @property
+    @param('underlay_underpath',
+           _('Underpath'),
+           tooltip=_('Travel inside the shape when moving from section to section.  Underpath '
+                     'stitches avoid traveling in the direction of the row angle so that they '
+                     'are not visible.  This gives them a jagged appearance.'),
+           type='boolean',
+           default=False)
+    def underlay_underpath(self):
+        return self.get_boolean_param('underpath', False)
+
     def shrink_or_grow_shape(self, amount):
         if amount:
             shape = self.shape.buffer(amount)
@@ -169,7 +191,8 @@ class AutoFill(Fill):
                                           self.running_stitch_length,
                                           self.staggers,
                                           self.fill_underlay_skip_last,
-                                          starting_point))
+                                          starting_point,
+                                          underpath=self.underlay_underpath))
                 starting_point = stitches[-1]
 
             stitches.extend(auto_fill(self.fill_shape,
@@ -181,7 +204,8 @@ class AutoFill(Fill):
                                       self.staggers,
                                       self.skip_last,
                                       starting_point,
-                                      ending_point))
+                                      ending_point,
+                                      self.underpath))
         except InkstitchException, exc:
             # for one of our exceptions, just print the message
             self.fatal(_("Unable to autofill: ") + str(exc))
-- 
cgit v1.2.3


From 68590492f55af51bf681a73200f12eb4d9a4f27a Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 19 Mar 2019 22:36:05 -0400
Subject: allow starting and ending on the border of a hole

---
 lib/stitches/auto_fill.py | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 7ca354bb..3dff3d96 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -281,10 +281,9 @@ def check_graph(graph, shape, max_stitch_length):
                                 "This most often happens because your shape is made up of multiple sections that aren't connected."))
 
 
-def nearest_node_on_outline(graph, point, outline_index=0):
+def nearest_node_on_outline(graph, point):
     point = shgeo.Point(*point)
-    outline_nodes = [node for node, data in graph.nodes(data=True) if data['outline'] == outline_index]
-    nearest = min(outline_nodes, key=lambda node: shgeo.Point(*node).distance(point))
+    nearest = min(graph.nodes, key=lambda node: shgeo.Point(*node).distance(point))
 
     return nearest
 
-- 
cgit v1.2.3


From 685df3b3f05f8e81751bde2e7bb59c50b658f764 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 19 Mar 2019 23:28:19 -0400
Subject: fix start/end at top or bottom of shape

---
 lib/stitches/auto_fill.py | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 3dff3d96..b85d335e 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -59,7 +59,7 @@ def auto_fill(shape,
     fill_stitch_graph = build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing)
     check_graph(fill_stitch_graph, shape, max_stitch_length)
     travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
-    path = find_stitch_path(fill_stitch_graph, starting_point, ending_point)
+    path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point)
     result = path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing,
                               max_stitch_length, running_stitch_length, staggers, skip_last)
 
@@ -281,14 +281,14 @@ def check_graph(graph, shape, max_stitch_length):
                                 "This most often happens because your shape is made up of multiple sections that aren't connected."))
 
 
-def nearest_node_on_outline(graph, point):
+def nearest_node(graph, point):
     point = shgeo.Point(*point)
     nearest = min(graph.nodes, key=lambda node: shgeo.Point(*node).distance(point))
 
     return nearest
 
 
-def find_stitch_path(graph, starting_point=None, ending_point=None):
+def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None):
     """find a path that visits every grating segment exactly once
 
     Theoretically, we just need to find an Eulerian Path in the graph.
@@ -315,12 +315,13 @@ def find_stitch_path(graph, starting_point=None, ending_point=None):
     if starting_point is None:
         starting_point = graph.nodes.keys()[0]
 
-    starting_node = nearest_node_on_outline(graph, starting_point)
+    starting_node = nearest_node(graph, starting_point)
 
     if ending_point is None:
+        ending_point = starting_point
         ending_node = starting_node
     else:
-        ending_node = nearest_node_on_outline(graph, ending_point)
+        ending_node = nearest_node(graph, ending_point)
 
     # The algorithm below is adapted from networkx.eulerian_circuit().
     path = []
@@ -354,6 +355,14 @@ def find_stitch_path(graph, starting_point=None, ending_point=None):
     if starting_node is not ending_node:
         path.insert(0, PathEdge((starting_node, ending_node), key="initial"))
 
+    real_start = nearest_node(travel_graph, starting_point)
+    if real_start != starting_node:
+        path.insert(0, PathEdge((real_start, starting_node), key="outline"))
+
+    real_end = nearest_node(travel_graph, ending_point)
+    if real_end != ending_node:
+        path.append(PathEdge((ending_node, real_end), key="outline"))
+
     return path
 
 
-- 
cgit v1.2.3


From 69df0271b5e9c5be8ff0d16fe6e24f1e7ed8e6fc Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 20 Mar 2019 20:35:54 -0400
Subject: protect against shapely error

---
 lib/stitches/auto_fill.py | 5 +++++
 1 file changed, 5 insertions(+)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index b85d335e..8435d156 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -268,6 +268,11 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
 
             graph.add_edge(*edge, weight=p1.distance(p2))
 
+        # otherwise we sometimes get exceptions like this:
+        # Exception AttributeError: "'NoneType' object has no attribute 'GEOSSTRtree_destroy'" in
+        #   <bound method STRtree.__del__ of <shapely.strtree.STRtree instance at 0x0D2BFD50>> ignored
+        del rtree
+
     return graph
 
 
-- 
cgit v1.2.3


From 4c1f1bc2bbf9277e399dc8ddbed5c0d81d930a34 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 20 Mar 2019 20:45:29 -0400
Subject: tidy up start/end travel code

---
 lib/stitches/auto_fill.py | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 8435d156..2414e937 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -360,13 +360,14 @@ def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None
     if starting_node is not ending_node:
         path.insert(0, PathEdge((starting_node, ending_node), key="initial"))
 
+    # If the starting and/or ending point falls far away from the end of a row
+    # of stitches (like can happen at the top of a square), then we need to
+    # add travel stitch to that point.
     real_start = nearest_node(travel_graph, starting_point)
-    if real_start != starting_node:
-        path.insert(0, PathEdge((real_start, starting_node), key="outline"))
+    path.insert(0, PathEdge((real_start, starting_node), key="outline"))
 
     real_end = nearest_node(travel_graph, ending_point)
-    if real_end != ending_node:
-        path.append(PathEdge((ending_node, real_end), key="outline"))
+    path.append(PathEdge((ending_node, real_end), key="outline"))
 
     return path
 
-- 
cgit v1.2.3


From 1e5733bbcdb000b27a0569b2b838cc0c04ffb461 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 20 Mar 2019 20:46:26 -0400
Subject: add first stitch

---
 lib/stitches/auto_fill.py | 4 ++++
 1 file changed, 4 insertions(+)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 2414e937..8ad9fa16 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -442,6 +442,10 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing,
 
     stitches = []
 
+    # If the very first stitch is travel, we'll omit it in travel(), so add it here.
+    if not path[0].is_segment():
+        stitches.append(InkstitchPoint(*path[0].nodes[0]))
+
     for edge in path:
         if edge.is_segment():
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last)
-- 
cgit v1.2.3


From 97ced89e8793ff608588324304e53427d180ee1e Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 20 Mar 2019 22:41:57 -0400
Subject: switch to multigraph to avoid accidentally deleting outline edges

---
 lib/stitches/auto_fill.py | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 8ad9fa16..a7ac49e7 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -149,7 +149,7 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
         # Tag each node with its index and projection.
         graph.add_node(node, index=outline_index, projection=outline_projection)
 
-    add_edges_between_outline_nodes(graph, key="outline")
+    add_edges_between_outline_nodes(graph)
 
     for node1, node2, key, data in graph.edges(keys=True, data=True):
         if key == "outline":
@@ -168,7 +168,7 @@ def tag_nodes_with_outline_and_projection(graph, shape, nodes):
         graph.add_node(node, outline=outline_index, projection=outline_projection)
 
 
-def add_edges_between_outline_nodes(graph, key=None):
+def add_edges_between_outline_nodes(graph):
     """Add edges around the outlines of the graph, connecting sequential nodes.
 
     This function assumes that all nodes in the graph are on the outline of the
@@ -188,10 +188,7 @@ def add_edges_between_outline_nodes(graph, key=None):
         # add an edge between each successive node
         for i, (node1, node2) in enumerate(zip(nodes, nodes[1:] + [nodes[0]])):
             data = dict(outline=outline_index, index=i)
-            if key:
-                graph.add_edge(node1, node2, key=key, **data)
-            else:
-                graph.add_edge(node1, node2, **data)
+            graph.add_edge(node1, node2, key="outline", **data)
 
 
 def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
@@ -215,7 +212,7 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
     calculation.
     """
 
-    graph = networkx.Graph()
+    graph = networkx.MultiGraph()
 
     # Add all the nodes from the main graph.  This will be all of the endpoints
     # of the rows of stitches.  Every node will be on the outline of the shape.
@@ -237,13 +234,13 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         tag_nodes_with_outline_and_projection(graph, shape, endpoints)
 
     add_edges_between_outline_nodes(graph)
-    for start, end in graph.edges:
+    for start, end, key in graph.edges:
         p1 = InkstitchPoint(*start)
         p2 = InkstitchPoint(*end)
 
         # Set the weight equal to triple the edge length, to encourage travel()
         # to avoid them when underpathing is enabled.
-        graph.add_edge(start, end, weight=3 * p1.distance(p2))
+        graph[start][end][key]["weight"] = 3 * p1.distance(p2)
 
     if underpath:
         segments = []
@@ -260,7 +257,7 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         interior_edges = grating1.symmetric_difference(grating2)
         for ls in interior_edges.geoms:
             p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords]
-            edge = (p1.as_tuple(), p2.as_tuple())
+            edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
 
             for segment in rtree.query(ls):
                 start, end = segment.coords
-- 
cgit v1.2.3


From 90fe0451695dafc8fff2272b122c9112dd205bd6 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 20 Mar 2019 22:43:36 -0400
Subject: don't try to end inside the shape

---
 lib/stitches/auto_fill.py | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index a7ac49e7..e9c9b9e5 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -283,9 +283,9 @@ def check_graph(graph, shape, max_stitch_length):
                                 "This most often happens because your shape is made up of multiple sections that aren't connected."))
 
 
-def nearest_node(graph, point):
+def nearest_node(nodes, point, attr=None):
     point = shgeo.Point(*point)
-    nearest = min(graph.nodes, key=lambda node: shgeo.Point(*node).distance(point))
+    nearest = min(nodes, key=lambda node: shgeo.Point(*node).distance(point))
 
     return nearest
 
@@ -363,7 +363,13 @@ def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None
     real_start = nearest_node(travel_graph, starting_point)
     path.insert(0, PathEdge((real_start, starting_node), key="outline"))
 
-    real_end = nearest_node(travel_graph, ending_point)
+    # We're willing to start inside the shape, since we'll just cover the
+    # stitches.  We have to end on the outline of the shape.  This is mostly
+    # relevant in the case that the user specifies an underlay with an inset
+    # value, because the starting point (and possibly ending point) can be
+    # inside the shape.
+    outline_nodes = [node for node, outline in travel_graph.nodes(data="outline") if outline is not None]
+    real_end = nearest_node(outline_nodes, ending_point)
     path.append(PathEdge((ending_node, real_end), key="outline"))
 
     return path
-- 
cgit v1.2.3


From eada4bed7eb5cf8671eed8e208889db88552815b Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 20 Mar 2019 22:43:54 -0400
Subject: don't let simulator preview thread crash

---
 lib/gui/simulator.py | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

(limited to 'lib')

diff --git a/lib/gui/simulator.py b/lib/gui/simulator.py
index e0d78983..c601ab66 100644
--- a/lib/gui/simulator.py
+++ b/lib/gui/simulator.py
@@ -699,7 +699,14 @@ class SimulatorPreview(Thread):
             self.update_patches()
 
     def update_patches(self):
-        patches = self.parent.generate_patches(self.refresh_needed)
+        try:
+            patches = self.parent.generate_patches(self.refresh_needed)
+        except:
+            # If something goes wrong when rendering patches, it's not great,
+            # but we don't really want the simulator thread to crash.  Instead,
+            # just swallow the exception and abort.  It'll show up when they
+            # try to actually embroider the shape.
+            return
 
         if patches and not self.refresh_needed.is_set():
             stitch_plan = patches_to_stitch_plan(patches)
-- 
cgit v1.2.3


From e7a8a3677b805d338362be6556aa702d40791fa2 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 21 Mar 2019 21:07:48 -0400
Subject: put underlay underpath checkbox in the right tab

---
 lib/elements/auto_fill.py | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

(limited to 'lib')

diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index e78943ec..a30bb6df 100644
--- a/lib/elements/auto_fill.py
+++ b/lib/elements/auto_fill.py
@@ -131,13 +131,15 @@ class AutoFill(Fill):
         return self.get_boolean_param('underpath', True)
 
     @property
-    @param('underlay_underpath',
-           _('Underpath'),
-           tooltip=_('Travel inside the shape when moving from section to section.  Underpath '
-                     'stitches avoid traveling in the direction of the row angle so that they '
-                     'are not visible.  This gives them a jagged appearance.'),
-           type='boolean',
-           default=False)
+    @param(
+        'underlay_underpath',
+        _('Underpath'),
+        tooltip=_('Travel inside the shape when moving from section to section.  Underpath '
+                  'stitches avoid traveling in the direction of the row angle so that they '
+                  'are not visible.  This gives them a jagged appearance.'),
+        group=_('AutoFill Underlay'),
+        type='boolean',
+        default=False)
     def underlay_underpath(self):
         return self.get_boolean_param('underpath', False)
 
-- 
cgit v1.2.3


From e54b9d7d8dae59321c6bfbc2de1b02e06c58466d Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 21 Mar 2019 21:25:14 -0400
Subject: default underlay underpathing to enabled as well

---
 lib/elements/auto_fill.py | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'lib')

diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index a30bb6df..bbb2aff1 100644
--- a/lib/elements/auto_fill.py
+++ b/lib/elements/auto_fill.py
@@ -139,9 +139,9 @@ class AutoFill(Fill):
                   'are not visible.  This gives them a jagged appearance.'),
         group=_('AutoFill Underlay'),
         type='boolean',
-        default=False)
+        default=True)
     def underlay_underpath(self):
-        return self.get_boolean_param('underpath', False)
+        return self.get_boolean_param('underpath', True)
 
     def shrink_or_grow_shape(self, amount):
         if amount:
-- 
cgit v1.2.3


From cf6621d0dd748376ed0fc8b138458a37d75b5180 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Fri, 22 Mar 2019 20:08:47 -0400
Subject: make travel stitch prefer the center of the shape

---
 lib/stitches/auto_fill.py | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index e9c9b9e5..39a924fe 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -238,9 +238,9 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         p1 = InkstitchPoint(*start)
         p2 = InkstitchPoint(*end)
 
-        # Set the weight equal to triple the edge length, to encourage travel()
+        # Set the weight equal to 5x the edge length, to encourage travel()
         # to avoid them when underpathing is enabled.
-        graph[start][end][key]["weight"] = 3 * p1.distance(p2)
+        graph[start][end][key]["weight"] = 5 * p1.distance(p2)
 
     if underpath:
         segments = []
@@ -263,7 +263,16 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
                 start, end = segment.coords
                 fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
 
-            graph.add_edge(*edge, weight=p1.distance(p2))
+            # The weight of a travel edge is the length of the line segment.
+            weight = p1.distance(p2)
+
+            # Give a bonus to edges that are far from the outline of the shape.
+            # This includes the outer outline and the outlines of the holes.
+            # The result is that travel stitching will tend to hug the center
+            # of the shape.
+            weight /= ls.distance(shape.boundary) + 0.1
+
+            graph.add_edge(*edge, weight=weight)
 
         # otherwise we sometimes get exceptions like this:
         # Exception AttributeError: "'NoneType' object has no attribute 'GEOSSTRtree_destroy'" in
-- 
cgit v1.2.3


From af6588a4426c0998fa51daf29d9b8f8f983bb0dd Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sun, 24 Mar 2019 14:50:49 -0400
Subject: 'fix' style

---
 lib/gui/simulator.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'lib')

diff --git a/lib/gui/simulator.py b/lib/gui/simulator.py
index c601ab66..6a2a08a9 100644
--- a/lib/gui/simulator.py
+++ b/lib/gui/simulator.py
@@ -701,7 +701,7 @@ class SimulatorPreview(Thread):
     def update_patches(self):
         try:
             patches = self.parent.generate_patches(self.refresh_needed)
-        except:
+        except:  # noqa: E722
             # If something goes wrong when rendering patches, it's not great,
             # but we don't really want the simulator thread to crash.  Instead,
             # just swallow the exception and abort.  It'll show up when they
-- 
cgit v1.2.3


From f6e6d099d2ada30cda3ee2ece9a7cf93d8442040 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sun, 24 Mar 2019 14:57:47 -0400
Subject: penalize outline edges more

---
 lib/stitches/auto_fill.py | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 39a924fe..9ccc93b2 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -238,9 +238,9 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         p1 = InkstitchPoint(*start)
         p2 = InkstitchPoint(*end)
 
-        # Set the weight equal to 5x the edge length, to encourage travel()
+        # Set the weight equal to 10x the edge length, to encourage travel()
         # to avoid them when underpathing is enabled.
-        graph[start][end][key]["weight"] = 5 * p1.distance(p2)
+        graph[start][end][key]["weight"] = 10 * p1.distance(p2)
 
     if underpath:
         segments = []
-- 
cgit v1.2.3


From f435520663d59378546426ea7263e78d51362c44 Mon Sep 17 00:00:00 2001
From: Kaalleen <36401965+kaalleen@users.noreply.github.com>
Date: Tue, 26 Mar 2019 18:24:02 +0100
Subject: Add Custom Page to Print PDF (#418)

---
 lib/extensions/print_pdf.py | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

(limited to 'lib')

diff --git a/lib/extensions/print_pdf.py b/lib/extensions/print_pdf.py
index c718fa09..4913a32a 100644
--- a/lib/extensions/print_pdf.py
+++ b/lib/extensions/print_pdf.py
@@ -353,7 +353,13 @@ class Print(InkstitchExtension):
         template = env.get_template('index.html')
 
         return template.render(
-            view={'client_overview': False, 'client_detailedview': False, 'operator_overview': True, 'operator_detailedview': True},
+            view={
+                'client_overview': False,
+                'client_detailedview': False,
+                'operator_overview': True,
+                'operator_detailedview': True,
+                'custom_page': False
+            },
             logo={'src': '', 'title': 'LOGO'},
             date=date.today(),
             client="",
-- 
cgit v1.2.3


From 8aa86f66199a2657ab01ac1a8c52ed1312be2804 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 28 Mar 2019 14:47:05 -0400
Subject: set up debug logging

---
 lib/debug.py | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)
 create mode 100644 lib/debug.py

(limited to 'lib')

diff --git a/lib/debug.py b/lib/debug.py
new file mode 100644
index 00000000..33d30d4f
--- /dev/null
+++ b/lib/debug.py
@@ -0,0 +1,84 @@
+from datetime import datetime
+import os
+import socket
+import sys
+import time
+
+
+class Debug(object):
+    def __init__(self):
+        self.last_log_time = None
+
+    def enable(self):
+        self.enable_log()
+        self.enable_debugger()
+
+    def enable_log(self):
+        self.log = self._log
+        self.raw_log = self._raw_log
+        self.log_file = open(os.path.join(os.path.dirname(os.path.dirname(__file__)), "debug.log"), "w")
+        self.log("Debug logging enabled.")
+
+    def enable_debugger(self):
+        # How to debug Ink/Stitch:
+        #
+        # 1. Install LiClipse (liclipse.com) -- no need to install Eclipse first
+        # 2. Start debug server as described here: http://www.pydev.org/manual_adv_remote_debugger.html
+        #    * follow the "Note:" to enable the debug server menu item
+        # 3. Create a file named "DEBUG" next to inkstitch.py in your git clone.
+        # 4. Run any extension and PyDev will start debugging.
+
+        try:
+            import pydevd
+        except ImportError:
+            self.log("importing pydevd failed (debugger disabled)")
+
+        # pydevd likes to shout about errors to stderr whether I want it to or not
+        with open(os.devnull, 'w') as devnull:
+            stderr = sys.stderr
+            sys.stderr = devnull
+
+            try:
+                pydevd.settrace()
+            except socket.error, error:
+                self.log("Debugging: connection to pydevd failed: %s", error)
+                self.log("Be sure to run 'Start debugging server' in PyDev to enable debugging.")
+            else:
+                self.log("Enabled PyDev debugger.")
+
+            sys.stderr = stderr
+
+    def _noop(self, *args, **kwargs):
+        pass
+
+    log = _noop
+    raw_log = _noop
+
+    def _log(self, message, *args):
+        if self.last_log_time:
+            message = "(+%s) %s" % (datetime.now() - self.last_log_time, message)
+
+        self.raw_log(message, *args)
+
+    def _raw_log(self, message, *args):
+        now = datetime.now()
+        timestamp = now.isoformat()
+        self.last_log_time = now
+
+        print >> self.log_file, timestamp, message % args
+        self.log_file.flush()
+
+    def time(self, func):
+        def decorated(*args, **kwargs):
+            self.raw_log("entering %s()", func.func_name)
+            start = time.time()
+            result = func(*args, **kwargs)
+            end = time.time()
+            self.raw_log("leaving %s(), duration = %s", func.func_name, round(end - start, 6))
+            return result
+
+        return decorated
+
+
+debug = Debug()
+enable = debug.enable
-- 
cgit v1.2.3


From 56f1d856473836cb59ff226ebb60753ca63960ed Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 28 Mar 2019 15:22:11 -0400
Subject: add timing logging for auto-fill

---
 lib/stitches/auto_fill.py | 6 ++++++
 1 file changed, 6 insertions(+)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 9ccc93b2..496ac442 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -7,6 +7,7 @@ import networkx
 from shapely import geometry as shgeo
 from shapely.strtree import STRtree
 
+from ..debug import debug
 from ..exceptions import InkstitchException
 from ..i18n import _
 from ..svg import PIXELS_PER_MM
@@ -44,6 +45,7 @@ class PathEdge(object):
         return self.key == self.SEGMENT_KEY
 
 
+@debug.time
 def auto_fill(shape,
               angle,
               row_spacing,
@@ -94,6 +96,7 @@ def project(shape, coords, outline_index):
     return outline.project(shgeo.Point(*coords))
 
 
+@debug.time
 def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
     """build a graph representation of the grating segments
 
@@ -191,6 +194,7 @@ def add_edges_between_outline_nodes(graph):
             graph.add_edge(node1, node2, key="outline", **data)
 
 
+@debug.time
 def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
     """Build a graph for travel stitches.
 
@@ -299,6 +303,7 @@ def nearest_node(nodes, point, attr=None):
     return nearest
 
 
+@debug.time
 def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None):
     """find a path that visits every grating segment exactly once
 
@@ -449,6 +454,7 @@ def travel(travel_graph, start, end, running_stitch_length, skip_last):
         return stitches[1:]
 
 
+@debug.time
 def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
     path = collapse_sequential_outline_edges(path)
 
-- 
cgit v1.2.3


From 19950150210e5a3d7a76881b96e9b8b49e663309 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 28 Mar 2019 15:52:37 -0400
Subject: add SVG debugging with LineStrings

---
 lib/debug.py        | 42 ++++++++++++++++++++++++++++++++++++++++++
 lib/svg/__init__.py |  4 ++--
 lib/svg/path.py     |  9 +++++++++
 3 files changed, 53 insertions(+), 2 deletions(-)

(limited to 'lib')

diff --git a/lib/debug.py b/lib/debug.py
index 33d30d4f..05c367f0 100644
--- a/lib/debug.py
+++ b/lib/debug.py
@@ -1,17 +1,27 @@
+import atexit
 from datetime import datetime
 import os
 import socket
 import sys
 import time
 
+from inkex import etree
+import inkex
+from simplestyle import formatStyle
+
+from svg import line_strings_to_path
+from svg.tags import INKSCAPE_GROUPMODE, INKSCAPE_LABEL
+
 
 class Debug(object):
     def __init__(self):
         self.last_log_time = None
+        self.current_layer = None
 
     def enable(self):
         self.enable_log()
         self.enable_debugger()
+        self.enable_svg()
 
     def enable_log(self):
         self.log = self._log
@@ -48,6 +58,23 @@ class Debug(object):
 
             sys.stderr = stderr
 
+    def enable_svg(self):
+        self.svg = etree.Element("svg", nsmap=inkex.NSS)
+        atexit.register(self.save_svg)
+
+    def save_svg(self):
+        tree = etree.ElementTree(self.svg)
+        with open(os.path.join(os.path.dirname(os.path.dirname(__file__)), "debug.svg"), "w") as debug_svg:
+            tree.write(debug_svg)
+
+    def add_layer(self, name="Debug"):
+        layer = etree.Element("g", {
+            INKSCAPE_GROUPMODE: "layer",
+            INKSCAPE_LABEL: name
+        })
+        self.svg.append(layer)
+        self.current_layer = layer
+
     def _noop(self, *args, **kwargs):
         pass
 
@@ -79,6 +106,21 @@ class Debug(object):
 
         return decorated
 
+    def log_svg_element(self, element):
+        if self.current_layer is None:
+            self.add_layer()
+
+        self.current_layer.append(element)
+
+    def log_line_string(self, line_string, color="#000000"):
+        """Add a Shapely LineString to the SVG log."""
+        self.log_line_strings(self, [line_string])
+
+    def log_line_strings(self, line_strings, color="#000000"):
+        path = line_strings_to_path(line_strings)
+        path.set('style', formatStyle({"stroke": color, "stroke-width": "0.3"}))
+        self.log_svg_element(path)
+
 
 debug = Debug()
 enable = debug.enable
diff --git a/lib/svg/__init__.py b/lib/svg/__init__.py
index df76c0d2..34cc4b3d 100644
--- a/lib/svg/__init__.py
+++ b/lib/svg/__init__.py
@@ -1,4 +1,4 @@
+from .guides import get_guides
+from .path import apply_transforms, get_node_transform, get_correction_transform, line_strings_to_csp, point_lists_to_csp, line_strings_to_path
 from .svg import color_block_to_point_lists, render_stitch_plan
 from .units import *
-from .path import apply_transforms, get_node_transform, get_correction_transform, line_strings_to_csp, point_lists_to_csp
-from .guides import get_guides
diff --git a/lib/svg/path.py b/lib/svg/path.py
index d2b4aee1..f0f6708b 100644
--- a/lib/svg/path.py
+++ b/lib/svg/path.py
@@ -1,3 +1,4 @@
+import cubicsuperpath
 import inkex
 import simpletransform
 
@@ -80,3 +81,11 @@ def point_lists_to_csp(point_lists):
         csp.append(subpath)
 
     return csp
+
+
+def line_strings_to_path(line_strings):
+    csp = line_strings_to_csp(line_strings)
+
+    return inkex.etree.Element("path", {
+        "d": cubicsuperpath.formatPath(csp)
+    })
-- 
cgit v1.2.3


From 90a16fb7f9a44f4274d85cc693a51be9354737ec Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Fri, 29 Mar 2019 15:03:28 -0400
Subject: more debug logging

---
 lib/debug.py              | 102 +++++++++++++++++++++++++++++++++++-----------
 lib/stitches/auto_fill.py |  10 +++++
 2 files changed, 88 insertions(+), 24 deletions(-)

(limited to 'lib')

diff --git a/lib/debug.py b/lib/debug.py
index 05c367f0..13b2f2bc 100644
--- a/lib/debug.py
+++ b/lib/debug.py
@@ -13,23 +13,32 @@ from svg import line_strings_to_path
 from svg.tags import INKSCAPE_GROUPMODE, INKSCAPE_LABEL
 
 
+def check_enabled(func):
+    def decorated(self, *args, **kwargs):
+        if self.enabled:
+            func(self, *args, **kwargs)
+
+    return decorated
+
+
 class Debug(object):
     def __init__(self):
+        self.enabled = False
         self.last_log_time = None
         self.current_layer = None
+        self.group_stack = []
 
     def enable(self):
-        self.enable_log()
-        self.enable_debugger()
-        self.enable_svg()
+        self.enabled = True
+        self.init_log()
+        self.init_debugger()
+        self.init_svg()
 
-    def enable_log(self):
-        self.log = self._log
-        self.raw_log = self._raw_log
+    def init_log(self):
         self.log_file = open(os.path.join(os.path.dirname(os.path.dirname(__file__)), "debug.log"), "w")
         self.log("Debug logging enabled.")
 
-    def enable_debugger(self):
+    def init_debugger(self):
         # How to debug Ink/Stitch:
         #
         # 1. Install LiClipse (liclipse.com) -- no need to install Eclipse first
@@ -58,7 +67,7 @@ class Debug(object):
 
             sys.stderr = stderr
 
-    def enable_svg(self):
+    def init_svg(self):
         self.svg = etree.Element("svg", nsmap=inkex.NSS)
         atexit.register(self.save_svg)
 
@@ -67,6 +76,7 @@ class Debug(object):
         with open(os.path.join(os.path.dirname(os.path.dirname(__file__)), "debug.svg"), "w") as debug_svg:
             tree.write(debug_svg)
 
+    @check_enabled
     def add_layer(self, name="Debug"):
         layer = etree.Element("g", {
             INKSCAPE_GROUPMODE: "layer",
@@ -75,19 +85,28 @@ class Debug(object):
         self.svg.append(layer)
         self.current_layer = layer
 
-    def _noop(self, *args, **kwargs):
-        pass
+    @check_enabled
+    def open_group(self, name="Group"):
+        group = etree.Element("g", {
+            INKSCAPE_LABEL: name
+        })
 
-    log = _noop
-    raw_log = _noop
+        self.log_svg_element(group)
+        self.group_stack.append(group)
 
-    def _log(self, message, *args):
+    @check_enabled
+    def close_group(self):
+        if self.group_stack:
+            self.group_stack.pop()
+
+    @check_enabled
+    def log(self, message, *args):
         if self.last_log_time:
             message = "(+%s) %s" % (datetime.now() - self.last_log_time, message)
 
         self.raw_log(message, *args)
 
-    def _raw_log(self, message, *args):
+    def raw_log(self, message, *args):
         now = datetime.now()
         timestamp = now.isoformat()
         self.last_log_time = now
@@ -97,30 +116,65 @@ class Debug(object):
 
     def time(self, func):
         def decorated(*args, **kwargs):
-            self.raw_log("entering %s()", func.func_name)
-            start = time.time()
+            if self.enabled:
+                self.raw_log("entering %s()", func.func_name)
+                start = time.time()
+
             result = func(*args, **kwargs)
-            end = time.time()
-            self.raw_log("leaving %s(), duration = %s", func.func_name, round(end - start, 6))
+
+            if self.enabled:
+                end = time.time()
+                self.raw_log("leaving %s(), duration = %s", func.func_name, round(end - start, 6))
+
             return result
 
         return decorated
 
+    @check_enabled
     def log_svg_element(self, element):
         if self.current_layer is None:
             self.add_layer()
 
-        self.current_layer.append(element)
+        if self.group_stack:
+            self.group_stack[-1].append(element)
+        else:
+            self.current_layer.append(element)
 
-    def log_line_string(self, line_string, color="#000000"):
+    @check_enabled
+    def log_line_string(self, line_string, name=None, color=None):
         """Add a Shapely LineString to the SVG log."""
-        self.log_line_strings(self, [line_string])
+        self.log_line_strings([line_string], name, color)
 
-    def log_line_strings(self, line_strings, color="#000000"):
+    @check_enabled
+    def log_line_strings(self, line_strings, name=None, color=None):
         path = line_strings_to_path(line_strings)
-        path.set('style', formatStyle({"stroke": color, "stroke-width": "0.3"}))
+        path.set('style', formatStyle({"stroke": color or "#000000", "stroke-width": "0.3"}))
+
+        if name is not None:
+            path.set(INKSCAPE_LABEL, name)
+
         self.log_svg_element(path)
 
+    @check_enabled
+    def log_line(self, start, end, name="line", color=None):
+        self.log_svg_element(etree.Element("path", {
+            "d": "M%s,%s %s,%s" % (start + end),
+            "style": formatStyle({"stroke": color or "#000000", "stroke-width": "0.3"}),
+            INKSCAPE_LABEL: name
+        }))
+
+    @check_enabled
+    def log_graph(self, graph, name="Graph", color=None):
+        self.open_group(name)
+
+        for edge in graph.edges:
+            self.log_line(edge[0], edge[1], color=color)
+
+        self.close_group()
+
 
 debug = Debug()
-enable = debug.enable
+
+
+def enable():
+    debug.enable()
diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 496ac442..2a48b263 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -130,6 +130,8 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
     path must exist.
     """
 
+    debug.add_layer("auto-fill fill stitch")
+
     # Convert the shape into a set of parallel line segments.
     rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing)
     segments = [segment for row in rows_of_segments for segment in row]
@@ -160,6 +162,8 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
             if data['index'] % 2 == 0:
                 graph.add_edge(node1, node2, key="extra")
 
+    debug.log_graph(graph, "graph")
+
     return graph
 
 
@@ -228,6 +232,10 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
         grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
 
+        debug.add_layer("auto-fill travel")
+        debug.log_line_strings(grating1, "grating1")
+        debug.log_line_strings(grating2, "grating2")
+
         # We'll add the endpoints of the crosshatch grating lines too  These
         # will all be on the outline of the shape.  This will ensure that a
         # path traveling inside the shape can reach its target on the outline,
@@ -283,6 +291,8 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         #   <bound method STRtree.__del__ of <shapely.strtree.STRtree instance at 0x0D2BFD50>> ignored
         del rtree
 
+    debug.log_graph(graph, "travel graph")
+
     return graph
 
 
-- 
cgit v1.2.3


From 513850c975368f0e323e3cfc173398081245127a Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Fri, 29 Mar 2019 15:42:11 -0400
Subject: add vertical travel edges for less jagged travel paths

---
 lib/debug.py              |  15 +++++-
 lib/stitches/auto_fill.py | 131 ++++++++++++++++++++++++++++------------------
 2 files changed, 95 insertions(+), 51 deletions(-)

(limited to 'lib')

diff --git a/lib/debug.py b/lib/debug.py
index 13b2f2bc..fa3bd606 100644
--- a/lib/debug.py
+++ b/lib/debug.py
@@ -1,4 +1,5 @@
 import atexit
+from contextlib import contextmanager
 from datetime import datetime
 import os
 import socket
@@ -80,7 +81,8 @@ class Debug(object):
     def add_layer(self, name="Debug"):
         layer = etree.Element("g", {
             INKSCAPE_GROUPMODE: "layer",
-            INKSCAPE_LABEL: name
+            INKSCAPE_LABEL: name,
+            "style": "display: none"
         })
         self.svg.append(layer)
         self.current_layer = layer
@@ -172,6 +174,17 @@ class Debug(object):
 
         self.close_group()
 
+    @contextmanager
+    def time_this(self, label="code block"):
+        if self.enabled:
+            start = time.time()
+            self.raw_log("begin %s", label)
+
+        yield
+
+        if self.enabled:
+            self.raw_log("completed %s, duration = %s", label, time.time() - start)
+
 
 debug = Debug()
 
diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 2a48b263..88a54f0b 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -5,6 +5,7 @@ import math
 
 import networkx
 from shapely import geometry as shgeo
+from shapely.ops import snap
 from shapely.strtree import STRtree
 
 from ..debug import debug
@@ -146,21 +147,7 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing):
         graph.add_edge(*segment, key="segment", underpath_edges=[])
 
     tag_nodes_with_outline_and_projection(graph, shape, graph.nodes())
-
-    for node in graph.nodes():
-        outline_index = which_outline(shape, node)
-        outline_projection = project(shape, node, outline_index)
-
-        # Tag each node with its index and projection.
-        graph.add_node(node, index=outline_index, projection=outline_projection)
-
-    add_edges_between_outline_nodes(graph)
-
-    for node1, node2, key, data in graph.edges(keys=True, data=True):
-        if key == "outline":
-            # duplicate every other edge
-            if data['index'] % 2 == 0:
-                graph.add_edge(node1, node2, key="extra")
+    add_edges_between_outline_nodes(graph, duplicate_every_other=True)
 
     debug.log_graph(graph, "graph")
 
@@ -175,7 +162,7 @@ def tag_nodes_with_outline_and_projection(graph, shape, nodes):
         graph.add_node(node, outline=outline_index, projection=outline_projection)
 
 
-def add_edges_between_outline_nodes(graph):
+def add_edges_between_outline_nodes(graph, duplicate_every_other=False):
     """Add edges around the outlines of the graph, connecting sequential nodes.
 
     This function assumes that all nodes in the graph are on the outline of the
@@ -197,6 +184,9 @@ def add_edges_between_outline_nodes(graph):
             data = dict(outline=outline_index, index=i)
             graph.add_edge(node1, node2, key="outline", **data)
 
+            if i % 2 == 0:
+                graph.add_edge(node1, node2, key="extra", **data)
+
 
 @debug.time
 def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
@@ -210,14 +200,15 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
     edges.
 
     If underpath is True, we'll also allow travel inside the shape.  We'll
-    fill the shape with a cross-hatched grid of lines 2mm apart, at ±45
-    degrees from the fill stitch angle.  This will ensure that travel stitches
-    won't be visible and won't disrupt the fill stitch.
+    fill the shape with a cross-hatched grid of lines.  We'll construct a
+    graph from them and use a shortest path algorithm to construct travel
+    stitch paths in travel().
 
     When underpathing, we "encourage" the travel() function to travel inside
     the shape rather than on the boundary.  We do this by weighting the
     boundary edges extra so that they're more "expensive" in the shortest path
-    calculation.
+    calculation.  We also weight the interior edges extra proportional to
+    how close they are to the boundary.
     """
 
     graph = networkx.MultiGraph()
@@ -228,33 +219,23 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
     graph.add_nodes_from(fill_stitch_graph.nodes(data=True))
 
     if underpath:
-        # These two MultiLineStrings will make up the cross-hatched grid.
-        grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
-        grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
-
-        debug.add_layer("auto-fill travel")
-        debug.log_line_strings(grating1, "grating1")
-        debug.log_line_strings(grating2, "grating2")
-
-        # We'll add the endpoints of the crosshatch grating lines too  These
-        # will all be on the outline of the shape.  This will ensure that a
-        # path traveling inside the shape can reach its target on the outline,
-        # which will be one of the points added above.
-        endpoints = [coord for mls in (grating1, grating2)
-                     for ls in mls
-                     for coord in ls.coords]
-        tag_nodes_with_outline_and_projection(graph, shape, endpoints)
+        boundary_points, travel_edges = build_travel_edges(shape, fill_stitch_angle)
 
-    add_edges_between_outline_nodes(graph)
-    for start, end, key in graph.edges:
-        p1 = InkstitchPoint(*start)
-        p2 = InkstitchPoint(*end)
+        # This will ensure that a path traveling inside the shape can reach its
+        # target on the outline, which will be one of the points added above.
+        tag_nodes_with_outline_and_projection(graph, shape, boundary_points)
 
-        # Set the weight equal to 10x the edge length, to encourage travel()
-        # to avoid them when underpathing is enabled.
-        graph[start][end][key]["weight"] = 10 * p1.distance(p2)
+    add_edges_between_outline_nodes(graph)
 
     if underpath:
+        for start, end, key in graph.edges:
+            p1 = InkstitchPoint(*start)
+            p2 = InkstitchPoint(*end)
+
+            # Set the weight equal to 10x the edge length, to encourage travel()
+            # to avoid them.
+            graph[start][end][key]["weight"] = 10 * p1.distance(p2)
+
         segments = []
         for start, end, key, data in fill_stitch_graph.edges(keys=True, data=True):
             if key == 'segment':
@@ -264,14 +245,17 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         # allows for building a set of shapes and then efficiently testing
         # the set for intersection.  This allows us to do blazing-fast
         # queries of which line segments overlap each underpath edge.
-        rtree = STRtree(segments)
+        strtree = STRtree(segments)
+
+        # This makes the distance calculations below a bit faster.  We're
+        # not looking for high precision anyway.
+        outline = shape.boundary.simplify(0.5 * PIXELS_PER_MM, preserve_topology=False)
 
-        interior_edges = grating1.symmetric_difference(grating2)
-        for ls in interior_edges.geoms:
+        for ls in travel_edges:
             p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords]
             edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
 
-            for segment in rtree.query(ls):
+            for segment in strtree.query(ls):
                 start, end = segment.coords
                 fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
 
@@ -282,20 +266,67 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
             # This includes the outer outline and the outlines of the holes.
             # The result is that travel stitching will tend to hug the center
             # of the shape.
-            weight /= ls.distance(shape.boundary) + 0.1
+            weight /= ls.distance(outline) + 0.1
 
             graph.add_edge(*edge, weight=weight)
 
-        # otherwise we sometimes get exceptions like this:
+        # without this, we sometimes get exceptions like this:
         # Exception AttributeError: "'NoneType' object has no attribute 'GEOSSTRtree_destroy'" in
         #   <bound method STRtree.__del__ of <shapely.strtree.STRtree instance at 0x0D2BFD50>> ignored
-        del rtree
+        del strtree
 
     debug.log_graph(graph, "travel graph")
 
     return graph
 
 
+def build_travel_edges(shape, fill_angle):
+    """Given a graph, compute the interior travel edges.
+
+    We want to fill the shape with a grid of line segments that can be used for
+    travel stitch routing.  Our goals:
+
+      * not too many edges so that the shortest path algorithm is speedy
+      * don't travel in the direction of the fill stitch rows so that the
+        travel stitch doesn't visually disrupt the fill stitch pattern
+
+    To do this, we'll fill the shape with three gratings: one at +45 degrees
+    from the fill stitch angle, one at -45 degrees, and one at +90 degrees.
+    The pattern looks like this:
+
+    /|\|/|\|/|\
+    \|/|\|/|\|/
+    /|\|/|\|/|\
+    \|/|\|/|\|/
+
+    Returns: (endpoints, edges)
+        endpoints - the points on travel edges that intersect with the boundary
+                    of the shape
+        edges     - the line segments we can travel on, as individual LineString
+                    instances
+    """
+
+    grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
+    grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
+    grating3 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 2, math.sqrt(2) * PIXELS_PER_MM))))
+
+    debug.add_layer("auto-fill travel")
+    debug.log_line_strings(grating1, "grating1")
+    debug.log_line_strings(grating2, "grating2")
+    debug.log_line_strings(grating3, "grating3")
+
+    endpoints = [coord for mls in (grating1, grating2, grating3)
+                 for ls in mls
+                 for coord in ls.coords]
+
+    diagonal_edges = grating1.symmetric_difference(grating2)
+
+    # without this, floating point inaccuracies prevent the intersection points from lining up perfectly.
+    vertical_edges = snap(grating3.difference(grating1), diagonal_edges, 0.005)
+
+    return endpoints, chain(diagonal_edges, vertical_edges)
+
+
 def check_graph(graph, shape, max_stitch_length):
     if networkx.is_empty(graph) or not networkx.is_eulerian(graph):
         if shape.area < max_stitch_length ** 2:
-- 
cgit v1.2.3


From 284ef6afcb5e4604260f94566f2881ec2d84fe71 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Fri, 29 Mar 2019 20:24:24 -0400
Subject: avoid parsing forward slashes in docstring

---
 lib/stitches/auto_fill.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 88a54f0b..917b09a8 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -281,7 +281,7 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
 
 
 def build_travel_edges(shape, fill_angle):
-    """Given a graph, compute the interior travel edges.
+    r"""Given a graph, compute the interior travel edges.
 
     We want to fill the shape with a grid of line segments that can be used for
     travel stitch routing.  Our goals:
-- 
cgit v1.2.3


From 37722b7ddf8b1f612408bea783d9ac5455f7b9fd Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sat, 30 Mar 2019 21:56:39 -0400
Subject: fix underlay underpath checkbox

---
 lib/elements/auto_fill.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'lib')

diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index bbb2aff1..62d3493c 100644
--- a/lib/elements/auto_fill.py
+++ b/lib/elements/auto_fill.py
@@ -141,7 +141,7 @@ class AutoFill(Fill):
         type='boolean',
         default=True)
     def underlay_underpath(self):
-        return self.get_boolean_param('underpath', True)
+        return self.get_boolean_param('underlay_underpath', True)
 
     def shrink_or_grow_shape(self, amount):
         if amount:
-- 
cgit v1.2.3


From f5f0ce49a8db1445feba91e629e6b02584dbd05b Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Sat, 30 Mar 2019 22:20:46 -0400
Subject: fix 'too many values to unpack' exception

---
 lib/stitches/auto_fill.py | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 917b09a8..8bfbd092 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -252,7 +252,12 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
         outline = shape.boundary.simplify(0.5 * PIXELS_PER_MM, preserve_topology=False)
 
         for ls in travel_edges:
-            p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords]
+            # In most cases, ls will be a simple line segment.  If we're
+            # unlucky, in rare cases we can get a tiny little extra squiggle
+            # at the end that can be ignored.
+            points = [InkstitchPoint(*coord) for coord in ls.coords]
+            p1, p2 = points[0], points[-1]
+
             edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
 
             for segment in strtree.query(ls):
-- 
cgit v1.2.3


From 211561eabc1444135e0a000d8ec4ba822c2ebbd5 Mon Sep 17 00:00:00 2001
From: Kaalleen <36401965+kaalleen@users.noreply.github.com>
Date: Tue, 2 Apr 2019 06:27:33 +0200
Subject: simulator stitch box improvement (#402)

---
 lib/gui/simulator.py | 33 ++++++++++++++++++++++++++-------
 1 file changed, 26 insertions(+), 7 deletions(-)

(limited to 'lib')

diff --git a/lib/gui/simulator.py b/lib/gui/simulator.py
index e0d78983..d64e50c0 100644
--- a/lib/gui/simulator.py
+++ b/lib/gui/simulator.py
@@ -74,8 +74,12 @@ class ControlPanel(wx.Panel):
         self.slider = wx.Slider(self, -1, value=1, minValue=1, maxValue=2,
                                 style=wx.SL_HORIZONTAL | wx.SL_LABELS)
         self.slider.Bind(wx.EVT_SLIDER, self.on_slider)
-        self.stitchBox = IntCtrl(self, -1, value=1, min=1, max=2, limited=True, allow_none=False)
-        self.stitchBox.Bind(wx.EVT_TEXT, self.on_stitch_box)
+        self.stitchBox = IntCtrl(self, -1, value=1, min=1, max=2, limited=True, allow_none=True, style=wx.TE_PROCESS_ENTER)
+        self.stitchBox.Bind(wx.EVT_LEFT_DOWN, self.on_stitch_box_focus)
+        self.stitchBox.Bind(wx.EVT_SET_FOCUS, self.on_stitch_box_focus)
+        self.stitchBox.Bind(wx.EVT_TEXT_ENTER, self.on_stitch_box_focusout)
+        self.stitchBox.Bind(wx.EVT_KILL_FOCUS, self.on_stitch_box_focusout)
+        self.Bind(wx.EVT_LEFT_DOWN, self.on_stitch_box_focusout)
 
         # Layout
         self.vbSizer = vbSizer = wx.BoxSizer(wx.VERTICAL)
@@ -120,15 +124,15 @@ class ControlPanel(wx.Panel):
             (wx.ACCEL_NORMAL, wx.WXK_SPACE, self.on_pause_start_button),
             (wx.ACCEL_NORMAL, ord('q'), self.animation_quit)]
 
-        accel_entries = []
+        self.accel_entries = []
 
         for shortcut_key in shortcut_keys:
             eventId = wx.NewId()
-            accel_entries.append((shortcut_key[0], shortcut_key[1], eventId))
+            self.accel_entries.append((shortcut_key[0], shortcut_key[1], eventId))
             self.Bind(wx.EVT_MENU, shortcut_key[2], id=eventId)
 
-        accel_table = wx.AcceleratorTable(accel_entries)
-        self.SetAcceleratorTable(accel_table)
+        self.accel_table = wx.AcceleratorTable(self.accel_entries)
+        self.SetAcceleratorTable(self.accel_table)
         self.SetFocus()
 
     def set_drawing_panel(self, drawing_panel):
@@ -186,6 +190,8 @@ class ControlPanel(wx.Panel):
         if self.drawing_panel:
             self.drawing_panel.set_current_stitch(stitch)
 
+        self.parent.SetFocus()
+
     def on_current_stitch(self, stitch, command):
         if self.current_stitch != stitch:
             self.current_stitch = stitch
@@ -193,8 +199,20 @@ class ControlPanel(wx.Panel):
             self.stitchBox.SetValue(stitch)
             self.statusbar.SetStatusText(COMMAND_NAMES[command], 1)
 
-    def on_stitch_box(self, event):
+    def on_stitch_box_focus(self, event):
+        self.animation_pause()
+        self.SetAcceleratorTable(wx.AcceleratorTable([]))
+        event.Skip()
+
+    def on_stitch_box_focusout(self, event):
+        self.SetAcceleratorTable(self.accel_table)
         stitch = self.stitchBox.GetValue()
+        self.parent.SetFocus()
+
+        if stitch is None:
+            stitch = 1
+            self.stitchBox.SetValue(1)
+
         self.slider.SetValue(stitch)
 
         if self.drawing_panel:
@@ -629,6 +647,7 @@ class EmbroiderySimulator(wx.Frame):
         if self.on_close_hook:
             self.on_close_hook()
 
+        self.SetFocus()
         self.Destroy()
 
     def go(self):
-- 
cgit v1.2.3


From 1f7b69980c439c2be00033f566de38c35468782c Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 4 Apr 2019 19:57:40 -0400
Subject: render graphs as a single path to avoid killing inkscape

---
 lib/debug.py | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

(limited to 'lib')

diff --git a/lib/debug.py b/lib/debug.py
index fa3bd606..6ce67697 100644
--- a/lib/debug.py
+++ b/lib/debug.py
@@ -167,12 +167,16 @@ class Debug(object):
 
     @check_enabled
     def log_graph(self, graph, name="Graph", color=None):
-        self.open_group(name)
+        d = ""
 
         for edge in graph.edges:
-            self.log_line(edge[0], edge[1], color=color)
+            d += "M%s,%s %s,%s" % (edge[0] + edge[1])
 
-        self.close_group()
+        self.log_svg_element(etree.Element("path", {
+            "d": d,
+            "style": formatStyle({"stroke": color or "#000000", "stroke-width": "0.3"}),
+            INKSCAPE_LABEL: name
+        }))
 
     @contextmanager
     def time_this(self, label="code block"):
-- 
cgit v1.2.3


From f204366347d6847b4d5699efa33fd5858624cfd6 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Thu, 4 Apr 2019 19:58:35 -0400
Subject: try harder to avoid traveling around the border

---
 lib/stitches/auto_fill.py | 29 ++++++++++++++++++++++-------
 1 file changed, 22 insertions(+), 7 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 8bfbd092..1300a4df 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -232,9 +232,9 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
             p1 = InkstitchPoint(*start)
             p2 = InkstitchPoint(*end)
 
-            # Set the weight equal to 10x the edge length, to encourage travel()
+            # Set the weight equal to 5x the edge length, to encourage travel()
             # to avoid them.
-            graph[start][end][key]["weight"] = 10 * p1.distance(p2)
+            graph[start][end][key]["weight"] = 5 * p1.distance(p2)
 
         segments = []
         for start, end, key, data in fill_stitch_graph.edges(keys=True, data=True):
@@ -261,8 +261,12 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
             edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
 
             for segment in strtree.query(ls):
-                start, end = segment.coords
-                fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
+                # It seems like the STRTree only gives an approximate answer of
+                # segments that _might_ intersect ls.  Refining the result is
+                # necessary but the STRTree still saves us a ton of time.
+                if segment.crosses(ls):
+                    start, end = segment.coords
+                    fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
 
             # The weight of a travel edge is the length of the line segment.
             weight = p1.distance(p2)
@@ -311,9 +315,20 @@ def build_travel_edges(shape, fill_angle):
                     instances
     """
 
-    grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_angle + math.pi / 4, 2 * PIXELS_PER_MM))))
-    grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 4, 2 * PIXELS_PER_MM))))
-    grating3 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 2, math.sqrt(2) * PIXELS_PER_MM))))
+    # If the shape is smaller, we'll have less room to maneuver and it's more likely
+    # we'll travel around the outside border of the shape.  Counteract that by making
+    # the grid denser.
+    if shape.area < 10000:
+        scale = 0.5
+    else:
+        scale = 1.0
+
+    grating1 = shgeo.MultiLineString(
+        list(chain(*intersect_region_with_grating(shape, fill_angle + math.pi / 4, scale * 2 * PIXELS_PER_MM))))
+    grating2 = shgeo.MultiLineString(
+        list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 4, scale * 2 * PIXELS_PER_MM))))
+    grating3 = shgeo.MultiLineString(
+        list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 2, scale * math.sqrt(2) * PIXELS_PER_MM))))
 
     debug.add_layer("auto-fill travel")
     debug.log_line_strings(grating1, "grating1")
-- 
cgit v1.2.3


From c94a28756d805aad2ec6bda946e37099ce46310d Mon Sep 17 00:00:00 2001
From: Kaalleen <36401965+kaalleen@users.noreply.github.com>
Date: Sun, 7 Apr 2019 21:00:14 +0200
Subject: simulate needle penetration points

---
 lib/gui/simulator.py | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

(limited to 'lib')

diff --git a/lib/gui/simulator.py b/lib/gui/simulator.py
index d64e50c0..3c51c7f2 100644
--- a/lib/gui/simulator.py
+++ b/lib/gui/simulator.py
@@ -68,6 +68,9 @@ class ControlPanel(wx.Panel):
         self.restartBtn = wx.Button(self, -1, label=_('Restart'))
         self.restartBtn.Bind(wx.EVT_BUTTON, self.animation_restart)
         self.restartBtn.SetToolTip(_('Restart (R)'))
+        self.nppBtn = wx.ToggleButton(self, -1, label=_('O'))
+        self.nppBtn.Bind(wx.EVT_TOGGLEBUTTON, self.toggle_npp)
+        self.nppBtn.SetToolTip(_('Display needle penetration point (O)'))
         self.quitBtn = wx.Button(self, -1, label=_('Quit'))
         self.quitBtn.Bind(wx.EVT_BUTTON, self.animation_quit)
         self.quitBtn.SetToolTip(_('Quit (Q)'))
@@ -95,6 +98,7 @@ class ControlPanel(wx.Panel):
         hbSizer2.Add(self.directionBtn, 0, wx.EXPAND | wx.ALL, 2)
         hbSizer2.Add(self.pauseBtn, 0, wx.EXPAND | wx.ALL, 2)
         hbSizer2.Add(self.restartBtn, 0, wx.EXPAND | wx.ALL, 2)
+        hbSizer2.Add(self.nppBtn, 0, wx.EXPAND | wx.ALL, 2)
         hbSizer2.Add(self.quitBtn, 0, wx.EXPAND | wx.ALL, 2)
         vbSizer.Add(hbSizer2, 0, wx.EXPAND | wx.ALL, 3)
         self.SetSizerAndFit(vbSizer)
@@ -120,6 +124,7 @@ class ControlPanel(wx.Panel):
             (wx.ACCEL_NORMAL, wx.WXK_SUBTRACT, self.animation_one_stitch_backward),
             (wx.ACCEL_NORMAL, wx.WXK_NUMPAD_SUBTRACT, self.animation_one_stitch_backward),
             (wx.ACCEL_NORMAL, ord('r'), self.animation_restart),
+            (wx.ACCEL_NORMAL, ord('o'), self.on_toggle_npp_shortcut),
             (wx.ACCEL_NORMAL, ord('p'), self.on_pause_start_button),
             (wx.ACCEL_NORMAL, wx.WXK_SPACE, self.on_pause_start_button),
             (wx.ACCEL_NORMAL, ord('q'), self.animation_quit)]
@@ -259,6 +264,15 @@ class ControlPanel(wx.Panel):
     def animation_restart(self, event):
         self.drawing_panel.restart()
 
+    def on_toggle_npp_shortcut(self, event):
+        self.nppBtn.SetValue(not self.nppBtn.GetValue())
+        self.toggle_npp(event)
+
+    def toggle_npp(self, event):
+        if self.pauseBtn.GetLabel() == _('Start'):
+            stitch = self.stitchBox.GetValue()
+            self.drawing_panel.set_current_stitch(stitch)
+
 
 class DrawingPanel(wx.Panel):
     """"""
@@ -364,11 +378,13 @@ class DrawingPanel(wx.Panel):
                 stitch += len(stitches)
                 if len(stitches) > 1:
                     canvas.DrawLines(stitches)
+                    self.draw_needle_penetration_points(canvas, pen, stitches)
                 last_stitch = stitches[-1]
             else:
                 stitches = stitches[:self.current_stitch - stitch]
                 if len(stitches) > 1:
                     canvas.DrawLines(stitches)
+                    self.draw_needle_penetration_points(canvas, pen, stitches)
                 last_stitch = stitches[-1]
                 break
         self.last_frame_duration = time.time() - start
@@ -383,6 +399,12 @@ class DrawingPanel(wx.Panel):
             canvas.DrawLines(((x - crosshair_radius, y), (x + crosshair_radius, y)))
             canvas.DrawLines(((x, y - crosshair_radius), (x, y + crosshair_radius)))
 
+    def draw_needle_penetration_points(self, canvas, pen, stitches):
+        if self.control_panel.nppBtn.GetValue():
+            npp_pen = wx.Pen(pen.GetColour(), width=int(0.3 * PIXELS_PER_MM * self.PIXEL_DENSITY))
+            canvas.SetPen(npp_pen)
+            canvas.StrokeLineSegments(stitches, stitches)
+
     def clear(self):
         dc = wx.ClientDC(self)
         dc.Clear()
@@ -719,6 +741,14 @@ class SimulatorPreview(Thread):
 
     def update_patches(self):
         patches = self.parent.generate_patches(self.refresh_needed)
+        try:
+            patches = self.parent.generate_patches(self.refresh_needed)
+        except:  # noqa: E722
+            # If something goes wrong when rendering patches, it's not great,
+            # but we don't really want the simulator thread to crash.  Instead,
+            # just swallow the exception and abort.  It'll show up when they
+            # try to actually embroider the shape.
+            return
 
         if patches and not self.refresh_needed.is_set():
             stitch_plan = patches_to_stitch_plan(patches)
-- 
cgit v1.2.3


From 92541eb760eca6df14abca194e087be5183ffdfd Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 9 Apr 2019 23:47:24 -0400
Subject: split up long function

---
 lib/stitches/auto_fill.py | 142 ++++++++++++++++++++++++++--------------------
 1 file changed, 81 insertions(+), 61 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 1300a4df..7d231953 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -228,67 +228,90 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath):
     add_edges_between_outline_nodes(graph)
 
     if underpath:
-        for start, end, key in graph.edges:
-            p1 = InkstitchPoint(*start)
-            p2 = InkstitchPoint(*end)
-
-            # Set the weight equal to 5x the edge length, to encourage travel()
-            # to avoid them.
-            graph[start][end][key]["weight"] = 5 * p1.distance(p2)
-
-        segments = []
-        for start, end, key, data in fill_stitch_graph.edges(keys=True, data=True):
-            if key == 'segment':
-                segments.append(shgeo.LineString((start, end)))
-
-        # The shapely documentation is pretty unclear on this.  An STRtree
-        # allows for building a set of shapes and then efficiently testing
-        # the set for intersection.  This allows us to do blazing-fast
-        # queries of which line segments overlap each underpath edge.
-        strtree = STRtree(segments)
-
-        # This makes the distance calculations below a bit faster.  We're
-        # not looking for high precision anyway.
-        outline = shape.boundary.simplify(0.5 * PIXELS_PER_MM, preserve_topology=False)
-
-        for ls in travel_edges:
-            # In most cases, ls will be a simple line segment.  If we're
-            # unlucky, in rare cases we can get a tiny little extra squiggle
-            # at the end that can be ignored.
-            points = [InkstitchPoint(*coord) for coord in ls.coords]
-            p1, p2 = points[0], points[-1]
-
-            edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
-
-            for segment in strtree.query(ls):
-                # It seems like the STRTree only gives an approximate answer of
-                # segments that _might_ intersect ls.  Refining the result is
-                # necessary but the STRTree still saves us a ton of time.
-                if segment.crosses(ls):
-                    start, end = segment.coords
-                    fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
-
-            # The weight of a travel edge is the length of the line segment.
-            weight = p1.distance(p2)
-
-            # Give a bonus to edges that are far from the outline of the shape.
-            # This includes the outer outline and the outlines of the holes.
-            # The result is that travel stitching will tend to hug the center
-            # of the shape.
-            weight /= ls.distance(outline) + 0.1
-
-            graph.add_edge(*edge, weight=weight)
-
-        # without this, we sometimes get exceptions like this:
-        # Exception AttributeError: "'NoneType' object has no attribute 'GEOSSTRtree_destroy'" in
-        #   <bound method STRtree.__del__ of <shapely.strtree.STRtree instance at 0x0D2BFD50>> ignored
-        del strtree
+        process_travel_edges(graph, fill_stitch_graph, shape, travel_edges)
 
     debug.log_graph(graph, "travel graph")
 
     return graph
 
 
+def weight_edges_by_length(graph, multiplier=1):
+    for start, end, key in graph.edges:
+        p1 = InkstitchPoint(*start)
+        p2 = InkstitchPoint(*end)
+
+        graph[start][end][key]["weight"] = multiplier * p1.distance(p2)
+
+
+def get_segments(graph):
+    segments = []
+    for start, end, key, data in graph.edges(keys=True, data=True):
+        if key == 'segment':
+            segments.append(shgeo.LineString((start, end)))
+
+    return segments
+
+
+def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges):
+    """Weight the interior edges and pre-calculate intersection with fill stitch rows."""
+
+    # Set the weight equal to 5x the edge length, to encourage travel()
+    # to avoid them.
+    weight_edges_by_length(graph, 5)
+
+    segments = get_segments(fill_stitch_graph)
+
+    # The shapely documentation is pretty unclear on this.  An STRtree
+    # allows for building a set of shapes and then efficiently testing
+    # the set for intersection.  This allows us to do blazing-fast
+    # queries of which line segments overlap each underpath edge.
+    strtree = STRtree(segments)
+
+    # This makes the distance calculations below a bit faster.  We're
+    # not looking for high precision anyway.
+    outline = shape.boundary.simplify(0.5 * PIXELS_PER_MM, preserve_topology=False)
+
+    for ls in travel_edges:
+        # In most cases, ls will be a simple line segment.  If we're
+        # unlucky, in rare cases we can get a tiny little extra squiggle
+        # at the end that can be ignored.
+        points = [InkstitchPoint(*coord) for coord in ls.coords]
+        p1, p2 = points[0], points[-1]
+
+        edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
+
+        for segment in strtree.query(ls):
+            # It seems like the STRTree only gives an approximate answer of
+            # segments that _might_ intersect ls.  Refining the result is
+            # necessary but the STRTree still saves us a ton of time.
+            if segment.crosses(ls):
+                start, end = segment.coords
+                fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
+
+        # The weight of a travel edge is the length of the line segment.
+        weight = p1.distance(p2)
+
+        # Give a bonus to edges that are far from the outline of the shape.
+        # This includes the outer outline and the outlines of the holes.
+        # The result is that travel stitching will tend to hug the center
+        # of the shape.
+        weight /= ls.distance(outline) + 0.1
+
+        graph.add_edge(*edge, weight=weight)
+
+    # without this, we sometimes get exceptions like this:
+    # Exception AttributeError: "'NoneType' object has no attribute 'GEOSSTRtree_destroy'" in
+    #   <bound method STRtree.__del__ of <shapely.strtree.STRtree instance at 0x0D2BFD50>> ignored
+    del strtree
+
+
+def travel_grating(shape, angle, row_spacing):
+    rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing)
+    segments = list(chain(*rows_of_segments))
+
+    return shgeo.MultiLineString(segments)
+
+
 def build_travel_edges(shape, fill_angle):
     r"""Given a graph, compute the interior travel edges.
 
@@ -323,12 +346,9 @@ def build_travel_edges(shape, fill_angle):
     else:
         scale = 1.0
 
-    grating1 = shgeo.MultiLineString(
-        list(chain(*intersect_region_with_grating(shape, fill_angle + math.pi / 4, scale * 2 * PIXELS_PER_MM))))
-    grating2 = shgeo.MultiLineString(
-        list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 4, scale * 2 * PIXELS_PER_MM))))
-    grating3 = shgeo.MultiLineString(
-        list(chain(*intersect_region_with_grating(shape, fill_angle - math.pi / 2, scale * math.sqrt(2) * PIXELS_PER_MM))))
+    grating1 = travel_grating(shape, fill_angle + math.pi / 4, scale * 2 * PIXELS_PER_MM)
+    grating2 = travel_grating(shape, fill_angle - math.pi / 4, scale * 2 * PIXELS_PER_MM)
+    grating3 = travel_grating(shape, fill_angle - math.pi / 2, scale * math.sqrt(2) * PIXELS_PER_MM)
 
     debug.add_layer("auto-fill travel")
     debug.log_line_strings(grating1, "grating1")
-- 
cgit v1.2.3


From a766e4e40858cb7954c8c6ea4a1a9de8d31ee054 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Tue, 9 Apr 2019 23:49:54 -0400
Subject: make error message more readable

---
 lib/stitches/auto_fill.py | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 7d231953..84f10d45 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -370,11 +370,13 @@ def build_travel_edges(shape, fill_angle):
 def check_graph(graph, shape, max_stitch_length):
     if networkx.is_empty(graph) or not networkx.is_eulerian(graph):
         if shape.area < max_stitch_length ** 2:
-            raise InvalidPath(_("This shape is so small that it cannot be filled with rows of stitches.  "
-                                "It would probably look best as a satin column or running stitch."))
+            message = "This shape is so small that it cannot be filled with rows of stitches.  " \
+                      "It would probably look best as a satin column or running stitch."
+            raise InvalidPath(_(message))
         else:
-            raise InvalidPath(_("Cannot parse shape.  "
-                                "This most often happens because your shape is made up of multiple sections that aren't connected."))
+            message = "Cannot parse shape.  " \
+                      "This most often happens because your shape is made up of multiple sections that aren't connected."
+            raise InvalidPath(_(message))
 
 
 def nearest_node(nodes, point, attr=None):
-- 
cgit v1.2.3


From 9d4441b7009564a57425ab0ab73a70be5b8dabf4 Mon Sep 17 00:00:00 2001
From: Lex Neva <github.com@lexneva.name>
Date: Wed, 10 Apr 2019 00:00:44 -0400
Subject: remove unnecessary comparisons to None

---
 lib/stitches/auto_fill.py | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'lib')

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 84f10d45..9d946ae2 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -411,16 +411,16 @@ def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None
 
     graph = graph.copy()
 
-    if starting_point is None:
+    if not starting_point:
         starting_point = graph.nodes.keys()[0]
 
     starting_node = nearest_node(graph, starting_point)
 
-    if ending_point is None:
+    if ending_point:
+        ending_node = nearest_node(graph, ending_point)
+    else:
         ending_point = starting_point
         ending_node = starting_node
-    else:
-        ending_node = nearest_node(graph, ending_point)
 
     # The algorithm below is adapted from networkx.eulerian_circuit().
     path = []
@@ -431,7 +431,7 @@ def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None
     while vertex_stack:
         current_vertex, current_key = vertex_stack[-1]
         if graph.degree(current_vertex) == 0:
-            if last_vertex is not None:
+            if last_vertex:
                 path.append(PathEdge((last_vertex, current_vertex), last_key))
             last_vertex, last_key = current_vertex, current_key
             vertex_stack.pop()
-- 
cgit v1.2.3


From 75fdfe22deddbfc8a875840cde48844207b7b76e Mon Sep 17 00:00:00 2001
From: Kaalleen <36401965+kaalleen@users.noreply.github.com>
Date: Wed, 10 Apr 2019 17:42:49 +0200
Subject: fix base file name bug

---
 lib/extensions/base.py | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/extensions/base.py b/lib/extensions/base.py
index 98673541..6b846aeb 100644
--- a/lib/extensions/base.py
+++ b/lib/extensions/base.py
@@ -2,6 +2,7 @@ from collections import MutableMapping
 from copy import deepcopy
 import json
 import re
+import os
 
 import inkex
 from stringcase import snakecase
@@ -187,10 +188,7 @@ class InkstitchExtension(inkex.Effect):
     def get_base_file_name(self):
         svg_filename = self.document.getroot().get(inkex.addNS('docname', 'sodipodi'), "embroidery.svg")
 
-        if svg_filename.endswith('.svg'):
-            svg_filename = svg_filename[:-4]
-
-        return svg_filename
+        return os.path.splitext(svg_filename)[0]
 
     def uniqueId(self, prefix, make_new_id=True):
         """Override inkex.Effect.uniqueId with a nicer naming scheme."""
-- 
cgit v1.2.3


From 944834593de7f6008b0edbd8d75e18face9ee2a1 Mon Sep 17 00:00:00 2001
From: Kate Murphy <hello@kate.io>
Date: Tue, 16 Apr 2019 20:05:45 -0400
Subject: Build inx files in locale folders and build release for each locale

---
 lib/inx/utils.py | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

(limited to 'lib')

diff --git a/lib/inx/utils.py b/lib/inx/utils.py
index a22b1892..1dc96829 100644
--- a/lib/inx/utils.py
+++ b/lib/inx/utils.py
@@ -1,3 +1,4 @@
+import errno
 import os
 import gettext
 from os.path import dirname
@@ -28,8 +29,16 @@ def build_environment():
 
 
 def write_inx_file(name, contents):
-    inx_file_name = "inkstitch_%s_%s.inx" % (name, current_locale)
-    with open(os.path.join(inx_path, inx_file_name), 'w') as inx_file:
+    inx_locale_dir = os.path.join(inx_path, current_locale)
+
+    try:
+        os.makedirs(inx_locale_dir)
+    except OSError as e:
+        if e.errno != errno.EEXIST:
+            raise
+
+    inx_file_name = "inkstitch_%s.inx" % name
+    with open(os.path.join(inx_locale_dir, inx_file_name), 'w') as inx_file:
         print >> inx_file, contents.encode("utf-8")
 
 
-- 
cgit v1.2.3