refactor, tidy, and C901 fixes

6 files changed, 574 insertions, 650 deletions

diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py
index 5e795f45..d7b859b5 100644
--- a/lib/elements/fill_stitch.py
+++ b/lib/elements/fill_stitch.py
@@ -15,10 +15,9 @@ 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, guided_fill
+from ..stitches import tangential_fill, auto_fill, legacy_fill, guided_fill
 from ..svg import PIXELS_PER_MM
 from ..svg.tags import INKSCAPE_LABEL
-from ..utils import Point as InkstitchPoint
 from ..utils import cache, version
 from .element import EmbroideryElement, param
 from .validation import ValidationError, ValidationWarning
@@ -571,26 +570,40 @@ class FillStitch(EmbroideryElement):
         return [stitch_group]
 
     def do_tangential_fill(self, last_patch, starting_point):
-        stitch_groups = []
-        polygons = self.fill_shape.geoms
         if not starting_point:
             starting_point = (0, 0)
-        for poly in polygons:
-            connected_line = tangential_fill_stitch_line_creator.tangential_fill(
-                poly,
-                self.tangential_strategy,
-                self.row_spacing,
-                self.max_stitch_length,
-                self.join_style + 1,
-                self.clockwise,
-                shgeo.Point(starting_point),
-                self.avoid_self_crossing,
-            )
-            path = [InkstitchPoint(*p) for p in connected_line]
+        starting_point = shgeo.Point(starting_point)
+
+        stitch_groups = []
+        for polygon in self.fill_shape.geoms:
+            tree = tangential_fill.offset_polygon(polygon, self.row_spacing, self.join_style + 1, self.clockwise)
+
+            stitches = []
+            if self.tangential_strategy == 0:
+                stitches = tangential_fill.inner_to_outer(
+                    tree,
+                    self.row_spacing,
+                    self.max_stitch_length,
+                    starting_point,
+                    self.avoid_self_crossing
+                )
+            elif self.tangential_strategy == 1:
+                stitches = tangential_fill.single_spiral(
+                    tree,
+                    self.max_stitch_length,
+                    starting_point
+                )
+            elif self.tangential_strategy == 2:
+                stitches = tangential_fill.double_spiral(
+                    tree,
+                    self.max_stitch_length,
+                    starting_point
+                )
+
             stitch_group = StitchGroup(
                 color=self.color,
                 tags=("auto_fill", "auto_fill_top"),
-                stitches=path)
+                stitches=stitches)
             stitch_groups.append(stitch_group)
 
         return stitch_groups
@@ -611,13 +624,11 @@ class FillStitch(EmbroideryElement):
                 self.angle,
                 self.row_spacing,
                 self.max_stitch_length,
-                min(self.min_stitch_length, self.max_stitch_length),
                 self.running_stitch_length,
                 self.skip_last,
                 starting_point,
                 ending_point,
-                self.underpath,
-                self.interlaced))
+                self.underpath))
         return [stitch_group]
 
     @cache
diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py
index 40728c53..9694a546 100644
--- a/lib/stitches/guided_fill.py
+++ b/lib/stitches/guided_fill.py
@@ -11,19 +11,16 @@ from ..stitch_plan import Stitch
 from ..utils.geometry import Point as InkstitchPoint, reverse_line_string
 
 
-@debug.time
 def guided_fill(shape,
                 guideline,
                 angle,
                 row_spacing,
                 max_stitch_length,
-                min_stitch_length,
                 running_stitch_length,
                 skip_last,
                 starting_point,
                 ending_point=None,
-                underpath=True,
-                offset_by_half=True):
+                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)
@@ -36,15 +33,12 @@ def guided_fill(shape,
 
     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, min_stitch_length, running_stitch_length, skip_last, offset_by_half)
+    result = path_to_stitches(path, travel_graph, fill_stitch_graph, max_stitch_length, running_stitch_length, skip_last)
 
     return result
 
 
-@debug.time
-def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, min_stitch_length,
-                     running_stitch_length, skip_last, offset_by_half):
+def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, running_stitch_length, skip_last):
     path = collapse_sequential_outline_edges(path)
 
     stitches = []
@@ -62,7 +56,7 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing,
                 path_geometry = reverse_line_string(path_geometry)
 
             point_list = [Stitch(*point) for point in path_geometry.coords]
-            new_stitches = running_stitch(point_list, max_stitch_length)
+            new_stitches = running_stitch(point_list, stitch_length)
 
             # need to tag stitches
 
@@ -124,7 +118,7 @@ def repair_non_simple_lines(line):
         counter += 1
     if repaired.geom_type != 'LineString':
         raise ValueError(
-            _("Guide line (or offsetted instance) is self crossing!"))
+            _("Guide line (or offset copy) is self crossing!"))
     else:
         return repaired
 
diff --git a/lib/stitches/tangential_fill.py b/lib/stitches/tangential_fill.py
new file mode 100644
index 00000000..3cc3335f
--- /dev/null
+++ b/lib/stitches/tangential_fill.py
@@ -0,0 +1,538 @@
+from collections import namedtuple
+from itertools import chain
+
+import networkx as nx
+import numpy as np
+import trimesh
+from shapely.geometry import GeometryCollection, MultiPolygon, Polygon, LineString, MultiLineString, Point
+from shapely.geometry.polygon import orient
+from shapely.ops import nearest_points
+from shapely.ops import polygonize
+
+from .running_stitch import running_stitch
+from ..i18n import _
+from ..stitch_plan import Stitch
+from ..stitches import constants
+from ..utils import DotDict
+from ..utils.geometry import cut, reverse_line_string, roll_linear_ring
+from ..utils.geometry import ensure_geometry_collection, ensure_multi_polygon
+
+
+class Tree(nx.DiGraph):
+    # This lets us do tree.nodes['somenode'].parent instead of the default
+    # tree.nodes['somenode']['parent'].
+    node_attr_dict_factory = DotDict
+
+    def __init__(self, *args, **kwargs):
+        self.__node_num = 0
+        super().__init__(**kwargs)
+
+    def generate_node_name(self):
+        node = self.__node_num
+        self.__node_num += 1
+
+        return node
+
+
+nearest_neighbor_tuple = namedtuple(
+    "nearest_neighbor_tuple",
+    [
+        "nearest_point_parent",
+        "nearest_point_child",
+        "proj_distance_parent",
+        "child_node",
+    ],
+)
+
+
+def _offset_linear_ring(ring, offset, resolution, join_style, mitre_limit):
+    result = Polygon(ring).buffer(-offset, resolution, cap_style=2, join_style=join_style, mitre_limit=mitre_limit, single_sided=True)
+    result = ensure_multi_polygon(result)
+
+    rings = GeometryCollection([poly.exterior for poly in result.geoms])
+    rings = rings.simplify(constants.simplification_threshold, False)
+
+    return _take_only_valid_linear_rings(rings)
+
+
+def _take_only_valid_linear_rings(rings):
+    """
+    Removes all geometries which do not form a "valid" LinearRing.
+
+    A "valid" ring is one that does not form a straight line.
+    """
+
+    valid_rings = []
+
+    for ring in ensure_geometry_collection(rings).geoms:
+        if len(ring.coords) > 3 or (len(ring.coords) == 3 and ring.coords[0] != ring.coords[-1]):
+            valid_rings.append(ring)
+
+    return GeometryCollection(valid_rings)
+
+
+def _orient_linear_ring(ring, clockwise=True):
+    # Unfortunately for us, Inkscape SVGs have an inverted Y coordinate.
+    # Normally we don't have to care about that, but in this very specific
+    # case, the meaning of is_ccw is flipped.  It actually tests whether
+    # a ring is clockwise.  That makes this logic super-confusing.
+    if ring.is_ccw != clockwise:
+        return reverse_line_string(ring)
+    else:
+        return ring
+
+
+def _orient_tree(tree, clockwise=True):
+    """
+    Orient all linear rings in the tree.
+
+    Since naturally holes have the opposite point ordering than non-holes we
+    make all lines within the tree uniform (having all the same ordering
+    direction)
+    """
+
+    for node in tree.nodes.values():
+        node.val = _orient_linear_ring(node.val, clockwise)
+
+
+def offset_polygon(polygon, offset, join_style, clockwise):
+    """
+    Convert a polygon to a tree of isocontours.
+
+    An isocontour is an offset version of the polygon's boundary.  For example,
+    the isocontours of a circle are a set of concentric circles inside the
+    circle.
+
+    This function takes a polygon (which may have holes) as input and creates
+    isocontours until the polygon is filled completely.  The isocontours are
+    returned as a Tree, with a parent-child relationship indicating that the
+    parent isocontour contains the child isocontour.
+
+    Arguments:
+        polygon - The shapely Polygon which may have holes
+        offset - The spacing between isocontours
+        join_style - Join style used when offsetting the Polygon border to create
+                     isocontours.  Can be round, mitered or bevel, as defined by
+                     shapely:
+                       https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.JOIN_STYLE
+        clockwise - If True, isocontour points are in clockwise order; if False, counter-clockwise.
+
+    Return Value:
+        Tree - see above
+    """
+
+    ordered_polygon = orient(polygon, -1)
+    tree = Tree()
+    tree.add_node('root', type='node', parent=None, val=ordered_polygon.exterior)
+    active_polygons = ['root']
+    active_holes = [[]]
+
+    for hole in ordered_polygon.interiors:
+        hole_node = tree.generate_node_name()
+        tree.add_node(hole_node, type="hole", val=hole)
+        active_holes[0].append(hole_node)
+
+    while len(active_polygons) > 0:
+        current_poly = active_polygons.pop()
+        current_holes = active_holes.pop()
+
+        outer, inners = _offset_polygon_and_holes(tree, current_poly, current_holes, offset, join_style)
+        polygons = _match_polygons_and_holes(outer, inners)
+
+        for polygon in polygons.geoms:
+            new_polygon, new_holes = _convert_polygon_to_nodes(tree, polygon, parent_polygon=current_poly, child_holes=current_holes)
+
+            if new_polygon is not None:
+                active_polygons.append(new_polygon)
+                active_holes.append(new_holes)
+
+        for previous_hole in current_holes:
+            # If the previous holes are not
+            # contained in the new holes they
+            # have been merged with the
+            # outer polygon
+            if not tree.nodes[previous_hole].parent:
+                tree.nodes[previous_hole].parent = current_poly
+                tree.add_edge(current_poly, previous_hole)
+
+    _orient_tree(tree, clockwise)
+    return tree
+
+
+def _offset_polygon_and_holes(tree, poly, holes, offset, join_style):
+    outer = _offset_linear_ring(
+        tree.nodes[poly].val,
+        offset,
+        resolution=5,
+        join_style=join_style,
+        mitre_limit=10,
+    )
+
+    inners = []
+    for hole in holes:
+        inner = _offset_linear_ring(
+            tree.nodes[hole].val,
+            -offset,  # take negative offset for holes
+            resolution=5,
+            join_style=join_style,
+            mitre_limit=10,
+        )
+        if not inner.is_empty:
+            inners.append(Polygon(inner.geoms[0]))
+
+    return outer, inners
+
+
+def _match_polygons_and_holes(outer, inners):
+    result = MultiPolygon(polygonize(outer.geoms))
+    if len(inners) > 0:
+        result = ensure_geometry_collection(result.difference(MultiPolygon(inners)))
+
+    return result
+
+
+def _convert_polygon_to_nodes(tree, polygon, parent_polygon, child_holes):
+    polygon = orient(polygon, -1)
+
+    if polygon.area < 0.1:
+        return None, None
+
+    polygon = polygon.simplify(constants.simplification_threshold, False)
+    valid_rings = _take_only_valid_linear_rings(polygon.exterior)
+
+    try:
+        exterior = valid_rings.geoms[0]
+    except IndexError:
+        return None, None
+
+    node = tree.generate_node_name()
+    tree.add_node(node, type='node', parent=parent_polygon, val=exterior)
+    tree.add_edge(parent_polygon, node)
+
+    hole_nodes = []
+    for hole in polygon.interiors:
+        hole_node = tree.generate_node_name()
+        tree.add_node(hole_node, type="hole", val=hole)
+        for previous_hole in child_holes:
+            if Polygon(hole).contains(Polygon(tree.nodes[previous_hole].val)):
+                tree.nodes[previous_hole].parent = hole_node
+                tree.add_edge(hole_node, previous_hole)
+        hole_nodes.append(hole_node)
+
+    return node, hole_nodes
+
+
+def _get_nearest_points_closer_than_thresh(travel_line, next_line, threshold):
+    """
+    Find the first point along travel_line that is within threshold of next_line.
+
+    Input:
+        travel_line - The "parent" line for which the distance should
+                      be minimized to enter next_line
+        next_line - contains the next_line which need to be entered
+        threshold - The distance between travel_line and next_line needs
+                    to below threshold to be a valid point for entering
+
+    Return value:
+        tuple or None
+            - the tuple structure is:
+              (point in travel_line, point in next_line)
+            - None is returned if there is no point that satisfies the threshold.
+    """
+
+    # We'll buffer next_line and find the intersection with travel_line.
+    # Then we'll return the very first point in the intersection,
+    # matched with a corresponding point on next_line.  Fortunately for
+    # us, intersection of a Polygon with a LineString yields pieces of
+    # the LineString in the same order as the input LineString.
+    threshold_area = next_line.buffer(threshold)
+    portion_within_threshold = travel_line.intersection(threshold_area)
+
+    if portion_within_threshold.is_empty:
+        return None
+    else:
+        if isinstance(portion_within_threshold, MultiLineString):
+            portion_within_threshold = portion_within_threshold.geoms[0]
+
+        parent_point = Point(portion_within_threshold.coords[0])
+        return nearest_points(parent_point, next_line)
+
+
+def _create_nearest_points_list(
+        travel_line, tree, children, threshold, threshold_hard):
+    """Determine the best place to enter each of parent's children
+
+    Arguments:
+        travel_line - The "parent" line for which the distance should
+                      be minimized to enter each child
+        children - children of travel_line that need to be entered
+        threshold - The distance between travel_line and a child should
+                    to be below threshold to be a valid point for entering
+        threshold_hard - As a last resort, we can accept an entry point
+                         that is this far way
+
+    Return value:
+        list of nearest_neighbor_tuple - indicating where to enter each
+                                         respective child
+    """
+
+    children_nearest_points = []
+
+    for child in children:
+        result = _get_nearest_points_closer_than_thresh(travel_line, tree.nodes[child].val, threshold)
+        if result is None:
+            # where holes meet outer borders a distance
+            # up to 2 * used offset can arise
+            result = _get_nearest_points_closer_than_thresh(travel_line, tree.nodes[child].val, threshold_hard)
+
+        proj = travel_line.project(result[0])
+        children_nearest_points.append(
+            nearest_neighbor_tuple(
+                nearest_point_parent=result[0],
+                nearest_point_child=result[1],
+                proj_distance_parent=proj,
+                child_node=child,
+            )
+        )
+
+    return children_nearest_points
+
+
+def _find_path_inner_to_outer(tree, node, offset, starting_point,
+                              avoid_self_crossing, forward=True):
+    """Find a stitch path for this ring and its children.
+
+    Strategy: A connection from parent to child is made as fast as possible to
+    reach the innermost child as fast as possible in order to stitch afterwards
+    from inner to outer.
+
+    This function calls itself recursively to find a stitch path for each child
+    (and its children).
+
+    Arguments:
+        tree - a Tree of isocontours (as returned by offset_polygon)
+        offset - offset that was passed to offset_polygon
+        starting_point - starting point for stitching
+        avoid_self_crossing - if True, tries to generate a path that does not
+                              cross itself.
+        forward - if True, this ring will be stitched in its natural direction
+                  (used internally by avoid_self_crossing)
+
+    Return value:
+        LineString -- the stitching path
+    """
+
+    current_node = tree.nodes[node]
+    current_ring = current_node.val
+
+    if not forward and avoid_self_crossing:
+        current_ring = reverse_line_string(current_ring)
+
+    # reorder the coordinates of this ring so that it starts with
+    # a point nearest the starting_point
+    start_distance = current_ring.project(starting_point)
+    current_ring = roll_linear_ring(current_ring, start_distance)
+    current_node.val = current_ring
+
+    # Find where along this ring to connect to each child.
+    nearest_points_list = _create_nearest_points_list(
+        current_ring,
+        tree,
+        tree[node],
+        constants.offset_factor_for_adjacent_geometry * offset,
+        2.05 * offset
+    )
+    nearest_points_list.sort(key=lambda tup: tup.proj_distance_parent)
+
+    result_coords = []
+    if not nearest_points_list:
+        # We have no children, so we're at the center of a spiral.  Reversing
+        # the ring gives a nicer visual appearance.
+        # current_ring = reverse_line_string(current_ring)
+        pass
+    else:
+        # This is a recursive algorithm.  We'll stitch along this ring, pausing
+        # to jump to each child ring in turn and sew it before continuing on
+        # this ring.  We'll end back where we started.
+
+        result_coords.append(current_ring.coords[0])
+        distance_so_far = 0
+        for child_connection in nearest_points_list:
+            # Cut this ring into pieces before and after where this child will connect.
+            before, after = cut(current_ring, child_connection.proj_distance_parent - distance_so_far)
+            distance_so_far += child_connection.proj_distance_parent
+
+            # Stitch the part leading up to this child.
+            if before is not None:
+                result_coords.extend(before.coords)
+
+            # Stitch this child.  The child will start and end in the same
+            # place, which should be close to our current location.
+            child_path = _find_path_inner_to_outer(
+                tree,
+                child_connection.child_node,
+                offset,
+                child_connection.nearest_point_child,
+                avoid_self_crossing,
+                not forward
+            )
+            result_coords.extend(child_path.coords)
+
+            # Skip ahead a little bit on this ring before resuming.  This
+            # gives a nice spiral pattern, where we spiral out from the
+            # innermost child.
+            if after is not None:
+                skip, after = cut(after, offset)
+                distance_so_far += offset
+
+            current_ring = after
+
+    if current_ring is not None:
+        # skip a little at the end so we don't end exactly where we started.
+        remaining_length = current_ring.length
+        if remaining_length > offset:
+            current_ring, skip = cut(current_ring, current_ring.length - offset)
+
+        result_coords.extend(current_ring.coords)
+
+    return LineString(result_coords)
+
+
+def inner_to_outer(tree, offset, stitch_length, starting_point, avoid_self_crossing):
+    """Fill a shape with spirals, from innermost to outermost."""
+
+    stitch_path = _find_path_inner_to_outer(tree, 'root', offset, starting_point, avoid_self_crossing)
+    points = [Stitch(*point) for point in stitch_path.coords]
+    stitches = running_stitch(points, stitch_length)
+
+    return stitches
+
+
+def _reorder_linear_ring(ring, start):
+    distances = ring - start
+    start_index = np.argmin(np.linalg.norm(distances, axis=1))
+    return np.roll(ring, -start_index, axis=0)
+
+
+def _interpolate_linear_rings(ring1, ring2, max_stitch_length, start=None):
+    """
+    Interpolate between two LinearRings
+
+    Creates a path from start_point on ring1 and around the rings, ending at a
+    nearby point on ring2.  The path will smoothly transition from ring1 to
+    ring2 as it travels around the rings.
+
+    Inspired by interpolate() from https://github.com/mikedh/pocketing/blob/master/pocketing/polygons.py
+
+    Arguments:
+        ring1 -- LinearRing start point will lie on
+        ring2 -- LinearRing end point will lie on
+        max_stitch_length -- maximum stitch length (used to calculate resampling accuracy)
+        start -- Point on ring1 to start at, as a tuple
+
+    Return value: Path interpolated between two LinearRings, as a LineString.
+    """
+
+    # Resample the two LinearRings so that they are the same number of points
+    # long.  Then take the corresponding points in each ring and interpolate
+    # between them, gradually going more toward ring2.
+    #
+    # This is a little less accurate than the method in interpolate(), but several
+    # orders of magnitude faster because we're not building and querying a KDTree.
+
+    num_points = int(20 * ring1.length / max_stitch_length)
+    ring1_resampled = trimesh.path.traversal.resample_path(np.array(ring1.coords), count=num_points)
+    ring2_resampled = trimesh.path.traversal.resample_path(np.array(ring2.coords), count=num_points)
+
+    if start is not None:
+        ring1_resampled = _reorder_linear_ring(ring1_resampled, start)
+        ring2_resampled = _reorder_linear_ring(ring2_resampled, start)
+
+    weights = np.linspace(0.0, 1.0, num_points).reshape((-1, 1))
+    points = (ring1_resampled * (1.0 - weights)) + (ring2_resampled * weights)
+    result = LineString(points)
+
+    # TODO: remove when rastering is cheaper
+    return result.simplify(constants.simplification_threshold, False)
+
+
+def _check_and_prepare_tree_for_valid_spiral(tree):
+    """Check whether spiral fill is possible, and tweak if necessary.
+
+    Takes a tree consisting of isocontours. If a parent has more than one child
+    we cannot create a spiral. However, to make the routine more robust, we
+    allow more than one child if only one of the children has own children. The
+    other children are removed in this routine then. If the routine returns true,
+    the tree will have been cleaned up from unwanted children.
+
+    If even with these weaker constraints, a spiral is not possible, False is
+    returned.
+    """
+
+    def process_node(node):
+        children = set(tree[node])
+
+        if len(children) == 0:
+            return True
+        elif len(children) == 1:
+            child = children.pop()
+            return process_node(child)
+        else:
+            children_with_children = {child for child in children if tree[child]}
+            if len(children_with_children) > 1:
+                # Node has multiple children with children, so a perfect spiral is not possible.
+                # This False value will be returned all the way up the stack.
+                return False
+            elif len(children_with_children) == 1:
+                children_without_children = children - children_with_children
+                child = children_with_children.pop()
+                tree.remove_nodes_from(children_without_children)
+                return process_node(child)
+            else:
+                # None of the children has its own children, so we'll just take the longest.
+                longest = max(children, key=lambda child: tree[child]['val'].length)
+                shorter_children = children - {longest}
+                tree.remove_nodes_from(shorter_children)
+                return process_node(longest)
+
+    return process_node('root')
+
+
+def single_spiral(tree, stitch_length, starting_point):
+    """Fill a shape with a single spiral going from outside to center."""
+    return _spiral_fill(tree, stitch_length, starting_point, _make_spiral)
+
+
+def double_spiral(tree, stitch_length, starting_point):
+    """Fill a shape with a double spiral going from outside to center and back to outside. """
+    return _spiral_fill(tree, stitch_length, starting_point, _make_fermat_spiral)
+
+
+def _spiral_fill(tree, stitch_length, close_point, spiral_maker):
+    if not _check_and_prepare_tree_for_valid_spiral(tree):
+        raise ValueError(_("Shape cannot be filled with single or double spiral!"))
+
+    starting_point = close_point.coords[0]
+    rings = [tree.nodes[node].val for node in nx.dfs_preorder_nodes(tree, 'root')]
+    path = spiral_maker(rings, stitch_length, starting_point)
+    path = [Stitch(*stitch) for stitch in path]
+
+    return running_stitch(path, stitch_length)
+
+
+def _make_fermat_spiral(rings, stitch_length, starting_point):
+    forward = _make_spiral(rings[::2], stitch_length, starting_point)
+    back = _make_spiral(rings[1::2], stitch_length, starting_point)
+    back.reverse()
+
+    return chain(forward, back)
+
+
+def _make_spiral(rings, stitch_length, starting_point):
+    path = []
+
+    for ring1, ring2 in zip(rings[:-1], rings[1:]):
+        spiral_part = _interpolate_linear_rings(ring1, ring2, stitch_length, starting_point)
+        path.extend(spiral_part.coords)
+
+    return path
diff --git a/lib/stitches/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py
deleted file mode 100644
index 1c10c397..00000000
--- a/lib/stitches/tangential_fill_stitch_line_creator.py
+++ /dev/null
@@ -1,279 +0,0 @@
-from enum import IntEnum
-
-import networkx as nx
-from shapely.geometry import Polygon, MultiPolygon, GeometryCollection
-from shapely.geometry.polygon import orient
-from shapely.ops import polygonize
-
-from .running_stitch import running_stitch
-from ..stitch_plan import Stitch
-from ..stitches import constants
-from ..stitches import tangential_fill_stitch_pattern_creator
-from ..utils import DotDict
-from ..utils.geometry import reverse_line_string, ensure_geometry_collection, ensure_multi_polygon
-
-
-class Tree(nx.DiGraph):
-    # This lets us do tree.nodes['somenode'].parent instead of the default
-    # tree.nodes['somenode']['parent'].
-    node_attr_dict_factory = DotDict
-
-
-def offset_linear_ring(ring, offset, resolution, join_style, mitre_limit):
-    result = Polygon(ring).buffer(-offset, resolution, cap_style=2, join_style=join_style, mitre_limit=mitre_limit, single_sided=True)
-    result = ensure_multi_polygon(result)
-
-    rings = GeometryCollection([poly.exterior for poly in result.geoms])
-    rings = rings.simplify(constants.simplification_threshold, False)
-
-    return take_only_valid_linear_rings(rings)
-
-
-def take_only_valid_linear_rings(rings):
-    """
-    Removes all geometries which do not form a "valid" LinearRing
-    (meaning a ring which does not form a straight line)
-    """
-
-    valid_rings = []
-
-    for ring in ensure_geometry_collection(rings).geoms:
-        if len(ring.coords) > 3 or (len(ring.coords) == 3 and ring.coords[0] != ring.coords[-1]):
-            valid_rings.append(ring)
-
-    return GeometryCollection(valid_rings)
-
-
-def orient_linear_ring(ring, clockwise=True):
-    # Unfortunately for us, Inkscape SVGs have an inverted Y coordinate.
-    # Normally we don't have to care about that, but in this very specific
-    # case, the meaning of is_ccw is flipped.  It actually tests whether
-    # a ring is clockwise.  That makes this logic super-confusing.
-    if ring.is_ccw != clockwise:
-        return reverse_line_string(ring)
-    else:
-        return ring
-
-
-def make_tree_uniform(tree, clockwise=True):
-    """
-    Since naturally holes have the opposite point ordering than non-holes we
-    make all lines within the tree "root" uniform (having all the same
-    ordering direction)
-    """
-
-    for node in tree.nodes.values():
-        node.val = orient_linear_ring(node.val, clockwise)
-
-
-# Used to define which stitching strategy shall be used
-class StitchingStrategy(IntEnum):
-    INNER_TO_OUTER = 0
-    SINGLE_SPIRAL = 1
-    DOUBLE_SPIRAL = 2
-
-
-def check_and_prepare_tree_for_valid_spiral(tree):
-    """
-    Takes a tree consisting of offsetted curves. If a parent has more than one child we
-    cannot create a spiral. However, to make the routine more robust, we allow more than
-    one child if only one of the childs has own childs. The other childs are removed in this
-    routine then. If the routine returns true, the tree will have been cleaned up from unwanted
-    childs. If the routine returns false even under the mentioned weaker conditions the
-    tree cannot be connected by one spiral.
-    """
-
-    def process_node(node):
-        children = set(tree[node])
-
-        if len(children) == 0:
-            return True
-        elif len(children) == 1:
-            child = children.pop()
-            return process_node(child)
-        else:
-            children_with_children = {child for child in children if tree[child]}
-            if len(children_with_children) > 1:
-                # Node has multiple children with children, so a perfect spiral is not possible.
-                # This False value will be returned all the way up the stack.
-                return False
-            elif len(children_with_children) == 1:
-                children_without_children = children - children_with_children
-                child = children_with_children.pop()
-                tree.remove_nodes_from(children_without_children)
-                return process_node(child)
-            else:
-                # None of the children has its own children, so we'll just take the longest.
-                longest = max(children, key=lambda child: tree[child]['val'].length)
-                shorter_children = children - {longest}
-                tree.remove_nodes_from(shorter_children)
-                return process_node(longest)
-
-    return process_node('root')
-
-
-def offset_poly(poly, offset, join_style, clockwise):
-    """
-    Takes a polygon (which can have holes) as input and creates offsetted
-    versions until the polygon is filled with these smaller offsets.
-    These created geometries are afterwards connected to each other and
-    resampled with a maximum stitch_distance.
-    The return value is a LineString which should cover the full polygon.
-    Input:
-    -poly: The shapely polygon which can have holes
-    -offset: The used offset for the curves
-    -join_style: Join style for the offset - can be round, mitered or bevel
-     (https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.JOIN_STYLE)
-     For examples look at
-     https://shapely.readthedocs.io/en/stable/_images/parallel_offset.png
-    -stitch_distance maximum allowed stitch distance between two points
-    -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting
-     offsetted paths might be shorter.
-    -offset_by_half: True if the points shall be interlaced
-    -strategy: According to StitchingStrategy enum class you can select between
-     different strategies for the connection between parent and childs. In
-     addition it offers the option "SPIRAL" which creates a real spiral towards inner.
-     In contrast to the other two options, "SPIRAL" does not end at the starting point
-     but at the innermost point
-    -starting_point: Defines the starting point for the stitching
-    -avoid_self_crossing: don't let the path cross itself when using the Inner to Outer strategy
-    Output:
-    -List of point coordinate tuples
-    -Tag (origin) of each point to analyze why a point was placed
-     at this position
-    """
-
-    ordered_poly = orient(poly, -1)
-    tree = Tree()
-    tree.add_node('root', type='node', parent=None, val=ordered_poly.exterior)
-    active_polys = ['root']
-    active_holes = [[]]
-
-    # We don't care about the names of the nodes, we just need them to be unique.
-    node_num = 0
-
-    for hole in ordered_poly.interiors:
-        tree.add_node(node_num, type="hole", val=hole)
-        active_holes[0].append(node_num)
-        node_num += 1
-
-    while len(active_polys) > 0:
-        current_poly = active_polys.pop()
-        current_holes = active_holes.pop()
-        outer, inners = offset_polygon_and_holes(tree, current_poly, current_holes, offset, join_style)
-
-        if not outer.is_empty:
-            polygons = match_polygons_and_holes(outer, inners)
-
-            if not polygons.is_empty:
-                for polygon in polygons.geoms:
-                    new_polygon, new_holes = convert_polygon_to_nodes(tree, polygon, parent_polygon=current_poly, child_holes=current_holes)
-
-                    if new_polygon:
-                        active_polys.append(new_polygon)
-                        active_holes.append(new_holes)
-
-        for previous_hole in current_holes:
-            # If the previous holes are not
-            # contained in the new holes they
-            # have been merged with the
-            # outer polygon
-            if not tree.nodes[previous_hole].parent:
-                tree.nodes[previous_hole].parent = current_poly
-                tree.add_edge(current_poly, previous_hole)
-
-    make_tree_uniform(tree, clockwise)
-
-    return tree
-
-
-def offset_polygon_and_holes(tree, poly, holes, offset, join_style):
-    outer = offset_linear_ring(
-        tree.nodes[poly].val,
-        offset,
-        resolution=5,
-        join_style=join_style,
-        mitre_limit=10,
-    )
-
-    inners = []
-    for hole in holes:
-        inner = offset_linear_ring(
-            tree.nodes[hole].val,
-            -offset,  # take negative offset for holes
-            resolution=5,
-            join_style=join_style,
-            mitre_limit=10,
-        )
-        if not inner.is_empty:
-            inners.append(Polygon(inner.geoms[0]))
-
-    return outer, inners
-
-
-def match_polygons_and_holes(outer, inners):
-    result = MultiPolygon(polygonize(outer))
-    if len(inners) > 0:
-        result = ensure_geometry_collection(result.difference(MultiPolygon(inners)))
-
-    return result
-
-
-def convert_polygon_to_nodes(tree, polygon, parent_polygon, child_holes):
-    polygon = orient(polygon, -1)
-
-    if polygon.area < 0.1:
-        return None, None
-
-    polygon = polygon.simplify(constants.simplification_threshold, False)
-    valid_rings = take_only_valid_linear_rings(polygon.exterior)
-
-    try:
-        exterior = valid_rings.geoms[0]
-    except IndexError:
-        return None, None
-
-    node = id(polygon)  # just needs to be unique
-
-    tree.add_node(node, type='node', parent=parent_polygon, val=exterior)
-    tree.add_edge(parent_polygon, node)
-
-    hole_node_list = []
-    for hole in polygon.interiors:
-        hole_node = id(hole)
-        tree.add_node(hole_node, type="hole", val=hole)
-        for previous_hole in child_holes:
-            if Polygon(hole).contains(Polygon(tree.nodes[previous_hole].val)):
-                tree.nodes[previous_hole].parent = hole_node
-                tree.add_edge(hole_node, previous_hole)
-        hole_node_list.append(hole_node)
-
-    return node, hole_node_list
-
-
-def tangential_fill(poly, strategy, offset, stitch_distance, join_style, clockwise, starting_point, avoid_self_crossing):
-    if strategy in (StitchingStrategy.SINGLE_SPIRAL, StitchingStrategy.DOUBLE_SPIRAL) and len(poly.interiors) > 1:
-        raise ValueError(
-            "Single spiral geometry must not have more than one hole!")
-
-    tree = offset_poly(poly, offset, join_style, clockwise)
-
-    if strategy == StitchingStrategy.INNER_TO_OUTER:
-        connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_from_inner_to_outer(
-            tree, 'root', offset, stitch_distance, starting_point, avoid_self_crossing)
-        path = [Stitch(*point) for point in connected_line.coords]
-        return running_stitch(path, stitch_distance)
-    elif strategy == StitchingStrategy.SINGLE_SPIRAL:
-        if not check_and_prepare_tree_for_valid_spiral(tree):
-            raise ValueError("Geometry cannot be filled with one spiral!")
-        connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_single_spiral(
-            tree, offset, stitch_distance, starting_point)
-    elif strategy == StitchingStrategy.DOUBLE_SPIRAL:
-        if not check_and_prepare_tree_for_valid_spiral(tree):
-            raise ValueError("Geometry cannot be filled with a double spiral!")
-        connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_double_spiral(
-            tree, offset, stitch_distance, starting_point)
-    else:
-        raise ValueError("Invalid stitching stratety!")
-
-    return connected_line
diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py
deleted file mode 100644
index a19c0a0a..00000000
--- a/lib/stitches/tangential_fill_stitch_pattern_creator.py
+++ /dev/null
@@ -1,339 +0,0 @@
-from collections import namedtuple
-from itertools import chain
-import networkx as nx
-import numpy as np
-import trimesh
-from shapely.geometry import Point, LineString, LinearRing, MultiLineString
-from shapely.ops import nearest_points
-
-from .running_stitch import running_stitch
-
-from ..debug import debug
-from ..stitches import constants
-from ..stitch_plan import Stitch
-from ..utils.geometry import cut, roll_linear_ring, reverse_line_string
-
-nearest_neighbor_tuple = namedtuple(
-    "nearest_neighbor_tuple",
-    [
-        "nearest_point_parent",
-        "nearest_point_child",
-        "proj_distance_parent",
-        "child_node",
-    ],
-)
-
-
-def get_nearest_points_closer_than_thresh(travel_line, next_line, threshold):
-    """
-    Find the first point along travel_line that is within threshold of next_line.
-
-    Input:
-    -travel_line: The "parent" line for which the distance should
-     be minimized to enter next_line
-    -next_line: contains the next_line which need to be entered
-    -threshold: The distance between travel_line and next_line needs
-     to below threshold to be a valid point for entering
-
-    Output:
-    -tuple or None
-      - the tuple structure is:
-        (nearest point in travel_line, nearest point in next_line)
-      - None is returned if there is no point that satisfies the threshold.
-    """
-
-    # We'll buffer next_line and find the intersection with travel_line.
-    # Then we'll return the very first point in the intersection,
-    # matched with a corresponding point on next_line.  Fortunately for
-    # us, intersection of a Polygon with a LineString yields pieces of
-    # the LineString in the same order as the input LineString.
-    threshold_area = next_line.buffer(threshold)
-    portion_within_threshold = travel_line.intersection(threshold_area)
-
-    if portion_within_threshold.is_empty:
-        return None
-    else:
-        if isinstance(portion_within_threshold, MultiLineString):
-            portion_within_threshold = portion_within_threshold.geoms[0]
-
-        parent_point = Point(portion_within_threshold.coords[0])
-        return nearest_points(parent_point, next_line)
-
-
-def create_nearest_points_list(
-        travel_line, tree, children_list, threshold, threshold_hard):
-    """
-    Takes a line and calculates the nearest distance along this line to
-    enter the childs in children_list
-    The method calculates the distances along the line and along the
-    reversed line to find the best direction which minimizes the overall
-    distance for all childs.
-    Input:
-    -travel_line: The "parent" line for which the distance should
-     be minimized to enter the childs
-    -children_list: contains the childs of travel_line which need to be entered
-    -threshold: The distance between travel_line and a child needs to be
-     below threshold to be a valid point for entering
-    -preferred_direction: Put a bias on the desired travel direction along
-     travel_line. If equals zero no bias is applied.
-     preferred_direction=1 means we prefer the direction of travel_line;
-     preferred_direction=-1 means we prefer the opposite direction.
-    Output:
-    -stitching direction for travel_line
-    -list of tuples (one tuple per child). The tuple structure is:
-     ((nearest point in travel_line, nearest point in child),
-       distance along travel_line, belonging child)
-    """
-
-    children_nearest_points = []
-
-    for child in children_list:
-        result = get_nearest_points_closer_than_thresh(travel_line, tree.nodes[child].val, threshold)
-        if result is None:
-            # where holes meet outer borders a distance
-            # up to 2 * used offset can arise
-            result = get_nearest_points_closer_than_thresh(travel_line, tree.nodes[child].val, threshold_hard)
-
-        proj = travel_line.project(result[0])
-        children_nearest_points.append(
-            nearest_neighbor_tuple(
-                nearest_point_parent=result[0],
-                nearest_point_child=result[1],
-                proj_distance_parent=proj,
-                child_node=child,
-            )
-        )
-
-    return children_nearest_points
-
-
-def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, starting_point,
-                                            avoid_self_crossing, forward=True):
-    """
-    Takes the offset curves organized as a tree, connects and samples them.
-    Strategy: A connection from parent to child is made as fast as possible to
-    reach the innermost child as fast as possible in order to stitch afterwards
-    from inner to outer.
-    Input:
-    -tree: contains the offsetted curves in a hierachical organized
-     data structure.
-    -used_offset: used offset when the offsetted curves were generated
-    -stitch_distance: maximum allowed distance between two points
-     after sampling
-    -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting
-     offsetted paths might be shorter.
-    -close_point: defines the beginning point for stitching
-     (stitching starts always from the undisplaced curve)
-    -offset_by_half: If true the resulting points are interlaced otherwise not.
-    Returnvalues:
-    -All offsetted curves connected to one line and sampled with points obeying
-     stitch_distance and offset_by_half
-    -Tag (origin) of each point to analyze why a point was placed
-     at this position
-    """
-
-    current_node = tree.nodes[node]
-    current_ring = current_node.val
-
-    if not forward and avoid_self_crossing:
-        current_ring = reverse_line_string(current_ring)
-
-    # reorder the coordinates of this ring so that it starts with
-    # a point nearest the starting_point
-    start_distance = current_ring.project(starting_point)
-    current_ring = roll_linear_ring(current_ring, start_distance)
-    current_node.val = current_ring
-
-    # Find where along this ring to connect to each child.
-    nearest_points_list = create_nearest_points_list(
-        current_ring,
-        tree,
-        tree[node],
-        constants.offset_factor_for_adjacent_geometry * offset,
-        2.05 * offset
-    )
-    nearest_points_list.sort(key=lambda tup: tup.proj_distance_parent)
-
-    result_coords = []
-    if not nearest_points_list:
-        # We have no children, so we're at the center of a spiral.  Reversing
-        # the ring gives a nicer visual appearance.
-        # current_ring = reverse_line_string(current_ring)
-        pass
-    else:
-        # This is a recursive algorithm.  We'll stitch along this ring, pausing
-        # to jump to each child ring in turn and sew it before continuing on
-        # this ring.  We'll end back where we started.
-
-        result_coords.append(current_ring.coords[0])
-        distance_so_far = 0
-        for child_connection in nearest_points_list:
-            # Cut this ring into pieces before and after where this child will connect.
-            before, after = cut(current_ring, child_connection.proj_distance_parent - distance_so_far)
-            distance_so_far += child_connection.proj_distance_parent
-
-            # Stitch the part leading up to this child.
-            if before is not None:
-                result_coords.extend(before.coords)
-
-            # Stitch this child.  The child will start and end in the same
-            # place, which should be close to our current location.
-            child_path = connect_raster_tree_from_inner_to_outer(
-                tree,
-                child_connection.child_node,
-                offset,
-                stitch_distance,
-                child_connection.nearest_point_child,
-                avoid_self_crossing,
-                not forward
-            )
-            result_coords.extend(child_path.coords)
-
-            # Skip ahead a little bit on this ring before resuming.  This
-            # gives a nice spiral pattern, where we spiral out from the
-            # innermost child.
-            if after is not None:
-                skip, after = cut(after, offset)
-                distance_so_far += offset
-
-            current_ring = after
-
-    if current_ring is not None:
-        # skip a little at the end so we don't end exactly where we started.
-        remaining_length = current_ring.length
-        if remaining_length > offset:
-            current_ring, skip = cut(current_ring, current_ring.length - offset)
-
-        result_coords.extend(current_ring.coords)
-
-    return LineString(result_coords)
-
-
-def reorder_linear_ring(ring, start):
-    distances = ring - start
-    start_index = np.argmin(np.linalg.norm(distances, axis=1))
-    return np.roll(ring, -start_index, axis=0)
-
-
-def interpolate_linear_rings(ring1, ring2, max_stitch_length, start=None):
-    """
-    Interpolate between two LinearRings
-
-    Creates a path from start_point on ring1 and around the rings, ending at a
-    nearby point on ring2.  The path will smoothly transition from ring1 to
-    ring2 as it travels around the rings.
-
-    Inspired by interpolate() from https://github.com/mikedh/pocketing/blob/master/pocketing/polygons.py
-
-    Arguments:
-        ring1 -- LinearRing start point will lie on
-        ring2 -- LinearRing end point will lie on
-        max_stitch_length -- maximum stitch length (used to calculate resampling accuracy)
-        start -- Point on ring1 to start at, as a tuple
-
-    Return value: Path interpolated between two LinearRings, as a LineString.
-    """
-
-    # Resample the two LinearRings so that they are the same number of points
-    # long.  Then take the corresponding points in each ring and interpolate
-    # between them, gradually going more toward ring2.
-    #
-    # This is a little less accurate than the method in interpolate(), but several
-    # orders of magnitude faster because we're not building and querying a KDTree.
-
-    num_points = int(20 * ring1.length / max_stitch_length)
-    ring1_resampled = trimesh.path.traversal.resample_path(np.array(ring1.coords), count=num_points)
-    ring2_resampled = trimesh.path.traversal.resample_path(np.array(ring2.coords), count=num_points)
-
-    if start is not None:
-        ring1_resampled = reorder_linear_ring(ring1_resampled, start)
-        ring2_resampled = reorder_linear_ring(ring2_resampled, start)
-
-    weights = np.linspace(0.0, 1.0, num_points).reshape((-1, 1))
-    points = (ring1_resampled * (1.0 - weights)) + (ring2_resampled * weights)
-    result = LineString(points)
-
-    # TODO: remove when rastering is cheaper
-    return result.simplify(constants.simplification_threshold, False)
-
-
-def connect_raster_tree_single_spiral(tree, used_offset, stitch_distance, close_point):  # noqa: C901
-    """
-    Takes the offsetted curves organized as tree, connects and samples them as a spiral.
-    It expects that each node in the tree has max. one child
-    Input:
-    -tree: contains the offsetted curves in a hierarchical organized
-     data structure.
-    -used_offset: used offset when the offsetted curves were generated
-    -stitch_distance: maximum allowed distance between two points
-     after sampling
-    -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting
-     offsetted paths might be shorter.
-    -close_point: defines the beginning point for stitching
-     (stitching starts always from the undisplaced curve)
-    -offset_by_half: If true the resulting points are interlaced otherwise not.
-    Return values:
-    -All offsetted curves connected to one spiral and sampled with
-     points obeying stitch_distance and offset_by_half
-    -Tag (origin) of each point to analyze why a point was
-     placed at this position
-    """
-
-    starting_point = close_point.coords[0]
-
-    rings = [tree.nodes[node].val for node in nx.dfs_preorder_nodes(tree, 'root')]
-
-    path = make_spiral(rings, stitch_distance, starting_point)
-    path = [Stitch(*stitch) for stitch in path]
-
-    return running_stitch(path, stitch_distance)
-
-
-def connect_raster_tree_double_spiral(tree, used_offset, stitch_distance, close_point):  # noqa: C901
-    """
-    Takes the offsetted curves organized as tree, connects and samples them as a spiral.
-    It expects that each node in the tree has max. one child
-    Input:
-    -tree: contains the offsetted curves in a hierarchical organized
-     data structure.
-    -used_offset: used offset when the offsetted curves were generated
-    -stitch_distance: maximum allowed distance between two points
-     after sampling
-    -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting
-     offsetted paths might be shorter.
-    -close_point: defines the beginning point for stitching
-     (stitching starts always from the undisplaced curve)
-    -offset_by_half: If true the resulting points are interlaced otherwise not.
-    Return values:
-    -All offsetted curves connected to one spiral and sampled with
-     points obeying stitch_distance and offset_by_half
-    -Tag (origin) of each point to analyze why a point was
-     placed at this position
-    """
-
-    starting_point = close_point.coords[0]
-
-    rings = [tree.nodes[node].val for node in nx.dfs_preorder_nodes(tree, 'root')]
-
-    path = make_fermat_spiral(rings, stitch_distance, starting_point)
-    path = [Stitch(*stitch) for stitch in path]
-
-    return running_stitch(path, stitch_distance)
-
-
-def make_fermat_spiral(rings, stitch_distance, starting_point):
-    forward = make_spiral(rings[::2], stitch_distance, starting_point)
-    back = make_spiral(rings[1::2], stitch_distance, starting_point)
-    back.reverse()
-
-    return chain(forward, back)
-
-
-def make_spiral(rings, stitch_distance, starting_point):
-    path = []
-
-    for ring1, ring2 in zip(rings[:-1], rings[1:]):
-        spiral_part = interpolate_linear_rings(ring1, ring2, stitch_distance, starting_point)
-        path.extend(spiral_part.coords)
-
-    return path
diff --git a/requirements.txt b/requirements.txt
index 585b1dac..e0b07b0b 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -19,7 +19,6 @@ stringcase
 tinycss2
 flask
 fonttools
-depq
 trimesh
 scipy==1.7.3