meander fixes

4 files changed, 43 insertions, 18 deletions

diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py
index 0a59da72..29ec6270 100644
--- a/lib/stitches/meander_fill.py
+++ b/lib/stitches/meander_fill.py
@@ -2,7 +2,7 @@ from itertools import combinations
 
 import networkx as nx
 from inkex import errormsg
-from shapely.geometry import MultiPoint, Point
+from shapely.geometry import LineString, MultiPoint, Point
 from shapely.ops import nearest_points
 
 from .. import tiles
@@ -126,10 +126,16 @@ def generate_meander_path(graph, start, end, rng):
             check_stop_flag()
 
             edge1, edge2 = poprandom(edge_pairs, rng)
-            edges_to_consider.extend(replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes))
-            break
+            new_edges = replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)
+            if new_edges:
+                edges_to_consider.extend(new_edges)
+                break
+
+    debug.log_graph(graph, "remaining graph", "#FF0000")
+    points = path_to_points(meander_path)
+    debug.log_line_string(LineString(points), "meander path", "#00FF00")
 
-    return path_to_points(meander_path)
+    return points
 
 
 def replace_edge(path, edge, graph, graph_nodes):
diff --git a/lib/stitches/running_stitch.py b/lib/stitches/running_stitch.py
index 1dbfcaaf..46f3a3e9 100644
--- a/lib/stitches/running_stitch.py
+++ b/lib/stitches/running_stitch.py
@@ -10,6 +10,8 @@ from copy import copy
 
 import numpy as np
 from shapely import geometry as shgeo
+
+from ..debug import debug
 from ..utils import prng
 from ..utils.geometry import Point
 from ..utils.threading import check_stop_flag
@@ -246,6 +248,7 @@ def path_to_curves(points: typing.List[Point], min_len: float):
     return curves
 
 
+@debug.time
 def running_stitch(points, stitch_length, tolerance):
     # Turn a continuous path into a running stitch.
     stitches = [points[0]]
diff --git a/lib/tiles.py b/lib/tiles.py
index 1b418905..15017e91 100644
--- a/lib/tiles.py
+++ b/lib/tiles.py
@@ -5,7 +5,7 @@ import inkex
 import json
 import lxml
 import networkx as nx
-from shapely.geometry import LineString
+from shapely.geometry import LineString, MultiLineString
 from shapely.prepared import prep
 
 from .debug import debug
@@ -59,8 +59,9 @@ class Tile:
 
     def _load_paths(self, tile_svg):
         path_elements = tile_svg.findall('.//svg:path', namespaces=inkex.NSS)
-        self.tile = self._path_elements_to_line_strings(path_elements)
-        # self.center, ignore, ignore = self._get_center_and_dimensions(self.tile)
+        tile = self._path_elements_to_line_strings(path_elements)
+        center, ignore, ignore = self._get_center_and_dimensions(MultiLineString(tile))
+        self.tile = [(start - center, end - center) for start, end in tile]
 
     def _load_dimensions(self, tile_svg):
         svg_element = tile_svg.getroot()
@@ -136,22 +137,34 @@ class Tile:
         shift0, shift1, tile = self._scale(x_scale, y_scale)
 
         shape_center, shape_width, shape_height = self._get_center_and_dimensions(shape)
-        shape_diagonal = Point(shape_width, shape_height).length()
         prepared_shape = prep(shape)
 
-        return self._generate_graph(prepared_shape, shape_center, shape_diagonal, shift0, shift1, tile)
+        return self._generate_graph(prepared_shape, shape_center, shape_width, shape_height, shift0, shift1, tile)
 
-    def _generate_graph(self, shape, shape_center, shape_diagonal, shift0, shift1, tile):
+    @debug.time
+    def _generate_graph(self, shape, shape_center, shape_width, shape_height, shift0, shift1, tile):
         graph = nx.Graph()
-        tiles0 = ceil(shape_diagonal / shift0.length()) + 2
-        tiles1 = ceil(shape_diagonal / shift1.length()) + 2
-        for repeat0 in range(floor(-tiles0 / 2), ceil(tiles0 / 2)):
-            for repeat1 in range(floor(-tiles1 / 2), ceil(tiles1 / 2)):
+
+        shape_diagonal = Point(shape_width, shape_height).length()
+        num_tiles = ceil(shape_diagonal / min(shift0.length(), shift1.length()))
+        debug.log(f"num_tiles: {num_tiles}")
+
+        tile_diagonal = (shift0 + shift1).length()
+        x_cutoff = shape_width / 2 + tile_diagonal
+        y_cutoff = shape_height / 2 + tile_diagonal
+
+        for repeat0 in range(-num_tiles, num_tiles):
+            for repeat1 in range(-num_tiles, num_tiles):
                 check_stop_flag()
 
                 offset0 = repeat0 * shift0
                 offset1 = repeat1 * shift1
-                this_tile = self._translate_tile(tile, offset0 + offset1 + shape_center)
+                offset = offset0 + offset1
+
+                if abs(offset.x) > x_cutoff or abs(offset.y) > y_cutoff:
+                    continue
+
+                this_tile = self._translate_tile(tile, offset + shape_center)
                 for line in this_tile:
                     line_string = LineString(line)
                     if shape.contains(line_string):
@@ -161,6 +174,7 @@ class Tile:
 
         return graph
 
+    @debug.time
     def _remove_dead_ends(self, graph):
         graph.remove_edges_from(nx.selfloop_edges(graph))
         while True:
diff --git a/lib/utils/smoothing.py b/lib/utils/smoothing.py
index 9d43a9f1..1bb250c5 100644
--- a/lib/utils/smoothing.py
+++ b/lib/utils/smoothing.py
@@ -70,7 +70,8 @@ def smooth_path(path, smoothness=1.0):
 
     # .T transposes the array (for some reason splprep expects
     # [[x1, x2, ...], [y1, y2, ...]]
-    tck, fp, ier, msg = splprep(coords.T, s=s, k=3, nest=-1, full_output=1)
+    with debug.time_this("splprep"):
+        tck, fp, ier, msg = splprep(coords.T, s=s, k=3, nest=-1, full_output=1)
     if ier > 0:
         debug.log(f"error {ier} smoothing path: {msg}")
         return path
@@ -78,7 +79,8 @@ def smooth_path(path, smoothness=1.0):
     # Evaluate the spline curve at many points along its length to produce the
     # smoothed point list.  2 * num_points seems to be a good number, but it
     # does produce a lot of points.
-    smoothed_x_values, smoothed_y_values = splev(np.linspace(0, 1, int(num_points * 2)), tck[0])
-    coords = np.array([smoothed_x_values, smoothed_y_values]).T
+    with debug.time_this("splev"):
+        smoothed_x_values, smoothed_y_values = splev(np.linspace(0, 1, int(num_points * 2)), tck[0])
+        coords = np.array([smoothed_x_values, smoothed_y_values]).T
 
     return [Point(x, y) for x, y in coords]