diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/stitches/meander_fill.py | 32 | ||||
| -rw-r--r-- | lib/tiles.py | 11 |
2 files changed, 32 insertions, 11 deletions
diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 2cd235fb..6278b0ad 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -1,3 +1,5 @@ +from itertools import combinations + import networkx as nx from shapely.geometry import MultiPoint, Point from shapely.ops import nearest_points @@ -5,11 +7,11 @@ from shapely.ops import nearest_points from .running_stitch import running_stitch from .. import tiles from ..debug import debug -from ..stitch_plan import Stitch -from ..utils.smoothing import smooth_path +from ..utils.clamp_path import clamp_path_to_polygon from ..utils.geometry import Point as InkStitchPoint, ensure_geometry_collection from ..utils.list import poprandom from ..utils.prng import iter_uniform_floats +from ..utils.smoothing import smooth_path from ..utils.threading import check_stop_flag @@ -24,11 +26,11 @@ def meander_fill(fill, shape, shape_index, starting_point, ending_point): debug.log_line_strings(lambda: ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') graph = tile.to_graph(shape, fill.meander_scale) debug.log_graph(graph, 'Meander graph') - debug.log(lambda: f"graph connected? {nx.is_connected(graph)}") + ensure_connected(graph) start, end = find_starting_and_ending_nodes(graph, shape, starting_point, ending_point) rng = iter_uniform_floats(fill.random_seed, 'meander-fill', shape_index) - return post_process(generate_meander_path(graph, start, end, rng), fill) + return post_process(generate_meander_path(graph, start, end, rng), shape, fill) def get_tile(tile_name): @@ -40,6 +42,24 @@ def get_tile(tile_name): return None +def ensure_connected(graph): + """If graph is unconnected, add edges to make it connected.""" + + # TODO: combine this with possible_jumps() in lib/stitches/utils/autoroute.py + possible_connections = [] + for component1, component2 in combinations(nx.connected_components(graph), 2): + points1 = MultiPoint([Point(node) for node in component1]) + points2 = MultiPoint([Point(node) for node in component2]) + + start_point, end_point = nearest_points(points1, points2) + possible_connections.append(((start_point.x, start_point.y), (end_point.x, end_point.y), start_point.distance(end_point))) + + if possible_connections: + for start, end in nx.k_edge_augmentation(graph, 1, avail=possible_connections): + check_stop_flag() + graph.add_edge(start, end) + + def find_starting_and_ending_nodes(graph, shape, starting_point, ending_point): if starting_point is None: starting_point = shape.exterior.coords[0] @@ -137,14 +157,14 @@ def replace_edge_pair(path, edge1, edge2, graph, graph_nodes): @debug.time -def post_process(points, fill): +def post_process(points, shape, fill): debug.log(f"smoothness: {fill.smoothness}") # debug.log_line_string(LineString(points), "pre-smoothed", "#FF0000") smoothed_points = smooth_path(points, fill.smoothness) smoothed_points = [InkStitchPoint.from_tuple(point) for point in smoothed_points] stitches = running_stitch(smoothed_points, fill.running_stitch_length, fill.running_stitch_tolerance) - stitches = [Stitch(point) for point in stitches] + stitches = clamp_path_to_polygon(stitches, shape) return stitches diff --git a/lib/tiles.py b/lib/tiles.py index e40692e8..d1e79071 100644 --- a/lib/tiles.py +++ b/lib/tiles.py @@ -3,7 +3,7 @@ from math import ceil, floor import inkex import lxml -from networkx import Graph +import networkx as nx from shapely.geometry import LineString from shapely.prepared import prep @@ -127,7 +127,7 @@ class Tile: return self._generate_graph(prepared_shape, shape_center, shape_diagonal) def _generate_graph(self, shape, shape_center, shape_diagonal): - graph = Graph() + graph = nx.Graph() tiles0 = ceil(shape_diagonal / self.shift0.length()) + 2 tiles1 = ceil(shape_diagonal / self.shift1.length()) + 2 for repeat0 in range(floor(-tiles0 / 2), ceil(tiles0 / 2)): @@ -147,11 +147,12 @@ class Tile: return graph def _remove_dead_ends(self, graph): + graph.remove_edges_from(nx.selfloop_edges(graph)) while True: - nodes_with_degree_1 = [node for node, degree in graph.degree() if degree == 1] + dead_end_nodes = [node for node, degree in graph.degree() if degree <= 1] - if nodes_with_degree_1: - graph.remove_nodes_from(nodes_with_degree_1) + if dead_end_nodes: + graph.remove_nodes_from(dead_end_nodes) else: return |