Second chance for invalid fill stitch graphs (#2643)

7 files changed, 121 insertions, 135 deletions

diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py
index bc42163e..593791e5 100644
--- a/lib/elements/fill_stitch.py
+++ b/lib/elements/fill_stitch.py
@@ -3,7 +3,6 @@
 # Copyright (c) 2010 Authors
 # Licensed under the GNU GPL version 3.0 or later.  See the file LICENSE for details.
 
-import logging
 import math
 import re
 
@@ -25,6 +24,7 @@ from ..svg import PIXELS_PER_MM, get_node_transform
 from ..svg.clip import get_clip_path
 from ..svg.tags import INKSCAPE_LABEL
 from ..utils import cache
+from ..utils.geometry import ensure_multi_polygon
 from ..utils.param import ParamOption
 from .element import EmbroideryElement, param
 from .validation import ValidationError, ValidationWarning
@@ -557,12 +557,6 @@ class FillStitch(EmbroideryElement):
         # biggest path.
         paths = self.paths
         paths.sort(key=lambda point_list: shgeo.Polygon(point_list).area, reverse=True)
-        # Very small holes will cause a shape to be rendered as an outline only
-        # they are too small to be rendered and only confuse the auto_fill algorithm.
-        # So let's ignore them
-        if shgeo.Polygon(paths[0]).area > 5 and shgeo.Polygon(paths[-1]).area < 5:
-            paths = [path for path in paths if shgeo.Polygon(path).area > 3]
-
         return shgeo.MultiPolygon([(paths[0], paths[1:])])
 
     @property
@@ -570,32 +564,11 @@ class FillStitch(EmbroideryElement):
     def shape(self):
         shape = self._get_clipped_path()
 
-        if self.shape_is_valid(shape):
-            return shape
-
-        # Repair not valid shapes
-        logger = logging.getLogger('shapely.geos')
-        level = logger.level
-        logger.setLevel(logging.CRITICAL)
-
-        valid_shape = make_valid(shape)
+        if shape.is_valid:
+            return ensure_multi_polygon(shape, 3)
 
-        logger.setLevel(level)
-
-        if isinstance(valid_shape, shgeo.Polygon):
-            return shgeo.MultiPolygon([valid_shape])
-        if isinstance(valid_shape, shgeo.LineString):
-            return shgeo.MultiPolygon([])
-        if shape.area == 0:
-            return shgeo.MultiPolygon([])
-
-        polygons = []
-        for polygon in valid_shape.geoms:
-            if isinstance(polygon, shgeo.Polygon) and polygon.area > 5:
-                polygons.append(polygon)
-            if isinstance(polygon, shgeo.MultiPolygon):
-                polygons.extend(polygon.geoms)
-        return shgeo.MultiPolygon(polygons)
+        shape = make_valid(shape)
+        return ensure_multi_polygon(shape, 3)
 
     def _get_clipped_path(self):
         if self.node.clip is None:
@@ -612,40 +585,16 @@ class FillStitch(EmbroideryElement):
         except GEOSException:
             return self.original_shape
 
-        if isinstance(intersection, shgeo.Polygon):
-            return shgeo.MultiPolygon([intersection])
-
-        if isinstance(intersection, shgeo.MultiPolygon):
-            return intersection
-
-        polygons = []
-        if isinstance(intersection, shgeo.GeometryCollection):
-            for geom in intersection.geoms:
-                if isinstance(geom, shgeo.Polygon):
-                    polygons.append(geom)
-        return shgeo.MultiPolygon([polygons])
-
-    def shape_is_valid(self, shape):
-        # Shapely will log to stdout to complain about the shape unless we make
-        # it shut up.
-        logger = logging.getLogger('shapely.geos')
-        level = logger.level
-        logger.setLevel(logging.CRITICAL)
-
-        valid = shape.is_valid
-
-        logger.setLevel(level)
-
-        return valid
+        return intersection
 
     def validation_errors(self):
-        if not self.shape_is_valid(self.shape):
+        if not self.shape.is_valid:
             why = explain_validity(self.shape)
             message, x, y = re.match(r"(?P<message>.+)\[(?P<x>.+)\s(?P<y>.+)\]", why).groups()
             yield InvalidShapeError((x, y))
 
     def validation_warnings(self):  # noqa: C901
-        if not self.shape_is_valid(self.original_shape):
+        if not self.original_shape.is_valid:
             why = explain_validity(self.original_shape)
             message, x, y = re.match(r"(?P<message>.+)\[(?P<x>.+)\s(?P<y>.+)\]", why).groups()
             if "Hole lies outside shell" in message:
diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py
index 40b74d23..ebb1fb6f 100644
--- a/lib/stitches/auto_fill.py
+++ b/lib/stitches/auto_fill.py
@@ -7,22 +7,25 @@
 
 import math
 from itertools import chain, groupby
-import warnings
 
 import networkx
 from shapely import geometry as shgeo
+from shapely import segmentize
 from shapely.ops import snap
 from shapely.strtree import STRtree
 
 from ..debug import debug
 from ..stitch_plan import Stitch
 from ..svg import PIXELS_PER_MM
+from ..utils import cache
 from ..utils.clamp_path import clamp_path_to_polygon
-from ..utils.geometry import Point as InkstitchPoint, line_string_to_point_list, ensure_multi_line_string
-from .fill import intersect_region_with_grating, stitch_row
-from .running_stitch import running_stitch
+from ..utils.geometry import Point as InkstitchPoint
+from ..utils.geometry import (ensure_multi_line_string,
+                              line_string_to_point_list)
 from ..utils.smoothing import smooth_path
 from ..utils.threading import check_stop_flag
+from .fill import intersect_region_with_grating, stitch_row
+from .running_stitch import running_stitch
 
 
 class NoGratingsError(Exception):
@@ -78,9 +81,14 @@ def auto_fill(shape,
     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):
+    if networkx.is_empty(fill_stitch_graph):
+        # The graph may be empty if the shape is so small that it fits between the
+        # rows of stitching.
         return fallback(shape, running_stitch_length, running_stitch_tolerance)
 
+    # ensure graph is eulerian
+    fill_stitch_graph = graph_make_valid(fill_stitch_graph)
+
     travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
 
     if not travel_graph:
@@ -105,14 +113,19 @@ def which_outline(shape, coords):
     # fail sometimes.
 
     point = shgeo.Point(*coords)
-    outlines = ensure_multi_line_string(shape.boundary).geoms
-    outline_indices = list(range(len(outlines)))
+    outlines, outline_indices = get_shape_outlines_and_indices(shape)
     closest = min(outline_indices,
                   key=lambda index: outlines[index].distance(point))
-
     return closest
 
 
+@cache
+def get_shape_outlines_and_indices(shape):
+    outlines = ensure_multi_line_string(shape.boundary).geoms
+    outline_indices = list(range(len(outlines)))
+    return outlines, outline_indices
+
+
 def project(shape, coords, outline_index):
     """project the point onto the specified outline
 
@@ -198,11 +211,25 @@ def insert_node(graph, shape, point):
         if key == "outline" and data['outline'] == outline:
             edges.append(((start, end), data))
 
-    edge, data = min(edges, key=lambda edge_data: shgeo.LineString(edge_data[0]).distance(projected_point))
+    if len(edges) > 0:
+        edge, data = min(edges, key=lambda edge_data: shgeo.LineString(edge_data[0]).distance(projected_point))
+        graph.remove_edge(*edge, key="outline")
+        graph.add_edge(edge[0], node, key="outline", **data)
+        graph.add_edge(node, edge[1], key="outline", **data)
+    else:
+        # The node lies on an outline which has no intersection with any segment.
+        # We need to add a segment to connect the inserted node with the nearest available edge from
+        # an other outline.  It's the best we can do without running into networkx no path errors.
+        for start, end, key, data in graph.edges(keys=True, data=True):
+            if key == "outline":
+                edges.append(((start, end), data))
+        edge, data = min(edges, key=lambda edge_data: shgeo.LineString(edge_data[0]).distance(projected_point))
+        line_segment = shgeo.LineString([edge[0], node])
+        if line_segment.length > 10:
+            line_segment = segmentize(line_segment, 10)
+        graph.add_edge(edge[0], node, key='segment', underpath_edges=[], geometry=line_segment)
+        graph.add_edge(node, edge[1], key='segment', underpath_edges=[], geometry=line_segment.reverse())
 
-    graph.remove_edge(*edge, key="outline")
-    graph.add_edge(edge[0], node, key="outline", **data)
-    graph.add_edge(node, edge[1], key="outline", **data)
     tag_nodes_with_outline_and_projection(graph, shape, nodes=[node])
 
 
@@ -269,17 +296,16 @@ def add_edges_between_outline_nodes(graph, duplicate_every_other=False):
         check_stop_flag()
 
 
-def graph_is_valid(graph):
-    # The graph may be empty if the shape is so small that it fits between the
-    # rows of stitching.  Certain small weird shapes can also cause a non-
-    # eulerian graph.
-    return not networkx.is_empty(graph) and networkx.is_eulerian(graph)
+def graph_make_valid(graph):
+    if not networkx.is_eulerian(graph):
+        return networkx.eulerize(graph)
+    return graph
 
 
 def fallback(shape, running_stitch_length, running_stitch_tolerance):
     """Generate stitches when the auto-fill algorithm fails.
 
-    If graph_is_valid() returns False, we're not going to be able to run the
+    If we received an empty graph, we're not going to be able to run the
     auto-fill algorithm.  Instead, we'll just do running stitch around the
     outside of the shape.  In all likelihood, the shape is so small it won't
     matter.
@@ -373,10 +399,7 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges):
     # 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.
-    with warnings.catch_warnings():
-        # We know about this upcoming change and we don't want to bother users.
-        warnings.filterwarnings('ignore', 'STRtree will be changed in 2.0.0 and will not be compatible with versions < 2.')
-        strtree = STRtree(segments)
+    strtree = STRtree(segments)
 
     # This makes the distance calculations below a bit faster.  We're
     # not looking for high precision anyway.
@@ -647,7 +670,8 @@ def travel(shape, travel_graph, edge, running_stitch_length, running_stitch_tole
         path = smooth_path(path, 2)
     else:
         path = [InkstitchPoint.from_tuple(point) for point in path]
-    path = clamp_path_to_polygon(path, shape)
+    if len(path) > 1:
+        path = clamp_path_to_polygon(path, shape)
 
     points = running_stitch(path, running_stitch_length, running_stitch_tolerance)
     stitches = [Stitch(point) for point in points]
diff --git a/lib/stitches/circular_fill.py b/lib/stitches/circular_fill.py
index 959759dc..ec133f99 100644
--- a/lib/stitches/circular_fill.py
+++ b/lib/stitches/circular_fill.py
@@ -1,3 +1,4 @@
+from networkx import is_empty
 from shapely import geometry as shgeo
 from shapely.ops import substring
 
@@ -5,7 +6,7 @@ from ..stitch_plan import Stitch
 from ..utils.geometry import reverse_line_string
 from .auto_fill import (build_fill_stitch_graph, build_travel_graph,
                         collapse_sequential_outline_edges, fallback,
-                        find_stitch_path, graph_is_valid, travel)
+                        find_stitch_path, graph_make_valid, travel)
 from .contour_fill import _make_fermat_spiral
 from .running_stitch import bean_stitch, running_stitch
 
@@ -73,8 +74,10 @@ def circular_fill(shape,
             segments.append([(point.x, point.y) for point in coords])
 
     fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point)
-    if not graph_is_valid(fill_stitch_graph):
+
+    if is_empty(fill_stitch_graph):
         return fallback(shape, running_stitch_length, running_stitch_tolerance)
+    fill_stitch_graph = graph_make_valid(fill_stitch_graph)
 
     travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
     path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point)
diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py
index 762515f6..6f650028 100644
--- a/lib/stitches/guided_fill.py
+++ b/lib/stitches/guided_fill.py
@@ -3,6 +3,7 @@ from random import random
 
 import numpy as np
 import shapely.prepared
+from networkx import is_empty
 from shapely import geometry as shgeo
 from shapely.affinity import translate
 from shapely.ops import linemerge, nearest_points, unary_union
@@ -15,7 +16,7 @@ from ..utils.geometry import (ensure_geometry_collection,
 from ..utils.threading import check_stop_flag
 from .auto_fill import (auto_fill, build_fill_stitch_graph, build_travel_graph,
                         collapse_sequential_outline_edges, find_stitch_path,
-                        graph_is_valid, travel)
+                        graph_make_valid, travel)
 
 
 def guided_fill(shape,
@@ -39,9 +40,10 @@ def guided_fill(shape,
 
     fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point)
 
-    if not graph_is_valid(fill_stitch_graph):
+    if is_empty(fill_stitch_graph):
         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 = graph_make_valid(fill_stitch_graph)
 
     travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
     path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point)
diff --git a/lib/stitches/linear_gradient_fill.py b/lib/stitches/linear_gradient_fill.py
index 34f91d5a..47dcba2e 100644
--- a/lib/stitches/linear_gradient_fill.py
+++ b/lib/stitches/linear_gradient_fill.py
@@ -7,16 +7,17 @@ from math import ceil, floor, sqrt
 
 import numpy as np
 from inkex import DirectedLineSegment, Transform
-from networkx import eulerize
+from networkx import is_empty
 from shapely import segmentize
 from shapely.affinity import rotate
 from shapely.geometry import LineString, MultiLineString, Point, Polygon
 
 from ..stitch_plan import StitchGroup
 from ..svg import get_node_transform
+from ..utils.geometry import ensure_multi_line_string
 from ..utils.threading import check_stop_flag
 from .auto_fill import (build_fill_stitch_graph, build_travel_graph,
-                        find_stitch_path, graph_is_valid)
+                        find_stitch_path, graph_make_valid)
 from .circular_fill import path_to_stitches
 from .guided_fill import apply_stitches
 
@@ -24,8 +25,6 @@ from .guided_fill import apply_stitches
 def linear_gradient_fill(fill, shape, starting_point, ending_point):
     lines, colors, stop_color_line_indices = _get_lines_and_colors(shape, fill)
     color_lines, colors = _get_color_lines(lines, colors, stop_color_line_indices)
-    if fill.gradient is None:
-        colors.pop()
     stitch_groups = _get_stitch_groups(fill, shape, colors, color_lines, starting_point, ending_point)
     return stitch_groups
 
@@ -45,7 +44,7 @@ def _get_lines_and_colors(shape, fill):
     # get lines
     lines, bottom_line = _get_lines(fill, shape, orig_bbox, angle)
 
-    gradient_start_line_index = round(bottom_line.project(Point(gradient_start)) / fill.row_spacing)
+    gradient_start_line_index = round(bottom_line.project(gradient_start) / fill.row_spacing)
     if gradient_start_line_index == 0:
         gradient_start_line_index = -round(LineString([gradient_start, gradient_end]).project(Point(bottom_line.coords[0])) / fill.row_spacing)
     stop_color_line_indices = [gradient_start_line_index]
@@ -70,7 +69,7 @@ def _get_gradient_info(fill, bbox):
         colors = [style['stop-color'] if float(style['stop-opacity']) > 0 else 'none' for style in fill.gradient.stop_styles]
         gradient_start, gradient_end = gradient_start_end(fill.node, fill.gradient)
         angle = gradient_angle(fill.node, fill.gradient)
-    return angle, colors, offsets, gradient_start, gradient_end
+    return angle, colors, offsets, Point(list(gradient_start)), Point(list(gradient_end))
 
 
 def _get_lines(fill, shape, bounding_box, angle):
@@ -260,22 +259,16 @@ def _get_stitch_groups(fill, shape, colors, color_lines, starting_point, ending_
     for i, color in enumerate(colors):
         lines = color_lines[color]
 
-        multiline = MultiLineString(lines).intersection(shape)
-        if not isinstance(multiline, MultiLineString):
-            if isinstance(multiline, LineString):
-                multiline = MultiLineString([multiline])
-            else:
-                continue
-        segments = [list(line.coords) for line in multiline.geoms if len(line.coords) > 1]
+        multiline = ensure_multi_line_string(MultiLineString(lines).intersection(shape), 1.5)
+        if multiline.is_empty:
+            continue
 
+        segments = [list(line.coords) for line in multiline.geoms if len(line.coords) > 1]
         fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point)
 
-        if not graph_is_valid(fill_stitch_graph):
-            # try to eulerize
-            fill_stitch_graph = eulerize(fill_stitch_graph)
-            # still not valid? continue without rendering the color section
-            if not graph_is_valid(fill_stitch_graph):
-                continue
+        if is_empty(fill_stitch_graph):
+            continue
+        fill_stitch_graph = graph_make_valid(fill_stitch_graph)
 
         travel_graph = build_travel_graph(fill_stitch_graph, shape, fill.angle, False)
         path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point)
@@ -290,7 +283,7 @@ def _get_stitch_groups(fill, shape, colors, color_lines, starting_point, ending_
             False  # no underpath
         )
 
-        stitches = _remove_start_end_travel(fill, stitches, colors, i)
+        stitches = remove_start_end_travel(fill, stitches, colors, i)
 
         stitch_groups.append(StitchGroup(
             color=color,
@@ -304,7 +297,7 @@ def _get_stitch_groups(fill, shape, colors, color_lines, starting_point, ending_
     return stitch_groups
 
 
-def _remove_start_end_travel(fill, stitches, colors, color_section):
+def remove_start_end_travel(fill, stitches, colors, color_section):
     # We can savely remove travel stitches at start since we are changing color all the time
     # but we do care for the first starting point, it is important when they use an underlay of the same color
     remove_before = 0
diff --git a/lib/utils/clamp_path.py b/lib/utils/clamp_path.py
index 432f618a..f6db66a8 100644
--- a/lib/utils/clamp_path.py
+++ b/lib/utils/clamp_path.py
@@ -56,8 +56,10 @@ def adjust_line_end(line, end):
 
 
 def find_border(polygon, point):
+    """Finds subpath of polygon which intersects with the point.
+       Ignores small border fragments"""
     for border in polygon.interiors:
-        if border.intersects(point):
+        if border.length > 0.1 and border.intersects(point):
             return border
     else:
         return polygon.exterior
@@ -76,7 +78,10 @@ def clamp_path_to_polygon(path, polygon):
 
     # This splits the path at the points where it intersects with the polygon
     # border and returns the pieces in the same order as the original path.
-    split_path = ensure_geometry_collection(LineString(path).difference(polygon.boundary))
+    try:
+        split_path = ensure_geometry_collection(LineString(path).difference(polygon.boundary))
+    except FloatingPointError:
+        return path
 
     if len(split_path.geoms) == 1:
         # The path never intersects with the polygon, so it's entirely inside.
diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py
index 6ef0d439..47347a02 100644
--- a/lib/utils/geometry.py
+++ b/lib/utils/geometry.py
@@ -7,7 +7,8 @@ import math
 import typing
 
 import numpy
-from shapely.geometry import LineString, LinearRing, MultiLineString, MultiPolygon, MultiPoint, GeometryCollection
+from shapely.geometry import (GeometryCollection, LinearRing, LineString,
+                              MultiLineString, MultiPolygon)
 from shapely.geometry import Point as ShapelyPoint
 
 
@@ -102,47 +103,56 @@ def reverse_line_string(line_string):
     return LineString(line_string.coords[::-1])
 
 
-def ensure_multi_line_string(thing):
-    """Given either a MultiLineString, a single LineString or GeometryCollection, return a MultiLineString"""
+def ensure_multi_line_string(thing, min_size=0):
+    """Given a shapely geometry, return a MultiLineString"""
+    multi_line_string = MultiLineString()
     if thing.is_empty:
-        return thing
-    if thing.geom_type == "LineString":
-        return MultiLineString([thing])
-    if thing.geom_type == "GeometryCollection":
+        return multi_line_string
+    if thing.geom_type == "MultiLineString":
+        multi_line_string = thing
+    elif thing.geom_type == "LineString":
+        multi_line_string = MultiLineString([thing])
+    elif thing.geom_type == "GeometryCollection":
         multilinestring = []
         for line in thing.geoms:
             if line.geom_type == "LineString":
                 multilinestring.append(line)
-        if multilinestring:
-            return MultiLineString(multilinestring)
-    return thing
+        multi_line_string = MultiLineString(multilinestring)
+    if min_size > 0:
+        multi_line_string = MultiLineString([line for line in multi_line_string.geoms if line.length > min_size])
+    return multi_line_string
 
 
 def ensure_geometry_collection(thing):
-    """Given either some kind of geometry or a GeometryCollection, return a GeometryCollection"""
-
-    if isinstance(thing, (MultiLineString, MultiPolygon, MultiPoint)):
-        return GeometryCollection(thing.geoms)
-    elif isinstance(thing, GeometryCollection):
+    """Given a shapely geometry, return a GeometryCollection"""
+    if thing.is_empty:
+        return GeometryCollection()
+    if thing.geom_type == "GeometryCollection":
         return thing
-    else:
-        return GeometryCollection([thing])
+    if thing.geom_type in ["MultiLineString", "MultiPolygon", "MultiPoint"]:
+        return GeometryCollection(thing.geoms)
+    # LineString, Polygon, Point
+    return GeometryCollection([thing])
 
 
-def ensure_multi_polygon(thing):
-    """Given either a MultiPolygon or a single Polygon, return a MultiPolygon"""
+def ensure_multi_polygon(thing, min_size=0):
+    """Given a shapely geometry, return a MultiPolygon"""
+    multi_polygon = MultiPolygon()
     if thing.is_empty:
-        return thing
-    if thing.geom_type == "Polygon":
-        return MultiPolygon([thing])
-    if thing.geom_type == "GeometryCollection":
+        return multi_polygon
+    if thing.geom_type == "MultiPolygon":
+        multi_polygon = thing
+    elif thing.geom_type == "Polygon":
+        multi_polygon = MultiPolygon([thing])
+    elif thing.geom_type == "GeometryCollection":
         multipolygon = []
         for polygon in thing.geoms:
             if polygon.geom_type == "Polygon":
                 multipolygon.append(polygon)
-        if multipolygon:
-            return MultiPolygon(multipolygon)
-    return thing
+        multi_polygon = MultiPolygon(multipolygon)
+    if min_size > 0:
+        multi_polygon = MultiPolygon([polygon for polygon in multi_polygon.geoms if polygon.area > min_size])
+    return multi_polygon
 
 
 def cut_path(points, length):