Merge pull request #268 from inkstitch/lexelby-auto-fill-run

avoid cutting corners in auto-fill running stitch

4 files changed, 93 insertions, 53 deletions

diff --git a/lib/elements/fill.py b/lib/elements/fill.py
index 8018b2b4..394f523e 100644
--- a/lib/elements/fill.py
+++ b/lib/elements/fill.py
@@ -105,9 +105,12 @@ class Fill(EmbroideryElement):
                         last_pt = pt
                 else:
                     last_pt = pt
-            if point_ary:
+            if len(point_ary) > 2:
                 poly_ary.append(point_ary)
 
+        if not poly_ary:
+            self.fatal(_("shape %s is so small that it cannot be filled with stitches.  Please make it bigger or delete it.") % self.node.get('id'))
+
         # shapely's idea of "holes" are to subtract everything in the second set
         # from the first. So let's at least make sure the "first" thing is the
         # biggest path.
diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 6326ced2..097ab1d9 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -6,9 +6,10 @@ from itertools import groupby, izip
 from collections import deque
 
 from .fill import intersect_region_with_grating, row_num, stitch_row
+from .running_stitch import running_stitch
 from ..i18n import _
 from ..svg import PIXELS_PER_MM
-from ..utils.geometry import Point as InkstitchPoint
+from ..utils.geometry import Point as InkstitchPoint, cut
 
 
 class MaxQueueLengthExceeded(Exception):
@@ -437,58 +438,86 @@ def collapse_sequential_outline_edges(graph, path):
     return new_path
 
 
-def outline_distance(outline, p1, p2):
-    # how far around the outline (and in what direction) do I need to go
-    # to get from p1 to p2?
-
-    p1_projection = outline.project(shapely.geometry.Point(p1))
-    p2_projection = outline.project(shapely.geometry.Point(p2))
-
-    distance = p2_projection - p1_projection
-
-    if abs(distance) > outline.length / 2.0:
-        # if we'd have to go more than halfway around, it's faster to go
-        # the other way
-        if distance < 0:
-            return distance + outline.length
-        elif distance > 0:
-            return distance - outline.length
-        else:
-            # this ought not happen, but just for completeness, return 0 if
-            # p1 and p0 are the same point
-            return 0
-    else:
-        return distance
+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.
+    """
 
-def connect_points(shape, start, end, running_stitch_length):
+    # 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]
 
-    pos = outline.project(shapely.geometry.Point(start))
-    distance = outline_distance(outline, start, end)
-    num_stitches = abs(int(distance / running_stitch_length))
-
-    direction = math.copysign(1.0, distance)
-    one_stitch = running_stitch_length * direction
-
-    stitches = [InkstitchPoint(*outline.interpolate(pos).coords[0])]
-
-    for i in xrange(num_stitches):
-        pos = (pos + one_stitch) % outline.length
-
-        stitches.append(InkstitchPoint(*outline.interpolate(pos).coords[0]))
+    # 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)).
+    if abs(end_projection - start_projection) < row_spacing * 1.4:
+        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 will be None if our starting point happens to already be at
+    # 12 o'clock.
+    if result is not None and result[1] 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))
 
-    end = InkstitchPoint(*end)
-    if (end - stitches[-1]).length() > 0.1 * PIXELS_PER_MM:
-        stitches.append(end)
+    # Now do running stitch along the path we've found.  running_stitch() will
+    # avoid cutting sharp corners.
+    path = [InkstitchPoint(*p) for p in points]
+    return running_stitch(path, running_stitch_length)
 
-    return stitches
 
 def trim_end(path):
     while path and path[-1].is_outline():
         path.pop()
 
+
 def path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers):
     path = collapse_sequential_outline_edges(graph, path)
 
@@ -498,6 +527,6 @@ def path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length,
         if edge.is_segment():
             stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers)
         else:
-            stitches.extend(connect_points(shape, edge[0], edge[1], running_stitch_length))
+            stitches.extend(connect_points(shape, edge[0], edge[1], running_stitch_length, row_spacing))
 
     return stitches
diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index d0cb96cf..bfdcd3c0 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -9,21 +9,22 @@ def cut(line, distance):
     """
     if distance <= 0.0 or distance >= line.length:
         return [LineString(line), None]
-    coords = list(line.coords)
-    for i, p in enumerate(coords):
-        # TODO: I think this doesn't work if the path doubles back on itself
-        pd = line.project(ShapelyPoint(p))
-        if pd == distance:
+    coords = list(ShapelyPoint(p) for p in line.coords)
+    traveled = 0
+    last_point = coords[0]
+    for i, p in enumerate(coords[1:], 1):
+        traveled += p.distance(last_point)
+        last_point = p
+        if traveled == distance:
             return [
                 LineString(coords[:i+1]),
                 LineString(coords[i:])]
-        if pd > distance:
+        if traveled > distance:
             cp = line.interpolate(distance)
             return [
                 LineString(coords[:i] + [(cp.x, cp.y)]),
                 LineString([(cp.x, cp.y)] + coords[i:])]
 
-
 def cut_path(points, length):
     """Return a subsection of at the start of the path that is length units long.
 
diff --git a/messages.po b/messages.po
index 3465114f..e1f5c1cb 100644
--- a/messages.po
+++ b/messages.po
@@ -8,7 +8,7 @@ msgid ""
 msgstr ""
 "Project-Id-Version: PROJECT VERSION\n"
 "Report-Msgid-Bugs-To: EMAIL@ADDRESS\n"
-"POT-Creation-Date: 2018-08-17 15:47-0400\n"
+"POT-Creation-Date: 2018-08-17 16:07-0400\n"
 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
 "Language-Team: LANGUAGE <LL@li.org>\n"
@@ -154,6 +154,13 @@ msgid ""
 "they fall in the same column position."
 msgstr ""
 
+#: lib/elements/fill.py:112
+#, python-format
+msgid ""
+"shape %s is so small that it cannot be filled with stitches.  Please make"
+" it bigger or delete it."
+msgstr ""
+
 #: lib/elements/satin_column.py:10
 msgid "Satin Column"
 msgstr ""
@@ -601,13 +608,13 @@ msgstr ""
 msgid "Stitch #"
 msgstr ""
 
-#: lib/stitches/auto_fill.py:167
+#: lib/stitches/auto_fill.py:168
 msgid ""
 "Unable to autofill.  This most often happens because your shape is made "
 "up of multiple sections that aren't connected."
 msgstr ""
 
-#: lib/stitches/auto_fill.py:392
+#: lib/stitches/auto_fill.py:393
 msgid ""
 "Unexpected error while generating fill stitches. Please send your SVG "
 "file to lexelby@github."