guided fill stagger (#1700)

5 files changed, 136 insertions, 87 deletions

diff --git a/lib/debug.py b/lib/debug.py
index f47d09ec..83dd1766 100644
--- a/lib/debug.py
+++ b/lib/debug.py
@@ -158,7 +158,7 @@ class Debug(object):
     @check_enabled
     def log_line_strings(self, line_strings, name=None, color=None):
         path = line_strings_to_path(line_strings)
-        path.set('style', str(inkex.Style({"stroke": color or "#000000", "stroke-width": "0.3"})))
+        path.set('style', str(inkex.Style({"stroke": color or "#000000", "stroke-width": "0.3", "fill": None})))
 
         if name is not None:
             path.set(INKSCAPE_LABEL, name)
@@ -169,7 +169,7 @@ class Debug(object):
     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": str(inkex.Style({"stroke": color or "#000000", "stroke-width": "0.3"})),
+            "style": str(inkex.Style({"stroke": color or "#000000", "stroke-width": "0.3", "fill": None})),
             INKSCAPE_LABEL: name
         }))
 
@@ -182,7 +182,7 @@ class Debug(object):
 
         self.log_svg_element(etree.Element("path", {
             "d": d,
-            "style": str(inkex.Style({"stroke": color or "#000000", "stroke-width": "0.3"})),
+            "style": str(inkex.Style({"stroke": color or "#000000", "stroke-width": "0.3", "fill": None})),
             INKSCAPE_LABEL: name
         }))
 
diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py
index dbd94fb4..157169ab 100644
--- a/lib/elements/fill_stitch.py
+++ b/lib/elements/fill_stitch.py
@@ -111,6 +111,15 @@ class FillStitch(EmbroideryElement):
         return self.get_int_param('fill_method', 0)
 
     @property
+    @param('guided_fill_strategy', _('Guided Fill Strategy'), type='dropdown', default=0,
+           options=[_("Copy"), _("Parallel Offset")], select_items=[('fill_method', 2)], sort_index=3,
+           tooltip=_('Copy (the default) will fill the shape with shifted copies of the line.' +
+                     'Parallel offset will ensure that each line is always a consistent distance from its neighbor.' +
+                     'Sharp corners may be introduced.'))
+    def guided_fill_strategy(self):
+        return self.get_int_param('guided_fill_strategy', 0)
+
+    @property
     @param('contour_strategy', _('Contour Fill Strategy'), type='dropdown', default=0,
            options=[_("Inner to Outer"), _("Single spiral"), _("Double spiral")], select_items=[('fill_method', 1)], sort_index=3)
     def contour_strategy(self):
@@ -210,7 +219,7 @@ class FillStitch(EmbroideryElement):
            tooltip=_('Setting this dictates how many rows apart the stitches will be before they fall in the same column position.'),
            type='int',
            sort_index=6,
-           select_items=[('fill_method', 0), ('fill_method', 3)],
+           select_items=[('fill_method', 0), ('fill_method', 2), ('fill_method', 3)],
            default=4)
     def staggers(self):
         return max(self.get_int_param("staggers", 4), 1)
@@ -648,7 +657,7 @@ class FillStitch(EmbroideryElement):
 
         # No guide line: fallback to normal autofill
         if not guide_line:
-            return self.do_auto_fill(last_patch, starting_point, ending_point)
+            return self.do_auto_fill(shape, last_patch, starting_point, ending_point)
 
         stitch_group = StitchGroup(
             color=self.color,
@@ -658,12 +667,16 @@ class FillStitch(EmbroideryElement):
                 guide_line.geoms[0],
                 self.angle,
                 self.row_spacing,
+                self.staggers,
                 self.max_stitch_length,
                 self.running_stitch_length,
+                self.running_stitch_tolerance,
                 self.skip_last,
                 starting_point,
                 ending_point,
-                self.underpath))
+                self.underpath,
+                self.guided_fill_strategy,
+            ))
         return [stitch_group]
 
     @cache
diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py
index e4918e1d..7eb49e86 100644
--- a/lib/stitches/guided_fill.py
+++ b/lib/stitches/guided_fill.py
@@ -1,43 +1,45 @@
+import numpy as np
 from shapely import geometry as shgeo
+from shapely.affinity import translate
 from shapely.ops import linemerge, unary_union
 
 from .auto_fill import (build_fill_stitch_graph,
                         build_travel_graph, collapse_sequential_outline_edges, fallback,
                         find_stitch_path, graph_is_valid, travel)
-from .running_stitch import running_stitch
+from ..debug import debug
 from ..i18n import _
 from ..stitch_plan import Stitch
-from ..utils.geometry import Point as InkstitchPoint, reverse_line_string
+from ..utils.geometry import Point as InkstitchPoint, ensure_geometry_collection, ensure_multi_line_string, reverse_line_string
 
 
 def guided_fill(shape,
                 guideline,
                 angle,
                 row_spacing,
+                num_staggers,
                 max_stitch_length,
                 running_stitch_length,
+                running_stitch_tolerance,
                 skip_last,
                 starting_point,
-                ending_point=None,
-                underpath=True):
-    try:
-        segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing)
-        fill_stitch_graph = build_fill_stitch_graph(shape, segments, 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)
+                ending_point,
+                underpath,
+                strategy
+                ):
+    segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing, num_staggers, max_stitch_length, strategy)
+    fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point)
 
     if not graph_is_valid(fill_stitch_graph, shape, max_stitch_length):
-        return fallback(shape, running_stitch_length)
+        return fallback(shape, running_stitch_length, running_stitch_tolerance)
 
     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, max_stitch_length, running_stitch_length, skip_last)
+    result = path_to_stitches(path, travel_graph, fill_stitch_graph, max_stitch_length, running_stitch_length, running_stitch_tolerance, skip_last)
 
     return result
 
 
-def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, running_stitch_length, skip_last):
+def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, running_stitch_length, running_stitch_tolerance, skip_last):
     path = collapse_sequential_outline_edges(path)
 
     stitches = []
@@ -54,8 +56,7 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, runni
             if edge[0] != path_geometry.coords[0]:
                 path_geometry = reverse_line_string(path_geometry)
 
-            point_list = [Stitch(*point) for point in path_geometry.coords]
-            new_stitches = running_stitch(point_list, stitch_length)
+            new_stitches = [Stitch(*point) for point in path_geometry.coords]
 
             # need to tag stitches
 
@@ -66,12 +67,14 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, runni
 
             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))
+            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, running_stitch_tolerance, skip_last))
 
     return stitches
 
 
-def extend_line(line, minx, maxx, miny, maxy):
+def extend_line(line, shape):
+    (minx, miny, maxx, maxy) = shape.bounds
+
     line = line.simplify(0.01, False)
 
     upper_left = InkstitchPoint(minx, miny)
@@ -91,19 +94,14 @@ def extend_line(line, minx, maxx, miny, maxy):
 
 
 def repair_multiple_parallel_offset_curves(multi_line):
-    lines = linemerge(multi_line)
-    lines = list(lines.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
+    lines = ensure_multi_line_string(linemerge(multi_line))
+    longest_line = max(lines.geoms, key=lambda line: line.length)
+
     # need simplify to avoid doubled points caused by linemerge
-    return lines[max_length_idx].simplify(0.01, False)
+    return longest_line.simplify(0.01, False)
 
 
-def repair_non_simple_lines(line):
+def repair_non_simple_line(line):
     repaired = unary_union(line)
     counter = 0
     # Do several iterations since we might have several concatenated selfcrossings
@@ -122,62 +120,99 @@ def repair_non_simple_lines(line):
         return repaired
 
 
-def intersect_region_with_grating_guideline(shape, line, row_spacing, flip=False):  # noqa: C901
+def take_only_line_strings(thing):
+    things = ensure_geometry_collection(thing)
+    line_strings = [line for line in things.geoms if isinstance(line, shgeo.LineString)]
 
-    row_spacing = abs(row_spacing)
-    (minx, miny, maxx, maxy) = shape.bounds
-    upper_left = InkstitchPoint(minx, miny)
-    rows = []
+    return shgeo.MultiLineString(line_strings)
+
+
+def apply_stitches(line, max_stitch_length, num_staggers, row_spacing, row_num):
+    start = (float(row_num % num_staggers) / num_staggers) * max_stitch_length
+    projections = np.arange(start, line.length, max_stitch_length)
+    points = np.array([line.interpolate(projection).coords[0] for projection in projections])
+    stitched_line = shgeo.LineString(points)
 
+    # stitched_line may round corners, which will look terrible.  This finds the
+    # corners.
+    threshold = row_spacing / 2.0
+    simplified_line = line.simplify(row_spacing / 2.0, False)
+    simplified_points = [shgeo.Point(x, y) for x, y in simplified_line.coords]
+
+    extra_points = []
+    extra_point_projections = []
+    for point in simplified_points:
+        if point.distance(stitched_line) > threshold:
+            extra_points.append(point.coords[0])
+            extra_point_projections.append(line.project(point))
+
+    # Now we need to insert the new points into their correct spots in the line.
+    indices = np.searchsorted(projections, extra_point_projections)
+    if len(indices) > 0:
+        points = np.insert(points, indices, extra_points, axis=0)
+
+    return shgeo.LineString(points)
+
+
+def prepare_guide_line(line, shape):
     if line.geom_type != 'LineString' or not line.is_simple:
-        line = repair_non_simple_lines(line)
+        line = repair_non_simple_line(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, (shgeo.GeometryCollection, shgeo.MultiLineString)) or (not res.is_empty and len(res.coords) > 1):
-        if isinstance(res, (shgeo.GeometryCollection, shgeo.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]
+    line = extend_line(line, shape)
+
+    return line
+
+
+def clean_offset_line(offset_line):
+    offset_line = take_only_line_strings(offset_line)
+
+    if isinstance(offset_line, shgeo.MultiLineString):
+        offset_line = repair_multiple_parallel_offset_curves(offset_line)
+
+    if not offset_line.is_simple:
+        offset_line = repair_non_simple_line(offset_line)
+
+    return offset_line
+
+
+def intersect_region_with_grating_guideline(shape, line, row_spacing, num_staggers, max_stitch_length, strategy):
+    debug.log_line_string(shape.exterior, "guided fill shape")
+
+    if strategy == 0:
+        translate_direction = InkstitchPoint(*line.coords[-1]) - InkstitchPoint(*line.coords[0])
+        translate_direction = translate_direction.unit().rotate_left()
+
+    line = prepare_guide_line(line, shape)
+
+    row = 0
+    direction = 1
+    offset_line = None
+    while True:
+        if strategy == 0:
+            translate_amount = translate_direction * row * direction * row_spacing
+            offset_line = translate(line, xoff=translate_amount.x, yoff=translate_amount.y)
+        elif strategy == 1:
+            offset_line = line.parallel_offset(row * row_spacing * direction, 'left', join_style=shgeo.JOIN_STYLE.bevel)
+
+        offset_line = clean_offset_line(offset_line)
+
+        if strategy == 1 and direction == -1:
+            # negative parallel offsets are reversed, so we need to compensate
+            offset_line = reverse_line_string(offset_line)
+
+        debug.log_line_string(offset_line, f"offset {row * direction}")
 
-        runs.sort(key=lambda seg: (
-                InkstitchPoint(*seg[0]) - upper_left).length())
-        if flip:
-            runs.reverse()
-            runs = [tuple(reversed(run)) for run in runs]
+        stitched_line = apply_stitches(offset_line, max_stitch_length, num_staggers, row_spacing, row * direction)
+        intersection = shape.intersection(stitched_line)
 
-        if row_spacing > 0:
-            rows.append(runs)
+        if intersection.is_empty:
+            if direction == 1:
+                direction = -1
+                row = 1
+            else:
+                break
         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 = reverse_line_string(line_offsetted)
-        line_offsetted = line_offsetted.simplify(0.01, False)
-        res = line_offsetted.intersection(shape)
-        if row_spacing > 0 and not isinstance(res, (shgeo.GeometryCollection, shgeo.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 = reverse_line_string(line_offsetted)
-                line_offsetted = line_offsetted.simplify(0.01, False)
-                res = line_offsetted.intersection(shape)
-
-    for row in rows:
-        yield from row
+            for segment in take_only_line_strings(intersection).geoms:
+                yield segment.coords[:]
+            row += 1
diff --git a/lib/svg/tags.py b/lib/svg/tags.py
index 2561667a..1ff425ec 100644
--- a/lib/svg/tags.py
+++ b/lib/svg/tags.py
@@ -60,6 +60,7 @@ inkstitch_attribs = [
     'auto_fill',
     'fill_method',
     'contour_strategy',
+    'guided_fill_strategy',
     'join_style',
     'avoid_self_crossing',
     'clockwise',
diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index 8d29ddb0..f5ba4ad8 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -5,7 +5,7 @@
 
 import math
 
-from shapely.geometry import LineString, LinearRing, MultiLineString, Polygon, MultiPolygon, GeometryCollection
+from shapely.geometry import LineString, LinearRing, MultiLineString, Polygon, MultiPolygon, MultiPoint, GeometryCollection
 from shapely.geometry import Point as ShapelyPoint
 
 
@@ -78,7 +78,7 @@ def ensure_multi_line_string(thing):
 def ensure_geometry_collection(thing):
     """Given either some kind of geometry or a GeometryCollection, return a GeometryCollection"""
 
-    if isinstance(thing, (MultiLineString, MultiPolygon)):
+    if isinstance(thing, (MultiLineString, MultiPolygon, MultiPoint)):
         return GeometryCollection(thing.geoms)
     elif isinstance(thing, GeometryCollection):
         return thing