separate guided fill methods

7 files changed, 395 insertions, 228 deletions

diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py
index 3256c1ea..eaddcfe0 100644
--- a/lib/elements/fill_stitch.py
+++ b/lib/elements/fill_stitch.py
@@ -15,7 +15,7 @@ from shapely.validation import explain_validity
 from ..i18n import _
 from ..marker import get_marker_elements
 from ..stitch_plan import StitchGroup
-from ..stitches import tangential_fill_stitch_line_creator, auto_fill, legacy_fill
+from ..stitches import tangential_fill_stitch_line_creator, auto_fill, legacy_fill, guided_fill
 from ..svg import PIXELS_PER_MM
 from ..svg.tags import INKSCAPE_LABEL
 from ..utils import Point as InkstitchPoint
@@ -45,7 +45,7 @@ class UnderlayInsetWarning(ValidationWarning):
 
 class MissingGuideLineWarning(ValidationWarning):
     name = _("Missing Guideline")
-    description = _('This object is set to "Guided AutoFill", but has no guide line.')
+    description = _('This object is set to "Guided Fill", but has no guide line.')
     steps_to_solve = [
         _('* Create a stroke object'),
         _('* Select this object and run Extensions > Ink/Stitch > Edit > Selection to guide line')
@@ -97,7 +97,7 @@ class FillStitch(EmbroideryElement):
 
     @property
     @param('fill_method', _('Fill method'), type='dropdown', default=0,
-           options=[_("Auto Fill"), _("Tangential"), _("Guided Auto Fill"), _("Legacy Fill")], sort_index=2)
+           options=[_("Auto Fill"), _("Tangential"), _("Guided Fill"), _("Legacy Fill")], sort_index=2)
     def fill_method(self):
         return self.get_int_param('fill_method', 0)
 
@@ -514,7 +514,6 @@ class FillStitch(EmbroideryElement):
                 tags=("auto_fill", "auto_fill_underlay"),
                 stitches=auto_fill(
                     self.underlay_shape,
-                    None,
                     self.fill_underlay_angle[i],
                     self.fill_underlay_row_spacing,
                     self.fill_underlay_row_spacing,
@@ -535,7 +534,6 @@ class FillStitch(EmbroideryElement):
             tags=("auto_fill", "auto_fill_top"),
             stitches=auto_fill(
                 self.fill_shape,
-                None,
                 self.angle,
                 self.row_spacing,
                 self.end_row_spacing,
@@ -580,16 +578,14 @@ class FillStitch(EmbroideryElement):
 
         stitch_group = StitchGroup(
             color=self.color,
-            tags=("auto_fill", "auto_fill_top"),
-            stitches=auto_fill(
+            tags=("guided_fill", "auto_fill_top"),
+            stitches=guided_fill(
                 self.fill_shape,
                 guide_line.geoms[0],
                 self.angle,
                 self.row_spacing,
-                self.end_row_spacing,
                 self.max_stitch_length,
                 self.running_stitch_length,
-                0,
                 self.skip_last,
                 starting_point,
                 ending_point,
diff --git a/lib/stitches/__init__.py b/lib/stitches/__init__.py
index 4de88733..8b2738bc 100644
--- a/lib/stitches/__init__.py
+++ b/lib/stitches/__init__.py
@@ -5,6 +5,7 @@
 
 from .auto_fill import auto_fill
 from .fill import legacy_fill
+from .guided_fill import guided_fill
 from .running_stitch import *
 
 # Can't put this here because we get a circular import :(
diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 7af99560..52dc6a81 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -12,16 +12,14 @@ import networkx
 from shapely import geometry as shgeo
 from shapely.ops import snap
 from shapely.strtree import STRtree
-from depq import DEPQ
+
 from ..debug import debug
 from ..stitch_plan import Stitch
 from ..svg import PIXELS_PER_MM
 from ..utils.geometry import Point as InkstitchPoint
 from ..utils.geometry import line_string_to_point_list
-from .fill import intersect_region_with_grating, intersect_region_with_grating_line, stitch_row
+from .fill import intersect_region_with_grating, stitch_row
 from .running_stitch import running_stitch
-from .point_transfer import transfer_points_to_surrounding_graph
-from .sample_linestring import raster_line_string_with_priority_points
 
 
 class PathEdge(object):
@@ -51,7 +49,6 @@ class PathEdge(object):
 
 @debug.time
 def auto_fill(shape,
-              line,
               angle,
               row_spacing,
               end_row_spacing,
@@ -61,14 +58,10 @@ def auto_fill(shape,
               skip_last,
               starting_point,
               ending_point=None,
-              underpath=True,
-              offset_by_half=True):
-    # offset_by_half only relevant for line != None; staggers only relevant for line == None!
-
+              underpath=True):
     fill_stitch_graph = []
     try:
-        fill_stitch_graph = build_fill_stitch_graph(
-            shape, line, angle, row_spacing, end_row_spacing, starting_point, ending_point)
+        fill_stitch_graph = build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting_point, ending_point)
     except ValueError:
         # Small shapes will cause the graph to fail - min() arg is an empty sequence through insert node
         return fallback(shape, running_stitch_length)
@@ -81,7 +74,7 @@ def auto_fill(shape,
     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, line is not None, offset_by_half)
+                              max_stitch_length, running_stitch_length, staggers, skip_last)
 
     return result
 
@@ -116,7 +109,7 @@ def project(shape, coords, outline_index):
 
 
 @debug.time
-def build_fill_stitch_graph(shape, line, angle, row_spacing, end_row_spacing, starting_point=None, ending_point=None):
+def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting_point=None, ending_point=None):
     """build a graph representation of the grating segments
 
     This function builds a specialized graph (as in graph theory) that will
@@ -151,37 +144,18 @@ def build_fill_stitch_graph(shape, line, angle, row_spacing, end_row_spacing, st
 
     debug.add_layer("auto-fill fill stitch")
 
-    if line is None:
-        # Convert the shape into a set of parallel line segments.
-        rows_of_segments = intersect_region_with_grating(
-            shape, angle, row_spacing, end_row_spacing)
-    else:
-        rows_of_segments = intersect_region_with_grating_line(
-            shape, line, row_spacing, end_row_spacing)
-
-    # segments = [segment for row in rows_of_segments for segment in row]
+    # 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()
 
-    for i in range(len(rows_of_segments)):
-        for segment in rows_of_segments[i]:
-            # First, add the grating segments as edges.  We'll use the coordinates
-            # of the endpoints as nodes, which networkx will add automatically.
-
-            # networkx allows us to label nodes with arbitrary data.  We'll
-            # mark this one as a grating segment.
-            # graph.add_edge(*segment, key="segment", underpath_edges=[])
-            previous_neighbors_ = [(seg[0], seg[-1])
-                                   for seg in rows_of_segments[i-1] if i > 0]
-            next_neighbors_ = [(seg[0], seg[-1]) for seg in rows_of_segments[(i+1) %
-                                                                             len(rows_of_segments)] if i < len(rows_of_segments)-1]
-
-            graph.add_edge(segment[0], segment[-1], key="segment", underpath_edges=[],
-                           geometry=shgeo.LineString(segment), previous_neighbors=previous_neighbors_, next_neighbors=next_neighbors_,
-                           projected_points=DEPQ(iterable=None, maxlen=None), already_rastered=False)
-
-
-# fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge)
+    # First, add the grating segments as edges.  We'll use the coordinates
+    # of the endpoints as nodes, which networkx will add automatically.
+    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", underpath_edges=[])
 
     tag_nodes_with_outline_and_projection(graph, shape, graph.nodes())
     add_edges_between_outline_nodes(graph, duplicate_every_other=True)
@@ -360,8 +334,7 @@ def get_segments(graph):
     segments = []
     for start, end, key, data in graph.edges(keys=True, data=True):
         if key == 'segment':
-            segments.append(data["geometry"])
-            # segments.append(shgeo.LineString((start, end)))
+            segments.append(shgeo.LineString((start, end)))
 
     return segments
 
@@ -400,10 +373,8 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges):
             # 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 = segment.coords[0]
-                end = segment.coords[-1]
-                fill_stitch_graph[start][end]['segment']['underpath_edges'].append(
-                    edge)
+                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)
@@ -661,30 +632,8 @@ def travel(travel_graph, start, end, running_stitch_length, skip_last):
         return stitches[1:]
 
 
-def stitch_line(stitches, stitching_direction, geometry, projected_points, max_stitch_length, row_spacing, skip_last, offset_by_half):
-    if stitching_direction == 1:
-        stitched_line, _ = raster_line_string_with_priority_points(
-            geometry, 0.0, geometry.length, max_stitch_length, projected_points, abs(row_spacing), offset_by_half, True)
-    else:
-        stitched_line, _ = raster_line_string_with_priority_points(
-            geometry, geometry.length, 0.0, max_stitch_length, projected_points, abs(row_spacing), offset_by_half, True)
-
-    stitches.append(Stitch(*stitched_line[0], tags=('fill_row_start',)))
-    for i in range(1, len(stitched_line)-1):
-        stitches.append(Stitch(*stitched_line[i], tags=('fill_row')))
-
-    if not skip_last:
-        if stitching_direction == 1:
-            stitches.append(
-                Stitch(*geometry.coords[-1], tags=('fill_row_end',)))
-        else:
-            stitches.append(
-                Stitch(*geometry.coords[0], tags=('fill_row_end',)))
-
-
 @debug.time
-def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length,
-                     running_stitch_length, staggers, skip_last, offsetted_line, offset_by_half):
+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 = []
@@ -695,29 +644,8 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing,
 
     for edge in path:
         if edge.is_segment():
-            if offsetted_line:
-                new_stitches = []
-                current_edge = fill_stitch_graph[edge[0]][edge[-1]]['segment']
-                path_geometry = current_edge['geometry']
-                projected_points = current_edge['projected_points']
-                stitching_direction = 1
-                if (abs(edge[0][0]-path_geometry.coords[0][0])+abs(edge[0][1]-path_geometry.coords[0][1]) >
-                        abs(edge[0][0]-path_geometry.coords[-1][0])+abs(edge[0][1]-path_geometry.coords[-1][1])):
-                    stitching_direction = -1
-                stitch_line(new_stitches, stitching_direction, path_geometry, projected_points,
-                            max_stitch_length, row_spacing, skip_last, offset_by_half)
-                current_edge['already_rastered'] = True
-                transfer_points_to_surrounding_graph(
-                    fill_stitch_graph, current_edge, row_spacing, False, new_stitches, overnext_neighbor=True)
-                transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, row_spacing, offset_by_half,
-                                                     new_stitches, overnext_neighbor=False, transfer_forbidden_points=offset_by_half)
-
-                stitches.extend(new_stitches)
-            else:
-                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', []))
+            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, skip_last))
diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py
index b5f86641..1fdc6fac 100644
--- a/lib/stitches/fill.py
+++ b/lib/stitches/fill.py
@@ -6,8 +6,8 @@
 import math
 
 import shapely
-from shapely.geometry.linestring import LineString
-from shapely.ops import linemerge, unary_union
+
+from ..stitch_plan import Stitch
 from ..svg import PIXELS_PER_MM
 from ..utils import Point as InkstitchPoint
 from ..utils import cache
@@ -94,119 +94,6 @@ def stitch_row(stitches, beg, end, angle, row_spacing, max_stitch_length, stagge
         stitches.append(end)
 
 
-def extend_line(line, minx, maxx, miny, maxy):
-    line = line.simplify(0.01, False)
-
-    upper_left = InkstitchPoint(minx, miny)
-    lower_right = InkstitchPoint(maxx, maxy)
-    length = (upper_left - lower_right).length()
-
-    point1 = InkstitchPoint(*line.coords[0])
-    point2 = InkstitchPoint(*line.coords[1])
-    new_starting_point = point1-(point2-point1).unit()*length
-
-    point3 = InkstitchPoint(*line.coords[-2])
-    point4 = InkstitchPoint(*line.coords[-1])
-    new_ending_point = point4+(point4-point3).unit()*length
-
-    return LineString([new_starting_point.as_tuple()] +
-                      line.coords[1:-1]+[new_ending_point.as_tuple()])
-
-
-def repair_multiple_parallel_offset_curves(multi_line):
-    lines = linemerge(multi_line)
-    lines = list(multi_line.geoms)
-    max_length = -1
-    max_length_idx = -1
-    for idx, subline in enumerate(lines):
-        if subline.length > max_length:
-            max_length = subline.length
-            max_length_idx = idx
-    # need simplify to avoid doubled points caused by linemerge
-    return lines[max_length_idx].simplify(0.01, False)
-
-
-def repair_non_simple_lines(line):
-    repaired = unary_union(line)
-    counter = 0
-    # Do several iterations since we might have several concatenated selfcrossings
-    while repaired.geom_type != 'LineString' and counter < 4:
-        line_segments = []
-        for line_seg in repaired.geoms:
-            if not line_seg.is_ring:
-                line_segments.append(line_seg)
-
-        repaired = unary_union(linemerge(line_segments))
-        counter += 1
-    if repaired.geom_type != 'LineString':
-        raise ValueError(
-            "Guide line (or offsetted instance) is self crossing!")
-    else:
-        return repaired
-
-
-def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing=None, flip=False):  # noqa: C901
-
-    row_spacing = abs(row_spacing)
-    (minx, miny, maxx, maxy) = shape.bounds
-    upper_left = InkstitchPoint(minx, miny)
-    rows = []
-
-    if line.geom_type != 'LineString' or not line.is_simple:
-        line = repair_non_simple_lines(line)
-    # extend the line towards the ends to increase probability that all offsetted curves cross the shape
-    line = extend_line(line, minx, maxx, miny, maxy)
-
-    line_offsetted = line
-    res = line_offsetted.intersection(shape)
-    while isinstance(res, (shapely.geometry.GeometryCollection, shapely.geometry.MultiLineString)) or (not res.is_empty and len(res.coords) > 1):
-        if isinstance(res, (shapely.geometry.GeometryCollection, shapely.geometry.MultiLineString)):
-            runs = [line_string.coords for line_string in res.geoms if (
-                not line_string.is_empty and len(line_string.coords) > 1)]
-        else:
-            runs = [res.coords]
-
-        runs.sort(key=lambda seg: (
-            InkstitchPoint(*seg[0]) - upper_left).length())
-        if flip:
-            runs.reverse()
-            runs = [tuple(reversed(run)) for run in runs]
-
-        if row_spacing > 0:
-            rows.append(runs)
-        else:
-            rows.insert(0, runs)
-
-        line_offsetted = line_offsetted.parallel_offset(row_spacing, 'left', 5)
-        if line_offsetted.geom_type == 'MultiLineString':  # if we got multiple lines take the longest
-            line_offsetted = repair_multiple_parallel_offset_curves(
-                line_offsetted)
-        if not line_offsetted.is_simple:
-            line_offsetted = repair_non_simple_lines(line_offsetted)
-
-        if row_spacing < 0:
-            line_offsetted.coords = line_offsetted.coords[::-1]
-        line_offsetted = line_offsetted.simplify(0.01, False)
-        res = line_offsetted.intersection(shape)
-        if row_spacing > 0 and not isinstance(res, (shapely.geometry.GeometryCollection, shapely.geometry.MultiLineString)):
-            if (res.is_empty or len(res.coords) == 1):
-                row_spacing = -row_spacing
-
-                line_offsetted = line.parallel_offset(row_spacing, 'left', 5)
-                if line_offsetted.geom_type == 'MultiLineString':  # if we got multiple lines take the longest
-                    line_offsetted = repair_multiple_parallel_offset_curves(
-                        line_offsetted)
-                if not line_offsetted.is_simple:
-                    line_offsetted = repair_non_simple_lines(line_offsetted)
-                # using negative row spacing leads as a side effect to reversed offsetted lines - here we undo this
-                line_offsetted.coords = line_offsetted.coords[::-1]
-                line_offsetted = line_offsetted.simplify(0.01, False)
-                res = line_offsetted.intersection(shape)
-
-
-    return rows
-
-
 def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=None, flip=False):
     # the max line length I'll need to intersect the whole shape is the diagonal
     (minx, miny, maxx, maxy) = shape.bounds
diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py
new file mode 100644
index 00000000..4cc250ef
--- /dev/null
+++ b/lib/stitches/guided_fill.py
@@ -0,0 +1,355 @@
+import networkx
+from depq import DEPQ
+from shapely.geometry import GeometryCollection, LineString, MultiLineString
+from shapely.ops import linemerge, unary_union
+from shapely.strtree import STRtree
+
+from ..debug import debug
+from ..i18n import _
+from ..stitch_plan import Stitch
+from ..svg import PIXELS_PER_MM
+from ..utils.geometry import Point as InkstitchPoint
+from .auto_fill import (add_edges_between_outline_nodes, build_travel_graph,
+                        collapse_sequential_outline_edges, fallback,
+                        find_stitch_path, graph_is_valid, insert_node,
+                        tag_nodes_with_outline_and_projection, travel,
+                        weight_edges_by_length)
+from .point_transfer import transfer_points_to_surrounding_graph
+from .sample_linestring import raster_line_string_with_priority_points
+
+
+@debug.time
+def guided_fill(shape,
+                guideline,
+                angle,
+                row_spacing,
+                max_stitch_length,
+                running_stitch_length,
+                skip_last,
+                starting_point,
+                ending_point=None,
+                underpath=True,
+                offset_by_half=True):
+
+    fill_stitch_graph = []
+    try:
+        fill_stitch_graph = build_guided_fill_stitch_graph(
+            shape, guideline, row_spacing, starting_point, ending_point)
+    except ValueError:
+        # Small shapes will cause the graph to fail - min() arg is an empty sequence through insert node
+        return fallback(shape, running_stitch_length)
+
+    if not graph_is_valid(fill_stitch_graph, shape, max_stitch_length):
+        return fallback(shape, running_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, skip_last, offset_by_half)
+
+    return result
+
+
+@debug.time
+def build_guided_fill_stitch_graph(shape, guideline, row_spacing, starting_point=None, ending_point=None):
+    """build a graph representation of the grating segments
+
+    This function builds a specialized graph (as in graph theory) that will
+    help us determine a stitching path.  The idea comes from this paper:
+
+    http://www.sciencedirect.com/science/article/pii/S0925772100000158
+
+    The goal is to build a graph that we know must have an Eulerian Path.
+    An Eulerian Path is a path from edge to edge in the graph that visits
+    every edge exactly once and ends at the node it started at.  Algorithms
+    exist to build such a path, and we'll use Hierholzer's algorithm.
+
+    A graph must have an Eulerian Path if every node in the graph has an
+    even number of edges touching it.  Our goal here is to build a graph
+    that will have this property.
+
+    Based on the paper linked above, we'll build the graph as follows:
+
+        * nodes are the endpoints of the grating segments, where they meet
+        with the outer outline of the region the outlines of the interior
+        holes in the region.
+        * edges are:
+        * each section of the outer and inner outlines of the region,
+            between nodes
+        * double every other edge in the outer and inner hole outlines
+
+    Doubling up on some of the edges seems as if it will just mean we have
+    to stitch those spots twice.  This may be true, but it also ensures
+    that every node has 4 edges touching it, ensuring that a valid stitch
+    path must exist.
+    """
+
+    debug.add_layer("auto-fill fill stitch")
+
+    rows_of_segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing)
+
+    # segments = [segment for row in rows_of_segments for segment in row]
+
+    graph = networkx.MultiGraph()
+
+    for i in range(len(rows_of_segments)):
+        for segment in rows_of_segments[i]:
+            # First, add the grating segments as edges.  We'll use the coordinates
+            # of the endpoints as nodes, which networkx will add automatically.
+
+            # networkx allows us to label nodes with arbitrary data.  We'll
+            # mark this one as a grating segment.
+            # graph.add_edge(*segment, key="segment", underpath_edges=[])
+            previous_neighbors = [(seg[0], seg[-1])
+                                  for seg in rows_of_segments[i-1] if i > 0]
+            next_neighbors = [(seg[0], seg[-1]) for seg in rows_of_segments[(i+1) %
+                              len(rows_of_segments)] if i < len(rows_of_segments)-1]
+
+            graph.add_edge(segment[0], segment[-1], key="segment", underpath_edges=[],
+                           geometry=LineString(segment), previous_neighbors=previous_neighbors, next_neighbors=next_neighbors,
+                           projected_points=DEPQ(iterable=None, maxlen=None), already_rastered=False)
+
+    tag_nodes_with_outline_and_projection(graph, shape, graph.nodes())
+    add_edges_between_outline_nodes(graph, duplicate_every_other=True)
+
+    if starting_point:
+        insert_node(graph, shape, starting_point)
+
+    if ending_point:
+        insert_node(graph, shape, ending_point)
+
+    debug.log_graph(graph, "graph")
+
+    return graph
+
+
+def get_segments(graph):
+    segments = []
+    for start, end, key, data in graph.edges(keys=True, data=True):
+        if key == 'segment':
+            segments.append(data["geometry"])
+
+    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 = segment.coords[0]
+                end = segment.coords[-1]
+                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 stitch_line(stitches, stitching_direction, geometry, projected_points, max_stitch_length, row_spacing, skip_last, offset_by_half):
+    if stitching_direction == 1:
+        stitched_line, _ = raster_line_string_with_priority_points(
+            geometry, 0.0, geometry.length, max_stitch_length, projected_points, abs(row_spacing), offset_by_half, True)
+    else:
+        stitched_line, _ = raster_line_string_with_priority_points(
+            geometry, geometry.length, 0.0, max_stitch_length, projected_points, abs(row_spacing), offset_by_half, True)
+
+    stitches.append(Stitch(*stitched_line[0], tags=('fill_row_start',)))
+    for i in range(1, len(stitched_line)-1):
+        stitches.append(Stitch(*stitched_line[i], tags=('fill_row')))
+
+    if not skip_last:
+        if stitching_direction == 1:
+            stitches.append(
+                Stitch(*geometry.coords[-1], tags=('fill_row_end',)))
+        else:
+            stitches.append(
+                Stitch(*geometry.coords[0], tags=('fill_row_end',)))
+
+
+@debug.time
+def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length,
+                     running_stitch_length, skip_last, offset_by_half):
+    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(Stitch(*path[0].nodes[0]))
+
+    for edge in path:
+        if edge.is_segment():
+            new_stitches = []
+            current_edge = fill_stitch_graph[edge[0]][edge[-1]]['segment']
+            path_geometry = current_edge['geometry']
+            projected_points = current_edge['projected_points']
+            stitching_direction = 1
+            if (abs(edge[0][0]-path_geometry.coords[0][0])+abs(edge[0][1]-path_geometry.coords[0][1]) >
+                    abs(edge[0][0]-path_geometry.coords[-1][0])+abs(edge[0][1]-path_geometry.coords[-1][1])):
+                stitching_direction = -1
+            stitch_line(new_stitches, stitching_direction, path_geometry, projected_points,
+                        max_stitch_length, row_spacing, skip_last, offset_by_half)
+            current_edge['already_rastered'] = True
+            transfer_points_to_surrounding_graph(
+                fill_stitch_graph, current_edge, row_spacing, False, new_stitches, overnext_neighbor=True)
+            transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, row_spacing, offset_by_half,
+                                                 new_stitches, overnext_neighbor=False, transfer_forbidden_points=offset_by_half)
+
+            stitches.extend(new_stitches)
+        else:
+            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, skip_last))
+
+    return stitches
+
+
+def extend_line(line, minx, maxx, miny, maxy):
+    line = line.simplify(0.01, False)
+
+    upper_left = InkstitchPoint(minx, miny)
+    lower_right = InkstitchPoint(maxx, maxy)
+    length = (upper_left - lower_right).length()
+
+    point1 = InkstitchPoint(*line.coords[0])
+    point2 = InkstitchPoint(*line.coords[1])
+    new_starting_point = point1-(point2-point1).unit()*length
+
+    point3 = InkstitchPoint(*line.coords[-2])
+    point4 = InkstitchPoint(*line.coords[-1])
+    new_ending_point = point4+(point4-point3).unit()*length
+
+    return LineString([new_starting_point.as_tuple()] +
+                      line.coords[1:-1]+[new_ending_point.as_tuple()])
+
+
+def repair_multiple_parallel_offset_curves(multi_line):
+    # TODO: linemerge is overritten by the very next line?!?
+    lines = linemerge(multi_line)
+    lines = list(multi_line.geoms)
+    max_length = -1
+    max_length_idx = -1
+    for idx, subline in enumerate(lines):
+        if subline.length > max_length:
+            max_length = subline.length
+            max_length_idx = idx
+    # need simplify to avoid doubled points caused by linemerge
+    return lines[max_length_idx].simplify(0.01, False)
+
+
+def repair_non_simple_lines(line):
+    repaired = unary_union(line)
+    counter = 0
+    # Do several iterations since we might have several concatenated selfcrossings
+    while repaired.geom_type != 'LineString' and counter < 4:
+        line_segments = []
+        for line_seg in repaired.geoms:
+            if not line_seg.is_ring:
+                line_segments.append(line_seg)
+
+        repaired = unary_union(linemerge(line_segments))
+        counter += 1
+    if repaired.geom_type != 'LineString':
+        raise ValueError(
+            _("Guide line (or offsetted instance) is self crossing!"))
+    else:
+        return repaired
+
+
+def intersect_region_with_grating_guideline(shape, line, row_spacing, flip=False):  # noqa: C901
+
+    row_spacing = abs(row_spacing)
+    (minx, miny, maxx, maxy) = shape.bounds
+    upper_left = InkstitchPoint(minx, miny)
+    rows = []
+
+    if line.geom_type != 'LineString' or not line.is_simple:
+        line = repair_non_simple_lines(line)
+    # extend the line towards the ends to increase probability that all offsetted curves cross the shape
+    line = extend_line(line, minx, maxx, miny, maxy)
+
+    line_offsetted = line
+    res = line_offsetted.intersection(shape)
+    while isinstance(res, (GeometryCollection, MultiLineString)) or (not res.is_empty and len(res.coords) > 1):
+        if isinstance(res, (GeometryCollection, MultiLineString)):
+            runs = [line_string.coords for line_string in res.geoms if (
+                not line_string.is_empty and len(line_string.coords) > 1)]
+        else:
+            runs = [res.coords]
+
+        runs.sort(key=lambda seg: (
+            InkstitchPoint(*seg[0]) - upper_left).length())
+        if flip:
+            runs.reverse()
+            runs = [tuple(reversed(run)) for run in runs]
+
+        if row_spacing > 0:
+            rows.append(runs)
+        else:
+            rows.insert(0, runs)
+
+        line_offsetted = line_offsetted.parallel_offset(row_spacing, 'left', 5)
+        if line_offsetted.geom_type == 'MultiLineString':  # if we got multiple lines take the longest
+            line_offsetted = repair_multiple_parallel_offset_curves(line_offsetted)
+        if not line_offsetted.is_simple:
+            line_offsetted = repair_non_simple_lines(line_offsetted)
+
+        if row_spacing < 0:
+            line_offsetted.coords = line_offsetted.coords[::-1]
+        line_offsetted = line_offsetted.simplify(0.01, False)
+        res = line_offsetted.intersection(shape)
+        if row_spacing > 0 and not isinstance(res, (GeometryCollection, MultiLineString)):
+            if (res.is_empty or len(res.coords) == 1):
+                row_spacing = -row_spacing
+
+                line_offsetted = line.parallel_offset(row_spacing, 'left', 5)
+                if line_offsetted.geom_type == 'MultiLineString':  # if we got multiple lines take the longest
+                    line_offsetted = repair_multiple_parallel_offset_curves(
+                        line_offsetted)
+                if not line_offsetted.is_simple:
+                    line_offsetted = repair_non_simple_lines(line_offsetted)
+                # using negative row spacing leads as a side effect to reversed offsetted lines - here we undo this
+                line_offsetted.coords = line_offsetted.coords[::-1]
+                line_offsetted = line_offsetted.simplify(0.01, False)
+                res = line_offsetted.intersection(shape)
+    return rows
diff --git a/lib/stitches/point_transfer.py b/lib/stitches/point_transfer.py
index a01e69cd..cf4597dd 100644
--- a/lib/stitches/point_transfer.py
+++ b/lib/stitches/point_transfer.py
@@ -1,10 +1,10 @@
-from shapely.geometry import Point, MultiPoint
-from shapely.geometry.polygon import LineString, LinearRing
+import math
 from collections import namedtuple
+
+from shapely.geometry import LinearRing, LineString, MultiPoint, Point
 from shapely.ops import nearest_points
-import math
-from ..stitches import constants
-from ..stitches import sample_linestring
+
+from ..stitches import constants, sample_linestring
 
 """This file contains routines which shall project already selected points for stitching to remaining
 unstitched lines in the neighborhood to create a regular pattern of points."""
diff --git a/lib/stitches/sample_linestring.py b/lib/stitches/sample_linestring.py
index fb4bbc52..b2298984 100644
--- a/lib/stitches/sample_linestring.py
+++ b/lib/stitches/sample_linestring.py
@@ -1,11 +1,11 @@
-from shapely.geometry.polygon import LineString
-from shapely.geometry import Point
-from shapely.ops import substring
 import math
-import numpy as np
 from enum import IntEnum
-from ..stitches import constants
-from ..stitches import point_transfer
+
+import numpy as np
+from shapely.geometry import LineString, Point
+from shapely.ops import substring
+
+from ..stitches import constants, point_transfer
 
 
 class PointSource(IntEnum):