Fixes (#1703)

* guide line position

* use direction from line to shape

* optimize intersection detection

* fix flapack elf

* handle weird guide lines better

* update starting point for self crossing (multiple) fills

* ripple: fixes and non circular join style

* avoid jumps in ripple stitch

* fallback only necessary if shape does not intersect grating

* make valid may return a polygon

* add profiling

* Stitch.__init__ didn't work right and was super slow

* shrink or grow to multipolygon

Co-authored-by: Lex Neva

4 files changed, 129 insertions, 51 deletions

diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index ac1e477b..3ff5a24f 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -59,14 +59,14 @@ def auto_fill(shape,
               starting_point,
               ending_point=None,
               underpath=True):
-    try:
-        rows = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing)
-        segments = [segment for row in rows for segment in row]
-        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
+    rows = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing)
+    if not rows:
+        # Small shapes may not intersect with the grating at all.
         return fallback(shape, running_stitch_length, running_stitch_tolerance)
 
+    segments = [segment for row in rows for segment in row]
+    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, running_stitch_tolerance)
 
diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py
index 46352d4f..7c07b5c2 100644
--- a/lib/stitches/fill.py
+++ b/lib/stitches/fill.py
@@ -132,7 +132,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non
     start -= (start + normal * center) % row_spacing
 
     current_row_y = start
-
+    rows = []
     while current_row_y < end:
         p0 = center + normal * current_row_y + direction * half_length
         p1 = center + normal * current_row_y - direction * half_length
@@ -157,13 +157,15 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non
                 runs.reverse()
                 runs = [tuple(reversed(run)) for run in runs]
 
-            yield runs
+            rows.append(runs)
 
         if end_row_spacing:
             current_row_y += row_spacing + (end_row_spacing - row_spacing) * ((current_row_y - start) / height)
         else:
             current_row_y += row_spacing
 
+    return rows
+
 
 def section_to_stitches(group_of_segments, angle, row_spacing, max_stitch_length, staggers, skip_last):
     stitches = []
diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py
index 7eb49e86..05de14cd 100644
--- a/lib/stitches/guided_fill.py
+++ b/lib/stitches/guided_fill.py
@@ -1,15 +1,20 @@
+from math import atan2, copysign
+from random import random
+
 import numpy as np
+import shapely.prepared
 from shapely import geometry as shgeo
 from shapely.affinity import translate
-from shapely.ops import linemerge, unary_union
+from shapely.ops import linemerge, nearest_points, 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 ..debug import debug
-from ..i18n import _
 from ..stitch_plan import Stitch
-from ..utils.geometry import Point as InkstitchPoint, ensure_geometry_collection, ensure_multi_line_string, reverse_line_string
+from ..utils.geometry import Point as InkstitchPoint
+from ..utils.geometry import (ensure_geometry_collection,
+                              ensure_multi_line_string, reverse_line_string)
+from .auto_fill import (auto_fill, build_fill_stitch_graph, build_travel_graph,
+                        collapse_sequential_outline_edges, find_stitch_path,
+                        graph_is_valid, travel)
 
 
 def guided_fill(shape,
@@ -27,10 +32,15 @@ def guided_fill(shape,
                 strategy
                 ):
     segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing, num_staggers, max_stitch_length, strategy)
+    if not segments:
+        return fallback(shape, guideline, row_spacing, max_stitch_length, running_stitch_length, running_stitch_tolerance,
+                        num_staggers, skip_last, starting_point, ending_point, underpath)
+
     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, running_stitch_tolerance)
+        return fallback(shape, guideline, row_spacing, max_stitch_length, running_stitch_length, running_stitch_tolerance,
+                        num_staggers, skip_last, starting_point, ending_point, underpath)
 
     travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
     path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point)
@@ -39,6 +49,15 @@ def guided_fill(shape,
     return result
 
 
+def fallback(shape, guideline, row_spacing, max_stitch_length, running_stitch_length, running_stitch_tolerance,
+             num_staggers, skip_last, starting_point, ending_point, underpath):
+    # fall back to normal auto-fill with an angle that matches the guideline (sorta)
+    guide_start, guide_end = [guideline.coords[0], guideline.coords[-1]]
+    angle = atan2(guide_end[1] - guide_start[1], guide_end[0] - guide_start[0]) * -1
+    return auto_fill(shape, angle, row_spacing, None, max_stitch_length, running_stitch_length, running_stitch_tolerance,
+                     num_staggers, skip_last, starting_point, ending_point, underpath)
+
+
 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)
 
@@ -75,22 +94,23 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, runni
 def extend_line(line, shape):
     (minx, miny, maxx, maxy) = shape.bounds
 
-    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
+    start_point = InkstitchPoint.from_tuple(line.coords[0])
+    end_point = InkstitchPoint.from_tuple(line.coords[-1])
+    direction = (end_point - start_point).unit()
 
-    point3 = InkstitchPoint(*line.coords[-2])
-    point4 = InkstitchPoint(*line.coords[-1])
-    new_ending_point = point4 + (point4 - point3).unit() * length
+    new_start_point = start_point - direction * length
+    new_end_point = end_point + direction * length
 
-    return shgeo.LineString([new_starting_point.as_tuple()] +
-                            line.coords[1:-1] + [new_ending_point.as_tuple()])
+    # without this, we seem especially likely to run into this libgeos bug:
+    #   https://github.com/shapely/shapely/issues/820
+    new_start_point += InkstitchPoint(random() * 0.01, random() * 0.01)
+    new_end_point += InkstitchPoint(random() * 0.01, random() * 0.01)
+
+    return shgeo.LineString((new_start_point, *line.coords, new_end_point))
 
 
 def repair_multiple_parallel_offset_curves(multi_line):
@@ -114,8 +134,8 @@ def repair_non_simple_line(line):
         repaired = unary_union(linemerge(line_segments))
         counter += 1
     if repaired.geom_type != 'LineString':
-        raise ValueError(
-            _("Guide line (or offset copy) is self crossing!"))
+        # They gave us a line with complicated self-intersections.  Use a fallback.
+        return shgeo.LineString((line.coords[0], line.coords[-1]))
     else:
         return repaired
 
@@ -158,7 +178,12 @@ def prepare_guide_line(line, shape):
     if line.geom_type != 'LineString' or not line.is_simple:
         line = repair_non_simple_line(line)
 
-    # extend the line towards the ends to increase probability that all offsetted curves cross the shape
+    if line.is_ring:
+        # If they pass us a ring, break it to avoid dividing by zero when
+        # calculating a unit vector from start to end.
+        line = shgeo.LineString(line.coords[:-2])
+
+    # extend the end points away from each other
     line = extend_line(line, shape)
 
     return line
@@ -176,24 +201,41 @@ def clean_offset_line(offset_line):
     return offset_line
 
 
+def _get_start_row(line, shape, row_spacing, line_direction):
+    if line.intersects(shape):
+        return 0
+
+    point1, point2 = nearest_points(line, shape.centroid)
+    distance = point1.distance(point2)
+    row = int(distance / row_spacing)
+
+    # This flips the sign of the starting row if the shape is on the other side
+    # of the guide line
+    shape_direction = InkstitchPoint.from_shapely_point(point2) - InkstitchPoint.from_shapely_point(point1)
+    return copysign(row, shape_direction * line_direction)
+
+
 def intersect_region_with_grating_guideline(shape, line, row_spacing, num_staggers, max_stitch_length, strategy):
+    line = prepare_guide_line(line, shape)
+
     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()
+    translate_direction = InkstitchPoint(*line.coords[-1]) - InkstitchPoint(*line.coords[0])
+    translate_direction = translate_direction.unit().rotate_left()
 
-    line = prepare_guide_line(line, shape)
+    shape_envelope = shapely.prepared.prep(shape.convex_hull)
 
-    row = 0
+    start_row = _get_start_row(line, shape, row_spacing, translate_direction)
+    row = start_row
     direction = 1
     offset_line = None
+    rows = []
     while True:
         if strategy == 0:
-            translate_amount = translate_direction * row * direction * row_spacing
+            translate_amount = translate_direction * row * 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 = line.parallel_offset(row * row_spacing, 'left', join_style=shgeo.JOIN_STYLE.round)
 
         offset_line = clean_offset_line(offset_line)
 
@@ -201,18 +243,20 @@ def intersect_region_with_grating_guideline(shape, line, row_spacing, num_stagge
             # 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}")
+        debug.log_line_string(offset_line, f"offset {row}")
 
         stitched_line = apply_stitches(offset_line, max_stitch_length, num_staggers, row_spacing, row * direction)
         intersection = shape.intersection(stitched_line)
 
-        if intersection.is_empty:
+        if shape_envelope.intersects(stitched_line):
+            for segment in take_only_line_strings(intersection).geoms:
+                rows.append(segment.coords[:])
+            row += direction
+        else:
             if direction == 1:
                 direction = -1
-                row = 1
+                row = start_row - 1
             else:
                 break
-        else:
-            for segment in take_only_line_strings(intersection).geoms:
-                yield segment.coords[:]
-            row += 1
+
+    return rows
diff --git a/lib/stitches/ripple_stitch.py b/lib/stitches/ripple_stitch.py
index 489666b0..6a0ef7f0 100644
--- a/lib/stitches/ripple_stitch.py
+++ b/lib/stitches/ripple_stitch.py
@@ -63,6 +63,8 @@ def _get_helper_lines(stroke):
 
         if stroke.is_closed:
             return False, _get_circular_ripple_helper_lines(stroke, outline)
+        elif stroke.join_style == 1:
+            return True, _get_point_style_linear_helper_lines(stroke, outline)
         else:
             return True, _get_linear_ripple_helper_lines(stroke, outline)
 
@@ -74,7 +76,7 @@ def _get_satin_ripple_helper_lines(stroke):
     # use satin column points for satin like build ripple stitches
     rail_points = SatinColumn(stroke.node).plot_points_on_rails(length, 0)
 
-    steps = _get_steps(stroke.line_count, exponent=stroke.exponent, flip=stroke.flip_exponent)
+    steps = _get_steps(stroke.get_line_count(), exponent=stroke.exponent, flip=stroke.flip_exponent)
 
     helper_lines = []
     for point0, point1 in zip(*rail_points):
@@ -83,24 +85,39 @@ def _get_satin_ripple_helper_lines(stroke):
         for step in steps:
             helper_lines[-1].append(InkstitchPoint.from_shapely_point(helper_line.interpolate(step, normalized=True)))
 
-    return helper_lines
+    if stroke.join_style == 1:
+        helper_lines = _converge_helper_line_points(helper_lines, True)
 
+    return helper_lines
 
-def _get_circular_ripple_helper_lines(stroke, outline):
-    helper_lines = _get_linear_ripple_helper_lines(stroke, outline)
 
-    # Now we want to adjust the helper lines to make a spiral.
+def _converge_helper_line_points(helper_lines, point_edge=False):
     num_lines = len(helper_lines)
     steps = _get_steps(num_lines)
     for i, line in enumerate(helper_lines):
         points = []
         for j in range(len(line) - 1):
-            points.append(line[j] * (1 - steps[i]) + line[j + 1] * steps[i])
+            if point_edge and j % 2 == 1:
+                k = num_lines - 1 - i
+                points.append(line[j] * (1 - steps[k]) + line[j + 1] * steps[k])
+            else:
+                points.append(line[j] * (1 - steps[i]) + line[j + 1] * steps[i])
         helper_lines[i] = points
 
     return helper_lines
 
 
+def _get_circular_ripple_helper_lines(stroke, outline):
+    helper_lines = _get_linear_ripple_helper_lines(stroke, outline)
+    # Now we want to adjust the helper lines to make a spiral.
+    return _converge_helper_line_points(helper_lines)
+
+
+def _get_point_style_linear_helper_lines(stroke, outline):
+    helper_lines = _get_linear_ripple_helper_lines(stroke, outline)
+    return _converge_helper_line_points(helper_lines, True)
+
+
 def _get_linear_ripple_helper_lines(stroke, outline):
     guide_line = stroke.get_guide_line()
     max_dist = stroke.grid_size or stroke.running_stitch_length
@@ -124,10 +141,25 @@ def _target_point_helper_lines(stroke, outline):
     return helper_lines
 
 
+def _adjust_helper_lines_for_grid(stroke, helper_lines):
+    num_lines = stroke.line_count - stroke.skip_end
+    if stroke.reverse:
+        helper_lines = [helper_line[::-1] for helper_line in helper_lines]
+        num_lines = stroke.skip_start
+    if (num_lines % 2 != 0 and not stroke.is_closed) or (stroke.is_closed and not stroke.reverse):
+        helper_lines.reverse()
+
+    return helper_lines
+
+
 def _do_grid(stroke, helper_lines):
+    helper_lines = _adjust_helper_lines_for_grid(stroke, helper_lines)
+    start = stroke.get_skip_start()
+    skip_end = stroke.get_skip_end()
+    if stroke.reverse:
+        start, skip_end = skip_end, start
     for i, helper in enumerate(helper_lines):
-        start = stroke.get_skip_start()
-        end = len(helper) - stroke.get_skip_end()
+        end = len(helper) - skip_end
         points = helper[start:end]
         if i % 2 == 0:
             points.reverse()
@@ -146,7 +178,7 @@ def _get_guided_helper_lines(stroke, outline, max_distance):
 
 
 def _generate_guided_helper_lines(stroke, outline, max_distance, guide_line):
-    # helper lines are generated by making copies of the outline alog the guide line
+    # helper lines are generated by making copies of the outline along the guide line
     line_point_dict = defaultdict(list)
     outline = LineString(running_stitch(line_string_to_point_list(outline), max_distance, stroke.running_stitch_tolerance))