Merge branch 'master' into lexelby/lettering-features

2 files changed, 306 insertions, 313 deletions

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 0f07b795..9d946ae2 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -1,21 +1,22 @@
-from collections import deque
-from itertools import groupby, izip
-import sys
+# -*- coding: UTF-8 -*-
+
+from itertools import groupby, chain
+import math
 
 import networkx
-import shapely
+from shapely import geometry as shgeo
+from shapely.ops import snap
+from shapely.strtree import STRtree
 
+from ..debug import debug
 from ..exceptions import InkstitchException
 from ..i18n import _
-from ..utils.geometry import Point as InkstitchPoint, cut
-from .fill import intersect_region_with_grating, row_num, stitch_row
+from ..svg import PIXELS_PER_MM
+from ..utils.geometry import Point as InkstitchPoint
+from .fill import intersect_region_with_grating, stitch_row
 from .running_stitch import running_stitch
 
 
-class MaxQueueLengthExceeded(InkstitchException):
-    pass
-
-
 class InvalidPath(InkstitchException):
     pass
 
@@ -45,6 +46,7 @@ class PathEdge(object):
         return self.key == self.SEGMENT_KEY
 
 
+@debug.time
 def auto_fill(shape,
               angle,
               row_spacing,
@@ -54,18 +56,17 @@ def auto_fill(shape,
               staggers,
               skip_last,
               starting_point,
-              ending_point=None):
-    stitches = []
+              ending_point=None,
+              underpath=True):
 
-    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]
+    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, 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)
 
-    graph = build_graph(shape, segments, angle, row_spacing, 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 result
 
 
 def which_outline(shape, coords):
@@ -78,11 +79,12 @@ def which_outline(shape, coords):
     # I'd use an intersection check, but floating point errors make it
     # fail sometimes.
 
-    point = shapely.geometry.Point(*coords)
-    outlines = enumerate(list(shape.boundary))
-    closest = min(outlines, key=lambda index_outline: index_outline[1].distance(point))
+    point = shgeo.Point(*coords)
+    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):
@@ -92,10 +94,11 @@ 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):
+@debug.time
+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
@@ -128,6 +131,12 @@ def build_graph(shape, segments, angle, row_spacing, max_stitch_length):
     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]
+
     graph = networkx.MultiGraph()
 
     # First, add the grating segments as edges.  We'll use the coordinates
@@ -135,241 +144,250 @@ def build_graph(shape, segments, angle, row_spacing, max_stitch_length):
     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())
+    add_edges_between_outline_nodes(graph, duplicate_every_other=True)
+
+    debug.log_graph(graph, "graph")
+
+    return graph
+
 
-    for node in graph.nodes():
+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)
 
-        # Tag each node with its index and projection.
-        graph.add_node(node, index=outline_index, projection=outline_projection)
+        graph.add_node(node, outline=outline_index, projection=outline_projection)
+
+
+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
+    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]
 
-        # 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")
+            data = dict(outline=outline_index, index=i)
+            graph.add_edge(node1, node2, key="outline", **data)
 
-            # duplicate every other edge around this outline
-            if i % 2 == edge_set:
-                graph.add_edge(node1, node2, key="extra")
+            if i % 2 == 0:
+                graph.add_edge(node1, node2, key="extra", **data)
 
-    check_graph(graph, shape, max_stitch_length)
 
-    return graph
+@debug.time
+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
+    outline of the shape.
 
-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."))
-        else:
-            raise InvalidPath(_("Cannot parse shape.  "
-                                "This most often happens because your shape is made up of multiple sections that aren't connected."))
+    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.  We'll construct a
+    graph from them and use a shortest path algorithm to construct travel
+    stitch paths in travel().
 
-def node_list_to_edge_list(node_list):
-    return zip(node_list[:-1], node_list[1:])
+    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.  We also weight the interior edges extra proportional to
+    how close they are to the boundary.
+    """
 
+    graph = networkx.MultiGraph()
 
-def bfs_for_loop(graph, starting_node, max_queue_length=2000):
-    to_search = deque()
-    to_search.append((None, set()))
+    # 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(fill_stitch_graph.nodes(data=True))
 
-    while to_search:
-        if len(to_search) > max_queue_length:
-            raise MaxQueueLengthExceeded()
+    if underpath:
+        boundary_points, travel_edges = build_travel_edges(shape, fill_stitch_angle)
 
-        path, visited_edges = to_search.pop()
+        # 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)
 
-        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]
+    add_edges_between_outline_nodes(graph)
 
-        # 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
-        ]
+    if underpath:
+        process_travel_edges(graph, fill_stitch_graph, shape, travel_edges)
 
-        # heuristic: try grating segments first
-        neighbors.sort(key=lambda dest_key: dest_key[1] == "segment", reverse=True)
+    debug.log_graph(graph, "travel graph")
 
-        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
+    return graph
 
-            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
+def weight_edges_by_length(graph, multiplier=1):
+    for start, end, key in graph.edges:
+        p1 = InkstitchPoint(*start)
+        p2 = InkstitchPoint(*end)
 
-            new_visited_edges = visited_edges.copy()
-            new_visited_edges.add(edge)
+        graph[start][end][key]["weight"] = multiplier * p1.distance(p2)
 
-            to_search.appendleft((new_path, new_visited_edges))
 
+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)))
 
-def find_loop(graph, starting_nodes):
-    """find a loop in the graph that is connected to the existing path
+    return segments
 
-    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.
+def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges):
+    """Weight the interior edges and pre-calculate intersection with fill stitch rows."""
 
-    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.
-    """
+    # Set the weight equal to 5x the edge length, to encourage travel()
+    # to avoid them.
+    weight_edges_by_length(graph, 5)
 
-    loop = None
-    retry = []
-    max_queue_length = 2000
+    segments = get_segments(fill_stitch_graph)
 
-    while not loop:
-        while not loop and starting_nodes:
-            starting_node = starting_nodes.pop()
+    # 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)
 
-            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)
+    # 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)
 
-            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)
+    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]
 
-        # Darn, couldn't find a loop.  Try harder.
-        starting_nodes.extendleft(retry)
-        max_queue_length *= 2
+        edge = (p1.as_tuple(), p2.as_tuple(), 'travel')
 
-    starting_nodes.extendleft(retry)
-    return loop
+        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)
 
-def insert_loop(path, loop):
-    """insert a sub-loop into an existing path
+        # 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
 
-    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.
+        graph.add_edge(*edge, weight=weight)
 
-    Insert the loop into the path, resulting in a longer path.
+    # 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
 
-    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), ...)
+def travel_grating(shape, angle, row_spacing):
+    rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing)
+    segments = list(chain(*rows_of_segments))
 
-    path will be modified in place.
-    """
+    return shgeo.MultiLineString(segments)
 
-    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
+def build_travel_edges(shape, fill_angle):
+    r"""Given a graph, compute the interior travel edges.
 
-    path[i:i] = loop
+    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
 
-def nearest_node_on_outline(graph, point, outline_index=0):
-    point = shapely.geometry.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))
+    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:
 
-    return nearest
+    /|\|/|\|/|\
+    \|/|\|/|\|/
+    /|\|/|\|/|\
+    \|/|\|/|\|/
 
+    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
+    """
 
-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]
+    # 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
 
-    return outline_nodes
+    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")
+    debug.log_line_strings(grating2, "grating2")
+    debug.log_line_strings(grating3, "grating3")
 
-def find_initial_path(graph, starting_point, ending_point=None):
-    starting_node = nearest_node_on_outline(graph, starting_point)
+    endpoints = [coord for mls in (grating1, grating2, grating3)
+                 for ls in mls
+                 for coord in ls.coords]
 
-    if ending_point is not None:
-        ending_node = nearest_node_on_outline(graph, ending_point)
+    diagonal_edges = grating1.symmetric_difference(grating2)
 
-    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)
+    # without this, floating point inaccuracies prevent the intersection points from lining up perfectly.
+    vertical_edges = snap(grating3.difference(grating1), diagonal_edges, 0.005)
 
-        # 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]
+    return endpoints, chain(diagonal_edges, vertical_edges)
 
-        # 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 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:
+            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:
+            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):
+    point = shgeo.Point(*point)
+    nearest = min(nodes, key=lambda node: shgeo.Point(*node).distance(point))
 
-def find_stitch_path(graph, segments, starting_point=None, ending_point=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
 
     Theoretically, we just need to find an Eulerian Path in the graph.
@@ -392,51 +410,81 @@ 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]
+    if not starting_point:
+        starting_point = graph.nodes.keys()[0]
 
-    path = find_initial_path(graph, starting_point, ending_point)
+    starting_node = nearest_node(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.
-
-    nodes_visited.append(path[0][0])
+    if ending_point:
+        ending_node = nearest_node(graph, ending_point)
+    else:
+        ending_point = starting_point
+        ending_node = starting_node
+
+    # 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:
+                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 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)
+    path.insert(0, PathEdge((real_start, starting_node), key="outline"))
+
+    # 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"))
 
-        if not loop:
-            print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.")
-            break
+    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):
+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,
@@ -466,99 +514,44 @@ def collapse_sequential_outline_edges(graph, path):
     return new_path
 
 
-def connect_points(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 = which_outline(shape, start)
-    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 = shapely.geometry.Point(start)
-    start_projection = outline.project(start)
-    end = shapely.geometry.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
-    # 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 = shapely.geometry.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(travel_graph, start, end, running_stitch_length, skip_last):
+    """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 trim_end(path):
-    while path and path[-1].is_outline():
-        path.pop()
+    # 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(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last):
-    path = collapse_sequential_outline_edges(graph, path)
+@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)
 
     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)
+            travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', []))
         else:
-            stitches.extend(connect_points(shape, edge[0], edge[1], running_stitch_length, row_spacing))
+            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, skip_last))
 
     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)