Merge branch 'master' into lexelby/lettering-features

11 files changed, 630 insertions, 333 deletions

diff --git a/lib/debug.py b/lib/debug.py
new file mode 100644
index 00000000..6ce67697
--- /dev/null
+++ b/lib/debug.py
@@ -0,0 +1,197 @@
+import atexit
+from contextlib import contextmanager
+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
+
+
+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.enabled = True
+        self.init_log()
+        self.init_debugger()
+        self.init_svg()
+
+    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 init_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 init_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)
+
+    @check_enabled
+    def add_layer(self, name="Debug"):
+        layer = etree.Element("g", {
+            INKSCAPE_GROUPMODE: "layer",
+            INKSCAPE_LABEL: name,
+            "style": "display: none"
+        })
+        self.svg.append(layer)
+        self.current_layer = layer
+
+    @check_enabled
+    def open_group(self, name="Group"):
+        group = etree.Element("g", {
+            INKSCAPE_LABEL: name
+        })
+
+        self.log_svg_element(group)
+        self.group_stack.append(group)
+
+    @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):
+        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):
+            if self.enabled:
+                self.raw_log("entering %s()", func.func_name)
+                start = time.time()
+
+            result = func(*args, **kwargs)
+
+            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()
+
+        if self.group_stack:
+            self.group_stack[-1].append(element)
+        else:
+            self.current_layer.append(element)
+
+    @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([line_string], name, color)
+
+    @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 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):
+        d = ""
+
+        for edge in graph.edges:
+            d += "M%s,%s %s,%s" % (edge[0] + edge[1])
+
+        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"):
+        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()
+
+
+def enable():
+    debug.enable()
diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index b8d8d15f..62d3493c 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
@@ -118,6 +119,30 @@ 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.'),
+        group=_('AutoFill Underlay'),
+        type='boolean',
+        default=True)
+    def underlay_underpath(self):
+        return self.get_boolean_param('underlay_underpath', True)
+
     def shrink_or_grow_shape(self, amount):
         if amount:
             shape = self.shape.buffer(amount)
@@ -168,7 +193,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,
@@ -180,11 +206,16 @@ 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))
         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.")
diff --git a/lib/extensions/base.py b/lib/extensions/base.py
index 8d45f790..c77aeacd 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
@@ -188,10 +189,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."""
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",
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="",
diff --git a/lib/gui/simulator.py b/lib/gui/simulator.py
index c07a7af3..7184a012 100644
--- a/lib/gui/simulator.py
+++ b/lib/gui/simulator.py
@@ -68,14 +68,21 @@ 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)'))
         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)
@@ -91,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)
@@ -116,19 +124,20 @@ 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)]
 
-        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 +195,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 +204,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:
@@ -241,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):
     """"""
@@ -346,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
@@ -402,6 +436,12 @@ class DrawingPanel(wx.Panel):
         canvas.SetFont(wx.Font(12, wx.DEFAULT, wx.NORMAL, wx.NORMAL), wx.Colour((0, 0, 0)))
         canvas.DrawText("%s mm" % scale_width_mm, scale_lower_left_x, scale_lower_left_y + 5)
 
+    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()
@@ -666,6 +706,7 @@ class EmbroiderySimulator(wx.Frame):
         if self.on_close_hook:
             self.on_close_hook()
 
+        self.SetFocus()
         self.Destroy()
 
     def go(self):
@@ -736,7 +777,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:  # 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)
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")
 
 
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)
 
diff --git a/lib/svg/__init__.py b/lib/svg/__init__.py
index 0b4a6ee4..640aee73 100644
--- a/lib/svg/__init__.py
+++ b/lib/svg/__init__.py
@@ -1,4 +1,5 @@
 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 .path import apply_transforms, get_node_transform, get_correction_transform, line_strings_to_csp, point_lists_to_csp
 from .rendering import color_block_to_point_lists, render_stitch_plan
 from .svg import get_document, generate_unique_id
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)
+    })