bug fixing+first spiral implementation

7 files changed, 348 insertions, 39 deletions

diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py
index 094ad91e..dc678087 100644
--- a/lib/elements/auto_fill.py
+++ b/lib/elements/auto_fill.py
@@ -61,7 +61,7 @@ class AutoFill(EmbroideryElement):
 
     @property
     @param('tangential_strategy', _('Tangential strategy'), type='dropdown', default=1,
-           options=[_("Closest point"), _("Inner to Outer")], select_items=[('fill_method', 1)], sort_index=2)
+           options=[_("Closest point"), _("Inner to Outer"), _("single Spiral")], select_items=[('fill_method', 1)], sort_index=2)
     def tangential_strategy(self):
         return self.get_int_param('tangential_strategy', 1)
 
diff --git a/lib/stitches/ConnectAndSamplePattern.py b/lib/stitches/ConnectAndSamplePattern.py
index e8f1def5..2410f3ca 100644
--- a/lib/stitches/ConnectAndSamplePattern.py
+++ b/lib/stitches/ConnectAndSamplePattern.py
@@ -3,7 +3,12 @@ from shapely.geometry import Point, MultiPoint
 from shapely.ops import nearest_points
 from collections import namedtuple
 from depq import DEPQ
+import trimesh
+import numpy as np
+from scipy import spatial
 import math
+from shapely.geometry import asLineString
+from anytree import PreOrderIter
 from ..stitches import LineStringSampling
 from ..stitches import PointTransfer
 from ..stitches import constants
@@ -48,8 +53,7 @@ def cut(line, distance):
 
 
 def connect_raster_tree_nearest_neighbor(
-    tree, used_offset, stitch_distance, close_point, offset_by_half
-):
+        tree, used_offset, stitch_distance, close_point, offset_by_half):
     """
     Takes the offsetted curves organized as tree, connects and samples them.
     Strategy: A connection from parent to child is made where both curves
@@ -338,8 +342,7 @@ def get_nearest_points_closer_than_thresh(travel_line, next_line, thresh):
 
 
 def create_nearest_points_list(
-    travel_line, children_list, threshold, threshold_hard, preferred_direction=0
-):
+        travel_line, children_list, threshold, threshold_hard, preferred_direction=0):
     """
     Takes a line and calculates the nearest distance along this line to
     enter the childs in children_list
@@ -456,8 +459,7 @@ def calculate_replacing_middle_point(line_segment, abs_offset, max_stitch_distan
 
 
 def connect_raster_tree_from_inner_to_outer(
-    tree, used_offset, stitch_distance, close_point, offset_by_half
-):
+        tree, used_offset, stitch_distance, close_point, offset_by_half):
     """
     Takes the offsetted curves organized as tree, connects and samples them.
     Strategy: A connection from parent to child is made as fast as possible to
@@ -772,3 +774,153 @@ def connect_raster_tree_from_inner_to_outer(
 
     assert len(result_coords) == len(result_coords_origin)
     return result_coords, result_coords_origin
+
+
+# Partly taken from https://github.com/mikedh/pocketing/blob/master/pocketing/polygons.py
+def interpolate_LinearRings(a, b, start=None, step=.005):
+    """
+    Interpolate between two LinearRings
+    Parameters
+    -------------
+    a : shapely.geometry.Polygon.LinearRing
+        LinearRing start point will lie on
+    b : shapely.geometry.Polygon.LinearRing
+        LinearRing end point will lie on
+    start : (2,) float, or None
+        Point to start at
+    step : float
+        How far apart should points on
+        the path be.
+    Returns
+    -------------
+    path : (n, 2) float
+       Path interpolated between two LinearRings
+    """
+
+    # resample the first LinearRing so every sample is spaced evenly
+    ra = trimesh.path.traversal.resample_path(
+        a, step=step)
+    if not a.is_ccw:
+        ra = ra[::-1]
+
+    assert trimesh.path.util.is_ccw(ra)
+    if start is not None:
+        # find the closest index on LinerRing 'a'
+        # by creating a KDTree
+        tree_a = spatial.cKDTree(ra)
+        index = tree_a.query(start)[1]
+        ra = np.roll(ra, -index, axis=0)
+
+    # resample the second LinearRing for even spacing
+    rb = trimesh.path.traversal.resample_path(b,
+                                              step=step)
+    if not b.is_ccw:
+        rb = rb[::-1]
+
+    # we want points on 'b' that correspond index- wise
+    # the resampled points on 'a'
+    tree_b = spatial.cKDTree(rb)
+    # points on b with corresponding indexes to ra
+    pb = rb[tree_b.query(ra)[1]]
+
+    # linearly interpolate between 'a' and 'b'
+    weights = np.linspace(0.0, 1.0, len(ra)).reshape((-1, 1))
+
+    # start on 'a' and end on 'b'
+    points = (ra * (1.0 - weights)) + (pb * weights)
+
+    result = LineString(points)
+
+    return result.simplify(constants.simplification_threshold, False)
+
+
+def connect_raster_tree_spiral(
+        tree, used_offset, stitch_distance, close_point, offset_by_half):
+    """
+    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 hierachical organized
+     data structure.
+    -used_offset: used offset when the offsetted curves were generated
+    -stitch_distance: maximum allowed distance between two points
+     after sampling
+    -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 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
+    """
+
+    abs_offset = abs(used_offset)
+    if tree.is_leaf:
+        return LineStringSampling.raster_line_string_with_priority_points(
+            tree.val,
+            0,
+            tree.val.length,
+            stitch_distance,
+            tree.transferred_point_priority_deque,
+            abs_offset,
+            offset_by_half,
+            False)
+
+    result_coords = []
+    result_coords_origin = []
+    starting_point = close_point.coords[0]
+    # iterate to the second last level
+    for node in PreOrderIter(tree, stop=lambda n: n.is_leaf):
+        ring1 = node.val
+        ring2 = node.children[0].val
+
+        part_spiral = interpolate_LinearRings(
+            ring1, ring2, starting_point)
+
+        (own_coords, own_coords_origin) = LineStringSampling.raster_line_string_with_priority_points(
+            part_spiral,
+            0,
+            part_spiral.length,
+            stitch_distance,
+            node.transferred_point_priority_deque,
+            abs_offset,
+            offset_by_half,
+            False)
+
+        PointTransfer.transfer_points_to_surrounding(
+            node,
+            used_offset,
+            offset_by_half,
+            own_coords,
+            own_coords_origin,
+            overnext_neighbor=False,
+            transfer_forbidden_points=False,
+            transfer_to_parent=False,
+            transfer_to_sibling=False,
+            transfer_to_child=True)
+
+        # We transfer also to the overnext child to get a more straight
+        # arrangement of points perpendicular to the stitching lines
+        if offset_by_half:
+            PointTransfer.transfer_points_to_surrounding(
+                node,
+                used_offset,
+                False,
+                own_coords,
+                own_coords_origin,
+                overnext_neighbor=True,
+                transfer_forbidden_points=False,
+                transfer_to_parent=False,
+                transfer_to_sibling=False,
+                transfer_to_child=True)
+
+        result_coords.extend(own_coords)
+        result_coords_origin.extend(own_coords_origin)
+
+        # make sure the next section starts where this
+        # section of the curve ends
+        starting_point = own_coords[-1]
+
+    assert len(result_coords) == len(result_coords_origin)
+    return result_coords, result_coords_origin
diff --git a/lib/stitches/LineStringSampling.py b/lib/stitches/LineStringSampling.py
index bd20f55c..43f650e6 100644
--- a/lib/stitches/LineStringSampling.py
+++ b/lib/stitches/LineStringSampling.py
@@ -139,32 +139,35 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance,
     angles[0] = 1.1*constants.limiting_angle
     angles[-1] = 1.1*constants.limiting_angle
 
-    current_distance = start_distance
-
+    current_distance = 0
+    last_point = Point(path_coords.coords[0])
     # Next we merge the line points and the projected (deque) points into one list
     merged_point_list = []
     dq_iter = 0
-    for point, angle in zip(aligned_line.coords, angles):
-        # if abs(point[0]-52.9) < 0.2 and abs(point[1]-183.4)< 0.2:
+    for point, angle in zip(path_coords.coords, angles):
+        # if abs(point[0]-7) < 0.2 and abs(point[1]-3.3) < 0.2:
         #    print("GEFUNDEN")
-        current_distance = aligned_line.project(Point(point))
-        while dq_iter < len(deque_points) and deque_points[dq_iter][1] < current_distance:
+        current_distance += last_point.distance(Point(point))
+        last_point = Point(point)
+        while dq_iter < len(deque_points) and deque_points[dq_iter][1] < current_distance+start_distance:
             # We want to avoid setting points at soft edges close to forbidden points
             if deque_points[dq_iter][0].point_source == PointSource.FORBIDDEN_POINT:
                 # Check whether a previous added point is a soft edge close to the forbidden point
                 if (merged_point_list[-1][0].point_source == PointSource.SOFT_EDGE_INTERNAL and
-                   abs(merged_point_list[-1][1]-deque_points[dq_iter][1] < abs_offset*constants.factor_offset_forbidden_point)):
+                   abs(merged_point_list[-1][1]-deque_points[dq_iter][1]+start_distance < abs_offset*constants.factor_offset_forbidden_point)):
                     item = merged_point_list.pop()
                     merged_point_list.append((PointTransfer.projected_point_tuple(
-                        point=item[0].point, point_source=PointSource.FORBIDDEN_POINT), item[1]))
+                        point=item[0].point, point_source=PointSource.FORBIDDEN_POINT), item[1]-start_distance))
             else:
-                merged_point_list.append(deque_points[dq_iter])
+                merged_point_list.append(
+                    (deque_points[dq_iter][0], deque_points[dq_iter][1]-start_distance))
+                # merged_point_list.append(deque_points[dq_iter])
             dq_iter += 1
         # Check whether the current point is close to a forbidden point
         if (dq_iter < len(deque_points) and
             deque_points[dq_iter-1][0].point_source == PointSource.FORBIDDEN_POINT and
             angle < constants.limiting_angle and
-                abs(deque_points[dq_iter-1][1]-current_distance) < abs_offset*constants.factor_offset_forbidden_point):
+                abs(deque_points[dq_iter-1][1]-current_distance-start_distance) < abs_offset*constants.factor_offset_forbidden_point):
             point_source = PointSource.FORBIDDEN_POINT
         else:
             if angle < constants.limiting_angle:
diff --git a/lib/stitches/PointTransfer.py b/lib/stitches/PointTransfer.py
index da73aea0..b6e4e026 100644
--- a/lib/stitches/PointTransfer.py
+++ b/lib/stitches/PointTransfer.py
@@ -9,12 +9,13 @@ from ..stitches import LineStringSampling
 projected_point_tuple = namedtuple(
     'projected_point_tuple', ['point', 'point_source'])
 
-# Calculated the nearest interserction point of "bisectorline" with the coordinates of child (child.val).
-# It returns the intersection point and its distance along the coordinates of the child or "None, None" if no
-# intersection was found.
-
 
 def calc_transferred_point(bisectorline, child):
+    """
+    Calculates the nearest interserction point of "bisectorline" with the coordinates of child (child.val).
+    It returns the intersection point and its distance along the coordinates of the child or "None, None" if no
+    intersection was found.
+    """
     result = bisectorline.intersection(child.val)
     if result.is_empty:
         return None, None
@@ -279,11 +280,10 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra
 
     assert(len(point_list) == len(point_source_list))
 
-# Calculated the nearest interserction point of "bisectorline" with the coordinates of child.
+
+# Calculates the nearest interserction point of "bisectorline" with the coordinates of child.
 # It returns the intersection point and its distance along the coordinates of the child or "None, None" if no
 # intersection was found.
-
-
 def calc_transferred_point_graph(bisectorline, edge_geometry):
     result = bisectorline.intersection(edge_geometry)
     if result.is_empty:
diff --git a/lib/stitches/StitchPattern.py b/lib/stitches/StitchPattern.py
index 1edfd452..62ef2b0f 100644
--- a/lib/stitches/StitchPattern.py
+++ b/lib/stitches/StitchPattern.py
@@ -1,8 +1,9 @@
+from anytree.render import RenderTree
 from shapely.geometry.polygon import LinearRing, LineString
 from shapely.geometry import Polygon, MultiLineString
 from shapely.ops import polygonize
 from shapely.geometry import MultiPolygon
-from anytree import AnyNode, PreOrderIter
+from anytree import AnyNode, PreOrderIter, LevelOrderGroupIter
 from shapely.geometry.polygon import orient
 from depq import DEPQ
 from enum import IntEnum
@@ -126,6 +127,38 @@ class StitchingStrategy(IntEnum):
     SPIRAL = 2
 
 
+def check_and_prepare_tree_for_valid_spiral(root):
+    """
+    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.
+    """
+    for children in LevelOrderGroupIter(root):
+        if len(children) > 1:
+            count = 0
+            child_with_children = None
+            for child in children:
+                if not child.is_leaf:
+                    count += 1
+                    child_with_children = child
+            if count > 1:
+                return False
+            elif count == 1:
+                child_with_children.parent.children = [child_with_children]
+            else:  # count == 0 means all childs have no children so we take only the longest child
+                max_length = 0
+                longest_child = None
+                for child in children:
+                    if child.val.length > max_length:
+                        max_length = child.val.length
+                        longest_child = child
+                longest_child.parent.children = [longest_child]
+    return True
+
+
 def offset_poly(
         poly, offset, join_style, stitch_distance, offset_by_half, strategy, starting_point):
     """
@@ -144,13 +177,21 @@ def offset_poly(
     -stitch_distance maximum allowed stitch distance between two points
     -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
+     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
     Output:
     -List of point coordinate tuples
     -Tag (origin) of each point to analyze why a point was placed
      at this position
     """
+
+    if strategy == StitchingStrategy.SPIRAL and len(poly.interiors) > 1:
+        raise ValueError(
+            "Single spiral geometry must not have more than one hole!")
+
     ordered_poly = orient(poly, -1)
     ordered_poly = ordered_poly.simplify(
         constants.simplification_threshold, False)
@@ -276,20 +317,105 @@ def offset_poly(
     make_tree_uniform_ccw(root)
     # print(RenderTree(root))
     if strategy == StitchingStrategy.CLOSEST_POINT:
-        (
-            connected_line,
-            connected_line_origin,
-        ) = ConnectAndSamplePattern.connect_raster_tree_nearest_neighbor(
-            root, offset, stitch_distance, starting_point, offset_by_half
-        )
+        (connected_line, connected_line_origin) = ConnectAndSamplePattern.connect_raster_tree_nearest_neighbor(
+            root, offset, stitch_distance, starting_point, offset_by_half)
     elif strategy == StitchingStrategy.INNER_TO_OUTER:
-        (
-            connected_line,
-            connected_line_origin,
-        ) = ConnectAndSamplePattern.connect_raster_tree_from_inner_to_outer(
-            root, offset, stitch_distance, starting_point, offset_by_half
-        )
+        (connected_line, connected_line_origin) = ConnectAndSamplePattern.connect_raster_tree_from_inner_to_outer(
+            root, offset, stitch_distance, starting_point, offset_by_half)
+    elif strategy == StitchingStrategy.SPIRAL:
+        if not check_and_prepare_tree_for_valid_spiral(root):
+            raise ValueError("Geometry cannot be filled with one spiral!")
+        (connected_line, connected_line_origin) = ConnectAndSamplePattern.connect_raster_tree_spiral(
+            root, offset, stitch_distance, starting_point, offset_by_half)
     else:
         raise ValueError("Invalid stitching stratety!")
 
     return connected_line, connected_line_origin
+
+
+if __name__ == "__main__":
+    line1 = LineString([(0, 0), (1, 0)])
+    line2 = LineString([(0, 0), (3, 0)])
+
+    root = AnyNode(
+        id="root",
+        val=line1)
+    child1 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child2 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child3 = AnyNode(
+        id="node",
+        val=line2,
+        parent=root)
+
+    print(RenderTree(root))
+    print(check_and_prepare_tree_for_valid_spiral(root))
+    print(RenderTree(root))
+    print("---------------------------")
+    root = AnyNode(
+        id="root",
+        val=line1)
+    child1 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child2 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child3 = AnyNode(
+        id="node",
+        val=line2,
+        parent=child1)
+    print(RenderTree(root))
+    print(check_and_prepare_tree_for_valid_spiral(root))
+    print(RenderTree(root))
+
+    print("---------------------------")
+    root = AnyNode(
+        id="root",
+        val=line1)
+    child1 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child2 = AnyNode(
+        id="node",
+        val=line1,
+        parent=child1)
+    child3 = AnyNode(
+        id="node",
+        val=line2,
+        parent=child2)
+    print(RenderTree(root))
+    print(check_and_prepare_tree_for_valid_spiral(root))
+    print(RenderTree(root))
+
+    print("---------------------------")
+    root = AnyNode(
+        id="root",
+        val=line1)
+    child1 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child2 = AnyNode(
+        id="node",
+        val=line1,
+        parent=root)
+    child3 = AnyNode(
+        id="node",
+        val=line2,
+        parent=child1)
+    child4 = AnyNode(
+        id="node",
+        val=line2,
+        parent=child2)
+    print(RenderTree(root))
+    print(check_and_prepare_tree_for_valid_spiral(root))
+    print(RenderTree(root))
diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py
index 01bfdc20..5afcb228 100644
--- a/lib/stitches/fill.py
+++ b/lib/stitches/fill.py
@@ -7,7 +7,7 @@ import math
 
 import shapely
 from shapely.geometry.linestring import LineString
-from shapely.ops import linemerge
+from shapely.ops import linemerge, unary_union
 from ..svg import PIXELS_PER_MM
 from ..utils import Point as InkstitchPoint
 from ..utils import cache
@@ -126,12 +126,34 @@ def repair_multiple_parallel_offset_curves(multi_line):
     return lines[max_length_idx].simplify(0.01, False)
 
 
+def repair_non_simple_lines(line):
+    repaired = unary_union(line)
+    counter = 0
+    # Do several iterations since we might have several concatenated selfcrossings
+    while repaired.geom_type != 'LineString' and counter < 4:
+        line_segments = []
+        for line_seg in repaired.geoms:
+            if not line_seg.is_ring:
+                line_segments.append(line_seg)
+
+        repaired = unary_union(linemerge(line_segments))
+        counter += 1
+    if repaired.geom_type != 'LineString':
+        raise ValueError(
+            "Guide line (or offsetted instance) is self crossing!")
+    else:
+        return repaired
+
+
 def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing=None, flip=False):
 
     row_spacing = abs(row_spacing)
     (minx, miny, maxx, maxy) = shape.bounds
     upper_left = InkstitchPoint(minx, miny)
     rows = []
+
+    if line.geom_type != 'LineString' or not line.is_simple:
+        line = repair_non_simple_lines(line)
     # extend the line towards the ends to increase probability that all offsetted curves cross the shape
     line = extend_line(line, minx, maxx, miny, maxy)
 
@@ -160,6 +182,8 @@ def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing
         if line_offsetted.geom_type == 'MultiLineString':  # if we got multiple lines take the longest
             line_offsetted = repair_multiple_parallel_offset_curves(
                 line_offsetted)
+        if not line_offsetted.is_simple:
+            line_offsetted = repair_non_simple_lines(line_offsetted)
 
         if row_spacing < 0:
             line_offsetted.coords = line_offsetted.coords[::-1]
@@ -173,6 +197,8 @@ def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing
                 if line_offsetted.geom_type == 'MultiLineString':  # if we got multiple lines take the longest
                     line_offsetted = repair_multiple_parallel_offset_curves(
                         line_offsetted)
+                if not line_offsetted.is_simple:
+                    line_offsetted = repair_non_simple_lines(line_offsetted)
                 # using negative row spacing leads as a side effect to reversed offsetted lines - here we undo this
                 line_offsetted.coords = line_offsetted.coords[::-1]
                 line_offsetted = line_offsetted.simplify(0.01, False)
diff --git a/requirements.txt b/requirements.txt
index 309e1be6..09999307 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -21,6 +21,8 @@ flask
 fonttools
 anytree
 depq
+trimesh
+scipy
 
 pywinutils; sys.platform == 'win32'
 pywin32; sys.platform == 'win32'